1 /* PSPP - computes sample statistics.
2 Copyright (C) 2006 Free Software Foundation, Inc.
4 This program is free software; you can redistribute it and/or
5 modify it under the terms of the GNU General Public License as
6 published by the Free Software Foundation; either version 2 of the
7 License, or (at your option) any later version.
9 This program is distributed in the hope that it will be useful, but
10 WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 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, write to the Free Software
16 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
19 /* Circular doubly linked lists.
21 This header (ll.h) supplies "embedded" circular doubly linked
22 lists. Its companion header (llx.h) supplies "external"
23 circular doubly linked lists. The two variants are described
24 briefly here. The embedded variant, for which this is the
25 header, is described in slightly more detail below. Each
26 function also has a detailed usage comment at its point of
29 The "ll" embedded linked list implementation puts the linked
30 list node within the data structure that the list contains.
31 This makes allocation efficient, in space and time. It also
32 makes it easy to find the list node associated with a given
33 object. However, it's difficult to include a given object in
34 an arbitrary number of lists, or to include a single object in
35 a single list in multiple positions.
37 The "llx" external linked list implementation allocates linked
38 list nodes separately from the objects in the list. Adding
39 and removing linked list nodes requires dynamic allocation, so
40 it is normally slower and takes more memory than the embedded
41 implementation. It also requires searching the list to find
42 the list node associated with a given object. However, it's
43 easy to include a given object in an arbitrary number of
44 lists, or to include a single object more than once within a
45 single list. It's also possible to create an external linked
46 list without adding a member to the data structure that the
56 /* Embedded, circular doubly linked list.
58 Each list contains a single "null" element that separates the
59 head and the tail of the list. The null element is both
60 before the head and after the tail of the list. An empty list
61 contains just the null element.
63 An embedded linked list is represented as `struct ll_list'.
64 Each node in the list, presumably a structure type, must
65 include a `struct ll' member.
67 Many list functions take ranges of nodes as arguments. Ranges
68 are "half-open"; that is, R0...R1 includes R0 but not R1. A
69 range whose endpoints are the same (e.g. R0...R0) contains no
72 Here's an example of a structure type that includes a `struct
79 struct ll ll; // List member.
80 int x; // Another member.
83 Here's an example of iteration from head to tail:
86 for (ll = ll_head (&list); ll != ll_null (&list); ll = ll_next (ll))
88 struct foo *foo = ll_data (ll, struct foo, ll);
89 ...do something with foo->x...
92 Here's another way to do it:
94 struct ll *ll = ll_null (&list);
95 while ((ll = ll_next (ll)) != ll_null (&list))
97 struct foo *foo = ll_data (ll, struct foo, ll);
98 ...do something with foo->x...
104 ll_for_each (foo, struct foo, ll, &list)
106 ...do something with foo->x...
110 /* Returns the data structure corresponding to the given node LL,
111 assuming that LL is embedded as the given MEMBER name in data
113 #define ll_data(LL, STRUCT, MEMBER) \
114 ((STRUCT *) ((char *) (LL) - offsetof (STRUCT, MEMBER)))
116 /* Linked list node. */
119 struct ll *next; /* Next node. */
120 struct ll *prev; /* Previous node. */
126 struct ll null; /* Null node. */
129 /* Returns negative if A < B, zero if A == B, positive if A > B. */
130 typedef int ll_compare_func (const struct ll *a,
131 const struct ll *b, void *aux);
133 /* Returns true or false depending on properties of LL. */
134 typedef bool ll_predicate_func (const struct ll *ll, void *aux);
136 /* Takes some action on LL. */
137 typedef void ll_action_func (struct ll *ll, void *aux);
139 /* Suitable for use as the initializer for a `struct ll_list'
140 named LIST. Typical usage:
141 struct ll_list list = LL_INITIALIZER (list);
142 LL_INITIALIZER() is an alternative to ll_init(). */
143 #define LL_INITIALIZER(LIST) { { &(LIST).null, &(LIST).null } }
146 static inline void ll_init (struct ll_list *);
147 static inline bool ll_is_empty (const struct ll_list *);
148 size_t ll_count (const struct ll_list *);
151 static inline struct ll *ll_head (const struct ll_list *);
152 static inline struct ll *ll_tail (const struct ll_list *);
153 static inline struct ll *ll_null (const struct ll_list *);
154 static inline struct ll *ll_next (const struct ll *);
155 static inline struct ll *ll_prev (const struct ll *);
157 /* Stack- and queue-like behavior. */
158 static inline void ll_push_head (struct ll_list *, struct ll *);
159 static inline void ll_push_tail (struct ll_list *, struct ll *);
160 static inline struct ll *ll_pop_head (struct ll_list *);
161 static inline struct ll *ll_pop_tail (struct ll_list *);
164 static inline void ll_insert (struct ll *before, struct ll *new);
165 void ll_splice (struct ll *before, struct ll *r0, struct ll *r1);
166 void ll_swap (struct ll *a, struct ll *b);
167 void ll_swap_range (struct ll *a0, struct ll *a1,
168 struct ll *b0, struct ll *b1);
171 static inline struct ll *ll_remove (struct ll *);
172 static inline void ll_remove_range (struct ll *r0, struct ll *r1);
173 size_t ll_remove_equal (struct ll *r0, struct ll *r1, struct ll *target,
174 ll_compare_func *, void *aux);
175 size_t ll_remove_if (struct ll *r0, struct ll *r1,
176 ll_predicate_func *, void *aux);
177 static inline void ll_moved (struct ll *);
179 /* Non-mutating algorithms. */
180 struct ll *ll_find_equal (const struct ll *r0, const struct ll *r1,
181 const struct ll *target,
182 ll_compare_func *, void *aux);
183 struct ll *ll_find_if (const struct ll *r0, const struct ll *r1,
184 ll_predicate_func *, void *aux);
185 struct ll *ll_find_adjacent_equal (const struct ll *r0, const struct ll *r1,
186 ll_compare_func *, void *aux);
187 size_t ll_count_range (const struct ll *r0, const struct ll *r1);
188 size_t ll_count_equal (const struct ll *r0, const struct ll *r1,
189 const struct ll *target,
190 ll_compare_func *, void *aux);
191 size_t ll_count_if (const struct ll *r0, const struct ll *r1,
192 ll_predicate_func *, void *aux);
193 struct ll *ll_max (const struct ll *r0, const struct ll *r1,
194 ll_compare_func *, void *aux);
195 struct ll *ll_min (const struct ll *r0, const struct ll *r1,
196 ll_compare_func *, void *aux);
197 int ll_lexicographical_compare_3way (const struct ll *a0, const struct ll *a1,
198 const struct ll *b0, const struct ll *b1,
199 ll_compare_func *, void *aux);
201 /* Mutating algorithms. */
202 void ll_apply (struct ll *r0, struct ll *r1, ll_action_func *, void *aux);
203 void ll_reverse (struct ll *r0, struct ll *r1);
204 bool ll_next_permutation (struct ll *r0, struct ll *r1,
205 ll_compare_func *, void *aux);
206 bool ll_prev_permutation (struct ll *r0, struct ll *r1,
207 ll_compare_func *, void *aux);
209 /* Sorted list functions. */
210 void ll_sort (struct ll *r0, struct ll *r1, ll_compare_func *, void *aux);
211 struct ll *ll_find_run (const struct ll *r0, const struct ll *r1,
212 ll_compare_func *, void *aux);
213 struct ll *ll_merge (struct ll *a0, struct ll *a1,
214 struct ll *b0, struct ll *b1,
215 ll_compare_func *, void *aux);
216 bool ll_is_sorted (const struct ll *r0, const struct ll *r1,
217 ll_compare_func *, void *aux);
218 size_t ll_unique (struct ll *r0, struct ll *r1, struct ll *dups,
219 ll_compare_func *, void *aux);
220 void ll_sort_unique (struct ll *r0, struct ll *r1, struct ll *dups,
221 ll_compare_func *, void *aux);
222 void ll_insert_ordered (struct ll *r0, struct ll *r1, struct ll *new_elem,
223 ll_compare_func *, void *aux);
224 struct ll *ll_partition (struct ll *r0, struct ll *r1,
225 ll_predicate_func *, void *aux);
226 struct ll *ll_find_partition (const struct ll *r0, const struct ll *r1,
227 ll_predicate_func *, void *aux);
229 /* Iteration helper macros. */
231 /* Sets DATA to each object in LIST in turn, assuming that each
232 `struct ll' in LIST is embedded as the given MEMBER name in
235 Behavior is undefined if DATA is removed from the list between
237 #define ll_for_each(DATA, STRUCT, MEMBER, LIST) \
238 for (DATA = ll_head__ (STRUCT, MEMBER, LIST); \
240 DATA = ll_next__ (DATA, STRUCT, MEMBER, LIST))
242 /* Continues a iteration of LIST, starting from the object
243 currently in DATA and continuing forward through the remainder
244 of the list, assuming that each `struct ll' in LIST is
245 embedded as the given MEMBER name in data type STRUCT.
247 Behavior is undefined if DATA is removed from the list between
249 #define ll_for_each_continue(DATA, STRUCT, MEMBER, LIST) \
252 DATA = ll_next__ (DATA, STRUCT, MEMBER, LIST))
254 /* Sets DATA to each object in LIST in turn, assuming that each
255 `struct ll' in LIST is embedded as the given MEMBER name in
256 data type STRUCT. NEXT must be another variable of the same
259 Behavior is well-defined even if DATA is removed from the list
260 between iterations. */
261 #define ll_for_each_safe(DATA, NEXT, STRUCT, MEMBER, LIST) \
262 for (DATA = ll_head__ (STRUCT, MEMBER, LIST); \
264 ? (NEXT = ll_next__ (DATA, STRUCT, MEMBER, LIST), 1) \
268 /* Continues a iteration of LIST, starting from the object
269 currently in DATA and continuing forward through the remainder
270 of the list, assuming that each `struct ll' in LIST is
271 embedded as the given MEMBER name in data type STRUCT. NEXT
272 must be another variable of the same type as DATA.
274 Behavior is well-defined even if DATA is removed from the list
275 between iterations. */
276 #define ll_for_each_safe_continue(DATA, NEXT, STRUCT, MEMBER, LIST) \
279 ? (NEXT = ll_next__ (DATA, STRUCT, MEMBER, LIST), 1) \
283 /* Sets DATA to each object in LIST in turn, assuming that each
284 `struct ll' in LIST is embedded as the given MEMBER name in
286 Each object is removed from LIST before its loop iteration. */
287 #define ll_for_each_preremove(DATA, STRUCT, MEMBER, LIST) \
288 while (!ll_is_empty (LIST) \
289 ? (DATA = ll_data (ll_pop_head (LIST), STRUCT, MEMBER), 1) \
292 /* Sets DATA to each object in LIST in turn, assuming that each
293 `struct ll' in LIST is embedded as the given MEMBER name in
295 At the end of each loop iteration, DATA is removed from the
297 #define ll_for_each_postremove(DATA, STRUCT, MEMBER, LIST) \
299 (DATA = ll_head__ (STRUCT, MEMBER, LIST)) != NULL; \
300 ll_remove (&DATA->MEMBER))
302 /* Macros for internal use only. */
303 #define ll_data__(LL, STRUCT, MEMBER, LIST) \
304 ((LL) != ll_null (LIST) ? ll_data (LL, STRUCT, MEMBER) : NULL)
305 #define ll_head__(STRUCT, MEMBER, LIST) \
306 ll_data__ (ll_head (LIST), STRUCT, MEMBER, LIST)
307 #define ll_next__(DATA, STRUCT, MEMBER, LIST) \
308 ll_data__ (ll_next (&DATA->MEMBER), STRUCT, MEMBER, LIST)
309 #define ll_remove__(DATA, STRUCT, MEMBER, LIST) \
310 (ll_next (&DATA->MEMBER) == ll_null (LIST) \
311 ? ll_remove (&DATA->MEMBER), NULL \
312 : ll_data (ll_remove (&DATA->MEMBER), STRUCT, MEMBER))
314 /* Inline functions. */
316 /* Initializes LIST as an empty list. */
318 ll_init (struct ll_list *list)
320 list->null.next = list->null.prev = &list->null;
323 /* Returns true if LIST is empty (contains just the null node),
324 false if LIST is not empty (has at least one other node).
325 Executes in O(1) time. */
327 ll_is_empty (const struct ll_list *list)
329 return ll_head (list) == ll_null (list);
332 /* Returns the first node in LIST,
333 or the null node if LIST is empty. */
334 static inline struct ll *
335 ll_head (const struct ll_list *list)
337 return ll_next (ll_null (list));
340 /* Returns the last node in LIST,
341 or the null node if LIST is empty. */
342 static inline struct ll *
343 ll_tail (const struct ll_list *list)
345 return ll_prev (ll_null (list));
348 /* Returns LIST's null node. */
349 static inline struct ll *
350 ll_null (const struct ll_list *list)
352 return (struct ll *) &list->null;
355 /* Returns the node following LL in its list,
356 or the null node if LL is at the end of its list.
357 (In an empty list, the null node follows itself.) */
358 static inline struct ll *
359 ll_next (const struct ll *ll)
364 /* Returns the node preceding LL in its list,
365 or the null node if LL is the first node in its list.
366 (In an empty list, the null node precedes itself.) */
367 static inline struct ll *
368 ll_prev (const struct ll *ll)
373 /* Inserts LL at the head of LIST. */
375 ll_push_head (struct ll_list *list, struct ll *ll)
377 ll_insert (ll_head (list), ll);
380 /* Inserts LL at the tail of LIST. */
382 ll_push_tail (struct ll_list *list, struct ll *ll)
384 ll_insert (ll_null (list), ll);
387 /* Removes and returns the first node in LIST,
388 which must not be empty. */
389 static inline struct ll *
390 ll_pop_head (struct ll_list *list)
393 assert (!ll_is_empty (list));
394 head = ll_head (list);
399 /* Removes and returns the last node in LIST,
400 which must not be empty. */
401 static inline struct ll *
402 ll_pop_tail (struct ll_list *list)
405 assert (!ll_is_empty (list));
406 tail = ll_tail (list);
411 /* Inserts NEW_ELEM just before BEFORE.
412 (NEW_ELEM must not already be in a list.) */
414 ll_insert (struct ll *before, struct ll *new_elem)
416 struct ll *before_prev = ll_prev (before);
417 new_elem->next = before;
418 new_elem->prev = before_prev;
419 before_prev->next = before->prev = new_elem;
422 /* Removes LL from its list
423 and returns the node that formerly followed it. */
424 static inline struct ll *
425 ll_remove (struct ll *ll)
427 struct ll *next = ll_next (ll);
428 ll->prev->next = next;
429 ll->next->prev = ll->prev;
433 /* Removes R0...R1 from their list. */
435 ll_remove_range (struct ll *r0, struct ll *r1)
440 r0->prev->next = r1->next;
441 r1->next->prev = r0->prev;
445 /* Adjusts the nodes around LL to compensate for LL having
446 changed address, e.g. due to LL being inside a block of memory
447 that was realloc()'d. Equivalent to calling ll_remove()
448 before moving LL, then ll_insert() afterward, but more
451 ll_moved (struct ll *ll)
453 ll->prev->next = ll->next->prev = ll;