Mailing List Archive

[master] 4fa7f784f Update vtree.h from FreeBSD's sys/sys/tree.h (their: c2ddf2edb4aa4)
commit 4fa7f784f26c784d983e5b6b1c1dcba1f233fbc7
Author: Poul-Henning Kamp <phk@FreeBSD.org>
Date: Mon Dec 5 15:40:11 2022 +0000

Update vtree.h from FreeBSD's sys/sys/tree.h (their: c2ddf2edb4aa4)

diff --git a/bin/varnishd/cache/cache_vrt_priv.c b/bin/varnishd/cache/cache_vrt_priv.c
index fd4e84fbc..5ebce43b4 100644
--- a/bin/varnishd/cache/cache_vrt_priv.c
+++ b/bin/varnishd/cache/cache_vrt_priv.c
@@ -55,6 +55,7 @@ static inline int vrt_priv_dyncmp(const struct vrt_priv *,

VRBT_GENERATE_INSERT_COLOR(vrt_privs, vrt_priv, entry, static)
VRBT_GENERATE_FIND(vrt_privs, vrt_priv, entry, vrt_priv_dyncmp, static)
+VRBT_GENERATE_INSERT_FINISH(vrt_privs, vrt_priv, entry, static)
VRBT_GENERATE_INSERT(vrt_privs, vrt_priv, entry, vrt_priv_dyncmp, static)
VRBT_GENERATE_MINMAX(vrt_privs, vrt_priv, entry, static)
VRBT_GENERATE_NEXT(vrt_privs, vrt_priv, entry, static)
diff --git a/bin/varnishtop/varnishtop.c b/bin/varnishtop/varnishtop.c
index b8d600877..791f143b1 100644
--- a/bin/varnishtop/varnishtop.c
+++ b/bin/varnishtop/varnishtop.c
@@ -111,6 +111,7 @@ cmp_order(const struct top *a, const struct top *b)
}

VRBT_GENERATE_INSERT_COLOR(t_order, top, e_order, static)
+VRBT_GENERATE_INSERT_FINISH(t_order, top, e_order, static)
VRBT_GENERATE_INSERT(t_order, top, e_order, cmp_order, static)
VRBT_GENERATE_REMOVE_COLOR(t_order, top, e_order, static)
VRBT_GENERATE_MINMAX(t_order, top, e_order, static)
@@ -119,6 +120,7 @@ VRBT_GENERATE_REMOVE(t_order, top, e_order, static)

VRBT_GENERATE_INSERT_COLOR(t_key, top, e_key, static)
VRBT_GENERATE_REMOVE_COLOR(t_key, top, e_key, static)
+VRBT_GENERATE_INSERT_FINISH(t_key, top, e_key, static)
VRBT_GENERATE_INSERT(t_key, top, e_key, cmp_key, static)
VRBT_GENERATE_REMOVE(t_key, top, e_key, static)
VRBT_GENERATE_FIND(t_key, top, e_key, cmp_key, static)
diff --git a/flint.lnt b/flint.lnt
index af5a93da6..1f5598ded 100644
--- a/flint.lnt
+++ b/flint.lnt
@@ -216,6 +216,12 @@
-emacro(527, VRBT_*) // unreachable code
-emacro(740, VRBT_*) // unusual pointer cast
-emacro(438, VRBT_*) // last value assigned not used
+-emacro(613, VRBT_*) // Possible use of null pointer 'child' in left argument to
+-emacro(838, VRBT_*) // Previously assigned value to variable 'child' has not been used
+-emacro(50, VRBT_GENERATE_*) // Attempted to take the address of a non-lvalue
+-emacro(506, VRBT_GENERATE_*) // Constant value Boolean
+-emacro(845, VRBT_GENERATE_*) // The left argument to operator '&&' is certain to be 0
+-emacro(774, VRBT_GENERATE_*) // Boolean within 'if' always evaluates to False
-esym(534, *_VRBT_REMOVE) // ignore retval
-esym(534, *_VRBT_INSERT) // ignore retval

