Age Owner TLA Line data Source code
1 : /*-------------------------------------------------------------------------
2 : *
3 : * ilist.h
4 : * integrated/inline doubly- and singly-linked lists
5 : *
6 : * These list types are useful when there are only a predetermined set of
7 : * lists that an object could be in. List links are embedded directly into
8 : * the objects, and thus no extra memory management overhead is required.
9 : * (Of course, if only a small proportion of existing objects are in a list,
10 : * the link fields in the remainder would be wasted space. But usually,
11 : * it saves space to not have separately-allocated list nodes.)
12 : *
13 : * The doubly-linked list comes in 2 forms. dlist_head defines a head of a
14 : * doubly-linked list of dlist_nodes, whereas dclist_head defines the head of
15 : * a doubly-linked list of dlist_nodes with an additional 'count' field to
16 : * keep track of how many items are contained within the given list. For
17 : * simplicity, dlist_head and dclist_head share the same node and iterator
18 : * types. The functions to manipulate a dlist_head always have a name
19 : * starting with "dlist", whereas functions to manipulate a dclist_head have a
20 : * name starting with "dclist". dclist_head comes with an additional function
21 : * (dclist_count) to return the number of entries in the list. dclists are
22 : * able to store a maximum of PG_UINT32_MAX elements. It is up to the caller
23 : * to ensure no more than this many items are added to a dclist.
24 : *
25 : * None of the functions here allocate any memory; they just manipulate
26 : * externally managed memory. With the exception doubly-linked count lists
27 : * providing the ability to obtain the number of items in the list, the APIs
28 : * for singly and both doubly linked lists are identical as far as
29 : * capabilities of both allow.
30 : *
31 : * Each list has a list header, which exists even when the list is empty.
32 : * An empty singly-linked list has a NULL pointer in its header.
33 : *
34 : * For both doubly-linked list types, there are two valid ways to represent an
35 : * empty list. The head's 'next' pointer can either be NULL or the head's
36 : * 'next' and 'prev' links can both point back to the list head (circular).
37 : * (If a dlist is modified and then all its elements are deleted, it will be
38 : * in the circular state.). We prefer circular dlists because there are some
39 : * operations that can be done without branches (and thus faster) on lists
40 : * that use circular representation. However, it is often convenient to
41 : * initialize list headers to zeroes rather than setting them up with an
42 : * explicit initialization function, so we also allow the NULL initialization.
43 : *
44 : * EXAMPLES
45 : *
46 : * Here's a simple example demonstrating how this can be used. Let's assume
47 : * we want to store information about the tables contained in a database.
48 : *
49 : * #include "lib/ilist.h"
50 : *
51 : * // Define struct for the databases including a list header that will be
52 : * // used to access the nodes in the table list later on.
53 : * typedef struct my_database
54 : * {
55 : * char *datname;
56 : * dlist_head tables;
57 : * // ...
58 : * } my_database;
59 : *
60 : * // Define struct for the tables. Note the list_node element which stores
61 : * // prev/next list links. The list_node element need not be first.
62 : * typedef struct my_table
63 : * {
64 : * char *tablename;
65 : * dlist_node list_node;
66 : * perm_t permissions;
67 : * // ...
68 : * } my_table;
69 : *
70 : * // create a database
71 : * my_database *db = create_database();
72 : *
73 : * // and add a few tables to its table list
74 : * dlist_push_head(&db->tables, &create_table(db, "a")->list_node);
75 : * ...
76 : * dlist_push_head(&db->tables, &create_table(db, "b")->list_node);
77 : *
78 : *
79 : * To iterate over the table list, we allocate an iterator variable and use
80 : * a specialized looping construct. Inside a dlist_foreach, the iterator's
81 : * 'cur' field can be used to access the current element. iter.cur points to
82 : * a 'dlist_node', but most of the time what we want is the actual table
83 : * information; dlist_container() gives us that, like so:
84 : *
85 : * dlist_iter iter;
86 : * dlist_foreach(iter, &db->tables)
87 : * {
88 : * my_table *tbl = dlist_container(my_table, list_node, iter.cur);
89 : * printf("we have a table: %s in database %s\n",
90 : * tbl->tablename, db->datname);
91 : * }
92 : *
93 : *
94 : * While a simple iteration is useful, we sometimes also want to manipulate
95 : * the list while iterating. There is a different iterator element and looping
96 : * construct for that. Suppose we want to delete tables that meet a certain
97 : * criterion:
98 : *
99 : * dlist_mutable_iter miter;
100 : * dlist_foreach_modify(miter, &db->tables)
101 : * {
102 : * my_table *tbl = dlist_container(my_table, list_node, miter.cur);
103 : *
104 : * if (!tbl->to_be_deleted)
105 : * continue; // don't touch this one
106 : *
107 : * // unlink the current table from the linked list
108 : * dlist_delete(miter.cur);
109 : * // as these lists never manage memory, we can still access the table
110 : * // after it's been unlinked
111 : * drop_table(db, tbl);
112 : * }
113 : *
114 : *
115 : * Portions Copyright (c) 1996-2023, PostgreSQL Global Development Group
116 : * Portions Copyright (c) 1994, Regents of the University of California
117 : *
118 : * IDENTIFICATION
119 : * src/include/lib/ilist.h
120 : *-------------------------------------------------------------------------
121 : */
122 : #ifndef ILIST_H
123 : #define ILIST_H
124 :
125 : /*
126 : * Enable for extra debugging. This is rather expensive, so it's not enabled by
127 : * default even when USE_ASSERT_CHECKING.
128 : */
129 : /* #define ILIST_DEBUG */
130 :
131 : /*
132 : * Node of a doubly linked list.
133 : *
134 : * Embed this in structs that need to be part of a doubly linked list.
135 : */
136 : typedef struct dlist_node dlist_node;
137 : struct dlist_node
138 : {
139 : dlist_node *prev;
140 : dlist_node *next;
141 : };
142 :
143 : /*
144 : * Head of a doubly linked list.
145 : *
146 : * Non-empty lists are internally circularly linked. Circular lists have the
147 : * advantage of not needing any branches in the most common list manipulations.
148 : * An empty list can also be represented as a pair of NULL pointers, making
149 : * initialization easier.
150 : */
151 : typedef struct dlist_head
152 : {
153 : /*
154 : * head.next either points to the first element of the list; to &head if
155 : * it's a circular empty list; or to NULL if empty and not circular.
156 : *
157 : * head.prev either points to the last element of the list; to &head if
158 : * it's a circular empty list; or to NULL if empty and not circular.
159 : */
160 : dlist_node head;
161 : } dlist_head;
162 :
163 :
164 : /*
165 : * Doubly linked list iterator type for dlist_head and dclist_head types.
166 : *
167 : * Used as state in dlist_foreach() and dlist_reverse_foreach() (and the
168 : * dclist variant thereof).
169 : *
170 : * To get the current element of the iteration use the 'cur' member.
171 : *
172 : * Iterations using this are *not* allowed to change the list while iterating!
173 : *
174 : * NB: We use an extra "end" field here to avoid multiple evaluations of
175 : * arguments in the dlist_foreach() and dclist_foreach() macros.
176 : */
177 : typedef struct dlist_iter
178 : {
179 : dlist_node *cur; /* current element */
180 : dlist_node *end; /* last node we'll iterate to */
181 : } dlist_iter;
182 :
183 : /*
184 : * Doubly linked list iterator for both dlist_head and dclist_head types.
185 : * This iterator type allows some modifications while iterating.
186 : *
187 : * Used as state in dlist_foreach_modify() and dclist_foreach_modify().
188 : *
189 : * To get the current element of the iteration use the 'cur' member.
190 : *
191 : * Iterations using this are only allowed to change the list at the current
192 : * point of iteration. It is fine to delete the current node, but it is *not*
193 : * fine to insert or delete adjacent nodes.
194 : *
195 : * NB: We need a separate type for mutable iterations so that we can store
196 : * the 'next' node of the current node in case it gets deleted or modified.
197 : */
198 : typedef struct dlist_mutable_iter
199 : {
200 : dlist_node *cur; /* current element */
201 : dlist_node *next; /* next node we'll iterate to */
202 : dlist_node *end; /* last node we'll iterate to */
203 : } dlist_mutable_iter;
204 :
205 : /*
206 : * Head of a doubly linked list with a count of the number of items
207 : *
208 : * This internally makes use of a dlist to implement the actual list. When
209 : * items are added or removed from the list the count is updated to reflect
210 : * the current number of items in the list.
211 : */
212 : typedef struct dclist_head
213 : {
214 : dlist_head dlist; /* the actual list header */
215 : uint32 count; /* the number of items in the list */
216 : } dclist_head;
217 :
218 : /*
219 : * Node of a singly linked list.
220 : *
221 : * Embed this in structs that need to be part of a singly linked list.
222 : */
223 : typedef struct slist_node slist_node;
224 : struct slist_node
225 : {
226 : slist_node *next;
227 : };
228 :
229 : /*
230 : * Head of a singly linked list.
231 : *
232 : * Singly linked lists are not circularly linked, in contrast to doubly linked
233 : * lists; we just set head.next to NULL if empty. This doesn't incur any
234 : * additional branches in the usual manipulations.
235 : */
236 : typedef struct slist_head
237 : {
238 : slist_node head;
239 : } slist_head;
240 :
241 : /*
242 : * Singly linked list iterator.
243 : *
244 : * Used as state in slist_foreach(). To get the current element of the
245 : * iteration use the 'cur' member.
246 : *
247 : * It's allowed to modify the list while iterating, with the exception of
248 : * deleting the iterator's current node; deletion of that node requires
249 : * care if the iteration is to be continued afterward. (Doing so and also
250 : * deleting or inserting adjacent list elements might misbehave; also, if
251 : * the user frees the current node's storage, continuing the iteration is
252 : * not safe.)
253 : *
254 : * NB: this wouldn't really need to be an extra struct, we could use an
255 : * slist_node * directly. We prefer a separate type for consistency.
256 : */
257 : typedef struct slist_iter
258 : {
259 : slist_node *cur;
260 : } slist_iter;
261 :
262 : /*
263 : * Singly linked list iterator allowing some modifications while iterating.
264 : *
265 : * Used as state in slist_foreach_modify(). To get the current element of the
266 : * iteration use the 'cur' member.
267 : *
268 : * The only list modification allowed while iterating is to remove the current
269 : * node via slist_delete_current() (*not* slist_delete()). Insertion or
270 : * deletion of nodes adjacent to the current node would misbehave.
271 : */
272 : typedef struct slist_mutable_iter
273 : {
274 : slist_node *cur; /* current element */
275 : slist_node *next; /* next node we'll iterate to */
276 : slist_node *prev; /* prev node, for deletions */
277 : } slist_mutable_iter;
278 :
279 :
280 : /* Static initializers */
281 : #define DLIST_STATIC_INIT(name) {{&(name).head, &(name).head}}
282 : #define DCLIST_STATIC_INIT(name) {{{&(name).dlist.head, &(name).dlist.head}}, 0}
283 : #define SLIST_STATIC_INIT(name) {{NULL}}
284 :
285 :
286 : /* Prototypes for functions too big to be inline */
287 :
288 : /* Caution: this is O(n); consider using slist_delete_current() instead */
289 : extern void slist_delete(slist_head *head, const slist_node *node);
290 :
291 : #ifdef ILIST_DEBUG
292 : extern void dlist_member_check(const dlist_head *head, const dlist_node *node);
293 : extern void dlist_check(const dlist_head *head);
294 : extern void slist_check(const slist_head *head);
295 : #else
296 : /*
297 : * These seemingly useless casts to void are here to keep the compiler quiet
298 : * about the argument being unused in many functions in a non-debug compile,
299 : * in which functions the only point of passing the list head pointer is to be
300 : * able to run these checks.
301 : */
302 : #define dlist_member_check(head, node) ((void) (head))
303 : #define dlist_check(head) ((void) (head))
304 : #define slist_check(head) ((void) (head))
305 : #endif /* ILIST_DEBUG */
306 :
307 : /* doubly linked list implementation */
308 :
309 : /*
310 : * Initialize a doubly linked list.
311 : * Previous state will be thrown away without any cleanup.
312 : */
313 : static inline void
3827 alvherre 314 GIC 13097655 : dlist_init(dlist_head *head)
315 : {
316 13097655 : head->head.next = head->head.prev = &head->head;
3825 tgl 317 13097655 : }
318 :
319 : /*
320 : * Initialize a doubly linked list element.
321 : *
322 : * This is only needed when dlist_node_is_detached() may be needed.
323 : */
324 : static inline void
81 andres 325 GNC 28547 : dlist_node_init(dlist_node *node)
326 : {
327 28547 : node->next = node->prev = NULL;
328 28547 : }
329 :
330 : /*
331 : * Is the list empty?
332 : *
333 : * An empty list has either its first 'next' pointer set to NULL, or to itself.
334 : */
335 : static inline bool
87 peter 336 31347575 : dlist_is_empty(const dlist_head *head)
337 : {
338 : dlist_check(head);
339 :
3825 tgl 340 GIC 31347575 : return head->head.next == NULL || head->head.next == &(head->head);
341 : }
342 :
343 : /*
344 : * Insert a node at the beginning of the list.
345 : */
346 : static inline void
3827 alvherre 347 9709381 : dlist_push_head(dlist_head *head, dlist_node *node)
348 : {
3825 tgl 349 9709381 : if (head->head.next == NULL) /* convert NULL header to circular */
3827 alvherre 350 3223839 : dlist_init(head);
351 :
352 9709381 : node->next = head->head.next;
353 9709381 : node->prev = &head->head;
354 9709381 : node->next->prev = node;
355 9709381 : head->head.next = node;
356 :
357 : dlist_check(head);
358 9709381 : }
359 :
360 : /*
3825 tgl 361 ECB : * Insert a node at the end of the list.
362 : */
2804 andres 363 : static inline void
3827 alvherre 364 CBC 22009276 : dlist_push_tail(dlist_head *head, dlist_node *node)
365 : {
3825 tgl 366 GIC 22009276 : if (head->head.next == NULL) /* convert NULL header to circular */
3827 alvherre 367 1857 : dlist_init(head);
368 :
369 22009276 : node->next = &head->head;
370 22009276 : node->prev = head->head.prev;
371 22009276 : node->prev->next = node;
3827 alvherre 372 CBC 22009276 : head->head.prev = node;
373 :
3827 alvherre 374 ECB : dlist_check(head);
3827 alvherre 375 CBC 22009276 : }
376 :
377 : /*
378 : * Insert a node after another *in the same list*
379 : */
380 : static inline void
3825 tgl 381 GIC 929 : dlist_insert_after(dlist_node *after, dlist_node *node)
382 : {
3827 alvherre 383 CBC 929 : node->prev = after;
3827 alvherre 384 GIC 929 : node->next = after->next;
385 929 : after->next = node;
386 929 : node->next->prev = node;
3827 alvherre 387 CBC 929 : }
388 :
389 : /*
390 : * Insert a node before another *in the same list*
391 : */
392 : static inline void
3825 tgl 393 UIC 0 : dlist_insert_before(dlist_node *before, dlist_node *node)
3827 alvherre 394 ECB : {
3827 alvherre 395 UIC 0 : node->prev = before->prev;
3827 alvherre 396 LBC 0 : node->next = before;
397 0 : before->prev = node;
3827 alvherre 398 UIC 0 : node->prev->next = node;
3827 alvherre 399 LBC 0 : }
3827 alvherre 400 ECB :
401 : /*
3825 tgl 402 : * Delete 'node' from its list (it must be in one).
403 : */
404 : static inline void
3825 tgl 405 CBC 15673498 : dlist_delete(dlist_node *node)
406 : {
3827 alvherre 407 GIC 15673498 : node->prev->next = node->next;
408 15673498 : node->next->prev = node->prev;
409 15673498 : }
410 :
411 : /*
412 : * Like dlist_delete(), but also sets next/prev to NULL to signal not being in
413 : * a list.
414 : */
415 : static inline void
81 andres 416 GNC 2207 : dlist_delete_thoroughly(dlist_node *node)
417 : {
418 2207 : node->prev->next = node->next;
419 2207 : node->next->prev = node->prev;
420 2207 : node->next = NULL;
421 2207 : node->prev = NULL;
422 2207 : }
423 :
424 : /*
425 : * Same as dlist_delete, but performs checks in ILIST_DEBUG builds to ensure
426 : * that 'node' belongs to 'head'.
427 : */
428 : static inline void
158 drowley 429 341263 : dlist_delete_from(dlist_head *head, dlist_node *node)
430 : {
431 : dlist_member_check(head, node);
432 341263 : dlist_delete(node);
433 341263 : }
434 :
435 : /*
436 : * Like dlist_delete_from, but also sets next/prev to NULL to signal not
437 : * being in a list.
438 : */
439 : static inline void
81 andres 440 983 : dlist_delete_from_thoroughly(dlist_head *head, dlist_node *node)
441 : {
442 : dlist_member_check(head, node);
443 983 : dlist_delete_thoroughly(node);
444 983 : }
445 :
3827 alvherre 446 ECB : /*
447 : * Remove and return the first node from a list (there must be one).
448 : */
2804 andres 449 : static inline dlist_node *
3827 alvherre 450 GIC 42881 : dlist_pop_head_node(dlist_head *head)
3827 alvherre 451 ECB : {
3825 tgl 452 : dlist_node *node;
3827 alvherre 453 :
3825 tgl 454 CBC 42881 : Assert(!dlist_is_empty(head));
3825 tgl 455 GIC 42881 : node = head->head.next;
456 42881 : dlist_delete(node);
3825 tgl 457 CBC 42881 : return node;
458 : }
459 :
460 : /*
461 : * Move element from its current position in the list to the head position in
462 : * the same list.
3827 alvherre 463 ECB : *
464 : * Undefined behaviour if 'node' is not already part of the list.
465 : */
2804 andres 466 : static inline void
3827 alvherre 467 CBC 50427695 : dlist_move_head(dlist_head *head, dlist_node *node)
3827 alvherre 468 ECB : {
469 : /* fast path if it's already at the head */
3827 alvherre 470 GIC 50427695 : if (head->head.next == node)
471 48378791 : return;
472 :
3825 tgl 473 2048904 : dlist_delete(node);
3827 alvherre 474 2048904 : dlist_push_head(head, node);
3827 alvherre 475 EUB :
476 : dlist_check(head);
477 : }
478 :
737 drowley 479 : /*
480 : * Move element from its current position in the list to the tail position in
481 : * the same list.
482 : *
483 : * Undefined behaviour if 'node' is not already part of the list.
484 : */
485 : static inline void
737 drowley 486 GIC 183610 : dlist_move_tail(dlist_head *head, dlist_node *node)
737 drowley 487 ECB : {
488 : /* fast path if it's already at the tail */
737 drowley 489 CBC 183610 : if (head->head.prev == node)
490 100226 : return;
737 drowley 491 ECB :
737 drowley 492 GIC 83384 : dlist_delete(node);
493 83384 : dlist_push_tail(head, node);
494 :
495 : dlist_check(head);
496 : }
497 :
3827 alvherre 498 ECB : /*
499 : * Check whether 'node' has a following node.
3825 tgl 500 : * Caution: unreliable if 'node' is not in the list.
3827 alvherre 501 : */
2804 andres 502 : static inline bool
87 peter 503 GNC 4062048 : dlist_has_next(const dlist_head *head, const dlist_node *node)
3827 alvherre 504 ECB : {
3827 alvherre 505 GIC 4062048 : return node->next != &head->head;
506 : }
507 :
508 : /*
509 : * Check whether 'node' has a preceding node.
510 : * Caution: unreliable if 'node' is not in the list.
3827 alvherre 511 ECB : */
512 : static inline bool
87 peter 513 GNC 306 : dlist_has_prev(const dlist_head *head, const dlist_node *node)
3827 alvherre 514 ECB : {
3827 alvherre 515 CBC 306 : return node->prev != &head->head;
516 : }
517 :
518 : /*
519 : * Check if node is detached. A node is only detached if it either has been
520 : * initialized with dlist_init_node(), or deleted with
521 : * dlist_delete_thoroughly() / dlist_delete_from_thoroughly() /
522 : * dclist_delete_from_thoroughly().
523 : */
524 : static inline bool
81 andres 525 GNC 15670 : dlist_node_is_detached(const dlist_node *node)
526 : {
527 15670 : Assert((node->next == NULL && node->prev == NULL) ||
528 : (node->next != NULL && node->prev != NULL));
529 :
530 15670 : return node->next == NULL;
531 : }
532 :
533 : /*
534 : * Return the next node in the list (there must be one).
535 : */
536 : static inline dlist_node *
3827 alvherre 537 CBC 1885007 : dlist_next_node(dlist_head *head, dlist_node *node)
538 : {
3827 alvherre 539 GIC 1885007 : Assert(dlist_has_next(head, node));
3827 alvherre 540 CBC 1885007 : return node->next;
3827 alvherre 541 ECB : }
542 :
543 : /*
544 : * Return previous node in the list (there must be one).
545 : */
546 : static inline dlist_node *
3827 alvherre 547 CBC 176 : dlist_prev_node(dlist_head *head, dlist_node *node)
548 : {
3827 alvherre 549 GIC 176 : Assert(dlist_has_prev(head, node));
550 176 : return node->prev;
3827 alvherre 551 ECB : }
552 :
3825 tgl 553 : /* internal support function to get address of head element's struct */
2804 andres 554 : static inline void *
3827 alvherre 555 GIC 2132315 : dlist_head_element_off(dlist_head *head, size_t off)
556 : {
557 2132315 : Assert(!dlist_is_empty(head));
558 2132315 : return (char *) head->head.next - off;
559 : }
560 :
561 : /*
562 : * Return the first node in the list (there must be one).
563 : */
2804 andres 564 ECB : static inline dlist_node *
3827 alvherre 565 GIC 241497 : dlist_head_node(dlist_head *head)
566 : {
3785 tgl 567 CBC 241497 : return (dlist_node *) dlist_head_element_off(head, 0);
3827 alvherre 568 ECB : }
569 :
3825 tgl 570 : /* internal support function to get address of tail element's struct */
2804 andres 571 : static inline void *
3827 alvherre 572 GIC 643364 : dlist_tail_element_off(dlist_head *head, size_t off)
573 : {
574 643364 : Assert(!dlist_is_empty(head));
575 643364 : return (char *) head->head.prev - off;
576 : }
577 :
578 : /*
579 : * Return the last node in the list (there must be one).
580 : */
581 : static inline dlist_node *
582 24772 : dlist_tail_node(dlist_head *head)
3827 alvherre 583 ECB : {
3785 tgl 584 GIC 24772 : return (dlist_node *) dlist_tail_element_off(head, 0);
585 : }
3827 alvherre 586 ECB :
587 : /*
588 : * Return the containing struct of 'type' where 'membername' is the dlist_node
589 : * pointed at by 'ptr'.
590 : *
591 : * This is used to convert a dlist_node * back to its containing struct.
592 : */
593 : #define dlist_container(type, membername, ptr) \
594 : (AssertVariableIsOfTypeMacro(ptr, dlist_node *), \
595 : AssertVariableIsOfTypeMacro(((type *) NULL)->membername, dlist_node), \
596 : ((type *) ((char *) (ptr) - offsetof(type, membername))))
597 :
598 : /*
599 : * Return the address of the first element in the list.
600 : *
601 : * The list must not be empty.
602 : */
603 : #define dlist_head_element(type, membername, lhead) \
604 : (AssertVariableIsOfTypeMacro(((type *) NULL)->membername, dlist_node), \
605 : (type *) dlist_head_element_off(lhead, offsetof(type, membername)))
606 :
607 : /*
608 : * Return the address of the last element in the list.
609 : *
610 : * The list must not be empty.
611 : */
3825 tgl 612 : #define dlist_tail_element(type, membername, lhead) \
613 : (AssertVariableIsOfTypeMacro(((type *) NULL)->membername, dlist_node), \
614 : ((type *) dlist_tail_element_off(lhead, offsetof(type, membername))))
615 :
616 : /*
617 : * Iterate through the list pointed at by 'lhead' storing the state in 'iter'.
618 : *
619 : * Access the current element with iter.cur.
620 : *
621 : * It is *not* allowed to manipulate the list during iteration.
3827 alvherre 622 : */
623 : #define dlist_foreach(iter, lhead) \
3825 tgl 624 : for (AssertVariableIsOfTypeMacro(iter, dlist_iter), \
625 : AssertVariableIsOfTypeMacro(lhead, dlist_head *), \
626 : (iter).end = &(lhead)->head, \
627 : (iter).cur = (iter).end->next ? (iter).end->next : (iter).end; \
628 : (iter).cur != (iter).end; \
629 : (iter).cur = (iter).cur->next)
630 :
631 : /*
632 : * Iterate through the list pointed at by 'lhead' storing the state in 'iter'.
633 : *
3827 alvherre 634 : * Access the current element with iter.cur.
635 : *
3825 tgl 636 : * Iterations using this are only allowed to change the list at the current
637 : * point of iteration. It is fine to delete the current node, but it is *not*
638 : * fine to insert or delete adjacent nodes.
639 : */
640 : #define dlist_foreach_modify(iter, lhead) \
641 : for (AssertVariableIsOfTypeMacro(iter, dlist_mutable_iter), \
642 : AssertVariableIsOfTypeMacro(lhead, dlist_head *), \
643 : (iter).end = &(lhead)->head, \
644 : (iter).cur = (iter).end->next ? (iter).end->next : (iter).end, \
645 : (iter).next = (iter).cur->next; \
646 : (iter).cur != (iter).end; \
647 : (iter).cur = (iter).next, (iter).next = (iter).cur->next)
648 :
649 : /*
650 : * Iterate through the list in reverse order.
651 : *
3827 alvherre 652 : * It is *not* allowed to manipulate the list during iteration.
653 : */
3825 tgl 654 : #define dlist_reverse_foreach(iter, lhead) \
655 : for (AssertVariableIsOfTypeMacro(iter, dlist_iter), \
656 : AssertVariableIsOfTypeMacro(lhead, dlist_head *), \
657 : (iter).end = &(lhead)->head, \
658 : (iter).cur = (iter).end->prev ? (iter).end->prev : (iter).end; \
659 : (iter).cur != (iter).end; \
660 : (iter).cur = (iter).cur->prev)
661 :
662 : /* doubly-linked count list implementation */
663 :
664 : /*
665 : * dclist_init
666 : * Initialize a doubly linked count list.
667 : *
668 : * Previous state will be thrown away without any cleanup.
669 : */
670 : static inline void
158 drowley 671 GNC 3463340 : dclist_init(dclist_head *head)
672 : {
673 3463340 : dlist_init(&head->dlist);
674 3463340 : head->count = 0;
675 3463340 : }
676 :
677 : /*
678 : * dclist_is_empty
679 : * Returns true if the list is empty, otherwise false.
680 : */
681 : static inline bool
87 peter 682 1111 : dclist_is_empty(const dclist_head *head)
683 : {
158 drowley 684 1111 : Assert(dlist_is_empty(&head->dlist) == (head->count == 0));
685 1111 : return (head->count == 0);
686 : }
687 :
688 : /*
689 : * dclist_push_head
690 : * Insert a node at the beginning of the list.
691 : */
692 : static inline void
693 29363 : dclist_push_head(dclist_head *head, dlist_node *node)
694 : {
695 29363 : if (head->dlist.head.next == NULL) /* convert NULL header to circular */
158 drowley 696 UNC 0 : dclist_init(head);
697 :
158 drowley 698 GNC 29363 : dlist_push_head(&head->dlist, node);
699 29363 : head->count++;
700 :
701 29363 : Assert(head->count > 0); /* count overflow check */
702 29363 : }
703 :
704 : /*
705 : * dclist_push_tail
706 : * Insert a node at the end of the list.
707 : */
708 : static inline void
709 213019 : dclist_push_tail(dclist_head *head, dlist_node *node)
710 : {
711 213019 : if (head->dlist.head.next == NULL) /* convert NULL header to circular */
712 207 : dclist_init(head);
713 :
714 213019 : dlist_push_tail(&head->dlist, node);
715 213019 : head->count++;
716 :
717 213019 : Assert(head->count > 0); /* count overflow check */
718 213019 : }
719 :
720 : /*
721 : * dclist_insert_after
722 : * Insert a node after another *in the same list*
723 : *
724 : * Caution: 'after' must be a member of 'head'.
725 : */
726 : static inline void
727 : dclist_insert_after(dclist_head *head, dlist_node *after, dlist_node *node)
728 : {
729 : dlist_member_check(&head->dlist, after);
730 : Assert(head->count > 0); /* must be at least 1 already */
731 :
732 : dlist_insert_after(after, node);
733 : head->count++;
734 :
735 : Assert(head->count > 0); /* count overflow check */
736 : }
737 :
738 : /*
739 : * dclist_insert_before
740 : * Insert a node before another *in the same list*
741 : *
742 : * Caution: 'before' must be a member of 'head'.
743 : */
744 : static inline void
158 drowley 745 UNC 0 : dclist_insert_before(dclist_head *head, dlist_node *before, dlist_node *node)
746 : {
747 : dlist_member_check(&head->dlist, before);
748 0 : Assert(head->count > 0); /* must be at least 1 already */
749 :
750 0 : dlist_insert_before(before, node);
751 0 : head->count++;
752 :
753 0 : Assert(head->count > 0); /* count overflow check */
754 0 : }
755 :
756 : /*
757 : * dclist_delete_from
758 : * Deletes 'node' from 'head'.
759 : *
760 : * Caution: 'node' must be a member of 'head'.
761 : */
762 : static inline void
158 drowley 763 GNC 212014 : dclist_delete_from(dclist_head *head, dlist_node *node)
764 : {
765 212014 : Assert(head->count > 0);
766 :
767 212014 : dlist_delete_from(&head->dlist, node);
768 212014 : head->count--;
769 212014 : }
770 :
771 : /*
772 : * Like dclist_delete_from(), but also sets next/prev to NULL to signal not
773 : * being in a list.
774 : */
775 : static inline void
81 andres 776 983 : dclist_delete_from_thoroughly(dclist_head *head, dlist_node *node)
777 : {
778 983 : Assert(head->count > 0);
779 :
780 983 : dlist_delete_from_thoroughly(&head->dlist, node);
781 983 : head->count--;
782 983 : }
783 :
784 : /*
785 : * dclist_pop_head_node
786 : * Remove and return the first node from a list (there must be one).
787 : */
788 : static inline dlist_node *
158 drowley 789 27823 : dclist_pop_head_node(dclist_head *head)
790 : {
791 : dlist_node *node;
792 :
793 27823 : Assert(head->count > 0);
794 :
795 27823 : node = dlist_pop_head_node(&head->dlist);
796 27823 : head->count--;
797 27823 : return node;
798 : }
799 :
800 : /*
801 : * dclist_move_head
802 : * Move 'node' from its current position in the list to the head position
803 : * in 'head'.
804 : *
805 : * Caution: 'node' must be a member of 'head'.
806 : */
807 : static inline void
808 2969 : dclist_move_head(dclist_head *head, dlist_node *node)
809 : {
810 : dlist_member_check(&head->dlist, node);
811 2969 : Assert(head->count > 0);
812 :
813 2969 : dlist_move_head(&head->dlist, node);
814 2969 : }
815 :
816 : /*
817 : * dclist_move_tail
818 : * Move 'node' from its current position in the list to the tail position
819 : * in 'head'.
820 : *
821 : * Caution: 'node' must be a member of 'head'.
822 : */
823 : static inline void
824 : dclist_move_tail(dclist_head *head, dlist_node *node)
825 : {
826 : dlist_member_check(&head->dlist, node);
827 : Assert(head->count > 0);
828 :
829 : dlist_move_tail(&head->dlist, node);
830 : }
831 :
832 : /*
833 : * dclist_has_next
834 : * Check whether 'node' has a following node.
835 : *
836 : * Caution: 'node' must be a member of 'head'.
837 : */
838 : static inline bool
839 : dclist_has_next(const dclist_head *head, const dlist_node *node)
840 : {
841 : dlist_member_check(&head->dlist, node);
842 : Assert(head->count > 0);
843 :
844 : return dlist_has_next(&head->dlist, node);
845 : }
846 :
847 : /*
848 : * dclist_has_prev
849 : * Check whether 'node' has a preceding node.
850 : *
851 : * Caution: 'node' must be a member of 'head'.
852 : */
853 : static inline bool
854 : dclist_has_prev(const dclist_head *head, const dlist_node *node)
855 : {
856 : dlist_member_check(&head->dlist, node);
857 : Assert(head->count > 0);
858 :
859 : return dlist_has_prev(&head->dlist, node);
860 : }
861 :
862 : /*
863 : * dclist_next_node
864 : * Return the next node in the list (there must be one).
865 : */
866 : static inline dlist_node *
867 : dclist_next_node(dclist_head *head, dlist_node *node)
868 : {
869 : Assert(head->count > 0);
870 :
871 : return dlist_next_node(&head->dlist, node);
872 : }
873 :
874 : /*
875 : * dclist_prev_node
876 : * Return the prev node in the list (there must be one).
877 : */
878 : static inline dlist_node *
879 : dclist_prev_node(dclist_head *head, dlist_node *node)
880 : {
881 : Assert(head->count > 0);
882 :
883 : return dlist_prev_node(&head->dlist, node);
884 : }
885 :
886 : /* internal support function to get address of head element's struct */
887 : static inline void *
888 : dclist_head_element_off(dclist_head *head, size_t off)
889 : {
890 : Assert(!dclist_is_empty(head));
891 :
892 : return (char *) head->dlist.head.next - off;
893 : }
894 :
895 : /*
896 : * dclist_head_node
897 : * Return the first node in the list (there must be one).
898 : */
899 : static inline dlist_node *
900 : dclist_head_node(dclist_head *head)
901 : {
902 : Assert(head->count > 0);
903 :
904 : return (dlist_node *) dlist_head_element_off(&head->dlist, 0);
905 : }
906 :
907 : /* internal support function to get address of tail element's struct */
908 : static inline void *
909 : dclist_tail_element_off(dclist_head *head, size_t off)
910 : {
911 : Assert(!dclist_is_empty(head));
912 :
913 : return (char *) head->dlist.head.prev - off;
914 : }
915 :
916 : /*
917 : * Return the last node in the list (there must be one).
918 : */
919 : static inline dlist_node *
158 drowley 920 UNC 0 : dclist_tail_node(dclist_head *head)
921 : {
922 0 : Assert(head->count > 0);
923 :
924 0 : return (dlist_node *) dlist_tail_element_off(&head->dlist, 0);
925 : }
926 :
927 : /*
928 : * dclist_count
929 : * Returns the stored number of entries in 'head'
930 : */
931 : static inline uint32
87 peter 932 GNC 713706 : dclist_count(const dclist_head *head)
933 : {
158 drowley 934 713706 : Assert(dlist_is_empty(&head->dlist) == (head->count == 0));
935 :
936 713706 : return head->count;
937 : }
938 :
939 : /*
940 : * Return the containing struct of 'type' where 'membername' is the dlist_node
941 : * pointed at by 'ptr'.
942 : *
943 : * This is used to convert a dlist_node * back to its containing struct.
944 : *
945 : * Note: This is effectively just the same as dlist_container, so reuse that.
946 : */
947 : #define dclist_container(type, membername, ptr) \
948 : dlist_container(type, membername, ptr)
949 :
950 : /*
951 : * Return the address of the first element in the list.
952 : *
953 : * The list must not be empty.
954 : */
955 : #define dclist_head_element(type, membername, lhead) \
956 : (AssertVariableIsOfTypeMacro(((type *) NULL)->membername, dlist_node), \
957 : (type *) dclist_head_element_off(lhead, offsetof(type, membername)))
958 :
959 : /*
960 : * Return the address of the last element in the list.
961 : *
962 : * The list must not be empty.
963 : */
964 : #define dclist_tail_element(type, membername, lhead) \
965 : (AssertVariableIsOfTypeMacro(((type *) NULL)->membername, dlist_node), \
966 : ((type *) dclist_tail_element_off(lhead, offsetof(type, membername))))
967 :
968 :
969 : /* Iterators for dclists */
970 : #define dclist_foreach(iter, lhead) \
971 : dlist_foreach(iter, &((lhead)->dlist))
972 :
973 : #define dclist_foreach_modify(iter, lhead) \
974 : dlist_foreach_modify(iter, &((lhead)->dlist))
975 :
976 : #define dclist_reverse_foreach(iter, lhead) \
977 : dlist_reverse_foreach(iter, &((lhead)->dlist))
3827 alvherre 978 ECB :
979 : /* singly linked list implementation */
980 :
981 : /*
982 : * Initialize a singly linked list.
983 : * Previous state will be thrown away without any cleanup.
984 : */
2804 andres 985 : static inline void
3827 alvherre 986 GIC 77228 : slist_init(slist_head *head)
3827 alvherre 987 ECB : {
3827 alvherre 988 CBC 77228 : head->head.next = NULL;
3827 alvherre 989 GIC 77228 : }
990 :
991 : /*
992 : * Is the list empty?
993 : */
994 : static inline bool
87 peter 995 GNC 31806 : slist_is_empty(const slist_head *head)
996 : {
3827 alvherre 997 ECB : slist_check(head);
998 :
3827 alvherre 999 GIC 31806 : return head->head.next == NULL;
1000 : }
1001 :
1002 : /*
1003 : * Insert a node at the beginning of the list.
1004 : */
1005 : static inline void
1006 1127977 : slist_push_head(slist_head *head, slist_node *node)
1007 : {
1008 1127977 : node->next = head->head.next;
1009 1127977 : head->head.next = node;
1010 :
1011 : slist_check(head);
1012 1127977 : }
1013 :
1014 : /*
1015 : * Insert a node after another *in the same list*
1016 : */
1017 : static inline void
1018 : slist_insert_after(slist_node *after, slist_node *node)
1019 : {
1020 : node->next = after->next;
1021 : after->next = node;
1022 : }
1023 :
1024 : /*
1025 : * Remove and return the first node from a list (there must be one).
1026 : */
1027 : static inline slist_node *
1028 7467 : slist_pop_head_node(slist_head *head)
1029 : {
1030 : slist_node *node;
1031 :
1032 7467 : Assert(!slist_is_empty(head));
1033 7467 : node = head->head.next;
3825 tgl 1034 7467 : head->head.next = node->next;
1035 : slist_check(head);
3827 alvherre 1036 7467 : return node;
1037 : }
1038 :
1039 : /*
1040 : * Check whether 'node' has a following node.
1041 : */
1042 : static inline bool
1043 : slist_has_next(const slist_head *head, const slist_node *node)
1044 : {
1045 : slist_check(head);
1046 :
1047 : return node->next != NULL;
1048 : }
1049 :
1050 : /*
1051 : * Return the next node in the list (there must be one).
1052 : */
1053 : static inline slist_node *
1054 : slist_next_node(slist_head *head, slist_node *node)
1055 : {
1056 : Assert(slist_has_next(head, node));
1057 : return node->next;
1058 : }
1059 :
1060 : /* internal support function to get address of head element's struct */
1061 : static inline void *
1062 : slist_head_element_off(slist_head *head, size_t off)
1063 : {
1064 : Assert(!slist_is_empty(head));
1065 : return (char *) head->head.next - off;
1066 : }
1067 :
1068 : /*
1069 : * Return the first node in the list (there must be one).
1070 : */
1071 : static inline slist_node *
1072 : slist_head_node(slist_head *head)
1073 : {
1074 : return (slist_node *) slist_head_element_off(head, 0);
1075 : }
1076 :
1077 : /*
1078 : * Delete the list element the iterator currently points to.
1079 : *
1080 : * Caution: this modifies iter->cur, so don't use that again in the current
1081 : * loop iteration.
1082 : */
1083 : static inline void
3546 tgl 1084 CBC 154257 : slist_delete_current(slist_mutable_iter *iter)
1085 : {
3546 tgl 1086 ECB : /*
1087 : * Update previous element's forward link. If the iteration is at the
1088 : * first list element, iter->prev will point to the list header's "head"
1089 : * field, so we don't need a special case for that.
1090 : */
3546 tgl 1091 GIC 154257 : iter->prev->next = iter->next;
1092 :
1093 : /*
1094 : * Reset cur to prev, so that prev will continue to point to the prior
3546 tgl 1095 ECB : * valid list element after slist_foreach_modify() advances to the next.
1096 : */
3546 tgl 1097 CBC 154257 : iter->cur = iter->prev;
1098 154257 : }
1099 :
1100 : /*
1101 : * Return the containing struct of 'type' where 'membername' is the slist_node
1102 : * pointed at by 'ptr'.
1103 : *
1104 : * This is used to convert a slist_node * back to its containing struct.
1105 : */
3827 alvherre 1106 ECB : #define slist_container(type, membername, ptr) \
1107 : (AssertVariableIsOfTypeMacro(ptr, slist_node *), \
1108 : AssertVariableIsOfTypeMacro(((type *) NULL)->membername, slist_node), \
3825 tgl 1109 EUB : ((type *) ((char *) (ptr) - offsetof(type, membername))))
1110 :
3827 alvherre 1111 ECB : /*
3825 tgl 1112 : * Return the address of the first element in the list.
1113 : *
1114 : * The list must not be empty.
3827 alvherre 1115 : */
1116 : #define slist_head_element(type, membername, lhead) \
1117 : (AssertVariableIsOfTypeMacro(((type *) NULL)->membername, slist_node), \
1118 : (type *) slist_head_element_off(lhead, offsetof(type, membername)))
1119 :
1120 : /*
1121 : * Iterate through the list pointed at by 'lhead' storing the state in 'iter'.
3825 tgl 1122 : *
1123 : * Access the current element with iter.cur.
3827 alvherre 1124 : *
3546 tgl 1125 : * It's allowed to modify the list while iterating, with the exception of
1126 : * deleting the iterator's current node; deletion of that node requires
3260 bruce 1127 : * care if the iteration is to be continued afterward. (Doing so and also
3546 tgl 1128 : * deleting or inserting adjacent list elements might misbehave; also, if
1129 : * the user frees the current node's storage, continuing the iteration is
1130 : * not safe.)
3827 alvherre 1131 : */
1132 : #define slist_foreach(iter, lhead) \
1133 : for (AssertVariableIsOfTypeMacro(iter, slist_iter), \
1134 : AssertVariableIsOfTypeMacro(lhead, slist_head *), \
1135 : (iter).cur = (lhead)->head.next; \
1136 : (iter).cur != NULL; \
1137 : (iter).cur = (iter).cur->next)
1138 :
1139 : /*
1140 : * Iterate through the list pointed at by 'lhead' storing the state in 'iter'.
1141 : *
1142 : * Access the current element with iter.cur.
1143 : *
1144 : * The only list modification allowed while iterating is to remove the current
1145 : * node via slist_delete_current() (*not* slist_delete()). Insertion or
1146 : * deletion of nodes adjacent to the current node would misbehave.
1147 : */
1148 : #define slist_foreach_modify(iter, lhead) \
1149 : for (AssertVariableIsOfTypeMacro(iter, slist_mutable_iter), \
1150 : AssertVariableIsOfTypeMacro(lhead, slist_head *), \
1151 : (iter).prev = &(lhead)->head, \
1152 : (iter).cur = (iter).prev->next, \
1153 : (iter).next = (iter).cur ? (iter).cur->next : NULL; \
1154 : (iter).cur != NULL; \
1155 : (iter).prev = (iter).cur, \
1156 : (iter).cur = (iter).next, \
1157 : (iter).next = (iter).next ? (iter).next->next : NULL)
3827 alvherre 1158 EUB :
1159 : #endif /* ILIST_H */
|
