[MAJOR] replace ultree with ebtree in wait-queues
The ultree code has been removed in favor of a simpler and
cleaner ebtree implementation. The eternity queue does not
need to exist anymore, and the pool_tree64 has been removed.
The ebtree node is stored in the task itself. The qlist list
header is still used by the run-queue, but will be able to
disappear once the run-queue uses ebtree too.
diff --git a/include/import/bitops.h b/include/import/bitops.h
deleted file mode 100644
index 96f1f65..0000000
--- a/include/import/bitops.h
+++ /dev/null
@@ -1,103 +0,0 @@
-/*
- * 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
deleted file mode 100644
index 11ca6e0..0000000
--- a/include/import/tree.h
+++ /dev/null
@@ -1,727 +0,0 @@
-/*
- * tree.h : tree manipulation macros and structures.
- * (C) 2002 - Willy Tarreau - willy@ant-computing.com
- *
- * 2007/05/13: adapted to mempools v2.
- *
- */
-
-#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 */
-};
-
-extern struct pool_head *pool2_tree64;
-
-#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_alloc2(pool2_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_alloc2(pool2_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_alloc2(pool2_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_alloc2(pool2_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_alloc2(pool2_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_alloc2(pool2_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;
- }
- }
- else {
- if ((l >> (next->level - 1)) & 1) { /* right branch */
- branch = &next->right;
- }
- }
- next = *branch;
-
- if (next == NULL) {
- /* we'll have to insert our node here */
- *branch = new =(struct ultree *)pool_alloc2(pool2_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_alloc2(pool2_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_alloc2(pool2_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_free2(pool2_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_free2(pool##__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_free2(pool2_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_free2(pool2_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_free2(pool2_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_free2(pool2_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_free2(pool2_tree64, node);
- node = up;
- if (down)
- down->up = node;
- }
-}
-
-#endif /* __TREE_H__ */
diff --git a/include/proto/task.h b/include/proto/task.h
index 49e3a94..d27e1db 100644
--- a/include/proto/task.h
+++ b/include/proto/task.h
@@ -2,7 +2,7 @@
include/proto/task.h
Functions for task management.
- Copyright (C) 2000-2007 Willy Tarreau - w@1wt.eu
+ Copyright (C) 2000-2008 Willy Tarreau - w@1wt.eu
This library is free software; you can redistribute it and/or
modify it under the terms of the GNU Lesser General Public
@@ -35,12 +35,9 @@
extern void *run_queue;
extern struct pool_head *pool2_task;
-/* perform minimal intializations, report 0 in case of error, 1 if OK. */
+/* perform minimal initializations, report 0 in case of error, 1 if OK. */
int init_task();
-/* needed later */
-void *tree_delete(void *node);
-
/* puts the task <t> in run queue <q>, and returns <t> */
#define task_wakeup _task_wakeup
struct task *_task_wakeup(struct task *t);
@@ -49,17 +46,12 @@
if (t->state == TASK_RUNNING)
return t;
- if (t->qlist.p != NULL)
- DLIST_DEL(&t->qlist);
+ if (likely(t->eb.node.leaf_p))
+ eb32_delete(&t->eb);
DLIST_ADD(run_queue, &t->qlist);
t->state = TASK_RUNNING;
- if (likely(t->wq != NULL)) {
- tree_delete(t->wq);
- t->wq = NULL;
- }
-
return t;
}
@@ -79,7 +71,7 @@
/*
* unlinks the task from wherever it is queued :
* - eternity_queue, run_queue
- * - wait queue : wq not null => remove carrier node too
+ * - wait queue
* A pointer to the task itself is returned.
*/
static inline struct task *task_delete(struct task *t)
@@ -89,10 +81,21 @@
t->qlist.p = NULL;
}
- if (t->wq) {
- tree_delete(t->wq);
- t->wq = NULL;
- }
+ if (t->eb.node.leaf_p)
+ eb32_delete(&t->eb);
+
+ return t;
+}
+
+/*
+ * Initialize a new task. The bare minimum is performed (queue pointers and state).
+ * The task is returned.
+ */
+static inline struct task *task_init(struct task *t)
+{
+ t->qlist.p = NULL;
+ t->eb.node.leaf_p = NULL;
+ t->state = TASK_IDLE;
return t;
}
diff --git a/include/types/task.h b/include/types/task.h
index e0bbd6d..6b56547 100644
--- a/include/types/task.h
+++ b/include/types/task.h
@@ -2,7 +2,7 @@
include/types/task.h
Macros, variables and structures for task management.
- Copyright (C) 2000-2007 Willy Tarreau - w@1wt.eu
+ Copyright (C) 2000-2008 Willy Tarreau - w@1wt.eu
This library is free software; you can redistribute it and/or
modify it under the terms of the GNU Lesser General Public
@@ -25,8 +25,8 @@
#include <sys/time.h>
#include <common/config.h>
+#include <common/eb32tree.h>
#include <common/mini-clist.h>
-#include <import/tree.h>
/* values for task->state */
#define TASK_IDLE 0
@@ -35,7 +35,7 @@
/* The base for all tasks */
struct task {
struct list qlist; /* chaining in the same queue; bidirectionnal but not circular */
- struct ultree *wq; /* NULL if unqueued, or back ref to the carrier node in the WQ */
+ struct eb32_node eb; /* ebtree node used to hold the task in the wait queue */
int state; /* task state : IDLE or RUNNING */
struct timeval expire; /* next expiration time for this task, use only for fast sorting */
void (*process)(struct task *t, struct timeval *next); /* the function which processes the task */