diff --git a/include/import/bitops.h b/include/import/bitops.h
new file mode 100644
index 0000000..96f1f65
--- /dev/null
+++ b/include/import/bitops.h
@@ -0,0 +1,103 @@
+/*
+ * bitops.h : macros and functions for bit operations.
+ * (C) 2002 - Willy Tarreau - willy@ant-computing.com
+ *
+ */
+
+#ifndef __BITOPS_H__
+#define __BITOPS_H__
+
+/* how many bits are needed to code the size of an int (eg: 32bits -> 5) */
+#define	LONGSHIFT	5
+#define LLONGSHIFT	6
+#define LONGBITS	32
+#define LLONGBITS	64
+
+/* very fast FFS function : returns the position of the lowest 1 */
+#define __ffs_fast32(___a) ({ \
+    register int ___x, ___bits = 32; \
+    if (___a) { \
+        ___x = (___a); \
+        ___bits--; \
+	if (___x & 0x0000ffff) { ___x &= 0x0000ffff; ___bits -= 16;} \
+	if (___x & 0x00ff00ff) { ___x &= 0x00ff00ff; ___bits -=  8;} \
+	if (___x & 0x0f0f0f0f) { ___x &= 0x0f0f0f0f; ___bits -=  4;} \
+	if (___x & 0x33333333) { ___x &= 0x33333333; ___bits -=  2;} \
+	if (___x & 0x55555555) { ___x &= 0x55555555; ___bits -=  1;} \
+    }\
+    ___bits; \
+    })
+
+/* very fast FLS function : returns the position of the highest 1  */
+#define __fls_fast32(___a) ({ \
+    register int ___x, ___bits = 0; \
+    if (___a) { \
+        ___x = (___a); \
+	if (___x & 0xffff0000) { ___x &= 0xffff0000; ___bits += 16;} \
+	if (___x & 0xff00ff00) { ___x &= 0xff00ff00; ___bits +=  8;} \
+	if (___x & 0xf0f0f0f0) { ___x &= 0xf0f0f0f0; ___bits +=  4;} \
+	if (___x & 0xcccccccc) { ___x &= 0xcccccccc; ___bits +=  2;} \
+	if (___x & 0xaaaaaaaa) { ___x &= 0xaaaaaaaa; ___bits +=  1;} \
+    } else { \
+	___bits = 32; \
+    } \
+    ___bits; \
+    })
+
+/* very fast FFS function working on 64 bits */
+#define __ffs_fast64(___a) ({ \
+    register int ___bits = 64; \
+    register unsigned long  ___x = ((___a) >> 32); \
+    if ((___a) & 0xffffffffUL) { \
+        ___x = (___a) & 0xffffffffUL; \
+	___bits -= 32; \
+    } \
+    if (___x) { \
+        ___bits--; \
+	if (___x & 0x0000ffff) { ___x &= 0x0000ffff; ___bits -= 16;} \
+	if (___x & 0x00ff00ff) { ___x &= 0x00ff00ff; ___bits -=  8;} \
+	if (___x & 0x0f0f0f0f) { ___x &= 0x0f0f0f0f; ___bits -=  4;} \
+	if (___x & 0x33333333) { ___x &= 0x33333333; ___bits -=  2;} \
+	if (___x & 0x55555555) { ___x &= 0x55555555; ___bits -=  1;} \
+    }\
+    ___bits; \
+    })
+
+
+/* very fast FLS function working on 64 bits */
+#define __fls_fast64(___a) ({ \
+    register int ___bits = 0; \
+    register unsigned long ___x = (___a); \
+    if (((unsigned long long)(___a)) >> 32) { \
+        ___x = ((unsigned long long)(___a)) >> 32; \
+	___bits += 32; \
+    } \
+    if (___x) { \
+	if (___x & 0xffff0000) { ___x &= 0xffff0000; ___bits += 16;} \
+	if (___x & 0xff00ff00) { ___x &= 0xff00ff00; ___bits +=  8;} \
+	if (___x & 0xf0f0f0f0) { ___x &= 0xf0f0f0f0; ___bits +=  4;} \
+	if (___x & 0xcccccccc) { ___x &= 0xcccccccc; ___bits +=  2;} \
+	if (___x & 0xaaaaaaaa) { ___x &= 0xaaaaaaaa; ___bits +=  1;} \
+    } else { \
+	 ___bits += 32; \
+    } \
+    ___bits; \
+    })
+
+static int ffs_fast32(register unsigned long a) {
+    return __ffs_fast32(a);
+}
+
+static int fls_fast32(unsigned long a) {
+    return __fls_fast32(a);
+}
+
+static int ffs_fast64(unsigned long long a) {
+    return __ffs_fast64(a);
+}
+
+static int fls_fast64(unsigned long long a) {
+    return __fls_fast64(a);
+}
+
+#endif /* __BITOPS_H__ */
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__ */