Mailing List Archive

commit bb401ab31d82f4332b38fbfc7beaf4d7143ef9ff
Author: Nils Goroll <nils.goroll@uplex.de>
Date: Wed Nov 10 14:07:32 2021 +0100

vtree.h: remove red/black tree augmentation entirely

As agreed with phk

diff --git a/include/vtree.h b/include/vtree.h
index b4913c8ea..325a2cb1f 100644
--- a/include/vtree.h
+++ b/include/vtree.h
@@ -365,23 +365,6 @@ struct { \
VRBT_RED_LEFT(VRBT_PARENT(elm, field), field) : \
VRBT_RED_RIGHT(VRBT_PARENT(elm, field), field))

-/*
- * Something to be invoked in a loop at the root of every modified subtree,
- * from the bottom up to the root, to update augmented node data.
- */
-#ifndef VRBT_AUGMENT
-#define VRBT_AUGMENT(x) do {} while (0)
-#define VRBT_AUGMENT_UP(x) do {} while (0)
-#else
-#define VRBT_AUGMENT_UP(x) \
- do { \
- while((x) != NULL) { \
- VRBT_AUGMENT(x); \
- x = VRBT_PARENT(x, field); \
- } \
- } while (0)
-#endif
-
#define VRBT_SWAP_CHILD(head, out, in, field) do { \
if (VRBT_PARENT(out, field) == NULL) \
VRBT_ROOT(head) = (in); \
@@ -400,7 +383,6 @@ struct { \
VRBT_SWAP_CHILD(head, elm, tmp, field); \
VRBT_LEFT(tmp, field) = (elm); \
VRBT_SET_PARENT(elm, tmp, field); \
- VRBT_AUGMENT(elm); \
} while (/*CONSTCOND*/ 0)

#define VRBT_ROTATE_RIGHT(head, elm, tmp, field) do { \
@@ -412,7 +394,6 @@ struct { \
VRBT_SWAP_CHILD(head, elm, tmp, field); \
VRBT_RIGHT(tmp, field) = (elm); \
VRBT_SET_PARENT(elm, tmp, field); \
- VRBT_AUGMENT(elm); \
} while (/*CONSTCOND*/ 0)

/* Generates prototypes and inline functions */
@@ -640,7 +621,6 @@ name##_VRBT_REMOVE(struct name *head, struct type *elm) \
VRBT_SET_PARENT(child, parent, field); \
if (parent != NULL) \
name##_VRBT_REMOVE_COLOR(head, parent, child); \
- VRBT_AUGMENT_UP(parent); \
return (old); \
}

@@ -671,7 +651,6 @@ name##_VRBT_INSERT(struct name *head, struct type *elm) \
else \
VRBT_RIGHT(parent, field) = elm; \
name##_VRBT_INSERT_COLOR(head, elm); \
- VRBT_AUGMENT_UP(elm); \
return (NULL); \
}

_______________________________________________
varnish-commit mailing list
varnish-commit@varnish-cache.org
https://www.varnish-cache.org/lists/mailman/listinfo/varnish-commit