Logo Search packages:      
Sourcecode: haproxy version File versions  Download package

tree.h

/*
 * 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__ */

Generated by  Doxygen 1.6.0   Back to index