diff --git a/include/vtree.h b/include/vtree.h
index 325a2cb1f..bfa5efcd7 100644
--- a/include/vtree.h
+++ b/include/vtree.h
@@ -59,9 +59,11 @@
* the same, and defines the rank of that node. The rank of the null node
* is -1.
*
- * Different additional conditions define different sorts of balanced
- * trees, including "red-black" and "AVL" trees. The set of conditions
- * applied here are the "weak-AVL" conditions of Haeupler, Sen and Tarjan:
+ * Different additional conditions define different sorts of balanced trees,
+ * including "red-black" and "AVL" trees. The set of conditions applied here
+ * are the "weak-AVL" conditions of Haeupler, Sen and Tarjan presented in in
+ * "Rank Balanced Trees", ACM Transactions on Algorithms Volume 11 Issue 4 June
+ * 2015 Article No.: 30pp 1–26 https://doi.org/10.1145/2689412 (the HST paper):
* - every rank-difference is 1 or 2.
* - the rank of any leaf is 1.
*
@@ -179,7 +181,7 @@ name##_VSPLAY_INSERT(struct name *head, struct type *elm) \
if (VSPLAY_EMPTY(head)) { \
VSPLAY_LEFT(elm, field) = VSPLAY_RIGHT(elm, field) = NULL; \
} else { \
- int __comp; \
+ __typeof(cmp(NULL, NULL)) __comp; \
name##_VSPLAY(head, elm); \
__comp = (cmp)(elm, (head)->sph_root); \
if (__comp < 0) { \
@@ -222,7 +224,7 @@ void \
name##_VSPLAY(struct name *head, struct type *elm) \
{ \
struct type __node, *__left, *__right, *__tmp; \
- int __comp; \
+ __typeof(cmp(NULL, NULL)) __comp; \
\
VSPLAY_LEFT(&__node, field) = VSPLAY_RIGHT(&__node, field) = NULL;\
__left = __right = &__node; \
@@ -321,14 +323,9 @@ struct name { \

#define VRBT_ENTRY(type) \
struct { \
- struct type *rbe_left; /* left element */ \
- struct type *rbe_right; /* right element */ \
- struct type *rbe_parent; /* parent element */ \
+ struct type *rbe_link[3]; \
}

-#define VRBT_LEFT(elm, field) (elm)->field.rbe_left
-#define VRBT_RIGHT(elm, field) (elm)->field.rbe_right
-
/*
* With the expectation that any object of struct type has an
* address that is a multiple of 4, and that therefore the
@@ -336,63 +333,78 @@ struct { \
* always zero, this implementation sets those bits to indicate
* that the left or right child of the tree node is "red".
*/
-#define VRBT_UP(elm, field) (elm)->field.rbe_parent
-#define VRBT_BITS(elm, field) (*(uintptr_t *)&VRBT_UP(elm, field))
-#define VRBT_RED_L ((uintptr_t)1)
-#define VRBT_RED_R ((uintptr_t)2)
-#define VRBT_RED_MASK ((uintptr_t)3)
-#define VRBT_FLIP_LEFT(elm, field) (VRBT_BITS(elm, field) ^= VRBT_RED_L)
-#define VRBT_FLIP_RIGHT(elm, field) (VRBT_BITS(elm, field) ^= VRBT_RED_R)
-#define VRBT_RED_LEFT(elm, field) ((VRBT_BITS(elm, field) & VRBT_RED_L) != 0)
-#define VRBT_RED_RIGHT(elm, field) ((VRBT_BITS(elm, field) & VRBT_RED_R) != 0)
-#define VRBT_PARENT(elm, field) ((__typeof(VRBT_UP(elm, field))) \
- (VRBT_BITS(elm, field) & ~VRBT_RED_MASK))
+#define _VRBT_LINK(elm, dir, field) (elm)->field.rbe_link[dir]
+#define _VRBT_UP(elm, field) _VRBT_LINK(elm, 0, field)
+#define _VRBT_L ((uintptr_t)1)
+#define _VRBT_R ((uintptr_t)2)
+#define _VRBT_LR ((uintptr_t)3)
+#define _VRBT_BITS(elm) (*(uintptr_t *)&elm)
+#define _VRBT_BITSUP(elm, field) _VRBT_BITS(_VRBT_UP(elm, field))
+#define _VRBT_PTR(elm) (__typeof(elm)) \
+ ((uintptr_t)elm & ~_VRBT_LR)
+
+#define VRBT_PARENT(elm, field) _VRBT_PTR(_VRBT_UP(elm, field))
+#define VRBT_LEFT(elm, field) _VRBT_LINK(elm, _VRBT_L, field)
+#define VRBT_RIGHT(elm, field) _VRBT_LINK(elm, _VRBT_R, field)
#define VRBT_ROOT(head) (head)->rbh_root
#define VRBT_EMPTY(head) (VRBT_ROOT(head) == NULL)

#define VRBT_SET_PARENT(dst, src, field) do { \
- VRBT_BITS(dst, field) &= VRBT_RED_MASK; \
- VRBT_BITS(dst, field) |= (uintptr_t)src; \
+ _VRBT_BITSUP(dst, field) = (uintptr_t)src | \
+ (_VRBT_BITSUP(dst, field) & _VRBT_LR); \
} while (/*CONSTCOND*/ 0)

#define VRBT_SET(elm, parent, field) do { \
- VRBT_UP(elm, field) = parent; \
+ _VRBT_UP(elm, field) = parent; \
VRBT_LEFT(elm, field) = VRBT_RIGHT(elm, field) = NULL; \
} while (/*CONSTCOND*/ 0)

-#define VRBT_COLOR(elm, field) (VRBT_PARENT(elm, field) == NULL ? 0 : \
- VRBT_LEFT(VRBT_PARENT(elm, field), field) == elm ? \
- VRBT_RED_LEFT(VRBT_PARENT(elm, field), field) : \
- VRBT_RED_RIGHT(VRBT_PARENT(elm, field), field))
+/*
+ * Either VRBT_AUGMENT or VRBT_AUGMENT_CHECK is invoked in a loop at the root of
+ * every modified subtree, from the bottom up to the root, to update augmented
+ * node data. VRBT_AUGMENT_CHECK returns true only when the update changes the
+ * node data, so that updating can be stopped short of the root when it returns
+ * false.
+ */
+#ifndef VRBT_AUGMENT_CHECK
+#ifndef VRBT_AUGMENT
+#define VRBT_AUGMENT_CHECK(x) 0
+#else
+#define VRBT_AUGMENT_CHECK(x) (VRBT_AUGMENT(x), 1)
+#endif
+#endif

-#define VRBT_SWAP_CHILD(head, out, in, field) do { \
- if (VRBT_PARENT(out, field) == NULL) \
+#define VRBT_UPDATE_AUGMENT(elm, field) do { \
+ __typeof(elm) rb_update_tmp = (elm); \
+ while (VRBT_AUGMENT_CHECK(rb_update_tmp) && \
+ (rb_update_tmp = VRBT_PARENT(rb_update_tmp, field)) != NULL) \
+ ; \
+} while (0)
+
+#define VRBT_SWAP_CHILD(head, par, out, in, field) do { \
+ if (par == NULL) \
VRBT_ROOT(head) = (in); \
- else if ((out) == VRBT_LEFT(VRBT_PARENT(out, field), field)) \
- VRBT_LEFT(VRBT_PARENT(out, field), field) = (in); \
+ else if ((out) == VRBT_LEFT(par, field)) \
+ VRBT_LEFT(par, field) = (in); \
else \
- VRBT_RIGHT(VRBT_PARENT(out, field), field) = (in); \
+ VRBT_RIGHT(par, field) = (in); \
} while (/*CONSTCOND*/ 0)

