fixes

[libucw.git] / lib / redblack.h

diff --git a/lib/redblack.h b/lib/redblack.h
index 69230f7f5d447c8e1f9ab2e4a58118e4573a20bf..05544c36a04ac22503cca216cee4450c60108494 100644 (file)
--- a/lib/redblack.h
+++ b/lib/redblack.h
@@ -1,7 +1,7 @@
 /*
 /*

- *     Red-black trees
+ *     UCW Library -- Red-black trees

  *
  *

- *     (c) 2002, Robert Spalek <robert@ucw.cz>
+ *     (c) 2002--2005, Robert Spalek <robert@ucw.cz>

  *
  *     Skeleton based on hash-tables by:
  *
  *
  *     Skeleton based on hash-tables by:
  *


@@ -63,18 +63,22 @@
  *  TREE_WANT_CLEANUP  cleanup() -- deallocate the tree.
  *  TREE_WANT_FIND     node *find(key) -- find first node with the specified
  *                     key, return NULL if no such node exists.
  *  TREE_WANT_CLEANUP  cleanup() -- deallocate the tree.
  *  TREE_WANT_FIND     node *find(key) -- find first node with the specified
  *                     key, return NULL if no such node exists.

- *  TREE_WANT_FIND_NEXT        node *find(node *start) -- find next node with the
+ *  TREE_WANT_FIND_NEXT        node *find_next(node *start) -- find next node with the

  *                     specified key, return NULL if no such node exists.
  *                     specified key, return NULL if no such node exists.

+ *                     Implies TREE_DUPLICATES.

  *  TREE_WANT_SEARCH   node *search(key) -- find the node with the specified
  *                     or, if it does not exist, the nearest one.
  *  TREE_WANT_SEARCH   node *search(key) -- find the node with the specified
  *                     or, if it does not exist, the nearest one.

- *  TREE_WANT_ADJACENT node *adjacent(node *) -- finds next/previous node.
+ *  TREE_WANT_BOUNDARY node *boundary(uns direction) -- finds smallest
+ *                     (direction==0) or largest (direction==1) node.
+ *  TREE_WANT_ADJACENT node *adjacent(node *, uns direction) -- finds next
+ *                     (direction==1) or previous (direction==0) node.

  *  TREE_WANT_NEW      node *new(key) -- create new node with given key.
  *                     If it already exists, it is created as the last one.
  *  TREE_WANT_LOOKUP   node *lookup(key) -- find node with given key,
  *                     if it doesn't exist, create it. Defining
  *                     TREE_GIVE_INIT_DATA is strongly recommended.
  *  TREE_WANT_DELETE   int delete(key) -- delete and deallocate node
  *  TREE_WANT_NEW      node *new(key) -- create new node with given key.
  *                     If it already exists, it is created as the last one.
  *  TREE_WANT_LOOKUP   node *lookup(key) -- find node with given key,
  *                     if it doesn't exist, create it. Defining
  *                     TREE_GIVE_INIT_DATA is strongly recommended.
  *  TREE_WANT_DELETE   int delete(key) -- delete and deallocate node

- *                     with given key. Returns success.
+ *                     with a given key. Returns success.

  *  TREE_WANT_REMOVE   remove(node *) -- delete and deallocate given node.
  *
  *  TREE_WANT_DUMP     dump() -- dumps the whole tree to stdout
  *  TREE_WANT_REMOVE   remove(node *) -- delete and deallocate given node.
  *
  *  TREE_WANT_DUMP     dump() -- dumps the whole tree to stdout


@@ -107,6 +111,7 @@
  *  TREE_GLOBAL                Functions are exported (i.e., not static).
  *  TREE_CONSERVE_SPACE        Use as little space as possible at the price of a
  *                     little slowdown.
  *  TREE_GLOBAL                Functions are exported (i.e., not static).
  *  TREE_CONSERVE_SPACE        Use as little space as possible at the price of a
  *                     little slowdown.

+ *  TREE_DUPLICATES    Records with duplicate keys are allowed.

  *  TREE_MAX_DEPTH     Maximal depth of a tree (for stack allocation).
  *
  *  If you set TREE_WANT_ITERATOR, you also get a iterator macro at no
  *  TREE_MAX_DEPTH     Maximal depth of a tree (for stack allocation).
  *
  *  If you set TREE_WANT_ITERATOR, you also get a iterator macro at no


@@ -255,13 +260,13 @@ typedef struct P(stack_entry) {
 #else
        /* Pointers are aligned, hence we can use lower bits.  */
        static inline uns P(red_flag) (P(bucket) *node)
 #else
        /* Pointers are aligned, hence we can use lower bits.  */
        static inline uns P(red_flag) (P(bucket) *node)

