rbtree.c (rbtree_join): Ensure sibling exists before examining colour.

diff --git a/Makefile b/Makefile
index b57ba77354f80595008bb1ffb9ba9aa77c35f56d..9b2dc95fb6c1b81fd98609ecda537590454e0981 100644 (file)
--- a/Makefile
+++ b/Makefile
@@ -65,7 +65,7 @@ avl_TESTS              = avltest
 TREES                  += rb
 rb_LIBSRCS              = rbtree.c
 rb_DEFINES              = -DTREE=RB
 TREES                  += rb
 rb_LIBSRCS              = rbtree.c
 rb_DEFINES              = -DTREE=RB

-rb_TESTS                = rbtest
+rb_TESTS                = rbtest rbregress

 
 libxyla.a: $(LIBOBJS)
        $(call v-tag,AR)$(AR) crs $@ $+
 
 libxyla.a: $(LIBOBJS)
        $(call v-tag,AR)$(AR) crs $@ $+

diff --git a/rb-rbregress.ref b/rb-rbregress.ref
new file mode 100644 (file)
index 0000000..f148f17
--- /dev/null
+++ b/rb-rbregress.ref
@@ -0,0 +1,11 @@
+
+;; `rbtree_join' could look for a sibling node's colour without checking
+;; that it actually existed.
+tree dump, ht = 1
+       #0x00000001 (n =   2)   (*) 0
+       #0x00000000 (n =   1)       ( ) 3
+6
+tree dump, ht = 1
+       #0x00000001 (n =   1)       ( ) 0
+       #0x00000000 (n =   3)   (*) 3
+       #0x00000002 (n =   1)       ( ) 6

diff --git a/rbregress.in b/rbregress.in
new file mode 100644 (file)
index 0000000..6f9668b
--- /dev/null
+++ b/rbregress.in
@@ -0,0 +1,8 @@
+;;; Regression testing for red-black trees.
+
+:
+:;; `rbtree_join' could look for a sibling node's colour without checking
+:;; that it actually existed.
+
+= (_ *0 (_ 3 _)) D!
+( 6k ~ D!

diff --git a/rbtree.c b/rbtree.c
index 4999beacfe84c0f1ce7b97dffb69bd69f7d4a946..047c47436aed82016fe989b336885315cae42101 100644 (file)
--- a/rbtree.c
+++ b/rbtree.c
@@ -913,7 +913,7 @@ int rbtree_join(struct bstree_nodecls *cls,
         * ascending.                                                   \
         */                                                             \
        s = (struct rbnode *)p->_bst.left;                              \
         * ascending.                                                   \
         */                                                             \
        s = (struct rbnode *)p->_bst.left;                              \

-       if (s->f&RBF_RED) {                                             \
+       if (s && s->f&RBF_RED) {                                        \

          V( fprintf(stderr, "RBTREE JOIN red sibling "                 \
                     "(" #right " child): %s\n",                        \
                     path.k ? "ascend" : "extend tree"); )              \
          V( fprintf(stderr, "RBTREE JOIN red sibling "                 \
                     "(" #right " child): %s\n",                        \
                     path.k ? "ascend" : "extend tree"); )              \