-#define VRBT_ROTATE_LEFT(head, elm, tmp, field) do { \
- (tmp) = VRBT_RIGHT(elm, field); \
- if ((VRBT_RIGHT(elm, field) = VRBT_LEFT(tmp, field)) != NULL) { \
- VRBT_SET_PARENT(VRBT_RIGHT(elm, field), elm, field); \
- } \
- VRBT_SET_PARENT(tmp, VRBT_PARENT(elm, field), field); \
- VRBT_SWAP_CHILD(head, elm, tmp, field); \
- VRBT_LEFT(tmp, field) = (elm); \
- VRBT_SET_PARENT(elm, tmp, field); \
-} while (/*CONSTCOND*/ 0)
-
-#define VRBT_ROTATE_RIGHT(head, elm, tmp, field) do { \
- (tmp) = VRBT_LEFT(elm, field); \
- if ((VRBT_LEFT(elm, field) = VRBT_RIGHT(tmp, field)) != NULL) { \
- VRBT_SET_PARENT(VRBT_LEFT(elm, field), elm, field); \
- } \
- VRBT_SET_PARENT(tmp, VRBT_PARENT(elm, field), field); \
- VRBT_SWAP_CHILD(head, elm, tmp, field); \
- VRBT_RIGHT(tmp, field) = (elm); \
+/*
+ * VRBT_ROTATE macro partially restructures the tree to improve balance. In the
+ * case when dir is _VRBT_L, tmp is a right child of elm. After rotation, elm
+ * is a left child of tmp, and the subtree that represented the items between
+ * them, which formerly hung to the left of tmp now hangs to the right of elm.
+ * The parent-child relationship between elm and its former parent is not
+ * changed; where this macro once updated those fields, that is now left to the
+ * caller of VRBT_ROTATE to clean up, so that a pair of rotations does not twice
+ * update the same pair of pointer fields with distinct values.
+ */
+#define VRBT_ROTATE(elm, tmp, dir, field) do { \
+ if ((_VRBT_LINK(elm, dir ^ _VRBT_LR, field) = \
+ _VRBT_LINK(tmp, dir, field)) != NULL) \
+ VRBT_SET_PARENT(_VRBT_LINK(tmp, dir, field), elm, field); \
+ _VRBT_LINK(tmp, dir, field) = (elm); \
VRBT_SET_PARENT(elm, tmp, field); \
} while (/*CONSTCOND*/ 0)

@@ -402,35 +414,55 @@ struct { \
#define VRBT_PROTOTYPE_STATIC(name, type, field, cmp) \
VRBT_PROTOTYPE_INTERNAL(name, type, field, cmp, v_unused_ static)
#define VRBT_PROTOTYPE_INTERNAL(name, type, field, cmp, attr) \
+ VRBT_PROTOTYPE_RANK(name, type, attr) \
VRBT_PROTOTYPE_INSERT_COLOR(name, type, attr); \
VRBT_PROTOTYPE_REMOVE_COLOR(name, type, attr); \
+ VRBT_PROTOTYPE_INSERT_FINISH(name, type, attr); \
VRBT_PROTOTYPE_INSERT(name, type, attr); \
VRBT_PROTOTYPE_REMOVE(name, type, attr); \
VRBT_PROTOTYPE_FIND(name, type, attr); \
VRBT_PROTOTYPE_NFIND(name, type, attr); \
VRBT_PROTOTYPE_NEXT(name, type, attr); \
+ VRBT_PROTOTYPE_INSERT_NEXT(name, type, attr); \
VRBT_PROTOTYPE_PREV(name, type, attr); \
+ VRBT_PROTOTYPE_INSERT_PREV(name, type, attr); \
VRBT_PROTOTYPE_MINMAX(name, type, attr); \
VRBT_PROTOTYPE_REINSERT(name, type, attr);
+#ifdef _VRBT_DIAGNOSTIC
+#define VRBT_PROTOTYPE_RANK(name, type, attr) \
+ attr int name##_VRBT_RANK(struct type *);
+#else
+#define VRBT_PROTOTYPE_RANK(name, type, attr)
+#endif
#define VRBT_PROTOTYPE_INSERT_COLOR(name, type, attr) \
- attr void name##_VRBT_INSERT_COLOR(struct name *, struct type *)
+ attr struct type *name##_VRBT_INSERT_COLOR(struct name *, \
+ struct type *, struct type *)
#define VRBT_PROTOTYPE_REMOVE_COLOR(name, type, attr) \
- attr void name##_VRBT_REMOVE_COLOR(struct name *, \
+ attr struct type *name##_VRBT_REMOVE_COLOR(struct name *, \
struct type *, struct type *)
#define VRBT_PROTOTYPE_REMOVE(name, type, attr) \
attr struct type *name##_VRBT_REMOVE(struct name *, struct type *)
+#define VRBT_PROTOTYPE_INSERT_FINISH(name, type, attr) \
+ attr struct type *name##_VRBT_INSERT_FINISH(struct name *, \
+ struct type *, struct type **, struct type *)
#define VRBT_PROTOTYPE_INSERT(name, type, attr) \
attr struct type *name##_VRBT_INSERT(struct name *, struct type *)
#define VRBT_PROTOTYPE_FIND(name, type, attr) \
- attr struct type *name##_VRBT_FIND(const struct name *, const struct type *)
+ attr const struct type *name##_VRBT_FIND(const struct name *, const struct type *)
#define VRBT_PROTOTYPE_NFIND(name, type, attr) \
- attr struct type *name##_VRBT_NFIND(const struct name *, const struct type *)
+ attr struct type *name##_VRBT_NFIND(struct name *, struct type *)
#define VRBT_PROTOTYPE_NEXT(name, type, attr) \
attr struct type *name##_VRBT_NEXT(struct type *)
+#define VRBT_PROTOTYPE_INSERT_NEXT(name, type, attr) \
+ attr struct type *name##_VRBT_INSERT_NEXT(struct name *, \
+ struct type *, struct type *)
#define VRBT_PROTOTYPE_PREV(name, type, attr) \
attr struct type *name##_VRBT_PREV(struct type *)
+#define VRBT_PROTOTYPE_INSERT_PREV(name, type, attr) \
+ attr struct type *name##_VRBT_INSERT_PREV(struct name *, \
+ struct type *, struct type *)
#define VRBT_PROTOTYPE_MINMAX(name, type, attr) \
- attr struct type *name##_VRBT_MINMAX(const struct name *, int)
+ attr const struct type *name##_VRBT_MINMAX(struct name *, int)
#define VRBT_PROTOTYPE_REINSERT(name, type, attr) \
attr struct type *name##_VRBT_REINSERT(struct name *, struct type *)

