6 The term *list* is used generically for lists, skiplists, trees and hash
7 tables in this document.
12 FRR includes a set of list-like data structure implementations with abstracted
13 common APIs. The purpose of this is easily allow swapping out one
14 data structure for another while also making the code easier to read and write.
15 There is one API for unsorted lists and a similar but not identical API for
18 For unsorted lists, the following implementations exist:
20 - single-linked list with tail pointer (e.g. STAILQ in BSD)
22 - atomic single-linked list with tail pointer
25 For sorted lists, these data structures are implemented:
29 - atomic single-linked list
33 - red-black tree (based on OpenBSD RB_TREE)
35 - hash table (note below)
37 Except for hash tables, each of the sorted data structures has a variant with
38 unique and non-unique list items. Hash tables always require unique items
39 and mostly follow the "sorted" API but use the hash value as sorting
40 key. Also, iterating while modifying does not work with hash tables.
43 The following sorted structures are likely to be implemented at some point
48 - atomic hash table (note below)
51 The APIs are all designed to be as type-safe as possible. This means that
52 there will be a compiler warning when an item doesn't match the list, or
53 the return value has a different type, or other similar situations. **You
54 should never use casts with these APIs.** If a cast is neccessary in relation
55 to these APIs, there is probably something wrong with the overall design.
57 Only the following pieces use dynamically allocated memory:
59 - the hash table itself is dynamically grown and shrunk
61 - skiplists store up to 4 next pointers inline but will dynamically allocate
62 memory to hold an item's 5th up to 16th next pointer (if they exist)
75 DECLARE_SORTLIST_NONUNIQ
77 DECLARE_ATOMLIST_NONUNIQ
79 DECLARE_SKIPLIST_NONUNIQ
81 DECLARE_RBTREE_NONUNIQ
87 +------------------------------------+------+------+---------+------------+
88 | Function | LIST | HASH | \*_UNIQ | \*_NONUNIQ |
89 +====================================+======+======+=========+============+
90 | _init, _fini | yes | yes | yes | yes |
91 +------------------------------------+------+------+---------+------------+
92 | _first, _next, _next_safe | yes | yes | yes | yes |
93 +------------------------------------+------+------+---------+------------+
94 | _add_head, _add_tail, _add_after | yes | -- | -- | -- |
95 +------------------------------------+------+------+---------+------------+
96 | _add | -- | yes | yes | yes |
97 +------------------------------------+------+------+---------+------------+
98 | _del, _pop | yes | yes | yes | yes |
99 +------------------------------------+------+------+---------+------------+
100 | _find | -- | yes | yes | -- |
101 +------------------------------------+------+------+---------+------------+
102 | _find_lt, _find_gteq | -- | -- | yes | yes |
103 +------------------------------------+------+------+---------+------------+
104 | use with for_each() macros | yes | yes | yes | yes |
105 +------------------------------------+------+------+---------+------------+
108 Datastructure type setup
109 ------------------------
111 Each of the data structures has a ``PREDECL_*`` and a ``DECLARE_*`` macro to
112 set up an "instantiation" of the list. This works somewhat similar to C++
113 templating, though much simpler.
115 **In all following text, the Z prefix is replaced with a name choosen
116 for the instance of the datastructure.**
118 The common setup pattern will look like this:
125 struct Z_item mylistitem;
128 struct Z_head mylisthead;
131 DECLARE_XXX(Z, struct item, mylistitem)
133 /* sorted, items that compare as equal cannot be added to list */
134 int compare_func(const struct item *a, const struct item *b);
135 DECLARE_XXX_UNIQ(Z, struct item, mylistitem, compare_func)
137 /* sorted, items that compare as equal can be added to list */
138 int compare_func(const struct item *a, const struct item *b);
139 DECLARE_XXX_NONUNIQ(Z, struct item, mylistitem, compare_func)
142 int compare_func(const struct item *a, const struct item *b);
143 uint32_t hash_func(const struct item *a);
144 DECLARE_XXX(Z, struct item, mylistitem, compare_func, hash_func)
146 ``XXX`` is replaced with the name of the data structure, e.g. ``SKIPLIST``
147 or ``ATOMLIST``. The ``DECLARE_XXX`` invocation can either occur in a `.h`
148 file (if the list needs to be accessed from several C files) or it can be
149 placed in a `.c` file (if the list is only accessed from that file.) The
150 ``PREDECL_XXX`` invocation defines the ``struct Z_item`` and ``struct
151 Z_head`` types and must therefore occur before these are used.
153 To switch between compatible data structures, only these two lines need to be
154 changes. To switch to a data structure with a different API, some source
155 changes are necessary.
157 Common iteration macros
158 -----------------------
160 The following iteration macros work across all data structures:
162 .. c:function:: for_each(Z, head, item)
168 for (item = Z_first(head); item; item = Z_next(head, item))
170 Note that this will fail if the list is modified while being iterated
173 .. c:function:: for_each_safe(Z, head, item)
175 Same as the previous, but the next element is pre-loaded into a "hidden"
176 variable (named ``Z_safe``.) Equivalent to:
180 for (item = Z_first(head); item; item = next) {
181 next = Z_next_safe(head, item);
187 Iterating over hash tables while adding or removing items is not
188 possible. The iteration position will be corrupted when the hash
189 tables is resized while iterating. This will cause items to be
190 skipped or iterated over twice.
192 .. c:function:: for_each_from(Z, head, item, from)
194 Iterates over the list, starting at item ``from``. This variant is "safe"
195 as in the previous macro. Equivalent to:
199 for (item = from; item; item = from) {
200 from = Z_next_safe(head, item);
206 The ``from`` variable is written to. This is intentional - you can
207 resume iteration after breaking out of the loop by keeping the ``from``
208 value persistent and reusing it for the next loop.
213 The following documentation assumes that a list has been defined using
214 ``Z`` as the name, and ``itemtype`` being the type of the list items (e.g.
217 .. c:function:: void Z_init(struct Z_head *)
219 Initializes the list for use. For most implementations, this just sets
220 some values. Hash tables are the only implementation that allocates
223 .. c:function:: void Z_fini(struct Z_head *)
225 Reverse the effects of :c:func:`Z_init()`. The list must be empty
226 when this function is called.
230 This function may ``assert()`` if the list is not empty.
232 .. c:function:: size_t Z_count(struct Z_head *)
234 Returns the number of items in a structure. All structures store a
235 counter in their `Z_head` so that calling this function completes
240 For atomic lists with concurrent access, the value will already be
241 outdated by the time this function returns and can therefore only be
244 .. c:function:: itemtype *Z_first(struct Z_head *)
246 Returns the first item in the structure, or ``NULL`` if the structure is
247 empty. This is O(1) for all data structures except red-black trees
248 where it is O(log n).
250 .. c:function:: itemtype *Z_pop(struct Z_head *)
252 Remove and return the first item in the structure, or ``NULL`` if the
253 structure is empty. Like :c:func:`Z_first`, this is O(1) for all
254 data structures except red-black trees where it is O(log n) again.
256 This function can be used to build queues (with unsorted structures) or
257 priority queues (with sorted structures.)
259 Another common pattern is deleting all list items:
263 while ((item = Z_pop(head)))
268 This function can - and should - be used with hash tables. It is not
269 affected by the "modification while iterating" problem. To remove
270 all items from a hash table, use the loop demonstrated above.
272 .. c:function:: itemtype *Z_next(struct Z_head *, itemtype *prev)
274 Return the item that follows after ``prev``, or ``NULL`` if ``prev`` is
279 ``prev`` must not be ``NULL``! Use :c:func:`Z_next_safe()` if
280 ``prev`` might be ``NULL``.
282 .. c:function:: itemtype *Z_next_safe(struct Z_head *, itemtype *prev)
284 Same as :c:func:`Z_next()`, except that ``NULL`` is returned if
285 ``prev`` is ``NULL``.
287 .. c:function:: itemtype *Z_del(struct Z_head *, itemtype *item)
289 Remove ``item`` from the list and return it.
293 This function's behaviour is undefined if ``item`` is not actually
294 on the list. Some structures return ``NULL`` in this case while others
295 return ``item``. The function may also call ``assert()`` (but most
300 ``Z_del_after()`` / ``Z_del_hint()``?
302 API for unsorted structures
303 ---------------------------
305 Since the insertion position is not pre-defined for unsorted data, there
306 are several functions exposed to insert data:
310 ``item`` must not be ``NULL`` for any of the following functions.
312 .. c:function:: DECLARE_XXX(Z, type, field)
314 :param listtype XXX: ``LIST`` or ``ATOMLIST`` to select a data structure
316 :param token Z: Gives the name prefix that is used for the functions
317 created for this instantiation. ``DECLARE_XXX(foo, ...)``
318 gives ``struct foo_item``, ``foo_add_head()``, ``foo_count()``, etc. Note
319 that this must match the value given in ``PREDECL_XXX(foo)``.
320 :param typename type: Specifies the data type of the list items, e.g.
321 ``struct item``. Note that ``struct`` must be added here, it is not
323 :param token field: References a struct member of ``type`` that must be
324 typed as ``struct foo_item``. This struct member is used to
325 store "next" pointers or other data structure specific data.
327 .. c:function:: void Z_add_head(struct Z_head *, itemtype *item)
329 Insert an item at the beginning of the structure, before the first item.
330 This is an O(1) operation for non-atomic lists.
332 .. c:function:: void Z_add_tail(struct Z_head *, itemtype *item)
334 Insert an item at the end of the structure, after the last item.
335 This is also an O(1) operation for non-atomic lists.
337 .. c:function:: void Z_add_after(struct Z_head *, itemtype *after, itemtype *item)
339 Insert ``item`` behind ``after``. If ``after`` is ``NULL``, the item is
340 inserted at the beginning of the list as with :c:func:`Z_add_head`.
341 This is also an O(1) operation for non-atomic lists.
343 A common pattern is to keep a "previous" pointer around while iterating:
347 itemtype *prev = NULL, *item;
349 for_each_safe(Z, head, item) {
351 Z_add_after(head, prev, item);
359 maybe flip the order of ``item`` & ``after``?
360 ``Z_add_after(head, item, after)``
362 API for sorted structures
363 -------------------------
365 Sorted data structures do not need to have an insertion position specified,
366 therefore the insertion calls are different from unsorted lists. Also,
367 sorted lists can be searched for a value.
369 .. c:function:: DECLARE_XXX_UNIQ(Z, type, field, compare_func)
371 :param listtype XXX: One of the following:
372 ``SORTLIST`` (single-linked sorted list), ``SKIPLIST`` (skiplist),
373 ``RBTREE`` (RB-tree) or ``ATOMSORT`` (atomic single-linked list).
374 :param token Z: Gives the name prefix that is used for the functions
375 created for this instantiation. ``DECLARE_XXX(foo, ...)``
376 gives ``struct foo_item``, ``foo_add()``, ``foo_count()``, etc. Note
377 that this must match the value given in ``PREDECL_XXX(foo)``.
378 :param typename type: Specifies the data type of the list items, e.g.
379 ``struct item``. Note that ``struct`` must be added here, it is not
381 :param token field: References a struct member of ``type`` that must be
382 typed as ``struct foo_item``. This struct member is used to
383 store "next" pointers or other data structure specific data.
384 :param funcptr compare_func: Item comparison function, must have the
385 following function signature:
386 ``int function(const itemtype *, const itemtype*)``. This function
387 may be static if the list is only used in one file.
389 .. c:function:: DECLARE_XXX_NONUNIQ(Z, type, field, compare_func)
391 Same as above, but allow adding multiple items to the list that compare
392 as equal in ``compare_func``. Ordering between these items is undefined
393 and depends on the list implementation.
395 .. c:function:: itemtype *Z_add(struct Z_head *, itemtype *item)
397 Insert an item at the appropriate sorted position. If another item exists
398 in the list that compares as equal (``compare_func()`` == 0), ``item`` is
399 not inserted into the list and the already-existing item in the list is
400 returned. Otherwise, on successful insertion, ``NULL`` is returned.
402 For ``_NONUNIQ`` lists, this function always returns NULL since ``item``
403 can always be successfully added to the list.
405 .. c:function:: itemtype *Z_find(struct Z_head *, const itemtype *ref)
407 Search the list for an item that compares equal to ``ref``. If no equal
408 item is found, return ``NULL``.
410 This function is likely used with a temporary stack-allocated value for
415 itemtype searchfor = { .foo = 123 };
417 itemtype *item = Z_find(head, &searchfor);
421 The ``Z_find()`` function is only available for lists that contain
422 unique items (i.e. ``DECLARE_XXX_UNIQ``.) This is because on a list
423 containing non-unique items, more than one item may compare as equal to
424 the item that is searched for.
426 .. c:function:: itemtype *Z_find_gteq(struct Z_head *, const itemtype *ref)
428 Search the list for an item that compares greater or equal to
429 ``ref``. See :c:func:`Z_find()` above.
431 .. c:function:: itemtype *Z_find_lt(struct Z_head *, const itemtype *ref)
433 Search the list for an item that compares less than
434 ``ref``. See :c:func:`Z_find()` above.
440 .. c:function:: DECLARE_XXX(Z, type, field, compare_func, hash_func)
442 :param listtype XXX: Only ``HASH`` is currently available.
443 :param token Z: Gives the name prefix that is used for the functions
444 created for this instantiation. ``DECLARE_XXX(foo, ...)``
445 gives ``struct foo_item``, ``foo_add()``, ``foo_count()``, etc. Note
446 that this must match the value given in ``PREDECL_XXX(foo)``.
447 :param typename type: Specifies the data type of the list items, e.g.
448 ``struct item``. Note that ``struct`` must be added here, it is not
450 :param token field: References a struct member of ``type`` that must be
451 typed as ``struct foo_item``. This struct member is used to
452 store "next" pointers or other data structure specific data.
453 :param funcptr compare_func: Item comparison function, must have the
454 following function signature:
455 ``int function(const itemtype *, const itemtype*)``. This function
456 may be static if the list is only used in one file. For hash tables,
457 this function is only used to check for equality, the ordering is
459 :param funcptr hash_func: Hash calculation function, must have the
460 following function signature:
461 ``uint32_t function(const itemtype *)``. The hash value for items
462 stored in a hash table is cached in each item, so this value need not
463 be cached by the user code.
467 Items that compare as equal cannot be inserted. Refer to the notes
468 about sorted structures in the previous section.
470 .. c:function:: void Z_init_size(struct Z_head *, size_t size)
472 Same as :c:func:`Z_init()` but preset the minimum hash table to
475 Hash tables also support :c:func:`Z_add()` and :c:func:`Z_find()` with
476 the same semantics as noted above. :c:func:`Z_find_gteq()` and
477 :c:func:`Z_find_lt()` are **not** provided for hash tables.
483 `atomlist.h` provides an unsorted and a sorted atomic single-linked list.
484 Since atomic memory accesses can be considerably slower than plain memory
485 accessses (depending on the CPU type), these lists should only be used where
488 The following guarantees are provided regarding concurrent access:
490 - the operations are lock-free but not wait-free.
492 Lock-free means that it is impossible for all threads to be blocked. Some
493 thread will always make progress, regardless of what other threads do. (This
494 even includes a random thread being stopped by a debugger in a random
497 Wait-free implies that the time any single thread might spend in one of the
498 calls is bounded. This is not provided here since it is not normally
499 relevant to practical operations. What this means is that if some thread is
500 hammering a particular list with requests, it is possible that another
501 thread is blocked for an extended time. The lock-free guarantee still
502 applies since the hammering thread is making progress.
504 - without a RCU mechanism in place, the point of contention for atomic lists
505 is memory deallocation. As it is, **a rwlock is required for correct
506 operation**. The *read* lock must be held for all accesses, including
507 reading the list, adding items to the list, and removing items from the
508 list. The *write* lock must be acquired and released before deallocating
509 any list element. If this is not followed, an use-after-free can occur
510 as a MT race condition when an element gets deallocated while another
511 thread is accessing the list.
515 The *write* lock does not need to be held for deleting items from the
516 list, and there should not be any instructions between the
517 ``pthread_rwlock_wrlock`` and ``pthread_rwlock_unlock``. The write lock
518 is used as a sequence point, not as an exclusion mechanism.
520 - insertion operations are always safe to do with the read lock held.
521 Added items are immediately visible after the insertion call returns and
522 should not be touched anymore.
524 - when removing a *particular* (pre-determined) item, the caller must ensure
525 that no other thread is attempting to remove that same item. If this cannot
526 be guaranteed by architecture, a separate lock might need to be added.
528 - concurrent `pop` calls are always safe to do with only the read lock held.
529 This does not fall under the previous rule since the `pop` call will select
530 the next item if the first is already being removed by another thread.
532 **Deallocation locking still applies.** Assume another thread starts
533 reading the list, but gets task-switched by the kernel while reading the
534 first item. `pop` will happily remove and return that item. If it is
535 deallocated without acquiring and releasing the write lock, the other thread
536 will later resume execution and try to access the now-deleted element.
538 - the list count should be considered an estimate. Since there might be
539 concurrent insertions or removals in progress, it might already be outdated
540 by the time the call returns. No attempt is made to have it be correct even
543 Overall, atomic lists are well-suited for MT queues; concurrent insertion,
544 iteration and removal operations will work with the read lock held.
555 pthread_rwlock_rdlock(&itemhead_rwlock);
556 for_each(itemlist, &itemhead, i) {
557 /* lock must remain held while iterating */
560 pthread_rwlock_unlock(&itemhead_rwlock);
562 Head removal (pop) and deallocation:
568 pthread_rwlock_rdlock(&itemhead_rwlock);
569 i = itemlist_pop(&itemhead);
570 pthread_rwlock_unlock(&itemhead_rwlock);
572 /* i might still be visible for another thread doing an
573 * for_each() (but won't be returned by another pop()) */
576 pthread_rwlock_wrlock(&itemhead_rwlock);
577 pthread_rwlock_unlock(&itemhead_rwlock);
578 /* i now guaranteed to be gone from the list.
579 * note nothing between wrlock() and unlock() */
580 XFREE(MTYPE_ITEM, i);
594 refer to external docs