* 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
* 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
#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. */
# 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)
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;
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];
}
#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;
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);
{
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);
#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