X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;f=lib%2Fredblack.h;h=2af759f1a65431b90832119cb7f9745d2551e15d;hb=997624f88f37bec5cb96cf9fc3b3cac05ccc6ed8;hp=f140ea5efc14b4b232ab93b82bfd7a336455c9a1;hpb=b3524e137a080e8a37687347e1898cc1f0a91379;p=libucw.git diff --git a/lib/redblack.h b/lib/redblack.h index f140ea5e..2af759f1 100644 --- a/lib/redblack.h +++ b/lib/redblack.h @@ -63,18 +63,20 @@ * 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. + * 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_ADJACENT node *adjacent(node *) -- finds next/previous 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 - * 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 @@ -104,9 +106,10 @@ * TREE_ATOMIC_TYPE=t Atomic values are of type `t' instead of int. * TREE_USE_POOL=pool Allocate all nodes from given mempool. * Collides with delete/remove functions. - * TREE_STATIC Functions are declared as static. + * 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 @@ -121,7 +124,7 @@ * } * TREE_END_FOR; * - * Then include and voila, you have a tree suiting all your + * Then include "lib/redblack.h" and voila, you have a tree suiting all your * needs (at least those which you've revealed :) ). * * After including this file, all parameter macros are automatically @@ -255,13 +258,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) - { 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) - { (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) - { 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) - { 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. */ @@ -312,16 +315,29 @@ static inline void P(init_data) (P(node) *n UNUSED) # define TREE_SAFE_FREE(x) P(free) (x) #endif -#ifdef TREE_STATIC -# define STATIC static -#else +#ifdef TREE_GLOBAL # define STATIC +#else +# define STATIC static #endif #ifndef TREE_MAX_DEPTH # 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) @@ -349,7 +365,7 @@ STATIC void P(cleanup) (T *t) } #endif -static uns P(fill_stack) (P(stack_entry) *stack, uns max_depth, P(bucket) *node, TREE_KEY_DECL, uns son_id) +static uns P(fill_stack) (P(stack_entry) *stack, uns max_depth, P(bucket) *node, TREE_KEY_DECL, uns son_id UNUSED) { uns i; stack[0].buck = node; @@ -366,7 +382,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); } -#ifdef TREE_WANT_FIND_NEXT +#ifdef TREE_DUPLICATES if (stack[i].buck) { uns idx; @@ -384,7 +400,7 @@ static uns P(fill_stack) (P(stack_entry) *stack, uns max_depth, P(bucket) *node, 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]; @@ -425,7 +441,7 @@ STATIC P(node) * P(adjacent) (P(node) *start, uns direction) } #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; @@ -476,14 +492,17 @@ STATIC P(node) * P(search) (T *t, TREE_KEY_DECL) } #endif -//#define TRACE(txt...) do { printf(txt); fflush(stdout); } while (0) -#define TRACE(txt...) +#if 0 +#define TREE_TRACE(txt...) do { printf(txt); fflush(stdout); } while (0) +#else +#define TREE_TRACE(txt...) +#endif static inline P(bucket) * P(rotation) (P(bucket) *node, uns son_id) { /* Destroys red_flag's in node, son. Returns new root. */ P(bucket) *son = P(tree_son) (node, son_id); - TRACE("Rotation (node %d, son %d), direction %d\n", node->n.key, son->n.key, son_id); + TREE_TRACE("Rotation (node %d, son %d), direction %d\n", node->n.key, son->n.key, son_id); node->son[son_id] = P(tree_son) (son, 1-son_id); son->son[1-son_id] = node; #ifdef TREE_STORE_PARENT @@ -536,7 +555,7 @@ try_it_again: P(set_red_flag) (uncle, 0); P(set_red_flag) (grand, 1); depth -= 2; - TRACE("Swapping colours (parent %d, uncle %d, grand %d), passing thru\n", parent->n.key, uncle->n.key, grand->n.key); + TREE_TRACE("Swapping colours (parent %d, uncle %d, grand %d), passing thru\n", parent->n.key, uncle->n.key, grand->n.key); goto try_it_again; } /* Black uncle and grandparent, we need to rotate. Test @@ -561,14 +580,14 @@ try_it_again: 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); -#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); @@ -658,7 +677,7 @@ missing_black: { depth--; iteration++; - TRACE("Swapping colours (parent %d, sibling %d), passing thru\n", parent->n.key, sibling->n.key); + TREE_TRACE("Swapping colours (parent %d, sibling %d), passing thru\n", parent->n.key, sibling->n.key); goto missing_black; } } else if (!red[del_son]) @@ -847,7 +866,7 @@ STATIC int P(delete) (T *t, TREE_KEY_DECL) #endif #ifdef TREE_WANT_DUMP -static void P(dump_subtree) (struct fastbuf *fb, T *t, P(bucket) *node, P(bucket) *parent, int cmp_res, int level, int black) +static void P(dump_subtree) (struct fastbuf *fb, T *t, P(bucket) *node, P(bucket) *parent, int cmp_res, int level, uns black) { uns flag; int i; @@ -864,7 +883,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.)); -#ifdef TREE_WANT_FIND_NEXT +#ifdef TREE_DUPLICATES ASSERT(cmp_res >= 0); #else ASSERT(cmp_res > 0); @@ -921,13 +940,12 @@ static P(node) * P(first_node) (T *t, uns direction) #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_GLUE(x,y) x##_##y #endif #endif @@ -965,9 +983,11 @@ do \ #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_EXTRA_SIZE #undef TREE_SAFE_FREE +#undef TREE_TRACE #undef STATIC