8 The term *list* is used generically for lists, skiplists, trees and hash
9 tables in this document.
14 FRR includes a set of list-like data structure implementations with abstracted
15 common APIs. The purpose of this is easily allow swapping out one
16 data structure for another while also making the code easier to read and write.
17 There is one API for unsorted lists and a similar but not identical API for
18 sorted lists - and heaps use a middle ground of both.
20 For unsorted lists, the following implementations exist:
22 - single-linked list with tail pointer (e.g. STAILQ in BSD)
26 - atomic single-linked list with tail pointer
29 Being partially sorted, the oddball structure:
34 For sorted lists, these data structures are implemented:
38 - atomic single-linked list
42 - red-black tree (based on OpenBSD RB_TREE)
44 - hash table (note below)
46 Except for hash tables, each of the sorted data structures has a variant with
47 unique and non-unique list items. Hash tables always require unique items
48 and mostly follow the "sorted" API but use the hash value as sorting
49 key. Also, iterating while modifying does not work with hash tables.
50 Conversely, the heap always has non-unique items, but iterating while modifying
54 The following sorted structures are likely to be implemented at some point
59 - atomic hash table (note below)
62 The APIs are all designed to be as type-safe as possible. This means that
63 there will be a compiler warning when an item doesn't match the list, or
64 the return value has a different type, or other similar situations. **You
65 should never use casts with these APIs.** If a cast is neccessary in relation
66 to these APIs, there is probably something wrong with the overall design.
68 Only the following pieces use dynamically allocated memory:
70 - the hash table itself is dynamically grown and shrunk
72 - skiplists store up to 4 next pointers inline but will dynamically allocate
73 memory to hold an item's 5th up to 16th next pointer (if they exist)
75 - the heap uses a dynamically grown and shrunk array of items
91 DECLARE_SORTLIST_NONUNIQ
93 DECLARE_ATOMLIST_NONUNIQ
95 DECLARE_SKIPLIST_NONUNIQ
97 DECLARE_RBTREE_NONUNIQ
103 +------------------------------------+------+------+------+---------+------------+
104 | Function | LIST | HEAP | HASH | \*_UNIQ | \*_NONUNIQ |
105 +====================================+======+======+======+=========+============+
106 | _init, _fini | yes | yes | yes | yes | yes |
107 +------------------------------------+------+------+------+---------+------------+
108 | _first, _next, _next_safe | yes | yes | yes | yes | yes |
109 +------------------------------------+------+------+------+---------+------------+
110 | _add_head, _add_tail, _add_after | yes | -- | -- | -- | -- |
111 +------------------------------------+------+------+------+---------+------------+
112 | _add | -- | yes | yes | yes | yes |
113 +------------------------------------+------+------+------+---------+------------+
114 | _del, _pop | yes | yes | yes | yes | yes |
115 +------------------------------------+------+------+------+---------+------------+
116 | _find | -- | -- | yes | yes | -- |
117 +------------------------------------+------+------+------+---------+------------+
118 | _find_lt, _find_gteq | -- | -- | -- | yes | yes |
119 +------------------------------------+------+------+------+---------+------------+
120 | use with frr_each() macros | yes | yes | yes | yes | yes |
121 +------------------------------------+------+------+------+---------+------------+
125 Datastructure type setup
126 ------------------------
128 Each of the data structures has a ``PREDECL_*`` and a ``DECLARE_*`` macro to
129 set up an "instantiation" of the list. This works somewhat similar to C++
130 templating, though much simpler.
132 **In all following text, the Z prefix is replaced with a name choosen
133 for the instance of the datastructure.**
135 The common setup pattern will look like this:
139 #include <typesafe.h>
144 struct Z_item mylistitem;
147 struct Z_head mylisthead;
150 DECLARE_XXX(Z, struct item, mylistitem)
152 /* sorted, items that compare as equal cannot be added to list */
153 int compare_func(const struct item *a, const struct item *b);
154 DECLARE_XXX_UNIQ(Z, struct item, mylistitem, compare_func)
156 /* sorted, items that compare as equal can be added to list */
157 int compare_func(const struct item *a, const struct item *b);
158 DECLARE_XXX_NONUNIQ(Z, struct item, mylistitem, compare_func)
161 int compare_func(const struct item *a, const struct item *b);
162 uint32_t hash_func(const struct item *a);
163 DECLARE_XXX(Z, struct item, mylistitem, compare_func, hash_func)
165 ``XXX`` is replaced with the name of the data structure, e.g. ``SKIPLIST``
166 or ``ATOMLIST``. The ``DECLARE_XXX`` invocation can either occur in a `.h`
167 file (if the list needs to be accessed from several C files) or it can be
168 placed in a `.c` file (if the list is only accessed from that file.) The
169 ``PREDECL_XXX`` invocation defines the ``struct Z_item`` and ``struct
170 Z_head`` types and must therefore occur before these are used.
172 To switch between compatible data structures, only these two lines need to be
173 changes. To switch to a data structure with a different API, some source
174 changes are necessary.
176 Common iteration macros
177 -----------------------
179 The following iteration macros work across all data structures:
181 .. c:function:: frr_each(Z, &head, item)
187 for (item = Z_first(&head); item; item = Z_next(&head, item))
189 Note that this will fail if the list is modified while being iterated
192 .. c:function:: frr_each_safe(Z, &head, item)
194 Same as the previous, but the next element is pre-loaded into a "hidden"
195 variable (named ``Z_safe``.) Equivalent to:
199 for (item = Z_first(&head); item; item = next) {
200 next = Z_next_safe(&head, item);
206 Iterating over hash tables while adding or removing items is not
207 possible. The iteration position will be corrupted when the hash
208 tables is resized while iterating. This will cause items to be
209 skipped or iterated over twice.
211 .. c:function:: frr_each_from(Z, &head, item, from)
213 Iterates over the list, starting at item ``from``. This variant is "safe"
214 as in the previous macro. Equivalent to:
218 for (item = from; item; item = from) {
219 from = Z_next_safe(&head, item);
225 The ``from`` variable is written to. This is intentional - you can
226 resume iteration after breaking out of the loop by keeping the ``from``
227 value persistent and reusing it for the next loop.
232 The following documentation assumes that a list has been defined using
233 ``Z`` as the name, and ``itemtype`` being the type of the list items (e.g.
236 .. c:function:: void Z_init(struct Z_head *)
238 Initializes the list for use. For most implementations, this just sets
239 some values. Hash tables are the only implementation that allocates
242 .. c:function:: void Z_fini(struct Z_head *)
244 Reverse the effects of :c:func:`Z_init()`. The list must be empty
245 when this function is called.
249 This function may ``assert()`` if the list is not empty.
251 .. c:function:: size_t Z_count(struct Z_head *)
253 Returns the number of items in a structure. All structures store a
254 counter in their `Z_head` so that calling this function completes
259 For atomic lists with concurrent access, the value will already be
260 outdated by the time this function returns and can therefore only be
263 .. c:function:: itemtype *Z_first(struct Z_head *)
265 Returns the first item in the structure, or ``NULL`` if the structure is
266 empty. This is O(1) for all data structures except red-black trees
267 where it is O(log n).
269 .. c:function:: itemtype *Z_pop(struct Z_head *)
271 Remove and return the first item in the structure, or ``NULL`` if the
272 structure is empty. Like :c:func:`Z_first`, this is O(1) for all
273 data structures except red-black trees where it is O(log n) again.
275 This function can be used to build queues (with unsorted structures) or
276 priority queues (with sorted structures.)
278 Another common pattern is deleting all list items:
282 while ((item = Z_pop(head)))
287 This function can - and should - be used with hash tables. It is not
288 affected by the "modification while iterating" problem. To remove
289 all items from a hash table, use the loop demonstrated above.
291 .. c:function:: itemtype *Z_next(struct Z_head *, itemtype *prev)
293 Return the item that follows after ``prev``, or ``NULL`` if ``prev`` is
298 ``prev`` must not be ``NULL``! Use :c:func:`Z_next_safe()` if
299 ``prev`` might be ``NULL``.
301 .. c:function:: itemtype *Z_next_safe(struct Z_head *, itemtype *prev)
303 Same as :c:func:`Z_next()`, except that ``NULL`` is returned if
304 ``prev`` is ``NULL``.
306 .. c:function:: itemtype *Z_del(struct Z_head *, itemtype *item)
308 Remove ``item`` from the list and return it.
312 This function's behaviour is undefined if ``item`` is not actually
313 on the list. Some structures return ``NULL`` in this case while others
314 return ``item``. The function may also call ``assert()`` (but most
319 ``Z_del_after()`` / ``Z_del_hint()``?
321 API for unsorted structures
322 ---------------------------
324 Since the insertion position is not pre-defined for unsorted data, there
325 are several functions exposed to insert data:
329 ``item`` must not be ``NULL`` for any of the following functions.
331 .. c:function:: DECLARE_XXX(Z, type, field)
333 :param listtype XXX: ``LIST``, ``DLIST`` or ``ATOMLIST`` to select a data
334 structure implementation.
335 :param token Z: Gives the name prefix that is used for the functions
336 created for this instantiation. ``DECLARE_XXX(foo, ...)``
337 gives ``struct foo_item``, ``foo_add_head()``, ``foo_count()``, etc. Note
338 that this must match the value given in ``PREDECL_XXX(foo)``.
339 :param typename type: Specifies the data type of the list items, e.g.
340 ``struct item``. Note that ``struct`` must be added here, it is not
342 :param token field: References a struct member of ``type`` that must be
343 typed as ``struct foo_item``. This struct member is used to
344 store "next" pointers or other data structure specific data.
346 .. c:function:: void Z_add_head(struct Z_head *, itemtype *item)
348 Insert an item at the beginning of the structure, before the first item.
349 This is an O(1) operation for non-atomic lists.
351 .. c:function:: void Z_add_tail(struct Z_head *, itemtype *item)
353 Insert an item at the end of the structure, after the last item.
354 This is also an O(1) operation for non-atomic lists.
356 .. c:function:: void Z_add_after(struct Z_head *, itemtype *after, itemtype *item)
358 Insert ``item`` behind ``after``. If ``after`` is ``NULL``, the item is
359 inserted at the beginning of the list as with :c:func:`Z_add_head`.
360 This is also an O(1) operation for non-atomic lists.
362 A common pattern is to keep a "previous" pointer around while iterating:
366 itemtype *prev = NULL, *item;
368 frr_each_safe(Z, head, item) {
370 Z_add_after(head, prev, item);
378 maybe flip the order of ``item`` & ``after``?
379 ``Z_add_after(head, item, after)``
381 API for sorted structures
382 -------------------------
384 Sorted data structures do not need to have an insertion position specified,
385 therefore the insertion calls are different from unsorted lists. Also,
386 sorted lists can be searched for a value.
388 .. c:function:: DECLARE_XXX_UNIQ(Z, type, field, compare_func)
390 :param listtype XXX: One of the following:
391 ``SORTLIST`` (single-linked sorted list), ``SKIPLIST`` (skiplist),
392 ``RBTREE`` (RB-tree) or ``ATOMSORT`` (atomic single-linked list).
393 :param token Z: Gives the name prefix that is used for the functions
394 created for this instantiation. ``DECLARE_XXX(foo, ...)``
395 gives ``struct foo_item``, ``foo_add()``, ``foo_count()``, etc. Note
396 that this must match the value given in ``PREDECL_XXX(foo)``.
397 :param typename type: Specifies the data type of the list items, e.g.
398 ``struct item``. Note that ``struct`` must be added here, it is not
400 :param token field: References a struct member of ``type`` that must be
401 typed as ``struct foo_item``. This struct member is used to
402 store "next" pointers or other data structure specific data.
403 :param funcptr compare_func: Item comparison function, must have the
404 following function signature:
405 ``int function(const itemtype *, const itemtype*)``. This function
406 may be static if the list is only used in one file.
408 .. c:function:: DECLARE_XXX_NONUNIQ(Z, type, field, compare_func)
410 Same as above, but allow adding multiple items to the list that compare
411 as equal in ``compare_func``. Ordering between these items is undefined
412 and depends on the list implementation.
414 .. c:function:: itemtype *Z_add(struct Z_head *, itemtype *item)
416 Insert an item at the appropriate sorted position. If another item exists
417 in the list that compares as equal (``compare_func()`` == 0), ``item`` is
418 not inserted into the list and the already-existing item in the list is
419 returned. Otherwise, on successful insertion, ``NULL`` is returned.
421 For ``_NONUNIQ`` lists, this function always returns NULL since ``item``
422 can always be successfully added to the list.
424 .. c:function:: itemtype *Z_find(struct Z_head *, const itemtype *ref)
426 Search the list for an item that compares equal to ``ref``. If no equal
427 item is found, return ``NULL``.
429 This function is likely used with a temporary stack-allocated value for
434 itemtype searchfor = { .foo = 123 };
436 itemtype *item = Z_find(head, &searchfor);
440 The ``Z_find()`` function is only available for lists that contain
441 unique items (i.e. ``DECLARE_XXX_UNIQ``.) This is because on a list
442 containing non-unique items, more than one item may compare as equal to
443 the item that is searched for.
445 .. c:function:: itemtype *Z_find_gteq(struct Z_head *, const itemtype *ref)
447 Search the list for an item that compares greater or equal to
448 ``ref``. See :c:func:`Z_find()` above.
450 .. c:function:: itemtype *Z_find_lt(struct Z_head *, const itemtype *ref)
452 Search the list for an item that compares less than
453 ``ref``. See :c:func:`Z_find()` above.
459 .. c:function:: DECLARE_XXX(Z, type, field, compare_func, hash_func)
461 :param listtype XXX: Only ``HASH`` is currently available.
462 :param token Z: Gives the name prefix that is used for the functions
463 created for this instantiation. ``DECLARE_XXX(foo, ...)``
464 gives ``struct foo_item``, ``foo_add()``, ``foo_count()``, etc. Note
465 that this must match the value given in ``PREDECL_XXX(foo)``.
466 :param typename type: Specifies the data type of the list items, e.g.
467 ``struct item``. Note that ``struct`` must be added here, it is not
469 :param token field: References a struct member of ``type`` that must be
470 typed as ``struct foo_item``. This struct member is used to
471 store "next" pointers or other data structure specific data.
472 :param funcptr compare_func: Item comparison function, must have the
473 following function signature:
474 ``int function(const itemtype *, const itemtype*)``. This function
475 may be static if the list is only used in one file. For hash tables,
476 this function is only used to check for equality, the ordering is
478 :param funcptr hash_func: Hash calculation function, must have the
479 following function signature:
480 ``uint32_t function(const itemtype *)``. The hash value for items
481 stored in a hash table is cached in each item, so this value need not
482 be cached by the user code.
486 Items that compare as equal cannot be inserted. Refer to the notes
487 about sorted structures in the previous section.
489 .. c:function:: void Z_init_size(struct Z_head *, size_t size)
491 Same as :c:func:`Z_init()` but preset the minimum hash table to
494 Hash tables also support :c:func:`Z_add()` and :c:func:`Z_find()` with
495 the same semantics as noted above. :c:func:`Z_find_gteq()` and
496 :c:func:`Z_find_lt()` are **not** provided for hash tables.
502 Heaps provide the same API as the sorted data structures, except:
504 * none of the find functions (:c:func:`Z_find()`, :c:func:`Z_find_gteq()`
505 or :c:func:`Z_find_lt()`) are available.
506 * iterating over the heap yields the items in semi-random order, only the
507 first item is guaranteed to be in order and actually the "lowest" item
508 on the heap. Being a heap, only the rebalancing performed on removing the
509 first item (either through :c:func:`Z_pop()` or :c:func:`Z_del()`) causes
510 the new lowest item to bubble up to the front.
511 * all heap modifications are O(log n). However, cacheline efficiency and
512 latency is likely quite a bit better than with other data structures.
517 `atomlist.h` provides an unsorted and a sorted atomic single-linked list.
518 Since atomic memory accesses can be considerably slower than plain memory
519 accessses (depending on the CPU type), these lists should only be used where
522 The following guarantees are provided regarding concurrent access:
524 - the operations are lock-free but not wait-free.
526 Lock-free means that it is impossible for all threads to be blocked. Some
527 thread will always make progress, regardless of what other threads do. (This
528 even includes a random thread being stopped by a debugger in a random
531 Wait-free implies that the time any single thread might spend in one of the
532 calls is bounded. This is not provided here since it is not normally
533 relevant to practical operations. What this means is that if some thread is
534 hammering a particular list with requests, it is possible that another
535 thread is blocked for an extended time. The lock-free guarantee still
536 applies since the hammering thread is making progress.
538 - without a RCU mechanism in place, the point of contention for atomic lists
539 is memory deallocation. As it is, **a rwlock is required for correct
540 operation**. The *read* lock must be held for all accesses, including
541 reading the list, adding items to the list, and removing items from the
542 list. The *write* lock must be acquired and released before deallocating
543 any list element. If this is not followed, an use-after-free can occur
544 as a MT race condition when an element gets deallocated while another
545 thread is accessing the list.
549 The *write* lock does not need to be held for deleting items from the
550 list, and there should not be any instructions between the
551 ``pthread_rwlock_wrlock`` and ``pthread_rwlock_unlock``. The write lock
552 is used as a sequence point, not as an exclusion mechanism.
554 - insertion operations are always safe to do with the read lock held.
555 Added items are immediately visible after the insertion call returns and
556 should not be touched anymore.
558 - when removing a *particular* (pre-determined) item, the caller must ensure
559 that no other thread is attempting to remove that same item. If this cannot
560 be guaranteed by architecture, a separate lock might need to be added.
562 - concurrent `pop` calls are always safe to do with only the read lock held.
563 This does not fall under the previous rule since the `pop` call will select
564 the next item if the first is already being removed by another thread.
566 **Deallocation locking still applies.** Assume another thread starts
567 reading the list, but gets task-switched by the kernel while reading the
568 first item. `pop` will happily remove and return that item. If it is
569 deallocated without acquiring and releasing the write lock, the other thread
570 will later resume execution and try to access the now-deleted element.
572 - the list count should be considered an estimate. Since there might be
573 concurrent insertions or removals in progress, it might already be outdated
574 by the time the call returns. No attempt is made to have it be correct even
577 Overall, atomic lists are well-suited for MT queues; concurrent insertion,
578 iteration and removal operations will work with the read lock held.
589 pthread_rwlock_rdlock(&itemhead_rwlock);
590 frr_each(itemlist, &itemhead, i) {
591 /* lock must remain held while iterating */
594 pthread_rwlock_unlock(&itemhead_rwlock);
596 Head removal (pop) and deallocation:
602 pthread_rwlock_rdlock(&itemhead_rwlock);
603 i = itemlist_pop(&itemhead);
604 pthread_rwlock_unlock(&itemhead_rwlock);
606 /* i might still be visible for another thread doing an
607 * frr_each() (but won't be returned by another pop()) */
610 pthread_rwlock_wrlock(&itemhead_rwlock);
611 pthread_rwlock_unlock(&itemhead_rwlock);
612 /* i now guaranteed to be gone from the list.
613 * note nothing between wrlock() and unlock() */
614 XFREE(MTYPE_ITEM, i);
619 Why is the list head not ``const`` in the list APIs?
620 The semantics that a ``const`` list head would imply are not obvious. It
621 could mean any of the following:
623 * the list just shouldn't be allocated/deallocated, but may be modified.
624 This doesn't actually work since the list head needs to be modified for
625 inserting or deleting items.
627 * the list shouldn't be modified, but items can. This may make sense for
628 iterating, but it's not exactly consistent - an item might be on more
629 than one list, does it apply to all of them? If not, which one?
631 * neither the list nor the items should be modified. This is consistent,
632 but hard to do without creating a ``const`` copy of every single list
633 function. Ease of use trumps this.
635 Why is there no "is this item on a/the list" test?
636 It's slow for several of the data structures, and the work of adding it
637 just hasn't been done. It can certainly be added if it's needed.
639 Why is it ``PREDECL`` + ``DECLARE`` instead of ``DECLARE`` + ``DEFINE``?
640 The rule is that a ``DEFINE`` must be in a ``.c`` file, and linked exactly
641 once because it defines some kind of global symbol. This is not the case
642 for the data structure macros; they only define ``static`` symbols and it
643 is perfectly fine to include both ``PREDECL`` and ``DECLARE`` in a header
644 file. It is also perfectly fine to have the same ``DECLARE`` statement in
645 2 ``.c`` files, but only **if the macro arguments are identical.** Maybe
646 don't do that unless you really need it.
660 refer to external docs