-       { return ((long) node->son[0]) & 1L; }
+       { return ((addr_int_t) node->son[0]) & 1L; }

        static inline void P(set_red_flag) (P(bucket) *node, uns flag)
        static inline void P(set_red_flag) (P(bucket) *node, uns flag)

-       { (long) node->son[0] = (((long) node->son[0]) & ~1L) | (flag & 1L); }
+       { (addr_int_t) node->son[0] = (((addr_int_t) node->son[0]) & ~1L) | (flag & 1L); }

        static inline P(bucket) * P(tree_son) (P(bucket) *node, uns id)
        static inline P(bucket) * P(tree_son) (P(bucket) *node, uns id)

-       { return (void *) (((long) node->son[id]) & ~1L); }
+       { return (void *) (((addr_int_t) node->son[id]) & ~1L); }

        static inline void P(set_tree_son) (P(bucket) *node, uns id, P(bucket) *son)
        static inline void P(set_tree_son) (P(bucket) *node, uns id, P(bucket) *son)

-       { node->son[id] = (void *) ((long) son | (((long) node->son[id]) & 1L) ); }
+       { node->son[id] = (void *) ((addr_int_t) son | (((addr_int_t) node->son[id]) & 1L) ); }

 #endif
 
 /* Defaults for missing parameters.  */
 #endif
 
 /* Defaults for missing parameters.  */


@@ -322,6 +327,19 @@ static inline void P(init_data) (P(node) *n UNUSED)
 #      define TREE_MAX_DEPTH 64
 #endif
 
 #      define TREE_MAX_DEPTH 64
 #endif
 

+#if defined(TREE_WANT_FIND_NEXT) && !defined(TREE_DUPLICATES)
+#      define TREE_DUPLICATES
+#endif
+
+#ifdef TREE_WANT_LOOKUP
+#ifndef TREE_WANT_FIND
+#      define TREE_WANT_FIND
+#endif
+#ifndef TREE_WANT_NEW
+#      define TREE_WANT_NEW
+#endif
+#endif
+

 /* Now the operations */
 
 STATIC void P(init) (T *t)
 /* Now the operations */
 
 STATIC void P(init) (T *t)


@@ -366,7 +384,7 @@ static uns P(fill_stack) (P(stack_entry) *stack, uns max_depth, P(bucket) *node,
                ASSERT(i+1 < max_depth);
                stack[i+1].buck = P(tree_son) (stack[i].buck, stack[i].son);
        }
                ASSERT(i+1 < max_depth);
                stack[i+1].buck = P(tree_son) (stack[i].buck, stack[i].son);
        }

