Branch data 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-2026, 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
314 : 720373 : dlist_init(dlist_head *head)
315 : : {
316 : 720373 : head->head.next = head->head.prev = &head->head;
317 : 720373 : }
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
325 : 1630 : dlist_node_init(dlist_node *node)
326 : : {
327 : 1630 : node->next = node->prev = NULL;
328 : 1630 : }
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
336 : 5179032 : dlist_is_empty(const dlist_head *head)
337 : : {
338 : 5179032 : dlist_check(head);
339 : :
340 [ - + ]: 5179032 : 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
347 : 716922 : dlist_push_head(dlist_head *head, dlist_node *node)
348 : : {
349 [ + + ]: 716922 : if (head->head.next == NULL) /* convert NULL header to circular */
350 : 175251 : dlist_init(head);
351 : :
352 : 716922 : node->next = head->head.next;
353 : 716922 : node->prev = &head->head;
354 : 716922 : node->next->prev = node;
355 : 716922 : head->head.next = node;
356 : :
357 : 716922 : dlist_check(head);
358 : 716922 : }
359 : :
360 : : /*
361 : : * Insert a node at the end of the list.
362 : : */
363 : : static inline void
364 : 872247 : dlist_push_tail(dlist_head *head, dlist_node *node)
365 : : {
366 [ + - ]: 872247 : if (head->head.next == NULL) /* convert NULL header to circular */
367 : 0 : dlist_init(head);
368 : :
369 : 872247 : node->next = &head->head;
370 : 872247 : node->prev = head->head.prev;
371 : 872247 : node->prev->next = node;
372 : 872247 : head->head.prev = node;
373 : :
374 : 872247 : dlist_check(head);
375 : 872247 : }
376 : :
377 : : /*
378 : : * Insert a node after another *in the same list*
379 : : */
380 : : static inline void
381 : 212 : dlist_insert_after(dlist_node *after, dlist_node *node)
382 : : {
383 : 212 : node->prev = after;
384 : 212 : node->next = after->next;
385 : 212 : after->next = node;
386 : 212 : node->next->prev = node;
387 : 212 : }
388 : :
389 : : /*
390 : : * Insert a node before another *in the same list*
391 : : */
392 : : static inline void
393 : 0 : dlist_insert_before(dlist_node *before, dlist_node *node)
394 : : {
395 : 0 : node->prev = before->prev;
396 : 0 : node->next = before;
397 : 0 : before->prev = node;
398 : 0 : node->prev->next = node;
399 : 0 : }
400 : :
401 : : /*
402 : : * Delete 'node' from its list (it must be in one).
403 : : */
404 : : static inline void
405 : 1152094 : dlist_delete(dlist_node *node)
406 : : {
407 : 1152094 : node->prev->next = node->next;
408 : 1152094 : node->next->prev = node->prev;
409 : 1152094 : }
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
416 : 50 : dlist_delete_thoroughly(dlist_node *node)
417 : : {
418 : 50 : node->prev->next = node->next;
419 : 50 : node->next->prev = node->prev;
420 : 50 : node->next = NULL;
421 : 50 : node->prev = NULL;
422 : 50 : }
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
429 : 35452 : dlist_delete_from(dlist_head *head, dlist_node *node)
430 : : {
431 : 35452 : dlist_member_check(head, node);
432 : 35452 : dlist_delete(node);
433 : 35452 : }
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
440 : 43 : dlist_delete_from_thoroughly(dlist_head *head, dlist_node *node)
441 : : {
442 : 43 : dlist_member_check(head, node);
443 : 43 : dlist_delete_thoroughly(node);
444 : 43 : }
445 : :
446 : : /*
447 : : * Remove and return the first node from a list (there must be one).
448 : : */
449 : : static inline dlist_node *
450 : 8694 : dlist_pop_head_node(dlist_head *head)
451 : : {
452 : 8694 : dlist_node *node;
453 : :
454 [ + - ]: 8694 : Assert(!dlist_is_empty(head));
455 : 8694 : node = head->head.next;
456 : 8694 : dlist_delete(node);
457 : 17388 : return node;
458 : 8694 : }
459 : :
460 : : /*
461 : : * Move element from its current position in the list to the head position in
462 : : * the same list.
463 : : *
464 : : * Undefined behaviour if 'node' is not already part of the list.
465 : : */
466 : : static inline void
467 : 10555694 : dlist_move_head(dlist_head *head, dlist_node *node)
468 : : {
469 : : /* fast path if it's already at the head */
470 [ + + ]: 10555694 : if (head->head.next == node)
471 : 10273438 : return;
472 : :
473 : 282256 : dlist_delete(node);
474 : 282256 : dlist_push_head(head, node);
475 : :
476 : 282256 : dlist_check(head);
477 : 10555694 : }
478 : :
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
486 : 105340 : dlist_move_tail(dlist_head *head, dlist_node *node)
487 : : {
488 : : /* fast path if it's already at the tail */
489 [ + + ]: 105340 : if (head->head.prev == node)
490 : 59326 : return;
491 : :
492 : 46014 : dlist_delete(node);
493 : 46014 : dlist_push_tail(head, node);
494 : :
495 : 46014 : dlist_check(head);
496 : 105340 : }
497 : :
498 : : /*
499 : : * Check whether 'node' has a following node.
500 : : * Caution: unreliable if 'node' is not in the list.
501 : : */
502 : : static inline bool
503 : 378629 : dlist_has_next(const dlist_head *head, const dlist_node *node)
504 : : {
505 : 378629 : 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.
511 : : */
512 : : static inline bool
513 : 77 : dlist_has_prev(const dlist_head *head, const dlist_node *node)
514 : : {
515 : 77 : 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_node_init(), or deleted with
521 : : * dlist_delete_thoroughly() / dlist_delete_from_thoroughly() /
522 : : * dclist_delete_from_thoroughly().
523 : : */
524 : : static inline bool
525 : 1647 : dlist_node_is_detached(const dlist_node *node)
526 : : {
527 [ + + - + : 1647 : Assert((node->next == NULL && node->prev == NULL) ||
+ - ]
528 : : (node->next != NULL && node->prev != NULL));
529 : :
530 : 1647 : 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 *
537 : 159922 : dlist_next_node(dlist_head *head, dlist_node *node)
538 : : {
539 [ + - ]: 159922 : Assert(dlist_has_next(head, node));
540 : 159922 : return node->next;
541 : : }
542 : :
543 : : /*
544 : : * Return previous node in the list (there must be one).
545 : : */
546 : : static inline dlist_node *
547 : 39 : dlist_prev_node(dlist_head *head, dlist_node *node)
548 : : {
549 [ + - ]: 39 : Assert(dlist_has_prev(head, node));
550 : 39 : return node->prev;
551 : : }
552 : :
553 : : /* internal support function to get address of head element's struct */
554 : : static inline void *
555 : 2620367 : dlist_head_element_off(dlist_head *head, size_t off)
556 : : {
557 [ + - ]: 2620367 : Assert(!dlist_is_empty(head));
558 : 2620367 : return (char *) head->head.next - off;
559 : : }
560 : :
561 : : /*
562 : : * Return the first node in the list (there must be one).
563 : : */
564 : : static inline dlist_node *
565 : 2619085 : dlist_head_node(dlist_head *head)
566 : : {
567 : 2619085 : return (dlist_node *) dlist_head_element_off(head, 0);
568 : : }
569 : :
570 : : /* internal support function to get address of tail element's struct */
571 : : static inline void *
572 : 3355 : dlist_tail_element_off(dlist_head *head, size_t off)
573 : : {
574 [ + - ]: 3355 : Assert(!dlist_is_empty(head));
575 : 3355 : 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 : 3352 : dlist_tail_node(dlist_head *head)
583 : : {
584 : 3352 : return (dlist_node *) dlist_tail_element_off(head, 0);
585 : : }
586 : :
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 : : */
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.
622 : : */
623 : : #define dlist_foreach(iter, lhead) \
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 : : *
634 : : * Access the current element with iter.cur.
635 : : *
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 : : *
652 : : * It is *not* allowed to manipulate the list during iteration.
653 : : */
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
671 : 305328 : dclist_init(dclist_head *head)
672 : : {
673 : 305328 : dlist_init(&head->dlist);
674 : 305328 : head->count = 0;
675 : 305328 : }
676 : :
677 : : /*
678 : : * dclist_is_empty
679 : : * Returns true if the list is empty, otherwise false.
680 : : */
681 : : static inline bool
682 : 7920 : dclist_is_empty(const dclist_head *head)
683 : : {
684 [ + - ]: 7920 : Assert(dlist_is_empty(&head->dlist) == (head->count == 0));
685 : 7920 : 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 : 7193 : dclist_push_head(dclist_head *head, dlist_node *node)
694 : : {
695 [ + - ]: 7193 : if (head->dlist.head.next == NULL) /* convert NULL header to circular */
696 : 0 : dclist_init(head);
697 : :
698 : 7193 : dlist_push_head(&head->dlist, node);
699 : 7193 : head->count++;
700 : :
701 [ + - ]: 7193 : Assert(head->count > 0); /* count overflow check */
702 : 7193 : }
703 : :
704 : : /*
705 : : * dclist_push_tail
706 : : * Insert a node at the end of the list.
707 : : */
708 : : static inline void
709 : 84300 : dclist_push_tail(dclist_head *head, dlist_node *node)
710 : : {
711 [ + + ]: 84300 : if (head->dlist.head.next == NULL) /* convert NULL header to circular */
712 : 24 : dclist_init(head);
713 : :
714 : 84300 : dlist_push_tail(&head->dlist, node);
715 : 84300 : head->count++;
716 : :
717 [ + - ]: 84300 : Assert(head->count > 0); /* count overflow check */
718 : 84300 : }
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
745 : 0 : dclist_insert_before(dclist_head *head, dlist_node *before, dlist_node *node)
746 : : {
747 : 0 : 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
763 : 28358 : dclist_delete_from(dclist_head *head, dlist_node *node)
764 : : {
765 [ + - ]: 28358 : Assert(head->count > 0);
766 : :
767 : 28358 : dlist_delete_from(&head->dlist, node);
768 : 28358 : head->count--;
769 : 28358 : }
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
776 : 43 : dclist_delete_from_thoroughly(dclist_head *head, dlist_node *node)
777 : : {
778 [ + - ]: 43 : Assert(head->count > 0);
779 : :
780 : 43 : dlist_delete_from_thoroughly(&head->dlist, node);
781 : 43 : head->count--;
782 : 43 : }
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 *
789 : 7057 : dclist_pop_head_node(dclist_head *head)
790 : : {
791 : 7057 : dlist_node *node;
792 : :
793 [ + - ]: 7057 : Assert(head->count > 0);
794 : :
795 : 7057 : node = dlist_pop_head_node(&head->dlist);
796 : 7057 : head->count--;
797 : 14114 : return node;
798 : 7057 : }
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 : 11 : dclist_move_head(dclist_head *head, dlist_node *node)
809 : : {
810 : 11 : dlist_member_check(&head->dlist, node);
811 [ + - ]: 11 : Assert(head->count > 0);
812 : :
813 : 11 : dlist_move_head(&head->dlist, node);
814 : 11 : }
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 : 0 : dclist_head_element_off(dclist_head *head, size_t off)
889 : : {
890 [ # # ]: 0 : Assert(!dclist_is_empty(head));
891 : :
892 : 0 : 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 *
920 : 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
932 : 69417 : dclist_count(const dclist_head *head)
933 : : {
934 [ + - ]: 69417 : Assert(dlist_is_empty(&head->dlist) == (head->count == 0));
935 : :
936 : 69417 : 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))
978 : :
979 : : /* singly linked list implementation */
980 : :
981 : : /*
982 : : * Initialize a singly linked list.
983 : : * Previous state will be thrown away without any cleanup.
984 : : */
985 : : static inline void
986 : 416444 : slist_init(slist_head *head)
987 : : {
988 : 416444 : head->head.next = NULL;
989 : 416444 : }
990 : :
991 : : /*
992 : : * Is the list empty?
993 : : */
994 : : static inline bool
995 : 10219 : slist_is_empty(const slist_head *head)
996 : : {
997 : 10219 : slist_check(head);
998 : :
999 : 10219 : return head->head.next == NULL;
1000 : : }
1001 : :
1002 : : /*
1003 : : * Insert a node at the beginning of the list.
1004 : : */
1005 : : static inline void
1006 : 516767 : slist_push_head(slist_head *head, slist_node *node)
1007 : : {
1008 : 516767 : node->next = head->head.next;
1009 : 516767 : head->head.next = node;
1010 : :
1011 : 516767 : slist_check(head);
1012 : 516767 : }
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 : 3220 : slist_pop_head_node(slist_head *head)
1029 : : {
1030 : 3220 : slist_node *node;
1031 : :
1032 [ + - ]: 3220 : Assert(!slist_is_empty(head));
1033 : 3220 : node = head->head.next;
1034 : 3220 : head->head.next = node->next;
1035 : 3220 : slist_check(head);
1036 : 6440 : return node;
1037 : 3220 : }
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
1084 : 40109 : slist_delete_current(slist_mutable_iter *iter)
1085 : : {
1086 : : /*
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 : : */
1091 : 40109 : iter->prev->next = iter->next;
1092 : :
1093 : : /*
1094 : : * Reset cur to prev, so that prev will continue to point to the prior
1095 : : * valid list element after slist_foreach_modify() advances to the next.
1096 : : */
1097 : 40109 : iter->cur = iter->prev;
1098 : 40109 : }
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 : : */
1106 : : #define slist_container(type, membername, ptr) \
1107 : : (AssertVariableIsOfTypeMacro(ptr, slist_node *), \
1108 : : AssertVariableIsOfTypeMacro(((type *) NULL)->membername, slist_node), \
1109 : : ((type *) ((char *) (ptr) - offsetof(type, membername))))
1110 : :
1111 : : /*
1112 : : * Return the address of the first element in the list.
1113 : : *
1114 : : * The list must not be empty.
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'.
1122 : : *
1123 : : * Access the current element with iter.cur.
1124 : : *
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
1127 : : * care if the iteration is to be continued afterward. (Doing so and also
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.)
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)
1158 : :
1159 : : #endif /* ILIST_H */
|