@@ -442,186 +474,371 @@ struct { \
#define VRBT_GENERATE_STATIC(name, type, field, cmp) \
VRBT_GENERATE_INTERNAL(name, type, field, cmp, v_unused_ static)
#define VRBT_GENERATE_INTERNAL(name, type, field, cmp, attr) \
+ VRBT_GENERATE_RANK(name, type, field, attr) \
VRBT_GENERATE_INSERT_COLOR(name, type, field, attr) \
VRBT_GENERATE_REMOVE_COLOR(name, type, field, attr) \
+ VRBT_GENERATE_INSERT_FINISH(name, type, field, attr) \
VRBT_GENERATE_INSERT(name, type, field, cmp, attr) \
VRBT_GENERATE_REMOVE(name, type, field, attr) \
VRBT_GENERATE_FIND(name, type, field, cmp, attr) \
VRBT_GENERATE_NFIND(name, type, field, cmp, attr) \
VRBT_GENERATE_NEXT(name, type, field, attr) \
+ VRBT_GENERATE_INSERT_NEXT(name, type, field, cmp, attr) \
VRBT_GENERATE_PREV(name, type, field, attr) \
+ VRBT_GENERATE_INSERT_PREV(name, type, field, cmp, attr) \
VRBT_GENERATE_MINMAX(name, type, field, attr) \
VRBT_GENERATE_REINSERT(name, type, field, cmp, attr)

+#ifdef _VRBT_DIAGNOSTIC
+#ifndef VRBT_AUGMENT
+#define _VRBT_AUGMENT_VERIFY(x) VRBT_AUGMENT_CHECK(x)
+#else
+#define _VRBT_AUGMENT_VERIFY(x) 0
+#endif
+#define VRBT_GENERATE_RANK(name, type, field, attr) \
+/* \
+ * Return the rank of the subtree rooted at elm, or -1 if the subtree \
+ * is not rank-balanced, or has inconsistent augmentation data.
+ */ \
+attr int \
+name##_VRBT_RANK(struct type *elm) \
+{ \
+ struct type *left, *right, *up; \
+ int left_rank, right_rank; \
+ \
+ if (elm == NULL) \
+ return (0); \
+ up = _VRBT_UP(elm, field); \
+ left = VRBT_LEFT(elm, field); \
+ left_rank = ((_VRBT_BITS(up) & _VRBT_L) ? 2 : 1) + \
+ name##_VRBT_RANK(left); \
+ right = VRBT_RIGHT(elm, field); \
+ right_rank = ((_VRBT_BITS(up) & _VRBT_R) ? 2 : 1) + \
+ name##_VRBT_RANK(right); \
+ if (left_rank != right_rank || \
+ (left_rank == 2 && left == NULL && right == NULL) || \
+ _VRBT_AUGMENT_VERIFY(elm)) \
+ return (-1); \
+ return (left_rank); \
+}
+#else
+#define VRBT_GENERATE_RANK(name, type, field, attr)
+#endif
+
#define VRBT_GENERATE_INSERT_COLOR(name, type, field, attr) \
-attr void \
-name##_VRBT_INSERT_COLOR(struct name *head, struct type *elm) \
+attr struct type * \
+name##_VRBT_INSERT_COLOR(struct name *head, \
+ struct type *parent, struct type *elm) \
{ \
- struct type *child, *parent; \
- while ((parent = VRBT_PARENT(elm, field)) != NULL) { \
- if (VRBT_LEFT(parent, field) == elm) { \
- if (VRBT_RED_LEFT(parent, field)) { \
- VRBT_FLIP_LEFT(parent, field); \
- return; \
- } \
- VRBT_FLIP_RIGHT(parent, field); \
- if (VRBT_RED_RIGHT(parent, field)) { \
- elm = parent; \
- continue; \
- } \
- if (!VRBT_RED_RIGHT(elm, field)) { \
- VRBT_FLIP_LEFT(elm, field); \
- VRBT_ROTATE_LEFT(head, elm, child, field);\
- if (VRBT_RED_LEFT(child, field)) \
- VRBT_FLIP_RIGHT(elm, field); \
- else if (VRBT_RED_RIGHT(child, field)) \
- VRBT_FLIP_LEFT(parent, field); \
- AN(parent); \
- elm = child; \
- } \
- VRBT_ROTATE_RIGHT(head, parent, elm, field); \
- } else { \
- if (VRBT_RED_RIGHT(parent, field)) { \
- VRBT_FLIP_RIGHT(parent, field); \
- return; \
- } \
- VRBT_FLIP_LEFT(parent, field); \
- if (VRBT_RED_LEFT(parent, field)) { \
- elm = parent; \
- continue; \
- } \
- if (!VRBT_RED_LEFT(elm, field)) { \
- VRBT_FLIP_RIGHT(elm, field); \
- VRBT_ROTATE_RIGHT(head, elm, child, field);\
- if (VRBT_RED_RIGHT(child, field)) \
- VRBT_FLIP_LEFT(elm, field); \
- else if (VRBT_RED_LEFT(child, field)) \
- VRBT_FLIP_RIGHT(parent, field); \
- elm = child; \
- } \
- VRBT_ROTATE_LEFT(head, parent, elm, field); \
+ /* \
+ * Initially, elm is a leaf. Either its parent was previously \
+ * a leaf, with two black null children, or an interior node \
+ * with a black non-null child and a red null child. The \
+ * balance criterion "the rank of any leaf is 1" precludes the \
+ * possibility of two red null children for the initial parent. \
+ * So the first loop iteration cannot lead to accessing an \
+ * uninitialized 'child', and a later iteration can only happen \
+ * when a value has been assigned to 'child' in the previous \
+ * one. \
+ */ \
+ struct type *child = NULL, *child_up, *gpar; \
+ uintptr_t elmdir, sibdir; \
+ \
+ do { \
+ /* the rank of the tree rooted at elm grew */ \
+ gpar = _VRBT_UP(parent, field); \
+ elmdir = VRBT_RIGHT(parent, field) == elm ? _VRBT_R : _VRBT_L; \
+ if (_VRBT_BITS(gpar) & elmdir) { \
+ /* shorten the parent-elm edge to rebalance */ \
+ _VRBT_BITSUP(parent, field) ^= elmdir; \
+ return (NULL); \
} \
- VRBT_BITS(elm, field) &= ~VRBT_RED_MASK; \
- break; \
- } \
+ sibdir = elmdir ^ _VRBT_LR; \
+ /* the other edge must change length */ \
+ _VRBT_BITSUP(parent, field) ^= sibdir; \
+ if ((_VRBT_BITS(gpar) & _VRBT_LR) == 0) { \
+ /* both edges now short, retry from parent */ \
+ child = elm; \
+ elm = parent; \
+ continue; \
+ } \
+ _VRBT_UP(parent, field) = gpar = _VRBT_PTR(gpar); \
+ if (_VRBT_BITSUP(elm, field) & elmdir) { \
+ /* \
+ * Exactly one of the edges descending from elm \
+ * is long. The long one is in the same \
+ * direction as the edge from parent to elm, \
+ * so change that by rotation. The edge from \
+ * parent to z was shortened above. Shorten \
+ * the long edge down from elm, and adjust \
+ * other edge lengths based on the downward \
+ * edges from 'child'. \
+ * \
+ * par par \
+ * ? ? ? ? \
+ * elm z ? z \
+ * ? ? child \
+ * ? child ? ? \
+ * ? ? ? elm ? \
+ * w ? ? ? ? y \
+ * x y w ? \
+ * x \
+ */ \
+ VRBT_ROTATE(elm, child, elmdir, field); \
+ child_up = _VRBT_UP(child, field); \
+ if (_VRBT_BITS(child_up) & sibdir) \
+ _VRBT_BITSUP(parent, field) ^= elmdir; \
+ if (_VRBT_BITS(child_up) & elmdir) \
+ _VRBT_BITSUP(elm, field) ^= _VRBT_LR; \
+ else \
+ _VRBT_BITSUP(elm, field) ^= elmdir; \
+ /* if child is a leaf, don't augment elm, \
+ * since it is restored to be a leaf again. */ \
+ if ((_VRBT_BITS(child_up) & _VRBT_LR) == 0) \
+ elm = child; \
+ } else \
+ child = elm; \
+ \
+ /* \
+ * The long edge descending from 'child' points back \
+ * in the direction of 'parent'. Rotate to make \
+ * 'parent' a child of 'child', then make both edges \
+ * of 'child' short to rebalance. \
+ * \
+ * par child \
+ * ? ? ? ? \
+ * ? z x par \
+ * child ? ? \
+ * ? ? ? z \
+ * x ? y \
+ * y \
+ */ \
+ VRBT_ROTATE(parent, child, sibdir, field); \
+ _VRBT_UP(child, field) = gpar; \
+ VRBT_SWAP_CHILD(head, gpar, parent, child, field); \
+ /* \
+ * Elements rotated down have new, smaller subtrees, \
+ * so update augmentation for them. \
+ */ \
+ if (elm != child) \
+ (void)VRBT_AUGMENT_CHECK(elm); \
+ (void)VRBT_AUGMENT_CHECK(parent); \
+ return (child); \
+ } while ((parent = gpar) != NULL); \
+ return (NULL); \
}

+#ifndef VRBT_STRICT_HST
+/*
+ * In REMOVE_COLOR, the HST paper, in figure 3, in the single-rotate case, has
+ * 'parent' with one higher rank, and then reduces its rank if 'parent' has
+ * become a leaf. This implementation always has the parent in its new position
+ * with lower rank, to avoid the leaf check. Define VRBT_STRICT_HST to 1 to get
+ * the behavior that HST describes.
+ */
+#define VRBT_STRICT_HST 0
+#endif
+
#define VRBT_GENERATE_REMOVE_COLOR(name, type, field, attr) \
-attr void \
+attr struct type * \
name##_VRBT_REMOVE_COLOR(struct name *head, \
struct type *parent, struct type *elm) \
{ \
- struct type *sib; \
- if (VRBT_LEFT(parent, field) == elm && \
- VRBT_RIGHT(parent, field) == elm) { \
- VRBT_BITS(parent, field) &= ~VRBT_RED_MASK; \
+ struct type *gpar, *sib, *up; \
+ uintptr_t elmdir, sibdir; \
+ \
+ if (VRBT_RIGHT(parent, field) == elm && \
+ VRBT_LEFT(parent, field) == elm) { \
+ /* Deleting a leaf that is an only-child creates a \
+ * rank-2 leaf. Demote that leaf. */ \
+ _VRBT_UP(parent, field) = _VRBT_PTR(_VRBT_UP(parent, field)); \
elm = parent; \
- parent = VRBT_PARENT(elm, field); \
- if (parent == NULL) \
- return; \
+ if ((parent = _VRBT_UP(elm, field)) == NULL) \
+ return (NULL); \
} \
- do { \
- if (VRBT_LEFT(parent, field) == elm) { \
- if (!VRBT_RED_LEFT(parent, field)) { \
- VRBT_FLIP_LEFT(parent, field); \
- return; \
- } \
- if (VRBT_RED_RIGHT(parent, field)) { \
- VRBT_FLIP_RIGHT(parent, field); \
- elm = parent; \
- continue; \
- } \
- sib = VRBT_RIGHT(parent, field); \
- if ((~VRBT_BITS(sib, field) & VRBT_RED_MASK) == 0) {\
- VRBT_BITS(sib, field) &= ~VRBT_RED_MASK; \
- elm = parent; \
- continue; \
- } \
- VRBT_FLIP_RIGHT(sib, field); \
- if (VRBT_RED_LEFT(sib, field)) \
- VRBT_FLIP_LEFT(parent, field); \
- else if (!VRBT_RED_RIGHT(sib, field)) { \
- VRBT_FLIP_LEFT(parent, field); \
- VRBT_ROTATE_RIGHT(head, sib, elm, field); \
- if (VRBT_RED_RIGHT(elm, field)) \
- VRBT_FLIP_LEFT(sib, field); \
- if (VRBT_RED_LEFT(elm, field)) \
- VRBT_FLIP_RIGHT(parent, field); \
- VRBT_BITS(elm, field) |= VRBT_RED_MASK; \
- sib = elm; \
- } \
- VRBT_ROTATE_LEFT(head, parent, sib, field); \
+ do { \
+ /* the rank of the tree rooted at elm shrank */ \
+ gpar = _VRBT_UP(parent, field); \
+ elmdir = VRBT_RIGHT(parent, field) == elm ? _VRBT_R : _VRBT_L; \
+ _VRBT_BITS(gpar) ^= elmdir; \
+ if (_VRBT_BITS(gpar) & elmdir) { \
+ /* lengthen the parent-elm edge to rebalance */ \
+ _VRBT_UP(parent, field) = gpar; \
+ return (NULL); \
+ } \
+ if (_VRBT_BITS(gpar) & _VRBT_LR) { \
+ /* shorten other edge, retry from parent */ \
+ _VRBT_BITS(gpar) ^= _VRBT_LR; \
+ _VRBT_UP(parent, field) = gpar; \
+ gpar = _VRBT_PTR(gpar); \
+ continue; \
+ } \
+ sibdir = elmdir ^ _VRBT_LR; \
+ sib = _VRBT_LINK(parent, sibdir, field); \
+ up = _VRBT_UP(sib, field); \
+ _VRBT_BITS(up) ^= _VRBT_LR; \
+ if ((_VRBT_BITS(up) & _VRBT_LR) == 0) { \
+ /* shorten edges descending from sib, retry */ \
+ _VRBT_UP(sib, field) = up; \
+ continue; \
+ } \
+ if ((_VRBT_BITS(up) & sibdir) == 0) { \
+ /* \
+ * The edge descending from 'sib' away from \
+ * 'parent' is long. The short edge descending \
+ * from 'sib' toward 'parent' points to 'elm*' \
+ * Rotate to make 'sib' a child of 'elm*' \
+ * then adjust the lengths of the edges \
+ * descending from 'sib' and 'elm*'. \
+ * \
+ * par par \
+ * ? ? ? ? \
+ * ? sib elm ? \
+ * ? / ? elm* \
+ * elm elm* ? ? ? \
+ * ? ? ? ? ? \
+ * ? ? z ? ? \
+ * x y x sib \
+ * ? ? \
+ * ? z \
+ * y \
+ */ \
+ elm = _VRBT_LINK(sib, elmdir, field); \
+ /* elm is a 1-child. First rotate at elm. */ \
+ VRBT_ROTATE(sib, elm, sibdir, field); \
+ up = _VRBT_UP(elm, field); \
+ _VRBT_BITSUP(parent, field) ^= \
+ (_VRBT_BITS(up) & elmdir) ? _VRBT_LR : elmdir; \
+ _VRBT_BITSUP(sib, field) ^= \
+ (_VRBT_BITS(up) & sibdir) ? _VRBT_LR : sibdir; \
+ _VRBT_BITSUP(elm, field) |= _VRBT_LR; \
} else { \
- if (!VRBT_RED_RIGHT(parent, field)) { \
- VRBT_FLIP_RIGHT(parent, field); \
- return; \
- } \
- if (VRBT_RED_LEFT(parent, field)) { \
- VRBT_FLIP_LEFT(parent, field); \
- elm = parent; \
- continue; \
- } \
- sib = VRBT_LEFT(parent, field); \
- if ((~VRBT_BITS(sib, field) & VRBT_RED_MASK) == 0) {\
- VRBT_BITS(sib, field) &= ~VRBT_RED_MASK; \
- elm = parent; \
- continue; \
- } \
- VRBT_FLIP_LEFT(sib, field); \
- if (VRBT_RED_RIGHT(sib, field)) \
- VRBT_FLIP_RIGHT(parent, field); \
- else if (!VRBT_RED_LEFT(sib, field)) { \
- VRBT_FLIP_RIGHT(parent, field); \
- VRBT_ROTATE_LEFT(head, sib, elm, field); \
- if (VRBT_RED_LEFT(elm, field)) \
- VRBT_FLIP_RIGHT(sib, field); \
- if (VRBT_RED_RIGHT(elm, field)) \
- VRBT_FLIP_LEFT(parent, field); \
- VRBT_BITS(elm, field) |= VRBT_RED_MASK; \
- sib = elm; \
- } \
- VRBT_ROTATE_RIGHT(head, parent, sib, field); \
+ if ((_VRBT_BITS(up) & elmdir) == 0 && \
+ VRBT_STRICT_HST && elm != NULL) { \
+ /* if parent does not become a leaf, \
+ do not demote parent yet. */ \
+ _VRBT_BITSUP(parent, field) ^= sibdir; \
+ _VRBT_BITSUP(sib, field) ^= _VRBT_LR; \
+ } else if ((_VRBT_BITS(up) & elmdir) == 0) { \
+ /* demote parent. */ \
+ _VRBT_BITSUP(parent, field) ^= elmdir; \
+ _VRBT_BITSUP(sib, field) ^= sibdir; \
+ } else \
+ _VRBT_BITSUP(sib, field) ^= sibdir; \
+ elm = sib; \
} \
- break; \
- } while ((parent = VRBT_PARENT(elm, field)) != NULL); \
+ \
+ /* \
+ * The edge descending from 'elm' away from 'parent' \
+ * is short. Rotate to make 'parent' a child of 'elm', \
+ * then lengthen the short edges descending from \
+ * 'parent' and 'elm' to rebalance. \
+ * \
+ * par elm \
+ * ? ? ? ? \
+ * e ? ? ? \
+ * elm ? ? \
+ * ? ? par s \
+ * ? ? ? ? \
+ * ? ? e ? \
+ * x s x \
+ */ \
+ VRBT_ROTATE(parent, elm, elmdir, field); \
+ VRBT_SET_PARENT(elm, gpar, field); \
+ VRBT_SWAP_CHILD(head, gpar, parent, elm, field); \
+ /* \
+ * An element rotated down, but not into the search \
+ * path has a new, smaller subtree, so update \
+ * augmentation for it. \
+ */ \
+ if (sib != elm) \
+ (void)VRBT_AUGMENT_CHECK(sib); \
+ return (parent); \
+ } while (elm = parent, (parent = gpar) != NULL); \
+ return (NULL); \
}

+#define _VRBT_AUGMENT_WALK(elm, match, field) \
+do { \
+ if (match == elm) \
+ match = NULL; \
+} while (VRBT_AUGMENT_CHECK(elm) && \
+ (elm = VRBT_PARENT(elm, field)) != NULL)
+
#define VRBT_GENERATE_REMOVE(name, type, field, attr) \
attr struct type * \
-name##_VRBT_REMOVE(struct name *head, struct type *elm) \
+name##_VRBT_REMOVE(struct name *head, struct type *out) \
{ \
- struct type *child, *old, *parent, *right; \
+ struct type *child = NULL, *in, *opar, *parent; \
\
- old = elm; \
- parent = VRBT_PARENT(elm, field); \
- right = VRBT_RIGHT(elm, field); \
- if (VRBT_LEFT(elm, field) == NULL) \
- elm = child = right; \
- else if (right == NULL) \
- elm = child = VRBT_LEFT(elm, field); \
- else { \
- if ((child = VRBT_LEFT(right, field)) == NULL) { \
- child = VRBT_RIGHT(right, field); \
- VRBT_RIGHT(old, field) = child; \
- parent = elm = right; \
- } else { \
- do \
- elm = child; \
- while ((child = VRBT_LEFT(elm, field)) != NULL); \
- child = VRBT_RIGHT(elm, field); \
- parent = VRBT_PARENT(elm, field); \
+ child = VRBT_LEFT(out, field); \
+ in = VRBT_RIGHT(out, field); \
+ opar = _VRBT_UP(out, field); \
+ if (in == NULL || child == NULL) { \
+ in = child = (in == NULL ? child : in); \
+ parent = opar = _VRBT_PTR(opar); \
+ } else { \
+ parent = in; \
+ while (VRBT_LEFT(in, field)) \
+ in = VRBT_LEFT(in, field); \
+ VRBT_SET_PARENT(child, in, field); \
+ VRBT_LEFT(in, field) = child; \
+ child = VRBT_RIGHT(in, field); \
+ if (parent != in) { \
+ VRBT_SET_PARENT(parent, in, field); \
+ VRBT_RIGHT(in, field) = parent; \
+ parent = VRBT_PARENT(in, field); \
VRBT_LEFT(parent, field) = child; \
- VRBT_SET_PARENT(VRBT_RIGHT(old, field), elm, field);\
} \
- VRBT_SET_PARENT(VRBT_LEFT(old, field), elm, field); \
- elm->field = old->field; \
+ _VRBT_UP(in, field) = opar; \
+ opar = _VRBT_PTR(opar); \
} \
- VRBT_SWAP_CHILD(head, old, elm, field); \
+ VRBT_SWAP_CHILD(head, opar, out, in, field); \
if (child != NULL) \
- VRBT_SET_PARENT(child, parent, field); \
+ _VRBT_UP(child, field) = parent; \
+ if (parent != NULL) { \
+ opar = name##_VRBT_REMOVE_COLOR(head, parent, child); \
+ /* if rotation has made 'parent' the root of the same \
+ * subtree as before, don't re-augment it. */ \
+ if (parent == in && VRBT_LEFT(parent, field) == NULL) { \
+ opar = NULL; \
+ parent = VRBT_PARENT(parent, field); \
+ } \
+ _VRBT_AUGMENT_WALK(parent, opar, field); \
+ if (opar != NULL) { \
+ /* \
+ * Elements rotated into the search path have \
+ * changed subtrees, so update augmentation for \
+ * them if AUGMENT_WALK didn't. \
+ */ \
+ (void)VRBT_AUGMENT_CHECK(opar); \
+ (void)VRBT_AUGMENT_CHECK(VRBT_PARENT(opar, field)); \
+ } \
+ } \
+ return (out); \
+}
+
+#define VRBT_GENERATE_INSERT_FINISH(name, type, field, attr) \
+/* Inserts a node into the RB tree */ \
+attr struct type * \
+name##_VRBT_INSERT_FINISH(struct name *head, struct type *parent, \
+ struct type **pptr, struct type *elm) \
+{ \
+ struct type *tmp = NULL; \
+ \
+ VRBT_SET(elm, parent, field); \
+ *pptr = elm; \
if (parent != NULL) \
- name##_VRBT_REMOVE_COLOR(head, parent, child); \
- return (old); \
+ tmp = name##_VRBT_INSERT_COLOR(head, parent, elm); \
+ _VRBT_AUGMENT_WALK(elm, tmp, field); \
+ if (tmp != NULL) \
+ /* \
+ * An element rotated into the search path has a \
+ * changed subtree, so update augmentation for it if \
+ * AUGMENT_WALK didn't. \
+ */ \
+ (void)VRBT_AUGMENT_CHECK(tmp); \
+ return (NULL); \
}

#define VRBT_GENERATE_INSERT(name, type, field, cmp, attr) \
@@ -630,28 +847,20 @@ attr struct type * \
name##_VRBT_INSERT(struct name *head, struct type *elm) \
{ \
struct type *tmp; \
+ struct type **tmpp = &VRBT_ROOT(head); \
struct type *parent = NULL; \
- int comp = 0; \
- tmp = VRBT_ROOT(head); \
- while (tmp) { \
+ \
+ while ((tmp = *tmpp) != NULL) { \
parent = tmp; \
- comp = (cmp)(elm, parent); \
+ __typeof(cmp(NULL, NULL)) comp = (cmp)(elm, parent); \
if (comp < 0) \
- tmp = VRBT_LEFT(tmp, field); \
+ tmpp = &VRBT_LEFT(parent, field); \
else if (comp > 0) \
- tmp = VRBT_RIGHT(tmp, field); \
+ tmpp = &VRBT_RIGHT(parent, field); \
else \
- return (tmp); \
+ return (parent); \
} \
- VRBT_SET(elm, parent, field); \
- if (parent == NULL) \
- VRBT_ROOT(head) = elm; \
- else if (comp < 0) \
- VRBT_LEFT(parent, field) = elm; \
- else \
- VRBT_RIGHT(parent, field) = elm; \
- name##_VRBT_INSERT_COLOR(head, elm); \
- return (NULL); \
+ return (name##_VRBT_INSERT_FINISH(head, parent, tmpp, elm)); \
}

#define VRBT_GENERATE_FIND(name, type, field, cmp, attr) \
@@ -660,7 +869,7 @@ attr struct type * \
name##_VRBT_FIND(const struct name *head, const struct type *elm) \
{ \
struct type *tmp = VRBT_ROOT(head); \
- int comp; \
+ __typeof(cmp(NULL, NULL)) comp; \
while (tmp) { \
comp = cmp(elm, tmp); \
if (comp < 0) \
@@ -676,11 +885,11 @@ name##_VRBT_FIND(const struct name *head, const struct type *elm) \
#define VRBT_GENERATE_NFIND(name, type, field, cmp, attr) \
/* Finds the first node greater than or equal to the search key */ \
attr struct type * \
-name##_VRBT_NFIND(const struct name *head, const struct type *elm) \
+name##_VRBT_NFIND(struct name *head, struct type *elm) \
{ \
struct type *tmp = VRBT_ROOT(head); \
struct type *res = NULL; \
- int comp; \
+ __typeof(cmp(NULL, NULL)) comp; \
while (tmp) { \
comp = cmp(elm, tmp); \
if (comp < 0) { \
@@ -705,19 +914,41 @@ name##_VRBT_NEXT(struct type *elm) \
while (VRBT_LEFT(elm, field)) \
elm = VRBT_LEFT(elm, field); \
} else { \
- if (VRBT_PARENT(elm, field) && \
- (elm == VRBT_LEFT(VRBT_PARENT(elm, field), field))) \
- elm = VRBT_PARENT(elm, field); \
- else { \
- while (VRBT_PARENT(elm, field) && \
- (elm == VRBT_RIGHT(VRBT_PARENT(elm, field), field)))\
- elm = VRBT_PARENT(elm, field); \
+ while (VRBT_PARENT(elm, field) && \
+ (elm == VRBT_RIGHT(VRBT_PARENT(elm, field), field))) \
elm = VRBT_PARENT(elm, field); \
- } \
+ elm = VRBT_PARENT(elm, field); \
} \
return (elm); \
}

+#if defined(_KERNEL) && defined(DIAGNOSTIC)
+#define _VRBT_ORDER_CHECK(cmp, lo, hi) do { \
+ KASSERT((cmp)(lo, hi) < 0, ("out of order insertion")); \
+} while (0)
+#else
+#define _VRBT_ORDER_CHECK(cmp, lo, hi) do {} while (0)
+#endif
+
+#define VRBT_GENERATE_INSERT_NEXT(name, type, field, cmp, attr) \
+/* Inserts a node into the next position in the RB tree */ \
+attr struct type * \
+name##_VRBT_INSERT_NEXT(struct name *head, \
+ struct type *elm, struct type *next) \
+{ \
+ struct type *tmp; \
+ struct type **tmpp = &VRBT_RIGHT(elm, field); \
+ \
+ _VRBT_ORDER_CHECK(cmp, elm, next); \
+ if (name##_VRBT_NEXT(elm) != NULL) \
+ _VRBT_ORDER_CHECK(cmp, next, name##_VRBT_NEXT(elm)); \
+ while ((tmp = *tmpp) != NULL) { \
+ elm = tmp; \
+ tmpp = &VRBT_LEFT(elm, field); \
+ } \
+ return (name##_VRBT_INSERT_FINISH(head, elm, tmpp, next)); \
+}
+
#define VRBT_GENERATE_PREV(name, type, field, attr) \
/* ARGSUSED */ \
attr struct type * \
@@ -728,19 +959,33 @@ name##_VRBT_PREV(struct type *elm) \
while (VRBT_RIGHT(elm, field)) \
elm = VRBT_RIGHT(elm, field); \
} else { \
- if (VRBT_PARENT(elm, field) && \
- (elm == VRBT_RIGHT(VRBT_PARENT(elm, field), field))) \
- elm = VRBT_PARENT(elm, field); \
- else { \
- while (VRBT_PARENT(elm, field) && \
- (elm == VRBT_LEFT(VRBT_PARENT(elm, field), field)))\
- elm = VRBT_PARENT(elm, field); \
+ while (VRBT_PARENT(elm, field) && \
+ (elm == VRBT_LEFT(VRBT_PARENT(elm, field), field))) \
elm = VRBT_PARENT(elm, field); \
- } \
+ elm = VRBT_PARENT(elm, field); \
} \
return (elm); \
}

+#define VRBT_GENERATE_INSERT_PREV(name, type, field, cmp, attr) \
+/* Inserts a node into the prev position in the RB tree */ \
+attr struct type * \
+name##_VRBT_INSERT_PREV(struct name *head, \
+ struct type *elm, struct type *prev) \
+{ \
+ struct type *tmp; \
+ struct type **tmpp = &VRBT_LEFT(elm, field); \
+ \
+ _VRBT_ORDER_CHECK(cmp, prev, elm); \
+ if (name##_VRBT_PREV(elm) != NULL) \
+ _VRBT_ORDER_CHECK(cmp, name##_VRBT_PREV(elm), prev); \
+ while ((tmp = *tmpp) != NULL) { \
+ elm = tmp; \
+ tmpp = &VRBT_RIGHT(elm, field); \
+ } \
+ return (name##_VRBT_INSERT_FINISH(head, elm, tmpp, prev)); \
+}
+
#define VRBT_GENERATE_MINMAX(name, type, field, attr) \
attr struct type * \
name##_VRBT_MINMAX(const struct name *head, int val) \
@@ -777,6 +1022,8 @@ name##_VRBT_REINSERT(struct name *head, struct type *elm) \
#define VRBT_INF 1

#define VRBT_INSERT(name, x, y) name##_VRBT_INSERT(x, y)
+#define VRBT_INSERT_NEXT(name, x, y, z) name##_VRBT_INSERT_NEXT(x, y, z)
+#define VRBT_INSERT_PREV(name, x, y, z) name##_VRBT_INSERT_PREV(x, y, z)
#define VRBT_REMOVE(name, x, y) name##_VRBT_REMOVE(x, y)
#define VRBT_FIND(name, x, y) name##_VRBT_FIND(x, y)
#define VRBT_NFIND(name, x, y) name##_VRBT_NFIND(x, y)
diff --git a/lib/libvarnishapi/vsl_dispatch.c b/lib/libvarnishapi/vsl_dispatch.c
index cf0683606..361407f1b 100644
--- a/lib/libvarnishapi/vsl_dispatch.c
+++ b/lib/libvarnishapi/vsl_dispatch.c
@@ -232,6 +232,7 @@ vtx_keycmp(const struct vtx_key *a, const struct vtx_key *b)
VRBT_GENERATE_REMOVE_COLOR(vtx_tree, vtx_key, entry, static)
VRBT_GENERATE_REMOVE(vtx_tree, vtx_key, entry, static)
VRBT_GENERATE_INSERT_COLOR(vtx_tree, vtx_key, entry, static)
+VRBT_GENERATE_INSERT_FINISH(vtx_tree, vtx_key, entry, static)
VRBT_GENERATE_INSERT(vtx_tree, vtx_key, entry, vtx_keycmp, static)
VRBT_GENERATE_FIND(vtx_tree, vtx_key, entry, vtx_keycmp, static)

diff --git a/lib/libvcc/vcc_acl.c b/lib/libvcc/vcc_acl.c
index 811f0bf3b..818693670 100644
--- a/lib/libvcc/vcc_acl.c
+++ b/lib/libvcc/vcc_acl.c
@@ -150,6 +150,7 @@ vcl_acl_disjoint(const struct acl_e *ae1, const struct acl_e *ae2)
}

VRBT_GENERATE_INSERT_COLOR(acl_tree, acl_e, branch, static)
+VRBT_GENERATE_INSERT_FINISH(acl_tree, acl_e, branch, static)
VRBT_GENERATE_INSERT(acl_tree, acl_e, branch, vcl_acl_cmp, static)
VRBT_GENERATE_MINMAX(acl_tree, acl_e, branch, static)
VRBT_GENERATE_NEXT(acl_tree, acl_e, branch, static)
_______________________________________________
varnish-commit mailing list
varnish-commit@varnish-cache.org
https://www.varnish-cache.org/lists/mailman/listinfo/varnish-commit