1 /* PSPP - a program for statistical analysis.
2 Copyright (C) 2006 Free Software Foundation, Inc.
4 This program is free software: you can redistribute it and/or modify
5 it under the terms of the GNU General Public License as published by
6 the Free Software Foundation, either version 3 of the License, or
7 (at your option) any later version.
9 This program is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 GNU General Public License for more details.
14 You should have received a copy of the GNU General Public License
15 along with this program. If not, see <http://www.gnu.org/licenses/>. */
17 /* Circular doubly linked lists.
19 This header (ll.h) supplies "embedded" circular doubly linked
20 lists. Its companion header (llx.h) supplies "external"
21 circular doubly linked lists. The two variants are described
22 briefly here. The embedded variant, for which this is the
23 header, is described in slightly more detail below. Each
24 function also has a detailed usage comment at its point of
27 The "ll" embedded linked list implementation puts the linked
28 list node within the data structure that the list contains.
29 This makes allocation efficient, in space and time. It also
30 makes it easy to find the list node associated with a given
31 object. However, it's difficult to include a given object in
32 an arbitrary number of lists, or to include a single object in
33 a single list in multiple positions.
35 The "llx" external linked list implementation allocates linked
36 list nodes separately from the objects in the list. Adding
37 and removing linked list nodes requires dynamic allocation, so
38 it is normally slower and takes more memory than the embedded
39 implementation. It also requires searching the list to find
40 the list node associated with a given object. However, it's
41 easy to include a given object in an arbitrary number of
42 lists, or to include a single object more than once within a
43 single list. It's also possible to create an external linked
44 list without adding a member to the data structure that the
54 /* Embedded, circular doubly linked list.
56 Each list contains a single "null" element that separates the
57 head and the tail of the list. The null element is both
58 before the head and after the tail of the list. An empty list
59 contains just the null element.
61 An embedded linked list is represented as `struct ll_list'.
62 Each node in the list, presumably a structure type, must
63 include a `struct ll' member.
65 Many list functions take ranges of nodes as arguments. Ranges
66 are "half-open"; that is, R0...R1 includes R0 but not R1. A
67 range whose endpoints are the same (e.g. R0...R0) contains no
70 Here's an example of a structure type that includes a `struct
77 struct ll ll; // List member.
78 int x; // Another member.
81 Here's an example of iteration from head to tail:
84 for (ll = ll_head (&list); ll != ll_null (&list); ll = ll_next (ll))
86 struct foo *foo = ll_data (ll, struct foo, ll);
87 ...do something with foo->x...
90 Here's another way to do it:
92 struct ll *ll = ll_null (&list);
93 while ((ll = ll_next (ll)) != ll_null (&list))
95 struct foo *foo = ll_data (ll, struct foo, ll);
96 ...do something with foo->x...
102 ll_for_each (foo, struct foo, ll, &list)
104 ...do something with foo->x...
108 /* Returns the data structure corresponding to the given node LL,
109 assuming that LL is embedded as the given MEMBER name in data
111 #define ll_data(LL, STRUCT, MEMBER) \
112 ((STRUCT *) ((char *) (LL) - offsetof (STRUCT, MEMBER)))
114 /* Linked list node. */
117 struct ll *next; /* Next node. */
118 struct ll *prev; /* Previous node. */
124 struct ll null; /* Null node. */
127 /* Returns negative if A < B, zero if A == B, positive if A > B. */
128 typedef int ll_compare_func (const struct ll *a,
129 const struct ll *b, void *aux);
131 /* Returns true or false depending on properties of LL. */
132 typedef bool ll_predicate_func (const struct ll *ll, void *aux);
134 /* Takes some action on LL. */
135 typedef void ll_action_func (struct ll *ll, void *aux);
137 /* Suitable for use as the initializer for a `struct ll_list'
138 named LIST. Typical usage:
139 struct ll_list list = LL_INITIALIZER (list);
140 LL_INITIALIZER() is an alternative to ll_init(). */
141 #define LL_INITIALIZER(LIST) { { &(LIST).null, &(LIST).null } }
144 static inline void ll_init (struct ll_list *);
145 static inline bool ll_is_empty (const struct ll_list *);
146 size_t ll_count (const struct ll_list *);
149 static inline struct ll *ll_head (const struct ll_list *);
150 static inline struct ll *ll_tail (const struct ll_list *);
151 static inline struct ll *ll_null (const struct ll_list *);
152 static inline struct ll *ll_next (const struct ll *);
153 static inline struct ll *ll_prev (const struct ll *);
155 /* Stack- and queue-like behavior. */
156 static inline void ll_push_head (struct ll_list *, struct ll *);
157 static inline void ll_push_tail (struct ll_list *, struct ll *);
158 static inline struct ll *ll_pop_head (struct ll_list *);
159 static inline struct ll *ll_pop_tail (struct ll_list *);
162 static inline void ll_insert (struct ll *before, struct ll *new);
163 void ll_splice (struct ll *before, struct ll *r0, struct ll *r1);
164 void ll_swap (struct ll *a, struct ll *b);
165 void ll_swap_range (struct ll *a0, struct ll *a1,
166 struct ll *b0, struct ll *b1);
169 static inline struct ll *ll_remove (struct ll *);
170 static inline void ll_remove_range (struct ll *r0, struct ll *r1);
171 size_t ll_remove_equal (struct ll *r0, struct ll *r1, struct ll *target,
172 ll_compare_func *, void *aux);
173 size_t ll_remove_if (struct ll *r0, struct ll *r1,
174 ll_predicate_func *, void *aux);
175 static inline void ll_moved (struct ll *);
177 /* Non-mutating algorithms. */
178 struct ll *ll_find_equal (const struct ll *r0, const struct ll *r1,
179 const struct ll *target,
180 ll_compare_func *, void *aux);
181 struct ll *ll_find_if (const struct ll *r0, const struct ll *r1,
182 ll_predicate_func *, void *aux);
183 struct ll *ll_find_adjacent_equal (const struct ll *r0, const struct ll *r1,
184 ll_compare_func *, void *aux);
185 size_t ll_count_range (const struct ll *r0, const struct ll *r1);
186 size_t ll_count_equal (const struct ll *r0, const struct ll *r1,
187 const struct ll *target,
188 ll_compare_func *, void *aux);
189 size_t ll_count_if (const struct ll *r0, const struct ll *r1,
190 ll_predicate_func *, void *aux);
191 struct ll *ll_max (const struct ll *r0, const struct ll *r1,
192 ll_compare_func *, void *aux);
193 struct ll *ll_min (const struct ll *r0, const struct ll *r1,
194 ll_compare_func *, void *aux);
195 int ll_lexicographical_compare_3way (const struct ll *a0, const struct ll *a1,
196 const struct ll *b0, const struct ll *b1,
197 ll_compare_func *, void *aux);
199 /* Mutating algorithms. */
200 void ll_apply (struct ll *r0, struct ll *r1, ll_action_func *, void *aux);
201 void ll_reverse (struct ll *r0, struct ll *r1);
202 bool ll_next_permutation (struct ll *r0, struct ll *r1,
203 ll_compare_func *, void *aux);
204 bool ll_prev_permutation (struct ll *r0, struct ll *r1,
205 ll_compare_func *, void *aux);
207 /* Sorted list functions. */
208 void ll_sort (struct ll *r0, struct ll *r1, ll_compare_func *, void *aux);
209 struct ll *ll_find_run (const struct ll *r0, const struct ll *r1,
210 ll_compare_func *, void *aux);
211 struct ll *ll_merge (struct ll *a0, struct ll *a1,
212 struct ll *b0, struct ll *b1,
213 ll_compare_func *, void *aux);
214 bool ll_is_sorted (const struct ll *r0, const struct ll *r1,
215 ll_compare_func *, void *aux);
216 size_t ll_unique (struct ll *r0, struct ll *r1, struct ll *dups,
217 ll_compare_func *, void *aux);
218 void ll_sort_unique (struct ll *r0, struct ll *r1, struct ll *dups,
219 ll_compare_func *, void *aux);
220 void ll_insert_ordered (struct ll *r0, struct ll *r1, struct ll *new_elem,
221 ll_compare_func *, void *aux);
222 struct ll *ll_partition (struct ll *r0, struct ll *r1,
223 ll_predicate_func *, void *aux);
224 struct ll *ll_find_partition (const struct ll *r0, const struct ll *r1,
225 ll_predicate_func *, void *aux);
227 /* Iteration helper macros. */
229 /* Sets DATA to each object in LIST in turn, in forward or
230 reverse order, assuming that each
231 `struct ll' in LIST is embedded as the given MEMBER name in
234 Behavior is undefined if DATA is removed from the list between
236 #define ll_for_each(DATA, STRUCT, MEMBER, LIST) \
237 for (DATA = ll_head__ (STRUCT, MEMBER, LIST); \
239 DATA = ll_next__ (DATA, STRUCT, MEMBER, LIST))
240 #define ll_for_each_reverse(DATA, STRUCT, MEMBER, LIST) \
241 for (DATA = ll_tail__ (STRUCT, MEMBER, LIST); \
243 DATA = ll_prev__ (DATA, STRUCT, MEMBER, LIST))
245 /* Continues a iteration of LIST, starting from the object
246 currently in DATA and continuing, in forward or reverse order,
247 through the remainder of the list, assuming that each `struct
248 ll' in LIST is embedded as the given MEMBER name in data type
251 Behavior is undefined if DATA is removed from the list between
253 #define ll_for_each_continue(DATA, STRUCT, MEMBER, LIST) \
256 DATA = ll_next__ (DATA, STRUCT, MEMBER, LIST))
257 #define ll_for_each_reverse_continue(DATA, STRUCT, MEMBER, LIST) \
260 DATA = ll_prev__ (DATA, STRUCT, MEMBER, LIST))
262 /* Sets DATA to each object in LIST in turn, in forward or
263 reverse order, assuming that each `struct ll' in LIST is
264 embedded as the given MEMBER name in data type STRUCT. NEXT
265 (or PREV) must be another variable of the same type as DATA.
267 Behavior is well-defined even if DATA is removed from the list
268 between iterations. */
269 #define ll_for_each_safe(DATA, NEXT, STRUCT, MEMBER, LIST) \
270 for (DATA = ll_head__ (STRUCT, MEMBER, LIST); \
272 ? (NEXT = ll_next__ (DATA, STRUCT, MEMBER, LIST), 1) \
275 #define ll_for_each_reverse_safe(DATA, PREV, STRUCT, MEMBER, LIST) \
276 for (DATA = ll_tail__ (STRUCT, MEMBER, LIST); \
278 ? (PREV = ll_prev__ (DATA, STRUCT, MEMBER, LIST), 1) \
282 /* Continues a iteration of LIST, in forward or reverse order,
283 starting from the object currently in DATA and continuing
284 forward through the remainder of the list, assuming that each
285 `struct ll' in LIST is embedded as the given MEMBER name in
286 data type STRUCT. NEXT (or PREV) must be another variable of
287 the same type as DATA.
289 Behavior is well-defined even if DATA is removed from the list
290 between iterations. */
291 #define ll_for_each_safe_continue(DATA, NEXT, STRUCT, MEMBER, LIST) \
294 ? (NEXT = ll_next__ (DATA, STRUCT, MEMBER, LIST), 1) \
297 #define ll_for_each_safe_reverse_continue(DATA, PREV, STRUCT, MEMBER, LIST) \
300 ? (PREV = ll_prev__ (DATA, STRUCT, MEMBER, LIST), 1) \
304 /* Sets DATA to each object in LIST in turn, in forward or
305 reverse order, assuming that each `struct ll' in LIST is
306 embedded as the given MEMBER name in data type STRUCT.
307 Each object is removed from LIST before its loop iteration. */
308 #define ll_for_each_preremove(DATA, STRUCT, MEMBER, LIST) \
309 while (!ll_is_empty (LIST) \
310 ? (DATA = ll_data (ll_pop_head (LIST), STRUCT, MEMBER), 1) \
312 #define ll_for_each_reverse_preremove(DATA, STRUCT, MEMBER, LIST) \
313 while (!ll_is_empty (LIST) \
314 ? (DATA = ll_data (ll_pop_tail (LIST), STRUCT, MEMBER), 1) \
317 /* Sets DATA to each object in LIST in turn, in forward or
318 reverse order, assuming that each `struct ll' in LIST is
319 embedded as the given MEMBER name in data type STRUCT.
320 At the end of each loop iteration, DATA is removed from the
322 #define ll_for_each_postremove(DATA, STRUCT, MEMBER, LIST) \
324 (DATA = ll_head__ (STRUCT, MEMBER, LIST)) != NULL; \
325 ll_remove (&DATA->MEMBER))
326 #define ll_for_each_reverse_postremove(DATA, STRUCT, MEMBER, LIST) \
328 (DATA = ll_tail__ (STRUCT, MEMBER, LIST)) != NULL; \
329 ll_remove (&DATA->MEMBER))
331 /* Macros for internal use only. */
332 #define ll_data__(LL, STRUCT, MEMBER, LIST) \
333 ((LL) != ll_null (LIST) ? ll_data (LL, STRUCT, MEMBER) : NULL)
334 #define ll_head__(STRUCT, MEMBER, LIST) \
335 ll_data__ (ll_head (LIST), STRUCT, MEMBER, LIST)
336 #define ll_tail__(STRUCT, MEMBER, LIST) \
337 ll_data__ (ll_tail (LIST), STRUCT, MEMBER, LIST)
338 #define ll_next__(DATA, STRUCT, MEMBER, LIST) \
339 ll_data__ (ll_next (&(DATA)->MEMBER), STRUCT, MEMBER, LIST)
340 #define ll_prev__(DATA, STRUCT, MEMBER, LIST) \
341 ll_data__ (ll_prev (&(DATA)->MEMBER), STRUCT, MEMBER, LIST)
343 /* Inline functions. */
345 /* Initializes LIST as an empty list. */
347 ll_init (struct ll_list *list)
349 list->null.next = list->null.prev = &list->null;
352 /* Returns true if LIST is empty (contains just the null node),
353 false if LIST is not empty (has at least one other node).
354 Executes in O(1) time. */
356 ll_is_empty (const struct ll_list *list)
358 return ll_head (list) == ll_null (list);
361 /* Returns the first node in LIST,
362 or the null node if LIST is empty. */
363 static inline struct ll *
364 ll_head (const struct ll_list *list)
366 return ll_next (ll_null (list));
369 /* Returns the last node in LIST,
370 or the null node if LIST is empty. */
371 static inline struct ll *
372 ll_tail (const struct ll_list *list)
374 return ll_prev (ll_null (list));
377 /* Returns LIST's null node. */
378 static inline struct ll *
379 ll_null (const struct ll_list *list)
381 return (struct ll *) &list->null;
384 /* Returns the node following LL in its list,
385 or the null node if LL is at the end of its list.
386 (In an empty list, the null node follows itself.) */
387 static inline struct ll *
388 ll_next (const struct ll *ll)
393 /* Returns the node preceding LL in its list,
394 or the null node if LL is the first node in its list.
395 (In an empty list, the null node precedes itself.) */
396 static inline struct ll *
397 ll_prev (const struct ll *ll)
402 /* Inserts LL at the head of LIST. */
404 ll_push_head (struct ll_list *list, struct ll *ll)
406 ll_insert (ll_head (list), ll);
409 /* Inserts LL at the tail of LIST. */
411 ll_push_tail (struct ll_list *list, struct ll *ll)
413 ll_insert (ll_null (list), ll);
416 /* Removes and returns the first node in LIST,
417 which must not be empty. */
418 static inline struct ll *
419 ll_pop_head (struct ll_list *list)
422 assert (!ll_is_empty (list));
423 head = ll_head (list);
428 /* Removes and returns the last node in LIST,
429 which must not be empty. */
430 static inline struct ll *
431 ll_pop_tail (struct ll_list *list)
434 assert (!ll_is_empty (list));
435 tail = ll_tail (list);
440 /* Inserts NEW_ELEM just before BEFORE.
441 (NEW_ELEM must not already be in a list.) */
443 ll_insert (struct ll *before, struct ll *new_elem)
445 struct ll *before_prev = ll_prev (before);
446 new_elem->next = before;
447 new_elem->prev = before_prev;
448 before_prev->next = before->prev = new_elem;
451 /* Removes LL from its list
452 and returns the node that formerly followed it. */
453 static inline struct ll *
454 ll_remove (struct ll *ll)
456 struct ll *next = ll_next (ll);
457 ll->prev->next = next;
458 ll->next->prev = ll->prev;
462 /* Removes R0...R1 from their list. */
464 ll_remove_range (struct ll *r0, struct ll *r1)
469 r0->prev->next = r1->next;
470 r1->next->prev = r0->prev;
474 /* Adjusts the nodes around LL to compensate for LL having
475 changed address, e.g. due to LL being inside a block of memory
476 that was realloc()'d. Equivalent to calling ll_remove()
477 before moving LL, then ll_insert() afterward, but more
480 ll_moved (struct ll *ll)
482 ll->prev->next = ll->next->prev = ll;