-#ifdef TREE_WANT_FIND_NEXT
+#ifdef TREE_DUPLICATES

        if (stack[i].buck)
        {
                uns idx;
        if (stack[i].buck)
        {
                uns idx;


@@ -384,7 +402,7 @@ static uns P(fill_stack) (P(stack_entry) *stack, uns max_depth, P(bucket) *node,
        return i;
 }
 
        return i;
 }
 

-#if defined(TREE_WANT_FIND) || defined(TREE_WANT_LOOKUP)
+#ifdef TREE_WANT_FIND

 STATIC P(node) * P(find) (T *t, TREE_KEY_DECL)
 {
        P(stack_entry) stack[TREE_MAX_DEPTH];
 STATIC P(node) * P(find) (T *t, TREE_KEY_DECL)
 {
        P(stack_entry) stack[TREE_MAX_DEPTH];


@@ -394,6 +412,22 @@ STATIC P(node) * P(find) (T *t, TREE_KEY_DECL)
 }
 #endif
 
 }
 #endif
 

+#ifdef TREE_WANT_BOUNDARY
+STATIC P(node) * P(boundary) (T *t, uns direction)
+{
+       P(bucket) *n = t->root, *ns;
+       if (!n)
+               return NULL;
+       else
+       {
+               uns son = !!direction;
+               while ((ns = P(tree_son) (n, son)))
+                       n = ns;
+               return &n->n;
+       }
+}
+#endif
+

 #ifdef TREE_STORE_PARENT
 STATIC P(node) * P(adjacent) (P(node) *start, uns direction)
 {
 #ifdef TREE_STORE_PARENT
 STATIC P(node) * P(adjacent) (P(node) *start, uns direction)
 {


@@ -425,7 +459,7 @@ STATIC P(node) * P(adjacent) (P(node) *start, uns direction)
 }
 #endif
 
 }
 #endif
 

-#if defined(TREE_WANT_FIND_NEXT) || defined(TREE_WANT_DELETE) || defined(TREE_WANT_REMOVE)
+#if defined(TREE_DUPLICATES) || defined(TREE_WANT_DELETE) || defined(TREE_WANT_REMOVE)

 static int P(find_next_node) (P(stack_entry) *stack, uns max_depth, uns direction)
 {
        uns depth = 0;
 static int P(find_next_node) (P(stack_entry) *stack, uns max_depth, uns direction)
 {
        uns depth = 0;


@@ -564,14 +598,14 @@ try_it_again:
                t->root = node;
 }
 
                t->root = node;
 }
 

-#if defined(TREE_WANT_NEW) || defined(TREE_WANT_LOOKUP)
+#ifdef TREE_WANT_NEW

 STATIC P(node) * P(new) (T *t, TREE_KEY_DECL)
 {
        P(stack_entry) stack[TREE_MAX_DEPTH];
        P(bucket) *added;
        uns depth;
        depth = P(fill_stack) (stack, TREE_MAX_DEPTH, t->root, TREE_KEY(), 1);
 STATIC P(node) * P(new) (T *t, TREE_KEY_DECL)
 {
        P(stack_entry) stack[TREE_MAX_DEPTH];
        P(bucket) *added;
        uns depth;
        depth = P(fill_stack) (stack, TREE_MAX_DEPTH, t->root, TREE_KEY(), 1);

-#ifdef TREE_WANT_FIND_NEXT
+#ifdef TREE_DUPLICATES

        /* It is the last found value, hence everything in the right subtree is
         * strongly _bigger_.  */
        depth += P(find_next_node) (stack+depth, TREE_MAX_DEPTH-depth, 1);
        /* It is the last found value, hence everything in the right subtree is
         * strongly _bigger_.  */
        depth += P(find_next_node) (stack+depth, TREE_MAX_DEPTH-depth, 1);


@@ -867,7 +901,7 @@ static void P(dump_subtree) (struct fastbuf *fb, T *t, P(bucket) *node, P(bucket
        {
                ASSERT(!flag || !P(red_flag) (parent));
                cmp_res *= P(cmp) (TREE_KEY(node->n.), TREE_KEY(parent->n.));
        {
                ASSERT(!flag || !P(red_flag) (parent));
                cmp_res *= P(cmp) (TREE_KEY(node->n.), TREE_KEY(parent->n.));

-#ifdef TREE_WANT_FIND_NEXT
+#ifdef TREE_DUPLICATES

                ASSERT(cmp_res >= 0);
 #else
                ASSERT(cmp_res > 0);
                ASSERT(cmp_res >= 0);
 #else
                ASSERT(cmp_res > 0);


@@ -924,13 +958,12 @@ static P(node) * P(first_node) (T *t, uns direction)
 #define TREE_FOR_ALL(t_px, t_ptr, t_var)                                               \
 do                                                                                     \
 {                                                                                      \
 #define TREE_FOR_ALL(t_px, t_ptr, t_var)                                               \
 do                                                                                     \
 {                                                                                      \

-       TREE_GLUE(t_px,node) *t_var = TREE_GLUE(t_px,first_node)(t_ptr, 0);             \
-       for (; t_var; t_var = TREE_GLUE(t_px,adjacent)(t_var, 1))                       \
+       GLUE_(t_px,node) *t_var = GLUE_(t_px,first_node)(t_ptr, 0);                     \
+       for (; t_var; t_var = GLUE_(t_px,adjacent)(t_var, 1))                           \

        {
 #define TREE_END_FOR } } while(0)
 #define TREE_BREAK break
 #define TREE_CONTINUE continue
        {
 #define TREE_END_FOR } } while(0)
 #define TREE_BREAK break
 #define TREE_CONTINUE continue

-#define TREE_GLUE(x,y) x##_##y

 
 #endif
 #endif
 
 #endif
 #endif


@@ -951,6 +984,7 @@ do                                                                                  \
 #undef TREE_WANT_FIND
 #undef TREE_WANT_FIND_NEXT
 #undef TREE_WANT_SEARCH
 #undef TREE_WANT_FIND
 #undef TREE_WANT_FIND_NEXT
 #undef TREE_WANT_SEARCH

+#undef TREE_WANT_BOUNDARY

 #undef TREE_WANT_ADJACENT
 #undef TREE_WANT_NEW
 #undef TREE_WANT_LOOKUP
 #undef TREE_WANT_ADJACENT
 #undef TREE_WANT_NEW
 #undef TREE_WANT_LOOKUP


@@ -968,6 +1002,7 @@ do                                                                                 \
 #undef TREE_USE_POOL
 #undef TREE_STATIC
 #undef TREE_CONSERVE_SPACE
 #undef TREE_USE_POOL
 #undef TREE_STATIC
 #undef TREE_CONSERVE_SPACE

+#undef TREE_DUPLICATES

 #undef TREE_MAX_DEPTH
 #undef TREE_STORE_PARENT
 #undef TREE_KEY
 #undef TREE_MAX_DEPTH
 #undef TREE_STORE_PARENT
 #undef TREE_KEY