;; `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 ;; In `rbtree_split' with an empty path, the root of the initial tree ;; wasn't forcibly blackened. Make sure this is done and that the ;; black heights are correctly tracked. This causes all manner of ;; trouble otherwise, including leaking nodes because `rbtree_join' ;; assumes that a tree with zero black-height must be empty -- which ;; is true. tree dump, ht = 3 #0x00000003 (n = 1) (*) 12 #0x00000005 (n = 3) (*) 13 #0x00000004 (n = 1) (*) 14 #0x0000000a (n = 8) ( ) 16 #0x00000006 (n = 1) (*) 17 #0x00000009 (n = 4) (*) 18 #0x00000008 (n = 2) (*) 19 #0x00000007 (n = 1) ( ) 23 #0x00000011 (n = 15) (*) 24 #0x0000000b (n = 1) (*) 28 #0x0000000d (n = 3) ( ) 32 #0x0000000c (n = 1) (*) 35 #0x00000010 (n = 6) (*) 36 #0x0000000f (n = 2) (*) 37 #0x0000000e (n = 1) ( ) 39 tree dump, ht = 2 #0x00000007 (n = 1) (*) 23 #0x00000011 (n = 3) ( ) 24 #0x0000000b (n = 1) (*) 28 #0x0000000d (n = 8) (*) 32 #0x0000000c (n = 1) (*) 35 #0x00000010 (n = 4) ( ) 36 #0x0000000f (n = 2) (*) 37 #0x0000000e (n = 1) ( ) 39 tree dump, ht = 0 (tree empty) tree dump, ht = 3 #0x00000003 (n = 1) (*) 12 #0x00000005 (n = 3) (*) 13 #0x00000004 (n = 1) (*) 14 #0x0000000a (n = 7) (*) 16 #0x00000006 (n = 1) (*) 17 #0x00000009 (n = 3) (*) 18 #0x00000008 (n = 1) (*) 19 ;; The hairy test case which found both of these bugs. tree dump, ht = 3 #0x00000012 (n = 1) ( ) 0 #0x00000013 (n = 2) (*) 3 #0x00000015 (n = 4) (*) 6 #0x00000014 (n = 1) (*) 9 #0x0000001d (n = 12) ( ) 11 #0x00000016 (n = 1) ( ) 12 #0x00000017 (n = 2) (*) 21 #0x0000001c (n = 7) (*) 22 #0x00000019 (n = 2) (*) 27 #0x00000018 (n = 1) ( ) 28 #0x0000001b (n = 4) ( ) 31 #0x0000001a (n = 1) (*) 35 #0x00000023 (n = 18) (*) 41 #0x0000001e (n = 1) ( ) 49 #0x00000020 (n = 3) (*) 50 #0x0000001f (n = 1) ( ) 55 #0x00000022 (n = 5) (*) 57 #0x00000021 (n = 1) (*) 59 tree dump, ht = 4 #0x00000025 (n = 2) (*) 0 #0x00000024 (n = 1) ( ) 1 #0x00000027 (n = 4) (*) 3 #0x00000026 (n = 1) (*) 4 #0x0000002c (n = 9) ( ) 6 #0x00000028 (n = 1) ( ) 11 #0x00000029 (n = 2) (*) 12 #0x0000002b (n = 4) (*) 13 #0x0000002a (n = 1) (*) 14 #0x00000037 (n = 20) (*) 16 #0x0000002d (n = 1) (*) 17 #0x00000030 (n = 4) (*) 18 #0x0000002f (n = 2) (*) 19 #0x0000002e (n = 1) ( ) 23 #0x00000036 (n = 10) ( ) 24 #0x00000031 (n = 1) (*) 28 #0x00000033 (n = 3) ( ) 32 #0x00000032 (n = 1) (*) 35 #0x00000035 (n = 5) (*) 36 #0x00000034 (n = 1) (*) 37 #0x00000042 (n = 31) (*) 39 #0x00000038 (n = 1) (*) 41 #0x0000003b (n = 4) (*) 43 #0x0000003a (n = 2) (*) 44 #0x00000039 (n = 1) ( ) 45 #0x00000041 (n = 10) (*) 52 #0x0000003c (n = 1) (*) 53 #0x0000003e (n = 3) ( ) 56 #0x0000003d (n = 1) (*) 58 #0x00000040 (n = 5) (*) 60 #0x0000003f (n = 1) (*) 61 tree dump, ht = 3 #0x00000024 (n = 2) (*) 1 #0x00000026 (n = 1) ( ) 4 #0x0000002b (n = 4) ( ) 13 #0x0000002a (n = 1) (*) 14 #0x00000037 (n = 8) (*) 16 #0x0000002d (n = 1) (*) 17 #0x00000030 (n = 3) ( ) 18 #0x0000002f (n = 1) (*) 19 #0x0000002e (n = 23) (*) 23 #0x00000036 (n = 1) (*) 24 #0x00000033 (n = 3) ( ) 32 #0x00000035 (n = 1) (*) 36 #0x00000034 (n = 5) (*) 37 #0x00000042 (n = 1) (*) 39 #0x0000003b (n = 14) ( ) 43 #0x0000003a (n = 2) (*) 44 #0x00000039 (n = 1) ( ) 45 #0x00000041 (n = 8) (*) 52 #0x0000003c (n = 2) (*) 53 #0x0000003e (n = 1) ( ) 56 #0x0000003d (n = 5) ( ) 58 #0x00000040 (n = 2) (*) 60 #0x0000003f (n = 1) ( ) 61 tree dump, ht = 2 #0x00000025 (n = 1) ( ) 0 #0x00000027 (n = 3) (*) 3 #0x0000002c (n = 1) ( ) 6 #0x00000028 (n = 5) ( ) 11 #0x00000029 (n = 1) (*) 12 #0x00000031 (n = 8) (*) 28 #0x00000032 (n = 2) (*) 35 #0x00000038 (n = 1) ( ) 41 tree dump, ht = 3 #0x00000012 (n = 1) ( ) 0 #0x00000013 (n = 2) (*) 3 #0x00000015 (n = 4) (*) 6 #0x00000014 (n = 1) (*) 9 #0x0000001d (n = 12) ( ) 11 #0x00000016 (n = 1) ( ) 12 #0x00000017 (n = 2) (*) 21 #0x0000001c (n = 7) (*) 22 #0x00000019 (n = 2) (*) 27 #0x00000018 (n = 1) ( ) 28 #0x0000001b (n = 4) ( ) 31 #0x0000001a (n = 1) (*) 35 #0x00000023 (n = 18) (*) 41 #0x0000001e (n = 1) ( ) 49 #0x00000020 (n = 3) (*) 50 #0x0000001f (n = 1) ( ) 55 #0x00000022 (n = 5) (*) 57 #0x00000021 (n = 1) (*) 59 ;; `rbtree_splitroot' just could not track subtree heights correctly. tree dump, ht = 4 #0x00000044 (n = 2) (*) 4 #0x00000043 (n = 1) ( ) 6 #0x00000046 (n = 4) (*) 10 #0x00000045 (n = 1) (*) 11 #0x0000004b (n = 9) ( ) 13 #0x00000047 (n = 1) (*) 17 #0x0000004a (n = 4) (*) 18 #0x00000048 (n = 1) ( ) 19 #0x00000049 (n = 2) (*) 20 #0x00000050 (n = 14) (*) 22 #0x0000004c (n = 1) (*) 23 #0x0000004f (n = 4) (*) 25 #0x0000004d (n = 1) ( ) 26 #0x0000004e (n = 2) (*) 27 #0x00000061 (n = 31) (*) 30 #0x00000051 (n = 1) ( ) 32 #0x00000052 (n = 2) (*) 33 #0x00000057 (n = 7) (*) 34 #0x00000054 (n = 2) (*) 36 #0x00000053 (n = 1) ( ) 38 #0x00000056 (n = 4) ( ) 40 #0x00000055 (n = 1) (*) 41 #0x00000060 (n = 16) (*) 43 #0x00000058 (n = 1) ( ) 45 #0x00000059 (n = 2) (*) 46 #0x0000005f (n = 8) (*) 48 #0x0000005a (n = 1) ( ) 49 #0x0000005b (n = 2) (*) 51 #0x0000005e (n = 5) ( ) 53 #0x0000005d (n = 2) (*) 61 #0x0000005c (n = 1) ( ) 62 tree dump, ht = 3 #0x00000062 (n = 1) (*) 6 #0x00000064 (n = 3) ( ) 15 #0x00000063 (n = 1) (*) 16 #0x00000066 (n = 5) (*) 23 #0x00000065 (n = 1) (*) 24 #0x00000070 (n = 15) ( ) 33 #0x00000067 (n = 1) (*) 35 #0x0000006a (n = 4) ( ) 36 #0x00000069 (n = 2) (*) 37 #0x00000068 (n = 1) ( ) 39 #0x0000006f (n = 9) (*) 40 #0x0000006b (n = 1) (*) 43 #0x0000006e (n = 4) ( ) 47 #0x0000006d (n = 2) (*) 48 #0x0000006c (n = 1) ( ) 49 #0x00000075 (n = 20) (*) 50 #0x00000071 (n = 1) (*) 57 #0x00000074 (n = 4) (*) 59 #0x00000072 (n = 1) ( ) 61 #0x00000073 (n = 2) (*) 62 tree dump, ht = 4 #0x00000044 (n = 1) ( ) 4 #0x00000043 (n = 2) (*) 6 #0x00000046 (n = 4) (*) 10 #0x00000045 (n = 1) (*) 11 #0x0000004b (n = 17) (*) 13 #0x00000064 (n = 1) ( ) 15 #0x00000063 (n = 3) (*) 16 #0x00000047 (n = 1) ( ) 17 #0x0000004a (n = 6) (*) 18 #0x00000048 (n = 1) ( ) 19 #0x00000049 (n = 2) (*) 20 #0x00000050 (n = 12) ( ) 22 #0x0000004c (n = 1) ( ) 23 #0x00000065 (n = 2) (*) 24 #0x0000004f (n = 5) (*) 25 #0x0000004d (n = 1) ( ) 26 #0x0000004e (n = 2) (*) 27 #0x00000061 (n = 28) ( ) 30 #0x00000051 (n = 2) (*) 32 #0x00000052 (n = 1) ( ) 33 #0x00000057 (n = 4) ( ) 34 #0x00000067 (n = 1) (*) 35 #0x00000054 (n = 6) (*) 36 #0x00000069 (n = 1) (*) 37 #0x00000053 (n = 10) (*) 38 #0x00000068 (n = 1) (*) 39 #0x00000056 (n = 3) (*) 40 #0x00000055 (n = 1) (*) 41 #0x00000060 (n = 41) (*) 43 #0x00000058 (n = 1) (*) 45 #0x00000059 (n = 3) (*) 46 #0x0000006e (n = 1) (*) 47 #0x0000005f (n = 12) (*) 48 #0x0000005a (n = 1) ( ) 49 #0x00000075 (n = 3) (*) 50 #0x0000005b (n = 1) ( ) 51 #0x0000005e (n = 6) ( ) 53 #0x00000071 (n = 2) (*) 57 #0x00000074 (n = 1) ( ) 59 #0x0000005d (n = 8) (*) 61 #0x0000005c (n = 1) (*) 62 tree dump, ht = 2 #0x00000062 (n = 2) (*) 6 #0x00000066 (n = 1) ( ) 23 #0x00000070 (n = 5) ( ) 33 #0x0000006a (n = 2) (*) 36 #0x0000006f (n = 1) ( ) 40 #0x0000006b (n = 10) (*) 43 #0x0000006d (n = 1) ( ) 48 #0x0000006c (n = 2) (*) 49 #0x00000072 (n = 4) ( ) 61 #0x00000073 (n = 1) (*) 62