]>
Commit | Line | Data |
---|---|---|
58ef912c MM |
1 | /* |
2 | * BIRD Library -- Linked Lists | |
3 | * | |
4 | * (c) 1998 Martin Mares <mj@ucw.cz> | |
5 | * | |
6 | * Can be freely distributed and used under the terms of the GNU GPL. | |
7 | */ | |
8 | ||
7722938d MM |
9 | /** |
10 | * DOC: Linked lists | |
11 | * | |
12 | * The BIRD library provides a set of functions for operating on linked | |
13 | * lists. The lists are internally represented as standard doubly linked | |
14 | * lists with synthetic head and tail which makes all the basic operations | |
15 | * run in constant time and contain no extra end-of-list checks. Each list | |
16 | * is described by a &list structure, nodes can have any format as long | |
17 | * as they start with a &node structure. If you want your nodes to belong | |
18 | * to multiple lists at once, you can embed multiple &node structures in them | |
19 | * and use the SKIP_BACK() macro to calculate a pointer to the start of the | |
20 | * structure from a &node pointer, but beware of obscurity. | |
21 | * | |
22 | * There also exist safe linked lists (&slist, &snode and all functions | |
23 | * being prefixed with |s_|) which support asynchronous walking very | |
24 | * similar to that used in the &fib structure. | |
25 | */ | |
26 | ||
58ef912c MM |
27 | #define _BIRD_LISTS_C_ |
28 | ||
1feea03e MM |
29 | #include "nest/bird.h" |
30 | #include "lib/lists.h" | |
58ef912c | 31 | |
7722938d MM |
32 | /** |
33 | * add_tail - append a node to a list | |
34 | * @l: linked list | |
35 | * @n: list node | |
36 | * | |
37 | * add_tail() takes a node @n and appends it at the end of the list @l. | |
38 | */ | |
58ef912c MM |
39 | LIST_INLINE void |
40 | add_tail(list *l, node *n) | |
41 | { | |
42 | node *z = l->tail; | |
43 | ||
18c8241a | 44 | n->next = (node *) &l->null; |
58ef912c MM |
45 | n->prev = z; |
46 | z->next = n; | |
47 | l->tail = n; | |
48 | } | |
49 | ||
7722938d MM |
50 | /** |
51 | * add_head - prepend a node to a list | |
52 | * @l: linked list | |
53 | * @n: list node | |
54 | * | |
55 | * add_head() takes a node @n and prepends it at the start of the list @l. | |
56 | */ | |
58ef912c MM |
57 | LIST_INLINE void |
58 | add_head(list *l, node *n) | |
59 | { | |
60 | node *z = l->head; | |
61 | ||
62 | n->next = z; | |
63 | n->prev = (node *) &l->head; | |
64 | z->prev = n; | |
65 | l->head = n; | |
66 | } | |
67 | ||
7722938d MM |
68 | /** |
69 | * insert_node - insert a node to a list | |
70 | * @n: a new list node | |
71 | * @after: a node of a list | |
72 | * | |
73 | * Inserts a node @n to a linked list after an already inserted | |
74 | * node @after. | |
75 | */ | |
58ef912c MM |
76 | LIST_INLINE void |
77 | insert_node(node *n, node *after) | |
78 | { | |
79 | node *z = after->next; | |
80 | ||
81 | n->next = z; | |
82 | n->prev = after; | |
83 | after->next = n; | |
84 | z->prev = n; | |
85 | } | |
86 | ||
7722938d MM |
87 | /** |
88 | * rem_node - remove a node from a list | |
89 | * @n: node to be removed | |
90 | * | |
91 | * Removes a node @n from the list it's linked in. | |
92 | */ | |
58ef912c MM |
93 | LIST_INLINE void |
94 | rem_node(node *n) | |
95 | { | |
96 | node *z = n->prev; | |
97 | node *x = n->next; | |
98 | ||
99 | z->next = x; | |
100 | x->prev = z; | |
101 | } | |
102 | ||
7722938d MM |
103 | /** |
104 | * init_list - create an empty list | |
105 | * @l: list | |
106 | * | |
107 | * init_list() takes a &list structure and initializes its | |
108 | * fields, so that it represents an empty list. | |
109 | */ | |
58ef912c MM |
110 | LIST_INLINE void |
111 | init_list(list *l) | |
112 | { | |
113 | l->head = (node *) &l->null; | |
114 | l->null = NULL; | |
115 | l->tail = (node *) &l->head; | |
116 | } | |
117 | ||
7722938d MM |
118 | /** |
119 | * add_tail_list - concatenate two lists | |
120 | * @to: destination list | |
121 | * @l: source list | |
122 | * | |
123 | * This function appends all elements of the list @l to | |
124 | * the list @to in constant time. | |
125 | */ | |
58ef912c MM |
126 | LIST_INLINE void |
127 | add_tail_list(list *to, list *l) | |
128 | { | |
129 | node *p = to->tail; | |
130 | node *q = l->head; | |
131 | ||
132 | p->next = q; | |
133 | q->prev = p; | |
134 | q = l->tail; | |
135 | q->next = (node *) &to->null; | |
136 | to->tail = q; | |
137 | } |