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 | _const_first, _const_next | | | | | |
110 +------------------------------------+------+------+------+---------+------------+
111 | _add_head, _add_tail, _add_after | yes | -- | -- | -- | -- |
112 +------------------------------------+------+------+------+---------+------------+
113 | _add | -- | yes | yes | yes | yes |
114 +------------------------------------+------+------+------+---------+------------+
115 | _del, _pop | yes | yes | yes | yes | yes |
116 +------------------------------------+------+------+------+---------+------------+
117 | _find, _const_find | -- | -- | yes | yes | -- |
118 +------------------------------------+------+------+------+---------+------------+
119 | _find_lt, _find_gteq, | -- | -- | -- | yes | yes |
120 | _const_find_lt, _const_find_gteq | | | | | |
121 +------------------------------------+------+------+------+---------+------------+
122 | use with frr_each() macros | yes | yes | yes | yes | yes |
123 +------------------------------------+------+------+------+---------+------------+
127 Datastructure type setup
128 ------------------------
130 Each of the data structures has a ``PREDECL_*`` and a ``DECLARE_*`` macro to
131 set up an "instantiation" of the list. This works somewhat similar to C++
132 templating, though much simpler.
134 **In all following text, the Z prefix is replaced with a name choosen
135 for the instance of the datastructure.**
137 The common setup pattern will look like this:
141 #include <typesafe.h>
146 struct Z_item mylistitem;
149 struct Z_head mylisthead;
152 DECLARE_XXX(Z, struct item, mylistitem)
154 /* sorted, items that compare as equal cannot be added to list */
155 int compare_func(const struct item *a, const struct item *b);
156 DECLARE_XXX_UNIQ(Z, struct item, mylistitem, compare_func)
158 /* sorted, items that compare as equal can be added to list */
159 int compare_func(const struct item *a, const struct item *b);
160 DECLARE_XXX_NONUNIQ(Z, struct item, mylistitem, compare_func)
163 int compare_func(const struct item *a, const struct item *b);
164 uint32_t hash_func(const struct item *a);
165 DECLARE_XXX(Z, struct item, mylistitem, compare_func, hash_func)
167 ``XXX`` is replaced with the name of the data structure, e.g. ``SKIPLIST``
168 or ``ATOMLIST``. The ``DECLARE_XXX`` invocation can either occur in a `.h`
169 file (if the list needs to be accessed from several C files) or it can be
170 placed in a `.c` file (if the list is only accessed from that file.) The
171 ``PREDECL_XXX`` invocation defines the ``struct Z_item`` and ``struct
172 Z_head`` types and must therefore occur before these are used.
174 To switch between compatible data structures, only these two lines need to be
175 changes. To switch to a data structure with a different API, some source
176 changes are necessary.
178 Common iteration macros
179 -----------------------
181 The following iteration macros work across all data structures:
183 .. c:function:: frr_each(Z, &head, item)
189 for (item = Z_first(&head); item; item = Z_next(&head, item))
191 Note that this will fail if the list is modified while being iterated
194 .. c:function:: frr_each_safe(Z, &head, item)
196 Same as the previous, but the next element is pre-loaded into a "hidden"
197 variable (named ``Z_safe``.) Equivalent to:
201 for (item = Z_first(&head); item; item = next) {
202 next = Z_next_safe(&head, item);
208 Iterating over hash tables while adding or removing items is not
209 possible. The iteration position will be corrupted when the hash
210 tables is resized while iterating. This will cause items to be
211 skipped or iterated over twice.
213 .. c:function:: frr_each_from(Z, &head, item, from)
215 Iterates over the list, starting at item ``from``. This variant is "safe"
216 as in the previous macro. Equivalent to:
220 for (item = from; item; item = from) {
221 from = Z_next_safe(&head, item);
227 The ``from`` variable is written to. This is intentional - you can
228 resume iteration after breaking out of the loop by keeping the ``from``
229 value persistent and reusing it for the next loop.
231 To iterate over ``const`` pointers, add ``_const`` to the name of the
232 datastructure (``Z`` above), e.g. ``frr_each (mylist, head, item)`` becomes
233 ``frr_each (mylist_const, head, item)``.
238 The following documentation assumes that a list has been defined using
239 ``Z`` as the name, and ``itemtype`` being the type of the list items (e.g.
242 .. c:function:: void Z_init(struct Z_head *)
244 Initializes the list for use. For most implementations, this just sets
245 some values. Hash tables are the only implementation that allocates
248 .. c:function:: void Z_fini(struct Z_head *)
250 Reverse the effects of :c:func:`Z_init()`. The list must be empty
251 when this function is called.
255 This function may ``assert()`` if the list is not empty.
257 .. c:function:: size_t Z_count(const struct Z_head *)
259 Returns the number of items in a structure. All structures store a
260 counter in their `Z_head` so that calling this function completes
265 For atomic lists with concurrent access, the value will already be
266 outdated by the time this function returns and can therefore only be
269 .. c:function:: const itemtype *Z_const_first(const struct Z_head *)
270 .. c:function:: itemtype *Z_first(struct Z_head *)
272 Returns the first item in the structure, or ``NULL`` if the structure is
273 empty. This is O(1) for all data structures except red-black trees
274 where it is O(log n).
276 .. c:function:: itemtype *Z_pop(struct Z_head *)
278 Remove and return the first item in the structure, or ``NULL`` if the
279 structure is empty. Like :c:func:`Z_first`, this is O(1) for all
280 data structures except red-black trees where it is O(log n) again.
282 This function can be used to build queues (with unsorted structures) or
283 priority queues (with sorted structures.)
285 Another common pattern is deleting all list items:
289 while ((item = Z_pop(head)))
294 This function can - and should - be used with hash tables. It is not
295 affected by the "modification while iterating" problem. To remove
296 all items from a hash table, use the loop demonstrated above.
298 .. c:function:: const itemtype *Z_next(const struct Z_head *, const itemtype *prev)
299 .. c:function:: itemtype *Z_next(struct Z_head *, itemtype *prev)
301 Return the item that follows after ``prev``, or ``NULL`` if ``prev`` is
306 ``prev`` must not be ``NULL``! Use :c:func:`Z_next_safe()` if
307 ``prev`` might be ``NULL``.
309 .. c:function:: itemtype *Z_next_safe(struct Z_head *, itemtype *prev)
311 Same as :c:func:`Z_next()`, except that ``NULL`` is returned if
312 ``prev`` is ``NULL``.
314 .. c:function:: itemtype *Z_del(struct Z_head *, itemtype *item)
316 Remove ``item`` from the list and return it.
320 This function's behaviour is undefined if ``item`` is not actually
321 on the list. Some structures return ``NULL`` in this case while others
322 return ``item``. The function may also call ``assert()`` (but most
327 ``Z_del_after()`` / ``Z_del_hint()``?
329 API for unsorted structures
330 ---------------------------
332 Since the insertion position is not pre-defined for unsorted data, there
333 are several functions exposed to insert data:
337 ``item`` must not be ``NULL`` for any of the following functions.
339 .. c:function:: DECLARE_XXX(Z, type, field)
341 :param listtype XXX: ``LIST``, ``DLIST`` or ``ATOMLIST`` to select a data
342 structure implementation.
343 :param token Z: Gives the name prefix that is used for the functions
344 created for this instantiation. ``DECLARE_XXX(foo, ...)``
345 gives ``struct foo_item``, ``foo_add_head()``, ``foo_count()``, etc. Note
346 that this must match the value given in ``PREDECL_XXX(foo)``.
347 :param typename type: Specifies the data type of the list items, e.g.
348 ``struct item``. Note that ``struct`` must be added here, it is not
350 :param token field: References a struct member of ``type`` that must be
351 typed as ``struct foo_item``. This struct member is used to
352 store "next" pointers or other data structure specific data.
354 .. c:function:: void Z_add_head(struct Z_head *, itemtype *item)
356 Insert an item at the beginning of the structure, before the first item.
357 This is an O(1) operation for non-atomic lists.
359 .. c:function:: void Z_add_tail(struct Z_head *, itemtype *item)
361 Insert an item at the end of the structure, after the last item.
362 This is also an O(1) operation for non-atomic lists.
364 .. c:function:: void Z_add_after(struct Z_head *, itemtype *after, itemtype *item)
366 Insert ``item`` behind ``after``. If ``after`` is ``NULL``, the item is
367 inserted at the beginning of the list as with :c:func:`Z_add_head`.
368 This is also an O(1) operation for non-atomic lists.
370 A common pattern is to keep a "previous" pointer around while iterating:
374 itemtype *prev = NULL, *item;
376 frr_each_safe(Z, head, item) {
378 Z_add_after(head, prev, item);
386 maybe flip the order of ``item`` & ``after``?
387 ``Z_add_after(head, item, after)``
389 API for sorted structures
390 -------------------------
392 Sorted data structures do not need to have an insertion position specified,
393 therefore the insertion calls are different from unsorted lists. Also,
394 sorted lists can be searched for a value.
396 .. c:function:: DECLARE_XXX_UNIQ(Z, type, field, compare_func)
398 :param listtype XXX: One of the following:
399 ``SORTLIST`` (single-linked sorted list), ``SKIPLIST`` (skiplist),
400 ``RBTREE`` (RB-tree) or ``ATOMSORT`` (atomic single-linked list).
401 :param token Z: Gives the name prefix that is used for the functions
402 created for this instantiation. ``DECLARE_XXX(foo, ...)``
403 gives ``struct foo_item``, ``foo_add()``, ``foo_count()``, etc. Note
404 that this must match the value given in ``PREDECL_XXX(foo)``.
405 :param typename type: Specifies the data type of the list items, e.g.
406 ``struct item``. Note that ``struct`` must be added here, it is not
408 :param token field: References a struct member of ``type`` that must be
409 typed as ``struct foo_item``. This struct member is used to
410 store "next" pointers or other data structure specific data.
411 :param funcptr compare_func: Item comparison function, must have the
412 following function signature:
413 ``int function(const itemtype *, const itemtype*)``. This function
414 may be static if the list is only used in one file.
416 .. c:function:: DECLARE_XXX_NONUNIQ(Z, type, field, compare_func)
418 Same as above, but allow adding multiple items to the list that compare
419 as equal in ``compare_func``. Ordering between these items is undefined
420 and depends on the list implementation.
422 .. c:function:: itemtype *Z_add(struct Z_head *, itemtype *item)
424 Insert an item at the appropriate sorted position. If another item exists
425 in the list that compares as equal (``compare_func()`` == 0), ``item`` is
426 not inserted into the list and the already-existing item in the list is
427 returned. Otherwise, on successful insertion, ``NULL`` is returned.
429 For ``_NONUNIQ`` lists, this function always returns NULL since ``item``
430 can always be successfully added to the list.
432 .. c:function:: const itemtype *Z_find(const struct Z_head *, const itemtype *ref)
433 .. c:function:: itemtype *Z_find(struct Z_head *, const itemtype *ref)
435 Search the list for an item that compares equal to ``ref``. If no equal
436 item is found, return ``NULL``.
438 This function is likely used with a temporary stack-allocated value for
443 itemtype searchfor = { .foo = 123 };
445 itemtype *item = Z_find(head, &searchfor);
449 The ``Z_find()`` function is only available for lists that contain
450 unique items (i.e. ``DECLARE_XXX_UNIQ``.) This is because on a list
451 containing non-unique items, more than one item may compare as equal to
452 the item that is searched for.
454 .. c:function:: const itemtype *Z_find_gteq(const struct Z_head *, const itemtype *ref)
455 .. c:function:: itemtype *Z_find_gteq(struct Z_head *, const itemtype *ref)
457 Search the list for an item that compares greater or equal to
458 ``ref``. See :c:func:`Z_find()` above.
460 .. c:function:: const itemtype *Z_find_lt(const struct Z_head *, const itemtype *ref)
461 .. c:function:: itemtype *Z_find_lt(struct Z_head *, const itemtype *ref)
463 Search the list for an item that compares less than
464 ``ref``. See :c:func:`Z_find()` above.
470 .. c:function:: DECLARE_XXX(Z, type, field, compare_func, hash_func)
472 :param listtype XXX: Only ``HASH`` is currently available.
473 :param token Z: Gives the name prefix that is used for the functions
474 created for this instantiation. ``DECLARE_XXX(foo, ...)``
475 gives ``struct foo_item``, ``foo_add()``, ``foo_count()``, etc. Note
476 that this must match the value given in ``PREDECL_XXX(foo)``.
477 :param typename type: Specifies the data type of the list items, e.g.
478 ``struct item``. Note that ``struct`` must be added here, it is not
480 :param token field: References a struct member of ``type`` that must be
481 typed as ``struct foo_item``. This struct member is used to
482 store "next" pointers or other data structure specific data.
483 :param funcptr compare_func: Item comparison function, must have the
484 following function signature:
485 ``int function(const itemtype *, const itemtype*)``. This function
486 may be static if the list is only used in one file. For hash tables,
487 this function is only used to check for equality, the ordering is
489 :param funcptr hash_func: Hash calculation function, must have the
490 following function signature:
491 ``uint32_t function(const itemtype *)``. The hash value for items
492 stored in a hash table is cached in each item, so this value need not
493 be cached by the user code.
497 Items that compare as equal cannot be inserted. Refer to the notes
498 about sorted structures in the previous section.
501 .. c:function:: void Z_init_size(struct Z_head *, size_t size)
503 Same as :c:func:`Z_init()` but preset the minimum hash table to
506 Hash tables also support :c:func:`Z_add()` and :c:func:`Z_find()` with
507 the same semantics as noted above. :c:func:`Z_find_gteq()` and
508 :c:func:`Z_find_lt()` are **not** provided for hash tables.
510 Hash table invariants
511 ^^^^^^^^^^^^^^^^^^^^^
513 There are several ways to injure yourself using the hash table API.
515 First, note that there are two functions related to computing uniqueness of
516 objects inserted into the hash table. There is a hash function and a comparison
517 function. The hash function computes the hash of the object. Our hash table
518 implementation uses `chaining
519 <https://en.wikipedia.org/wiki/Hash_table#Separate_chaining_with_linked_lists>`_.
520 This means that your hash function does not have to be perfect; multiple
521 objects having the same computed hash will be placed into a linked list
522 corresponding to that key. The closer to perfect the hash function, the better
523 performance, as items will be more evenly distributed and the chain length will
524 not be long on any given lookup, minimizing the number of list operations
525 required to find the correct item. However, the comparison function *must* be
526 perfect, in the sense that any two unique items inserted into the hash table
527 must compare not equal. At insertion time, if you try to insert an item that
528 compares equal to an existing item the insertion will not happen and
529 ``hash_get()`` will return the existing item. However, this invariant *must* be
530 maintained while the object is in the hash table. Suppose you insert items
531 ``A`` and ``B`` into the hash table which both hash to the same value ``1234``
532 but do not compare equal. They will be placed in a chain like so::
536 Now suppose you do something like this elsewhere in the code::
540 I.e. you copy all fields of ``B`` into ``A``, such that the comparison function
541 now says that they are equal based on their contents. At this point when you
542 look up ``B`` in the hash table, ``hash_get()`` will search the chain for the
543 first item that compares equal to ``B``, which will be ``A``. This leads to
548 Never modify the values looked at by the comparison or hash functions after
549 inserting an item into a hash table.
551 A similar situation can occur with the hash allocation function. ``hash_get()``
552 accepts a function pointer that it will call to get the item that should be
553 inserted into the list if the provided item is not already present. There is a
554 builtin function, ``hash_alloc_intern``, that will simply return the item you
555 provided; if you always want to store the value you pass to ``hash_get`` you
556 should use this one. If you choose to provide a different one, that function
557 *must* return a new item that hashes and compares equal to the one you provided
558 to ``hash_get()``. If it does not the behavior of the hash table is undefined.
562 Always make sure your hash allocation function returns a value that hashes
563 and compares equal to the item you provided to ``hash_get()``.
565 Finally, if you maintain pointers to items you have inserted into a hash table,
566 then before deallocating them you must release them from the hash table. This
567 is basic memory management but worth repeating as bugs have arisen from failure
574 Heaps provide the same API as the sorted data structures, except:
576 * none of the find functions (:c:func:`Z_find()`, :c:func:`Z_find_gteq()`
577 or :c:func:`Z_find_lt()`) are available.
578 * iterating over the heap yields the items in semi-random order, only the
579 first item is guaranteed to be in order and actually the "lowest" item
580 on the heap. Being a heap, only the rebalancing performed on removing the
581 first item (either through :c:func:`Z_pop()` or :c:func:`Z_del()`) causes
582 the new lowest item to bubble up to the front.
583 * all heap modifications are O(log n). However, cacheline efficiency and
584 latency is likely quite a bit better than with other data structures.
589 `atomlist.h` provides an unsorted and a sorted atomic single-linked list.
590 Since atomic memory accesses can be considerably slower than plain memory
591 accessses (depending on the CPU type), these lists should only be used where
594 The following guarantees are provided regarding concurrent access:
596 - the operations are lock-free but not wait-free.
598 Lock-free means that it is impossible for all threads to be blocked. Some
599 thread will always make progress, regardless of what other threads do. (This
600 even includes a random thread being stopped by a debugger in a random
603 Wait-free implies that the time any single thread might spend in one of the
604 calls is bounded. This is not provided here since it is not normally
605 relevant to practical operations. What this means is that if some thread is
606 hammering a particular list with requests, it is possible that another
607 thread is blocked for an extended time. The lock-free guarantee still
608 applies since the hammering thread is making progress.
610 - without a RCU mechanism in place, the point of contention for atomic lists
611 is memory deallocation. As it is, **a rwlock is required for correct
612 operation**. The *read* lock must be held for all accesses, including
613 reading the list, adding items to the list, and removing items from the
614 list. The *write* lock must be acquired and released before deallocating
615 any list element. If this is not followed, an use-after-free can occur
616 as a MT race condition when an element gets deallocated while another
617 thread is accessing the list.
621 The *write* lock does not need to be held for deleting items from the
622 list, and there should not be any instructions between the
623 ``pthread_rwlock_wrlock`` and ``pthread_rwlock_unlock``. The write lock
624 is used as a sequence point, not as an exclusion mechanism.
626 - insertion operations are always safe to do with the read lock held.
627 Added items are immediately visible after the insertion call returns and
628 should not be touched anymore.
630 - when removing a *particular* (pre-determined) item, the caller must ensure
631 that no other thread is attempting to remove that same item. If this cannot
632 be guaranteed by architecture, a separate lock might need to be added.
634 - concurrent `pop` calls are always safe to do with only the read lock held.
635 This does not fall under the previous rule since the `pop` call will select
636 the next item if the first is already being removed by another thread.
638 **Deallocation locking still applies.** Assume another thread starts
639 reading the list, but gets task-switched by the kernel while reading the
640 first item. `pop` will happily remove and return that item. If it is
641 deallocated without acquiring and releasing the write lock, the other thread
642 will later resume execution and try to access the now-deleted element.
644 - the list count should be considered an estimate. Since there might be
645 concurrent insertions or removals in progress, it might already be outdated
646 by the time the call returns. No attempt is made to have it be correct even
649 Overall, atomic lists are well-suited for MT queues; concurrent insertion,
650 iteration and removal operations will work with the read lock held.
661 pthread_rwlock_rdlock(&itemhead_rwlock);
662 frr_each(itemlist, &itemhead, i) {
663 /* lock must remain held while iterating */
666 pthread_rwlock_unlock(&itemhead_rwlock);
668 Head removal (pop) and deallocation:
674 pthread_rwlock_rdlock(&itemhead_rwlock);
675 i = itemlist_pop(&itemhead);
676 pthread_rwlock_unlock(&itemhead_rwlock);
678 /* i might still be visible for another thread doing an
679 * frr_each() (but won't be returned by another pop()) */
682 pthread_rwlock_wrlock(&itemhead_rwlock);
683 pthread_rwlock_unlock(&itemhead_rwlock);
684 /* i now guaranteed to be gone from the list.
685 * note nothing between wrlock() and unlock() */
686 XFREE(MTYPE_ITEM, i);
691 What are the semantics of ``const`` in the list APIs?
692 ``const`` pointers to list heads and/or items are interpreted to mean that
693 both the list itself as well as the data items are read-only.
695 Why is there no "is this item on a/the list" test?
696 It's slow for several of the data structures, and the work of adding it
697 just hasn't been done. It can certainly be added if it's needed.
699 Why is it ``PREDECL`` + ``DECLARE`` instead of ``DECLARE`` + ``DEFINE``?
700 The rule is that a ``DEFINE`` must be in a ``.c`` file, and linked exactly
701 once because it defines some kind of global symbol. This is not the case
702 for the data structure macros; they only define ``static`` symbols and it
703 is perfectly fine to include both ``PREDECL`` and ``DECLARE`` in a header
704 file. It is also perfectly fine to have the same ``DECLARE`` statement in
705 2 ``.c`` files, but only **if the macro arguments are identical.** Maybe
706 don't do that unless you really need it.
720 refer to external docs