From 05486e04a9aa2b5916ca7f3389edafff2ef2105e Mon Sep 17 00:00:00 2001 From: stevenj Date: Wed, 5 Sep 2007 22:00:18 -0400 Subject: [PATCH] added rb_tree_shift_keys darcs-hash:20070906020018-c8de0-ebbcf31bebdb208a5d1ff57aca14a3994f08f549.gz --- util/redblack.c | 13 +++++++++++++ util/redblack.h | 3 +++ 2 files changed, 16 insertions(+) diff --git a/util/redblack.c b/util/redblack.c index 44faf2d..4fb4a4d 100644 --- a/util/redblack.c +++ b/util/redblack.c @@ -371,3 +371,16 @@ rb_node *rb_tree_resort(rb_tree *t, rb_node *n) insert_node(t, n); return n; } + +/* shift all key pointers by kshift ... this is useful when the keys + are pointers into another array, that has been resized with realloc */ +static void shift_keys(rb_node *n, ptrdiff_t kshift) /* assumes n != NIL */ +{ + n->k += kshift; + if (n->l != NIL) shift_keys(n->l, kshift); + if (n->r != NIL) shift_keys(n->r, kshift); +} +void rb_tree_shift_keys(rb_tree *t, ptrdiff_t kshift) +{ + if (t->root != NIL) shift_keys(t->root, kshift); +} diff --git a/util/redblack.h b/util/redblack.h index 8fc9ae4..d428d64 100644 --- a/util/redblack.h +++ b/util/redblack.h @@ -1,6 +1,8 @@ #ifndef REDBLACK_H #define REDBLACK_H +#include /* for ptrdiff_t */ + #ifdef __cplusplus extern "C" { @@ -38,6 +40,7 @@ extern rb_node *rb_tree_min(rb_tree *t); extern rb_node *rb_tree_max(rb_tree *t); extern rb_node *rb_tree_succ(rb_node *n); extern rb_node *rb_tree_pred(rb_node *n); +extern void rb_tree_shift_keys(rb_tree *t, ptrdiff_t kshift); /* To change a key, use rb_tree_find+resort. Removing a node currently wastes memory unless you change the allocation scheme -- 2.30.2