[MINOR] import ul2tree from old librt project
This is an import of the old ul2tree code as well as required bitops.
All of them will have to be refreshed at one moment.
diff --git a/include/import/tree.h b/include/import/tree.h
new file mode 100644
index 0000000..0ae6fb4
--- /dev/null
+++ b/include/import/tree.h
@@ -0,0 +1,731 @@
+/*
+ * tree.h : tree manipulation macros and structures.
+ * (C) 2002 - Willy Tarreau - willy@ant-computing.com
+ *
+ */
+
+#ifndef __TREE_H__
+#define __TREE_H__
+
+#include <import/bitops.h>
+#include <common/memory.h>
+
+/* binary tree node : either 32 bits unsigned long int values, or
+ * 64 bits in two 32 bits unsigned long int values
+ */
+struct ultree {
+ unsigned long low; /* 32 bits low value of this node */
+ unsigned long high; /* 32 bits high value of this node, not used in 32 bits */
+ int level; /* bit level of this node */
+ void *data; /* carried data */
+ struct ultree *left, *right; /* children : left and right. NULL = leaf */
+ struct ultree *up; /* parent node. NULL = root */
+};
+
+/* binary tree node : 64 bits unsigned long long values */
+struct ulltree {
+ unsigned long long value; /* 64 bits value of this node */
+ int level; /* bit level of this node */
+ void *data; /* carried data */
+ struct ulltree *left, *right; /* children : left and right. NULL = leaf */
+ struct ulltree *up; /* parent node. NULL = root */
+};
+
+/* binary tree node : 64 bits in either one ull or two 32 bits unsigned long int values. This
+ * is the common type for all the above trees, which should be cast into it. This makes
+ * pool_free() far simpler since all types share a same pool.
+ */
+struct tree64 {
+ union {
+ struct {
+ unsigned long low; /* 32 bits low value of this node */
+ unsigned long high; /* 32 bits high value of this node */
+ } ul;
+ struct {
+ unsigned long long value; /* 64 bits value of this node */
+ } ull;
+ } value;
+ int level; /* bit level of this node */
+ void *data; /* carried data */
+ struct tree64 *left, *right; /* children : left and right. NULL = leaf */
+ struct tree64 *up; /* parent node. NULL = root */
+};
+
+#define sizeof_tree64 (sizeof (struct tree64))
+extern void **pool_tree64;
+
+static int node_right_lookup, node_lookup;
+
+#define ULTREE_HEAD(l) struct ultree (l) = { .left=NULL, .right=NULL, .up=NULL, .low=0, .level=LONGBITS, .data=NULL }
+#define ULTREE_INIT(l) { (l)->data = (l)->left = (l)->right = NULL; }
+#define ULTREE_INIT_ROOT(l) { (l)->left=(l)->right=(l)->up=(l)->data=NULL; (l)->low=0; (l)->level=LONGBITS; }
+
+#define ULLTREE_HEAD(l) struct ulltree (l) = { .left=NULL, .right=NULL, .up=NULL, .value=0, .level=LLONGBITS, .data=NULL }
+#define ULLTREE_INIT(l) { (l)->data = (l)->left = (l)->right = NULL; }
+#define ULLTREE_INIT_ROOT(l) { (l)->left=(l)->right=(l)->up=(l)->data=NULL; (l)->value=0; (l)->level=LLONGBITS; }
+
+#define UL2TREE_HEAD(l) struct ultree (l) = { .left=NULL, .right=NULL, .up=NULL, .high=0, .low=0, .level=LLONGBITS, .data=NULL }
+#define UL2TREE_INIT(l) { (l)->left = (l)->right = (l)->data = NULL; }
+#define UL2TREE_INIT_ROOT(l) { (l)->left=(l)->right=(l)->up=(l)->data=NULL; (l)->high=(l)->low=0; (l)->level=LLONGBITS; }
+
+/*
+ * inserts necessary nodes to reach <x> in tree starting at <root>. The node
+ * is not created if it exists. It is returned.
+ */
+inline static struct ulltree *__ulltree_insert(struct ulltree *root, unsigned long long x) {
+ int m;
+ struct ulltree *next, *new, *node;
+ struct ulltree **branch;
+ int ffs;
+
+ next = root;
+ ffs = ffs_fast64(x);
+
+ do {
+ root = next;
+
+ if (x == next->value) {
+ return next;
+ }
+
+ if (x & (1ULL << (next->level - 1))) { /* right branch */
+ branch = &next->right;
+ next = *branch;
+ } else {
+ branch = &next->left;
+ next = *branch;
+ }
+
+ if (next == NULL) {
+ /* we'll have to insert our node here */
+ *branch = new = (struct ulltree *)pool_alloc(tree64);
+ ULLTREE_INIT(new);
+ new->up = root;
+ new->value = x;
+ new->level = ffs;
+ return new;
+ }
+
+ /* we'll keep walking down as long as we have all bits in common */
+ } while ((x & ~((1ULL << next->level) - 1)) == next->value);
+
+
+ /* ok, now we know that we must insert between both. */
+
+ /* the new interconnect node */
+ *branch = node = (struct ulltree *)pool_alloc(tree64); /* was <next> */
+ ULLTREE_INIT(node);
+ node->up = root;
+ next->up = node;
+
+ /* we need the common higher bits between x and next->value. */
+
+ /* what differences are there between x and the node here ?
+ * NOTE that m is always < level(parent) because highest bit
+ * of x and next-value are identical here (else they would be
+ * on a different branch).
+ */
+ m = fls_fast64(x ^ next->value) + 1; /* m = lowest identical bit */
+ node->value = x & ~((1ULL << m) - 1); /* value of common bits */
+
+ if (node->value == x) { /* <x> is exactly on this node */
+ /* we must set its real position (eg: 8,10 => m=1 => val=8, m=3)*/
+ node->level = ffs;
+
+ if (next->value & (1ULL << (node->level - 1))) /* right branch */
+ node->right = next;
+ else
+ node->left = next;
+ return node;
+ }
+
+ /* the new leaf now */
+ node->level = m; /* set the level to the lowest common bit */
+ new = (struct ulltree *)pool_alloc(tree64);
+ ULLTREE_INIT(new);
+ new->value = x;
+ new->level = ffs;
+
+ if (x > next->value) {
+ node->left = next;
+ node->right = new;
+ }
+ else {
+ node->left = new;
+ node->right = next;
+ }
+ new->up = node;
+ return new;
+}
+
+/*
+ * inserts necessary nodes to reach <x> in tree starting at <root>. The node
+ * is not created if it exists. It is returned.
+ */
+inline static struct ultree *__ultree_insert(struct ultree *root, unsigned long x) {
+ int m;
+ struct ultree *next, *new, *node;
+ struct ultree **branch;
+ int ffs;
+
+ next = root;
+ ffs = ffs_fast32(x);
+
+ do {
+ root = next;
+
+ if (x == next->low) {
+ return next;
+ }
+
+ if ((x >> (next->level - 1)) & 1) { /* right branch */
+ branch = &next->right;
+ next = *branch;
+ } else {
+ branch = &next->left;
+ next = *branch;
+ }
+
+ if (next == NULL) {
+ /* we'll have to insert our node here */
+ *branch = new = (struct ultree *)pool_alloc(tree64);
+ ULTREE_INIT(new);
+ new->up = root;
+ new->low = x;
+ new->level = ffs;
+ return new;
+ }
+
+ /* we'll keep walking down as long as we have all bits in common */
+ } while ((x & ~((1 << next->level) - 1)) == next->low);
+
+ /* ok, now we know that we must insert between both. */
+
+ /* the new interconnect node */
+ *branch = node = (struct ultree *)pool_alloc(tree64); /* was <next> */
+ ULTREE_INIT(node);
+ node->up = root;
+ next->up = node;
+
+ /* we need the common higher bits between x and next->low. */
+
+ /* what differences are there between x and the node here ?
+ * NOTE that m is always < level(parent) because highest bit
+ * of x and next->low are identical here (else they would be
+ * on a different branch).
+ */
+ m = fls_fast32(x ^ next->low) + 1; /* m = lower identical bit */
+ node->low = x & ~((1 << m) - 1); /* value of common bits */
+
+ if (node->low == x) { /* <x> is exactly on this node */
+ /* we must set its real position (eg: 8,10 => m=1 => val=8, m=3)*/
+ node->level = ffs;
+
+ if (next->low & (1 << (node->level - 1))) /* right branch */
+ node->right = next;
+ else
+ node->left = next;
+ return node;
+ }
+
+ /* the new leaf now */
+ node->level = m; /* set the level to the lowest common bit */
+ new = (struct ultree *)pool_alloc(tree64);
+ ULTREE_INIT(new);
+ new->low = x;
+ new->level = ffs;
+
+ if (x > next->low) {
+ node->left = next;
+ node->right = new;
+ }
+ else {
+ node->left = new;
+ node->right = next;
+ }
+ new->up = node;
+ return new;
+}
+
+
+/*
+ * inserts necessary nodes to reach <h:l> in tree starting at <root>. The node
+ * is not created if it exists. It is returned.
+ */
+inline static struct ultree *__ul2tree_insert(struct ultree *root, unsigned long h, unsigned long l) {
+ int m;
+ struct ultree *next, *new, *node;
+ struct ultree **branch;
+
+ next = root;
+
+ do {
+ root = next;
+
+ if (h == next->high && l == next->low) {
+ return next;
+ }
+
+ branch = &next->left;
+ if (next->level >= 33) {
+ if ((h >> (next->level - 33)) & 1) { /* right branch */
+ branch = &next->right;
+ node_right_lookup++;
+ }
+ }
+ else {
+ if ((l >> (next->level - 1)) & 1) { /* right branch */
+ branch = &next->right;
+ node_right_lookup++;
+ }
+ }
+ next = *branch;
+
+ node_lookup++;
+ if (next == NULL) {
+ /* we'll have to insert our node here */
+ *branch = new =(struct ultree *)pool_alloc(tree64);
+ UL2TREE_INIT(new);
+ new->up = root;
+ new->high = h;
+ new->low = l;
+ if (l)
+ new->level = __ffs_fast32(l);
+ else
+ new->level = __ffs_fast32(h) + 32;
+
+ return new;
+ }
+
+ /* we'll keep walking down as long as we have all bits in common */
+ if (next->level >= 32) {
+ if ((h & ~((1 << (next->level-32)) - 1)) != next->high)
+ break;
+ }
+ else {
+ if (h != next->high)
+ break;
+ if ((l & ~((1 << next->level) - 1)) != next->low)
+ break;
+ }
+ } while (1);
+
+ /* ok, now we know that we must insert between both. */
+
+ /* the new interconnect node */
+ *branch = node = (struct ultree *)pool_alloc(tree64); /* was <next> */
+ UL2TREE_INIT(node);
+ node->up = root;
+ next->up = node;
+
+ /* we need the common higher bits between x and next->high:low. */
+
+ /* what differences are there between x and the node here ?
+ * NOTE that m is always < level(parent) because highest bit
+ * of x and next->high:low are identical here (else they would be
+ * on a different branch).
+ */
+ if (h != next->high) {
+ m = fls_fast32(h ^ next->high) + 1; /* m = lower identical bit */
+ node->high = h & ~((1 << m) - 1); /* value of common bits */
+ m += 32;
+ node->low = 0;
+ } else {
+ node->high = h;
+ m = fls_fast32(l ^ next->low) + 1; /* m = lower identical bit */
+ node->low = l & ~((1 << m) - 1); /* value of common bits */
+ }
+
+ if (node->high == h && node->low == l) { /* <h:l> is exactly on this node */
+ /* we must set its real position (eg: 8,10 => m=1 => val=8, m=3)*/
+ if (l) {
+ node->level = ffs_fast32(l);
+ if (next->low & (1 << (node->level - 1))) /* right branch */
+ node->right = next;
+ else
+ node->left = next;
+ }
+ else {
+ node->level = ffs_fast32(h) + 32;
+ if (next->high & (1 << (node->level - 33))) /* right branch */
+ node->right = next;
+ else
+ node->left = next;
+ }
+ return node;
+ }
+
+ /* the new leaf now */
+ node->level = m; /* set the level to the lowest common bit */
+ new = (struct ultree *)pool_alloc(tree64);
+ UL2TREE_INIT(new);
+ new->high = h;
+ new->low = l;
+ if (l)
+ new->level = __ffs_fast32(l);
+ else
+ new->level = __ffs_fast32(h) + 32;
+
+ if (h > next->high || (h == next->high && l > next->low)) {
+ node->left = next;
+ node->right = new;
+ }
+ else {
+ node->left = new;
+ node->right = next;
+ }
+ new->up = node;
+ return new;
+}
+
+
+/*
+ * finds a value in the tree <root>. If it cannot be found, NULL is returned.
+ */
+inline static struct ultree *__ultree_find(struct ultree *root, unsigned long x) {
+ do {
+ if (x == root->low)
+ return root;
+
+ if ((x >> (root->level - 1)) & 1)
+ root = root->right;
+ else
+ root = root->left;
+
+ if (root == NULL)
+ return NULL;
+
+ /* we'll keep walking down as long as we have all bits in common */
+ } while ((x & ~((1 << root->level) - 1)) == root->low);
+
+ /* should be there, but nothing. */
+ return NULL;
+}
+
+/*
+ * finds a value in the tree <root>. If it cannot be found, NULL is returned.
+ */
+inline static struct ulltree *__ulltree_find(struct ulltree *root, unsigned long long x) {
+ do {
+ if (x == root->value)
+ return root;
+
+ if ((x >> (root->level - 1)) & 1)
+ root = root->right;
+ else
+ root = root->left;
+
+ if (root == NULL)
+ return NULL;
+
+ /* we'll keep walking down as long as we have all bits in common */
+ } while ((x & ~((1ULL << root->level) - 1)) == root->value);
+
+ /* should be there, but nothing. */
+ return NULL;
+}
+
+
+/*
+ * walks down the tree <__root> and assigns each of its data to <__data>.
+ * <__stack> is an int array of at least N entries where N is the maximum number
+ * of levels of the tree. <__slen> is an integer variable used as a stack index.
+ * The instruction following the foreach statement is executed for each data,
+ * after the data has been unlinked from the tree.
+ * The nodes are deleted automatically, so it is illegal to manually delete a
+ * node within this loop.
+ */
+#define tree64_foreach_destructive(__root, __data, __stack, __slen) \
+ for (__slen = 0, __stack[0] = __root, __data = NULL; ({ \
+ __label__ __left, __right, __again, __end; \
+ typeof(__root) __ptr = __stack[__slen]; \
+__again: \
+ __data = __ptr->data; \
+ if (__data != NULL) { \
+ __ptr->data = NULL; \
+ goto __end; \
+ } \
+ else if (__ptr->left != NULL) { \
+ __stack[++__slen] = __ptr = __ptr->left; \
+ goto __again; \
+ } \
+ else \
+__left: \
+ if (__ptr->right != NULL) { \
+ __stack[++__slen] = __ptr = __ptr->right; \
+ goto __again; \
+ } \
+ else \
+__right: \
+ if (!__slen--) \
+ goto __end; /* nothing left, don't delete the root node */ \
+ else { \
+ typeof (__root) __old; \
+ pool_free(tree64, __ptr); \
+ __old = __ptr; \
+ __ptr = __stack[__slen]; \
+ if (__ptr->left == __old) { \
+ /* unlink this node from its parent */ \
+ __ptr->left = NULL; \
+ goto __left; \
+ } \
+ else { \
+ /* no need to unlink, the parent will also die */ \
+ goto __right; \
+ } \
+ } \
+__end: \
+ (__slen >= 0); /* nothing after loop */}); )
+
+
+/*
+ * walks down the tree <__root> of type <__type> and assigns each of its data
+ * to <__data>. <__stack> is an int array of at least N entries where N is the
+ * maximum number of levels of the tree. <__slen> is an integer variable used
+ * as a stack index. The instruction following the foreach statement is
+ * executed for each data, after the data has been unlinked from the tree.
+ */
+#define tree_foreach_destructive(__type, __root, __data, __stack, __slen) \
+ for (__slen = 0, __stack[0] = __root, __data = NULL; ({ \
+ __label__ __left, __right, __again, __end; \
+ typeof(__root) __ptr = __stack[__slen]; \
+__again: \
+ __data = __ptr->data; \
+ if (__data != NULL) { \
+ __ptr->data = NULL; \
+ goto __end; \
+ } \
+ else if (__ptr->left != NULL) { \
+ __stack[++__slen] = __ptr = __ptr->left; \
+ goto __again; \
+ } \
+ else \
+__left: \
+ if (__ptr->right != NULL) { \
+ __stack[++__slen] = __ptr = __ptr->right; \
+ goto __again; \
+ } \
+ else \
+__right: \
+ if (!__slen--) \
+ goto __end; /* nothing left, don't delete the root node */ \
+ else { \
+ typeof (__root) __old; \
+ pool_free(__type, __ptr); \
+ __old = __ptr; \
+ __ptr = __stack[__slen]; \
+ if (__ptr->left == __old) { \
+ /* unlink this node from its parent */ \
+ __ptr->left = NULL; \
+ goto __left; \
+ } \
+ else { \
+ /* no need to unlink, the parent will also die */ \
+ goto __right; \
+ } \
+ } \
+__end: \
+ (__slen >= 0); /* nothing after loop */}); )
+
+
+/*
+ * walks down the tree <__root> and assigns <__data> a pointer to each of its
+ * data pointers. <__stack> is an int array of at least N entries where N is the
+ * maximum number of levels of the tree. <__slen> is an integer variable used as
+ * a stack index. The instruction following the foreach statement is executed
+ * for each data.
+ * The tree will walk down only when the data field is empty (NULL), so it
+ * allows inner breaks, and will restart without losing items. The nodes data
+ * will be set to NULL after the inner code, or when the inner code does
+ * '__stack[__slen]->data = NULL';
+ * The nodes are deleted automatically, so it is illegal to manually delete a
+ * node within this loop.
+ */
+#define tree64_foreach(__root, __data, __stack, __slen) \
+ for (__slen = 0, __stack[0] = __root, __data = NULL; ({ \
+ __label__ __left, __right, __again, __end; \
+ typeof(__root) __ptr = __stack[__slen]; \
+__again: \
+ if (__ptr->data != NULL) { \
+ __data = __ptr->data; \
+ goto __end; \
+ } \
+ else if (__ptr->left != NULL) { \
+ __stack[++__slen] = __ptr = __ptr->left; \
+ goto __again; \
+ } \
+ else \
+__left: \
+ if (__ptr->right != NULL) { \
+ __stack[++__slen] = __ptr = __ptr->right; \
+ goto __again; \
+ } \
+ else \
+__right: \
+ if (!__slen--) \
+ goto __end; /* nothing left, don't delete the root node */ \
+ else { \
+ typeof (__root) __old; \
+ pool_free(tree64, __ptr); \
+ __old = __ptr; \
+ __ptr = __stack[__slen]; \
+ if (__ptr->left == __old) { \
+ /* unlink this node from its parent */ \
+ __ptr->left = NULL; \
+ goto __left; \
+ } \
+ else { \
+ /* no need to unlink, the parent will also die */ \
+ goto __right; \
+ } \
+ } \
+__end: \
+ (__slen >= 0); }); ((typeof(__root))__stack[__slen])->data = NULL)
+
+
+
+/*
+ * walks down the tree <__root> and assigns <__node> to each of its nodes.
+ * <__stack> is an int array of at least N entries where N is the
+ * maximum number of levels of the tree. <__slen> is an integer variable used as
+ * a stack index. The instruction following the foreach statement is executed
+ * for each node.
+ * The tree will walk down only when the data field is empty (NULL), so it
+ * allows inner breaks, and will restart without losing items. The nodes data
+ * will be set to NULL after the inner code, or when the inner code does
+ * '__node->data = NULL';
+ * The nodes are deleted automatically, so it is illegal to manually delete a
+ * node within this loop.
+ */
+#define tree64_foreach_node(__root, __node, __stack, __slen) \
+ for (__slen = 0, __stack[0] = __root; ({ \
+ __label__ __left, __right, __again, __end; \
+ typeof(__root) __ptr = __stack[__slen]; \
+__again: \
+ if (__ptr->data != NULL) { \
+ __node = __ptr; \
+ goto __end; \
+ } \
+ else if (__ptr->left != NULL) { \
+ __stack[++__slen] = __ptr = __ptr->left; \
+ goto __again; \
+ } \
+ else \
+__left: \
+ if (__ptr->right != NULL) { \
+ __stack[++__slen] = __ptr = __ptr->right; \
+ goto __again; \
+ } \
+ else \
+__right: \
+ if (!__slen--) \
+ goto __end; /* nothing left, don't delete the root node */ \
+ else { \
+ typeof (__root) __old; \
+ pool_free(tree64, __ptr); \
+ __old = __ptr; \
+ __ptr = __stack[__slen]; \
+ if (__ptr->left == __old) { \
+ /* unlink this node from its parent */ \
+ __ptr->left = NULL; \
+ goto __left; \
+ } \
+ else { \
+ /* no need to unlink, the parent will also die */ \
+ goto __right; \
+ } \
+ } \
+__end: \
+ (__slen >= 0); }); ((typeof(__root))__stack[__slen])->data = NULL)
+
+
+/*
+ * removes the current node if possible, and its parent if it doesn't handle
+ * data. A pointer to the parent or grandparent is returned (the parent of the
+ * last one deleted in fact). This function should be compatible with any
+ * tree struct because of the void types.
+ * WARNING : never call it from within a tree_foreach() because this last one
+ * uses a stack which will not be updated.
+ */
+
+inline static void *__tree_delete_only_one(void *firstnode) {
+ struct tree64 *down, **uplink;
+ struct tree64 *node = firstnode;
+
+ /* don't kill the root or a populated link */
+ if (node->data || node->up == NULL)
+ return node;
+ if (node->left && node->right)
+ return node;
+ /* since we know that at least left or right is null, we can do arithmetics on them */
+ down = (void *)((long)node->left | (long)node->right);
+ /* find where we are linked */
+ if (node == node->up->left)
+ uplink = &node->up->left;
+ else
+ uplink = &node->up->right;
+
+ *uplink = down; /* we relink the lower branch above us or simply cut it */
+ if (down) {
+ down->up = node->up;
+ /* we know that we cannot do more because we kept one branch */
+ }
+ else {
+ /* we'll redo this once for the node above us because there was no branch below us,
+ * so maybe it doesn't need to exist for only one branch
+ */
+ down = node;
+ node = node->up;
+ pool_free(tree64, down);
+ if (node->data || node->up == NULL)
+ return node;
+ /* now we're sure we were sharing this empty node with another branch, let's find it */
+ down = (void *)((long)node->left | (long)node->right);
+ if (node == node->up->left)
+ uplink = &node->up->left;
+ else
+ uplink = &node->up->right;
+ *uplink = down; /* we relink the lower branch above */
+ down->up = node->up;
+ }
+ /* free the last node */
+ pool_free(tree64, node);
+ return down->up;
+}
+
+/*
+ * removes the current node if possible, and all of its parents which do not
+ * carry data. A pointer to the parent of the last one deleted is returned.
+ * This function should be compatible with any tree struct because of the void
+ * types.
+ * WARNING : never call it from within a tree_foreach() because this last one
+ * uses a stack which will not be updated.
+ */
+
+inline static void *__tree_delete(void *firstnode) {
+ struct tree64 *down, **uplink, *up;
+ struct tree64 *node = firstnode;
+
+ while (1) {
+ /* don't kill the root or a populated link */
+ if (node->data || (up = node->up) == NULL)
+ return node;
+ if (node->left && node->right)
+ return node;
+ /* since we know that at least left or right is null, we can do arithmetics on them */
+ down = (void *)((long)node->left | (long)node->right);
+ /* find where we are linked */
+ if (node == up->left)
+ uplink = &up->left;
+ else
+ uplink = &up->right;
+
+ *uplink = down; /* we relink the lower branch above us or simply cut it */
+ pool_free(tree64, node);
+ node = up;
+ if (down)
+ down->up = node;
+ }
+}
+
+#endif /* __TREE_H__ */