/*
- * 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:
*
* A red-black tree is a binary search tree, where records are stored
* in nodes (may be also leaves). Every node has a colour. The
* following restrictions hold:
- *
+ *
* - a parent of a red node is black
* - every path from the root to a node with less than 2 children
* contains the same number of black nodes
* 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_DOWN node *search_down(key) -- find either the node with
+ * specified value, or if it does not exist, the node
+ * with nearest smaller value.
+ * 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.
* undef'd.
*/
+#include <stdio.h>
#include <string.h>
#if !defined(TREE_NODE) || !defined(TREE_PREFIX)
#else
/* Pointers are aligned, hence we can use lower bits. */
static inline uns P(red_flag) (P(bucket) *node)
- { return ((addr_int_t) node->son[0]) & 1L; }
+ { return ((uintptr_t) node->son[0]) & 1L; }
static inline void P(set_red_flag) (P(bucket) *node, uns flag)
- { (addr_int_t) node->son[0] = (((addr_int_t) node->son[0]) & ~1L) | (flag & 1L); }
+ { node->son[0] = (void*) ( (((uintptr_t) node->son[0]) & ~1L) | (flag & 1L) ); }
static inline P(bucket) * P(tree_son) (P(bucket) *node, uns id)
- { return (void *) (((addr_int_t) node->son[id]) & ~1L); }
+ { return (void *) (((uintptr_t) node->son[id]) & ~1L); }
static inline void P(set_tree_son) (P(bucket) *node, uns id, P(bucket) *son)
- { node->son[id] = (void *) ((addr_int_t) son | (((addr_int_t) node->son[id]) & 1L) ); }
+ { node->son[id] = (void *) ((uintptr_t) son | (((uintptr_t) node->son[id]) & 1L) ); }
#endif
/* Defaults for missing parameters. */
}
#endif
+#ifdef TREE_WANT_SEARCH_DOWN
+STATIC P(node) * P(search_down) (T *t, TREE_KEY_DECL)
+{
+ P(node) *last_right=NULL;
+ P(bucket) *node=t->root;
+ while(node)
+ {
+ int cmp;
+ cmp = P(cmp) (TREE_KEY(), TREE_KEY(node->n.));
+ if (cmp == 0)
+ return &node->n;
+ else if (cmp < 0)
+ node=P(tree_son) (node, 0);
+ else
+ {
+ last_right=&node->n;
+ node=P(tree_son) (node, 1);
+ }
+ }
+ return last_right;
+}
+#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)
{
#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
#undef TREE_WANT_FIND
#undef TREE_WANT_FIND_NEXT
#undef TREE_WANT_SEARCH
+#undef TREE_WANT_SEARCH_DOWN
+#undef TREE_WANT_BOUNDARY
#undef TREE_WANT_ADJACENT
#undef TREE_WANT_NEW
#undef TREE_WANT_LOOKUP