From: Mark Wooding <mdw@distorted.org.uk>
Date: Tue, 20 Aug 2024 18:58:50 +0000 (+0100)
Subject: rbtree.c (rbtree_join): Ensure sibling exists before examining colour.
X-Git-Tag: 0.99.0~115
X-Git-Url: https://www.chiark.greenend.org.uk/ucgi/~mdw/git/xyla/commitdiff_plain/0084cc9563afb53218f7e9881e122d69049896f3

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

diff --git a/Makefile b/Makefile
index b57ba77..9b2dc95 100644
--- a/Makefile
+++ b/Makefile
@@ -65,7 +65,7 @@ avl_TESTS		 = avltest
 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 $@ $+
diff --git a/rb-rbregress.ref b/rb-rbregress.ref
new file mode 100644
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
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 4999bea..047c474 100644
--- a/rbtree.c
+++ b/rbtree.c
@@ -913,7 +913,7 @@ int rbtree_join(struct bstree_nodecls *cls,
 	 * 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"); )		\