1 /* PSPP - a program for statistical analysis.
2 Copyright (C) 2006, 2009, 2011 Free Software Foundation, Inc.
3
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.
8
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.
13
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/>. */
16
17 /* Circular doubly linked lists.
18
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
25 definition.
26
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.
34
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
45 list contains. */
46
47 #ifndef LL_H
48 #define LL_H
49
50 #include <assert.h>
51 #include <stdbool.h>
52 #include <stddef.h>
53 #include "libpspp/cast.h"
54
55 /* Embedded, circular doubly linked list.
56
57 Each list contains a single "null" element that separates the
58 head and the tail of the list. The null element is both
59 before the head and after the tail of the list. An empty list
60 contains just the null element.
61
62 An embedded linked list is represented as `struct ll_list'.
63 Each node in the list, presumably a structure type, must
64 include a `struct ll' member.
65
66 Many list functions take ranges of nodes as arguments. Ranges
67 are "half-open"; that is, R0...R1 includes R0 but not R1. A
68 range whose endpoints are the same (e.g. R0...R0) contains no
69 nodes at all.
70
71 Here's an example of a structure type that includes a `struct
72 ll':
73
74 struct ll_list list;
75
76 struct foo
77 {
78 struct ll ll; // List member.
79 int x; // Another member.
80 };
81
82 Here's an example of iteration from head to tail:
83
84 struct ll *ll;
85 for (ll = ll_head (&list); ll != ll_null (&list); ll = ll_next (ll))
86 {
87 struct foo *foo = ll_data (ll, struct foo, ll);
88 ...do something with foo->x...
89 }
90
91 Here's another way to do it:
92
93 struct ll *ll = ll_null (&list);
94 while ((ll = ll_next (ll)) != ll_null (&list))
95 {
96 struct foo *foo = ll_data (ll, struct foo, ll);
97 ...do something with foo->x...
98 }
99
100 Here's a third way:
101
102 struct foo *foo;
103 ll_for_each (foo, struct foo, ll, &list)
104 {
105 ...do something with foo->x...
106 }
107 */
108
109 /* Returns the data structure corresponding to the given node LL,
110 assuming that LL is embedded as the given MEMBER name in data
111 type STRUCT. */
112 #define ll_data(LL, STRUCT, MEMBER) \
113 (CHECK_POINTER_HAS_TYPE(LL, struct ll *), \
114 UP_CAST(LL, STRUCT, MEMBER))
115
116 /* Linked list node. */
117 struct ll
118 {
119 struct ll *next; /* Next node. */
120 struct ll *prev; /* Previous node. */
121 };
122
123 /* Linked list. */
124 struct ll_list
125 {
126 struct ll null; /* Null node. */
127 };
128
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);
132
133 /* Returns true or false depending on properties of LL. */
134 typedef bool ll_predicate_func (const struct ll *ll, void *aux);
135
136 /* Takes some action on LL. */
137 typedef void ll_action_func (struct ll *ll, void *aux);
138
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 } }
144
145 /* Basics. */
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 *);
149
150 /* Iteration. */
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 *);
156
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 *);
162
163 /* Insertion. */
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);
169
170 /* Removal. */
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 *);
178
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);
200
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);
208
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);
228
229 /* Iteration helper macros. */
230
231 /* Sets DATA to each object in LIST in turn, in forward or
232 reverse order, assuming that each
233 `struct ll' in LIST is embedded as the given MEMBER name in
234 data type STRUCT.
235
236 Behavior is undefined if DATA is removed from the list between
237 loop iterations. */
238 #define ll_for_each(DATA, STRUCT, MEMBER, LIST) \
239 for (DATA = ll_head__ (STRUCT, MEMBER, LIST); \
240 DATA != NULL; \
241 DATA = ll_next__ (DATA, STRUCT, MEMBER, LIST))
242 #define ll_for_each_reverse(DATA, STRUCT, MEMBER, LIST) \
243 for (DATA = ll_tail__ (STRUCT, MEMBER, LIST); \
244 DATA != NULL; \
245 DATA = ll_prev__ (DATA, STRUCT, MEMBER, LIST))
246
247 /* Continues a iteration of LIST, starting from the object
248 currently in DATA and continuing, in forward or reverse order,
249 through the remainder of the list, assuming that each `struct
250 ll' in LIST is embedded as the given MEMBER name in data type
251 STRUCT.
252
253 Behavior is undefined if DATA is removed from the list between
254 loop iterations. */
255 #define ll_for_each_continue(DATA, STRUCT, MEMBER, LIST) \
256 for (; \
257 DATA != NULL; \
258 DATA = ll_next__ (DATA, STRUCT, MEMBER, LIST))
259 #define ll_for_each_reverse_continue(DATA, STRUCT, MEMBER, LIST) \
260 for (; \
261 DATA != NULL; \
262 DATA = ll_prev__ (DATA, STRUCT, MEMBER, LIST))
263
264 /* Sets DATA to each object in LIST in turn, in forward or
265 reverse order, assuming that each `struct ll' in LIST is
266 embedded as the given MEMBER name in data type STRUCT. NEXT
267 (or PREV) must be another variable of the same type as DATA.
268
269 Behavior is well-defined even if DATA is removed from the list
270 between iterations. */
271 #define ll_for_each_safe(DATA, NEXT, STRUCT, MEMBER, LIST) \
272 for (DATA = ll_head__ (STRUCT, MEMBER, LIST); \
273 (DATA != NULL \
274 ? (NEXT = ll_next__ (DATA, STRUCT, MEMBER, LIST), 1) \
275 : 0); \
276 DATA = NEXT)
277 #define ll_for_each_reverse_safe(DATA, PREV, STRUCT, MEMBER, LIST) \
278 for (DATA = ll_tail__ (STRUCT, MEMBER, LIST); \
279 (DATA != NULL \
280 ? (PREV = ll_prev__ (DATA, STRUCT, MEMBER, LIST), 1) \
281 : 0); \
282 DATA = PREV)
283
284 /* Continues a iteration of LIST, in forward or reverse order,
285 starting from the object currently in DATA and continuing
286 forward through the remainder of the list, assuming that each
287 `struct ll' in LIST is embedded as the given MEMBER name in
288 data type STRUCT. NEXT (or PREV) must be another variable of
289 the same type as DATA.
290
291 Behavior is well-defined even if DATA is removed from the list
292 between iterations. */
293 #define ll_for_each_safe_continue(DATA, NEXT, STRUCT, MEMBER, LIST) \
294 for (; \
295 (DATA != NULL \
296 ? (NEXT = ll_next__ (DATA, STRUCT, MEMBER, LIST), 1) \
297 : 0); \
298 DATA = NEXT)
299 #define ll_for_each_safe_reverse_continue(DATA, PREV, STRUCT, MEMBER, LIST) \
300 for (; \
301 (DATA != NULL \
302 ? (PREV = ll_prev__ (DATA, STRUCT, MEMBER, LIST), 1) \
303 : 0); \
304 DATA = PREV)
305
306 /* Sets DATA to each object in LIST in turn, in forward or
307 reverse order, assuming that each `struct ll' in LIST is
308 embedded as the given MEMBER name in data type STRUCT.
309 Each object is removed from LIST before its loop iteration. */
310 #define ll_for_each_preremove(DATA, STRUCT, MEMBER, LIST) \
311 while (!ll_is_empty (LIST) \
312 ? (DATA = ll_data (ll_pop_head (LIST), STRUCT, MEMBER), 1) \
313 : 0)
314 #define ll_for_each_reverse_preremove(DATA, STRUCT, MEMBER, LIST) \
315 while (!ll_is_empty (LIST) \
316 ? (DATA = ll_data (ll_pop_tail (LIST), STRUCT, MEMBER), 1) \
317 : 0)
318
319 /* Sets DATA to each object in LIST in turn, in forward or
320 reverse order, assuming that each `struct ll' in LIST is
321 embedded as the given MEMBER name in data type STRUCT.
322 At the end of each loop iteration, DATA is removed from the
323 list. */
324 #define ll_for_each_postremove(DATA, STRUCT, MEMBER, LIST) \
325 for (; \
326 (DATA = ll_head__ (STRUCT, MEMBER, LIST)) != NULL; \
327 ll_remove (&DATA->MEMBER))
328 #define ll_for_each_reverse_postremove(DATA, STRUCT, MEMBER, LIST) \
329 for (; \
330 (DATA = ll_tail__ (STRUCT, MEMBER, LIST)) != NULL; \
331 ll_remove (&DATA->MEMBER))
332
333 /* Macros for internal use only. */
334 #define ll_data__(LL, STRUCT, MEMBER, LIST) \
335 ((LL) != ll_null (LIST) ? ll_data (LL, STRUCT, MEMBER) : NULL)
336 #define ll_head__(STRUCT, MEMBER, LIST) \
337 ll_data__ (ll_head (LIST), STRUCT, MEMBER, LIST)
338 #define ll_tail__(STRUCT, MEMBER, LIST) \
339 ll_data__ (ll_tail (LIST), STRUCT, MEMBER, LIST)
340 #define ll_next__(DATA, STRUCT, MEMBER, LIST) \
341 ll_data__ (ll_next (&(DATA)->MEMBER), STRUCT, MEMBER, LIST)
342 #define ll_prev__(DATA, STRUCT, MEMBER, LIST) \
343 ll_data__ (ll_prev (&(DATA)->MEMBER), STRUCT, MEMBER, LIST)
344
345 /* Inline functions. */
346
347 /* Initializes LIST as an empty list. */
348 static inline void
ll_init(struct ll_list * list)349 ll_init (struct ll_list *list)
350 {
351 list->null.next = list->null.prev = &list->null;
352 }
353
354 /* Returns true if LIST is empty (contains just the null node),
355 false if LIST is not empty (has at least one other node).
356 Executes in O(1) time. */
357 static inline bool
ll_is_empty(const struct ll_list * list)358 ll_is_empty (const struct ll_list *list)
359 {
360 return ll_head (list) == ll_null (list);
361 }
362
363 /* Returns the first node in LIST,
364 or the null node if LIST is empty. */
365 static inline struct ll *
ll_head(const struct ll_list * list)366 ll_head (const struct ll_list *list)
367 {
368 return ll_next (ll_null (list));
369 }
370
371 /* Returns the last node in LIST,
372 or the null node if LIST is empty. */
373 static inline struct ll *
ll_tail(const struct ll_list * list)374 ll_tail (const struct ll_list *list)
375 {
376 return ll_prev (ll_null (list));
377 }
378
379 /* Returns LIST's null node. */
380 static inline struct ll *
ll_null(const struct ll_list * list)381 ll_null (const struct ll_list *list)
382 {
383 return CONST_CAST (struct ll *, &list->null);
384 }
385
386 /* Returns the node following LL in its list,
387 or the null node if LL is at the end of its list.
388 (In an empty list, the null node follows itself.) */
389 static inline struct ll *
ll_next(const struct ll * ll)390 ll_next (const struct ll *ll)
391 {
392 return ll->next;
393 }
394
395 /* Returns the node preceding LL in its list,
396 or the null node if LL is the first node in its list.
397 (In an empty list, the null node precedes itself.) */
398 static inline struct ll *
ll_prev(const struct ll * ll)399 ll_prev (const struct ll *ll)
400 {
401 return ll->prev;
402 }
403
404 /* Inserts LL at the head of LIST. */
405 static inline void
ll_push_head(struct ll_list * list,struct ll * ll)406 ll_push_head (struct ll_list *list, struct ll *ll)
407 {
408 ll_insert (ll_head (list), ll);
409 }
410
411 /* Inserts LL at the tail of LIST. */
412 static inline void
ll_push_tail(struct ll_list * list,struct ll * ll)413 ll_push_tail (struct ll_list *list, struct ll *ll)
414 {
415 ll_insert (ll_null (list), ll);
416 }
417
418 /* Removes and returns the first node in LIST,
419 which must not be empty. */
420 static inline struct ll *
ll_pop_head(struct ll_list * list)421 ll_pop_head (struct ll_list *list)
422 {
423 struct ll *head;
424 assert (!ll_is_empty (list));
425 head = ll_head (list);
426 ll_remove (head);
427 return head;
428 }
429
430 /* Removes and returns the last node in LIST,
431 which must not be empty. */
432 static inline struct ll *
ll_pop_tail(struct ll_list * list)433 ll_pop_tail (struct ll_list *list)
434 {
435 struct ll *tail;
436 assert (!ll_is_empty (list));
437 tail = ll_tail (list);
438 ll_remove (tail);
439 return tail;
440 }
441
442 /* Inserts NEW_ELEM just before BEFORE.
443 (NEW_ELEM must not already be in a list.) */
444 static inline void
ll_insert(struct ll * before,struct ll * new_elem)445 ll_insert (struct ll *before, struct ll *new_elem)
446 {
447 struct ll *before_prev = ll_prev (before);
448 new_elem->next = before;
449 new_elem->prev = before_prev;
450 before_prev->next = before->prev = new_elem;
451 }
452
453 /* Removes LL from its list
454 and returns the node that formerly followed it. */
455 static inline struct ll *
ll_remove(struct ll * ll)456 ll_remove (struct ll *ll)
457 {
458 struct ll *next = ll_next (ll);
459 ll->prev->next = next;
460 ll->next->prev = ll->prev;
461 return next;
462 }
463
464 /* Removes R0...R1 from their list. */
465 static inline void
ll_remove_range(struct ll * r0,struct ll * r1)466 ll_remove_range (struct ll *r0, struct ll *r1)
467 {
468 if (r0 != r1)
469 {
470 r1 = r1->prev;
471 r0->prev->next = r1->next;
472 r1->next->prev = r0->prev;
473 }
474 }
475
476 /* Adjusts the nodes around LL to compensate for LL having
477 changed address, e.g. due to LL being inside a block of memory
478 that was realloc()'d. Equivalent to calling ll_remove()
479 before moving LL, then ll_insert() afterward, but more
480 efficient. */
481 static inline void
ll_moved(struct ll * ll)482 ll_moved (struct ll *ll)
483 {
484 ll->prev->next = ll->next->prev = ll;
485 }
486
487 #endif /* ll.h */
488