- frr_each
- frr_each_safe
- frr_each_from
+ - frr_rev_each
+ - frr_rev_each_safe
+ - frr_rev_each_from
- frr_with_mutex
- frr_with_privs
- LIST_FOREACH
Functions provided:
-+------------------------------------+------+------+------+---------+------------+
-| Function | LIST | HEAP | HASH | \*_UNIQ | \*_NONUNIQ |
-+====================================+======+======+======+=========+============+
-| _init, _fini | yes | yes | yes | yes | yes |
-+------------------------------------+------+------+------+---------+------------+
-| _first, _next, _next_safe, | yes | yes | yes | yes | yes |
-| | | | | | |
-| _const_first, _const_next | | | | | |
-+------------------------------------+------+------+------+---------+------------+
-| _swap_all | yes | yes | yes | yes | yes |
-+------------------------------------+------+------+------+---------+------------+
-| _anywhere | yes | -- | -- | -- | -- |
-+------------------------------------+------+------+------+---------+------------+
-| _add_head, _add_tail, _add_after | yes | -- | -- | -- | -- |
-+------------------------------------+------+------+------+---------+------------+
-| _add | -- | yes | yes | yes | yes |
-+------------------------------------+------+------+------+---------+------------+
-| _member | yes | yes | yes | yes | yes |
-+------------------------------------+------+------+------+---------+------------+
-| _del, _pop | yes | yes | yes | yes | yes |
-+------------------------------------+------+------+------+---------+------------+
-| _find, _const_find | -- | -- | yes | yes | -- |
-+------------------------------------+------+------+------+---------+------------+
-| _find_lt, _find_gteq, | -- | -- | -- | yes | yes |
-| | | | | | |
-| _const_find_lt, _const_find_gteq | | | | | |
-+------------------------------------+------+------+------+---------+------------+
-| use with frr_each() macros | yes | yes | yes | yes | yes |
-+------------------------------------+------+------+------+---------+------------+
++------------------------------------+-------+------+------+---------+------------+
+| Function | LIST | HEAP | HASH | \*_UNIQ | \*_NONUNIQ |
++====================================+=======+======+======+=========+============+
+| _init, _fini | yes | yes | yes | yes | yes |
++------------------------------------+-------+------+------+---------+------------+
+| _first, _next, _next_safe, | yes | yes | yes | yes | yes |
+| | | | | | |
+| _const_first, _const_next | | | | | |
++------------------------------------+-------+------+------+---------+------------+
+| _last, _prev, _prev_safe, | DLIST | -- | -- | RB only | RB only |
+| | only | | | | |
+| _const_last, _const_prev | | | | | |
++------------------------------------+-------+------+------+---------+------------+
+| _swap_all | yes | yes | yes | yes | yes |
++------------------------------------+-------+------+------+---------+------------+
+| _anywhere | yes | -- | -- | -- | -- |
++------------------------------------+-------+------+------+---------+------------+
+| _add_head, _add_tail, _add_after | yes | -- | -- | -- | -- |
++------------------------------------+-------+------+------+---------+------------+
+| _add | -- | yes | yes | yes | yes |
++------------------------------------+-------+------+------+---------+------------+
+| _member | yes | yes | yes | yes | yes |
++------------------------------------+-------+------+------+---------+------------+
+| _del, _pop | yes | yes | yes | yes | yes |
++------------------------------------+-------+------+------+---------+------------+
+| _find, _const_find | -- | -- | yes | yes | -- |
++------------------------------------+-------+------+------+---------+------------+
+| _find_lt, _find_gteq, | -- | -- | -- | yes | yes |
+| | | | | | |
+| _const_find_lt, _const_find_gteq | | | | | |
++------------------------------------+-------+------+------+---------+------------+
+| use with frr_each() macros | yes | yes | yes | yes | yes |
++------------------------------------+-------+------+------+---------+------------+
resume iteration after breaking out of the loop by keeping the ``from``
value persistent and reusing it for the next loop.
+.. c:macro:: frr_rev_each(Z, head, item)
+.. c:macro:: frr_rev_each_safe(Z, head, item)
+.. c:macro:: frr_rev_each_from(Z, head, item, from)
+
+ Reverse direction variants of the above. Only supported on containers that
+ implement ``_last`` and ``_prev`` (i.e. ``RBTREE`` and ``DLIST``).
+
To iterate over ``const`` pointers, add ``_const`` to the name of the
datastructure (``Z`` above), e.g. ``frr_each (mylist, head, item)`` becomes
``frr_each (mylist_const, head, item)``.
empty. This is O(1) for all data structures except red-black trees
where it is O(log n).
+.. c:function:: const itemtype *Z_const_last(const struct Z_head *)
+.. c:function:: itemtype *Z_last(struct Z_head *)
+
+ Last item in the structure, or ``NULL``. Only available on containers
+ that support reverse iteration (i.e. ``RBTREE`` and ``DLIST``).
+
.. c:function:: itemtype *Z_pop(struct Z_head *)
Remove and return the first item in the structure, or ``NULL`` if the
Same as :c:func:`Z_next()`, except that ``NULL`` is returned if
``prev`` is ``NULL``.
+.. c:function:: const itemtype *Z_const_prev(const struct Z_head *, const itemtype *next)
+.. c:function:: itemtype *Z_prev(struct Z_head *, itemtype *next)
+.. c:function:: itemtype *Z_prev_safe(struct Z_head *, itemtype *next)
+
+ As above, but preceding item. Only available on structures that support
+ reverse iteration (i.e. ``RBTREE`` and ``DLIST``).
+
.. c:function:: itemtype *Z_del(struct Z_head *, itemtype *item)
Remove ``item`` from the list and return it.
return rbe;
}
+struct rb_entry *typed_rb_prev(const struct rb_entry *rbe_const)
+{
+ struct rb_entry *rbe = (struct rb_entry *)rbe_const;
+
+ if (RBE_LEFT(rbe)) {
+ rbe = RBE_LEFT(rbe);
+ while (RBE_RIGHT(rbe))
+ rbe = RBE_RIGHT(rbe);
+ } else {
+ if (RBE_PARENT(rbe) && (rbe == RBE_RIGHT(RBE_PARENT(rbe))))
+ rbe = RBE_PARENT(rbe);
+ else {
+ while (RBE_PARENT(rbe)
+ && (rbe == RBE_LEFT(RBE_PARENT(rbe))))
+ rbe = RBE_PARENT(rbe);
+ rbe = RBE_PARENT(rbe);
+ }
+ }
+
+ return rbe;
+}
+
struct rb_entry *typed_rb_min(const struct rbt_tree *rbt)
{
struct rb_entry *rbe = RBH_ROOT(rbt);
return parent;
}
+struct rb_entry *typed_rb_max(const struct rbt_tree *rbt)
+{
+ struct rb_entry *rbe = RBH_ROOT(rbt);
+ struct rb_entry *parent = NULL;
+
+ while (rbe != NULL) {
+ parent = rbe;
+ rbe = RBE_RIGHT(rbe);
+ }
+
+ return parent;
+}
+
bool typed_rb_member(const struct typed_rb_root *rbt,
const struct typed_rb_entry *rbe)
{
const struct typed_rb_entry *a,
const struct typed_rb_entry *b));
struct typed_rb_entry *typed_rb_min(const struct typed_rb_root *rbt);
+struct typed_rb_entry *typed_rb_max(const struct typed_rb_root *rbt);
+struct typed_rb_entry *typed_rb_prev(const struct typed_rb_entry *rbe);
struct typed_rb_entry *typed_rb_next(const struct typed_rb_entry *rbe);
bool typed_rb_member(const struct typed_rb_root *rbt,
const struct typed_rb_entry *rbe);
return container_of_null(re, type, field.re); \
} \
TYPESAFE_FIRST_NEXT(prefix, type) \
+macro_pure const type *prefix ## _const_last(const struct prefix##_head *h) \
+{ \
+ const struct typed_rb_entry *re; \
+ re = typed_rb_max(&h->rr); \
+ return container_of_null(re, type, field.re); \
+} \
+macro_pure const type *prefix ## _const_prev(const struct prefix##_head *h, \
+ const type *item) \
+{ \
+ const struct typed_rb_entry *re; \
+ re = typed_rb_prev(&item->field.re); \
+ return container_of_null(re, type, field.re); \
+} \
+TYPESAFE_LAST_PREV(prefix, type) \
macro_pure type *prefix ## _next_safe(struct prefix##_head *h, type *item) \
{ \
struct typed_rb_entry *re; \
re = item ? typed_rb_next(&item->field.re) : NULL; \
return container_of_null(re, type, field.re); \
} \
+macro_pure type *prefix ## _prev_safe(struct prefix##_head *h, type *item) \
+{ \
+ struct typed_rb_entry *re; \
+ re = item ? typed_rb_prev(&item->field.re) : NULL; \
+ return container_of_null(re, type, field.re); \
+} \
macro_pure size_t prefix ## _count(const struct prefix##_head *h) \
{ \
return h->rr.count; \
item; \
item = from, from = prefix##_next_safe(head, from))
+/* reverse direction, only supported by a few containers */
+
+#define frr_rev_each(prefix, head, item) \
+ for (item = prefix##_last(head); item; \
+ item = prefix##_prev(head, item))
+#define frr_rev_each_safe(prefix, head, item) \
+ for (typeof(prefix##_prev_safe(head, NULL)) prefix##_safe = \
+ prefix##_prev_safe(head, \
+ (item = prefix##_last(head))); \
+ item; \
+ item = prefix##_safe, \
+ prefix##_safe = prefix##_prev_safe(head, prefix##_safe))
+#define frr_rev_each_from(prefix, head, item, from) \
+ for (item = from, from = prefix##_prev_safe(head, item); \
+ item; \
+ item = from, from = prefix##_prev_safe(head, from))
/* non-const variants. these wrappers are the same for all the types, so
* bundle them together here.
return (type *)prefix ## _const_next(h, item); \
} \
/* ... */
+#define TYPESAFE_LAST_PREV(prefix, type) \
+macro_pure type *prefix ## _last(struct prefix##_head *h) \
+{ \
+ return (type *)prefix ## _const_last(h); \
+} \
+macro_pure type *prefix ## _prev(struct prefix##_head *h, type *item) \
+{ \
+ return (type *)prefix ## _const_prev(h, item); \
+} \
+/* ... */
#define TYPESAFE_FIND(prefix, type) \
macro_inline type *prefix ## _find(struct prefix##_head *h, \
const type *item) \
return container_of(ditem->next, type, field.di); \
} \
TYPESAFE_FIRST_NEXT(prefix, type) \
+macro_pure const type *prefix ## _const_last(const struct prefix##_head *h) \
+{ \
+ const struct dlist_item *ditem = h->dh.hitem.prev; \
+ if (ditem == &h->dh.hitem) \
+ return NULL; \
+ return container_of(ditem, type, field.di); \
+} \
+macro_pure const type *prefix ## _const_prev(const struct prefix##_head *h, \
+ const type *item) \
+{ \
+ const struct dlist_item *ditem = &item->field.di; \
+ if (ditem->prev == &h->dh.hitem) \
+ return NULL; \
+ return container_of(ditem->prev, type, field.di); \
+} \
+TYPESAFE_LAST_PREV(prefix, type) \
macro_pure type *prefix ## _next_safe(struct prefix##_head *h, type *item) \
{ \
if (!item) \
return NULL; \
return prefix ## _next(h, item); \
} \
+macro_pure type *prefix ## _prev_safe(struct prefix##_head *h, type *item) \
+{ \
+ if (!item) \
+ return NULL; \
+ return prefix ## _prev(h, item); \
+} \
macro_pure size_t prefix ## _count(const struct prefix##_head *h) \
{ \
return h->dh.count; \
#define T_HASH (1 << 2)
#define T_HEAP (1 << 3)
#define T_ATOMIC (1 << 4)
+#define T_REVERSE (1 << 5)
#define _T_LIST (0)
-#define _T_DLIST (0)
+#define _T_DLIST (0 | T_REVERSE)
#define _T_ATOMLIST (0 | T_ATOMIC)
#define _T_HEAP (T_SORTED | T_HEAP)
#define _T_SORTLIST_UNIQ (T_SORTED | T_UNIQ)
#define _T_HASH (T_SORTED | T_UNIQ | T_HASH)
#define _T_SKIPLIST_UNIQ (T_SORTED | T_UNIQ)
#define _T_SKIPLIST_NONUNIQ (T_SORTED)
-#define _T_RBTREE_UNIQ (T_SORTED | T_UNIQ)
-#define _T_RBTREE_NONUNIQ (T_SORTED)
+#define _T_RBTREE_UNIQ (T_SORTED | T_UNIQ | T_REVERSE)
+#define _T_RBTREE_NONUNIQ (T_SORTED | T_REVERSE)
#define _T_ATOMSORT_UNIQ (T_SORTED | T_UNIQ | T_ATOMIC)
#define _T_ATOMSORT_NONUNIQ (T_SORTED | T_ATOMIC)
#define IS_HASH(type) (_T_TYPE(type) & T_HASH)
#define IS_HEAP(type) (_T_TYPE(type) & T_HEAP)
#define IS_ATOMIC(type) (_T_TYPE(type) & T_ATOMIC)
+#define IS_REVERSE(type) (_T_TYPE(type) & T_REVERSE)
static struct timeval ref, ref0;
#define list_const_next concat(TYPE, _const_next)
#define list_next concat(TYPE, _next)
#define list_next_safe concat(TYPE, _next_safe)
+#define list_const_last concat(TYPE, _const_last)
+#define list_last concat(TYPE, _last)
+#define list_const_prev concat(TYPE, _const_prev)
+#define list_prev concat(TYPE, _prev)
+#define list_prev_safe concat(TYPE, _prev_safe)
#define list_count concat(TYPE, _count)
#define list_add concat(TYPE, _add)
#define list_add_head concat(TYPE, _add_head)
list_init(&head);
assert(list_first(&head) == NULL);
+#if IS_REVERSE(REALTYPE)
+ assert(list_last(&head) == NULL);
+#endif
ts_hash("init", "df3f619804a92fdb4057192dc43dd748ea778adc52bc498ce80524c014b81119");
assert(!list_first(&head));
assert(list_count(&other) == k);
assert(list_first(&other) != NULL);
+#if IS_REVERSE(REALTYPE)
+ assert(!list_last(&head));
+ assert(list_last(&other) != NULL);
+#endif
ts_hash_headx(
&other, "swap1",
"a538546a6e6ab0484e925940aa8dd02fd934408bbaed8cb66a0721841584d838");
(void)cprev;
#else
assert(!cprev || cprev->val < citem->val);
+#if IS_REVERSE(REALTYPE)
+ assert(list_const_prev(chead, citem) == cprev);
+#endif
#endif
cprev = citem;
k++;
}
assert(list_count(chead) == k);
+#if IS_REVERSE(REALTYPE)
+ assert(cprev == list_const_last(chead));
+#endif
ts_ref("walk");
+#if IS_REVERSE(REALTYPE) && !IS_HASH(REALTYPE) && !IS_HEAP(REALTYPE)
+ cprev = NULL;
+ k = 0;
+
+ frr_rev_each(list_const, chead, citem) {
+ assert(!cprev || cprev->val > citem->val);
+ assert(list_const_next(chead, citem) == cprev);
+
+ cprev = citem;
+ k++;
+ }
+ assert(list_count(chead) == k);
+ assert(cprev == list_const_first(chead));
+
+ ts_ref("reverse-walk");
+#endif
+
#if IS_UNIQ(REALTYPE)
prng_free(prng);
prng = prng_new(0);
}
assert(list_count(&head) == k);
assert(list_first(&head) != NULL);
+#if IS_REVERSE(REALTYPE)
+ assert(list_last(&head) != NULL);
+#endif
ts_hash("fill / add_tail", "eabfcf1413936daaf20965abced95762f45110a6619b84aac7d38481bce4ea19");
#if !IS_ATOMIC(REALTYPE)
assert(!list_first(&head));
assert(list_count(&other) == k);
assert(list_first(&other) != NULL);
+#if IS_REVERSE(REALTYPE)
+ assert(!list_last(&head));
+ assert(list_last(&other) != NULL);
+#endif
ts_hash_head(
&other, "swap1",
"eabfcf1413936daaf20965abced95762f45110a6619b84aac7d38481bce4ea19");
}
ts_hash("member", "42b8950c880535b2d2e0c980f9845f7841ecf675c0fb9801aec4170d2036349d");
#endif
+#if IS_REVERSE(REALTYPE)
+ i = 0;
+ prev = NULL;
+
+ frr_rev_each (list, &head, item) {
+ assert(item->scratchpad != 0);
+ assert(list_next(&head, item) == prev);
+
+ i++;
+ prev = item;
+ }
+ assert(list_first(&head) == prev);
+ assert(list_count(&head) == i);
+ ts_hash("reverse-walk", "42b8950c880535b2d2e0c980f9845f7841ecf675c0fb9801aec4170d2036349d");
+#endif
while ((item = list_pop(&head))) {
assert(item->scratchpad != 0);
#undef list_first
#undef list_next
#undef list_next_safe
+#undef list_const_first
+#undef list_const_next
+#undef list_last
+#undef list_prev
+#undef list_prev_safe
+#undef list_const_last
+#undef list_const_prev
#undef list_count
#undef list_add
#undef list_add_head
projects / mirror_frr.git / commitdiff