* 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
* 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)
- { node->son[0] = (void*) ( (((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)
{
#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