2 ;; `rbtree_join' could look for a sibling node's colour without checking
3 ;; that it actually existed.
5 #0x00000001 (n = 2) (*) 0
6 #0x00000000 (n = 1) ( ) 3
9 #0x00000001 (n = 1) ( ) 0
10 #0x00000000 (n = 3) (*) 3
11 #0x00000002 (n = 1) ( ) 6
13 ;; In `rbtree_split' with an empty path, the root of the initial tree
14 ;; wasn't forcibly blackened. Make sure this is done and that the
15 ;; black heights are correctly tracked. This causes all manner of
16 ;; trouble otherwise, including leaking nodes because `rbtree_join'
17 ;; assumes that a tree with zero black-height must be empty -- which
20 #0x00000003 (n = 1) (*) 12
21 #0x00000005 (n = 3) (*) 13
22 #0x00000004 (n = 1) (*) 14
23 #0x0000000a (n = 8) ( ) 16
24 #0x00000006 (n = 1) (*) 17
25 #0x00000009 (n = 4) (*) 18
26 #0x00000008 (n = 2) (*) 19
27 #0x00000007 (n = 1) ( ) 23
28 #0x00000011 (n = 15) (*) 24
29 #0x0000000b (n = 1) (*) 28
30 #0x0000000d (n = 3) ( ) 32
31 #0x0000000c (n = 1) (*) 35
32 #0x00000010 (n = 6) (*) 36
33 #0x0000000f (n = 2) (*) 37
34 #0x0000000e (n = 1) ( ) 39
36 #0x00000007 (n = 1) (*) 23
37 #0x00000011 (n = 3) ( ) 24
38 #0x0000000b (n = 1) (*) 28
39 #0x0000000d (n = 8) (*) 32
40 #0x0000000c (n = 1) (*) 35
41 #0x00000010 (n = 4) ( ) 36
42 #0x0000000f (n = 2) (*) 37
43 #0x0000000e (n = 1) ( ) 39
47 #0x00000003 (n = 1) (*) 12
48 #0x00000005 (n = 3) (*) 13
49 #0x00000004 (n = 1) (*) 14
50 #0x0000000a (n = 7) (*) 16
51 #0x00000006 (n = 1) (*) 17
52 #0x00000009 (n = 3) (*) 18
53 #0x00000008 (n = 1) (*) 19
55 ;; The hairy test case which found both of these bugs.
57 #0x00000012 (n = 1) ( ) 0
58 #0x00000013 (n = 2) (*) 3
59 #0x00000015 (n = 4) (*) 6
60 #0x00000014 (n = 1) (*) 9
61 #0x0000001d (n = 12) ( ) 11
62 #0x00000016 (n = 1) ( ) 12
63 #0x00000017 (n = 2) (*) 21
64 #0x0000001c (n = 7) (*) 22
65 #0x00000019 (n = 2) (*) 27
66 #0x00000018 (n = 1) ( ) 28
67 #0x0000001b (n = 4) ( ) 31
68 #0x0000001a (n = 1) (*) 35
69 #0x00000023 (n = 18) (*) 41
70 #0x0000001e (n = 1) ( ) 49
71 #0x00000020 (n = 3) (*) 50
72 #0x0000001f (n = 1) ( ) 55
73 #0x00000022 (n = 5) (*) 57
74 #0x00000021 (n = 1) (*) 59
76 #0x00000025 (n = 2) (*) 0
77 #0x00000024 (n = 1) ( ) 1
78 #0x00000027 (n = 4) (*) 3
79 #0x00000026 (n = 1) (*) 4
80 #0x0000002c (n = 9) ( ) 6
81 #0x00000028 (n = 1) ( ) 11
82 #0x00000029 (n = 2) (*) 12
83 #0x0000002b (n = 4) (*) 13
84 #0x0000002a (n = 1) (*) 14
85 #0x00000037 (n = 20) (*) 16
86 #0x0000002d (n = 1) (*) 17
87 #0x00000030 (n = 4) (*) 18
88 #0x0000002f (n = 2) (*) 19
89 #0x0000002e (n = 1) ( ) 23
90 #0x00000036 (n = 10) ( ) 24
91 #0x00000031 (n = 1) (*) 28
92 #0x00000033 (n = 3) ( ) 32
93 #0x00000032 (n = 1) (*) 35
94 #0x00000035 (n = 5) (*) 36
95 #0x00000034 (n = 1) (*) 37
96 #0x00000042 (n = 31) (*) 39
97 #0x00000038 (n = 1) (*) 41
98 #0x0000003b (n = 4) (*) 43
99 #0x0000003a (n = 2) (*) 44
100 #0x00000039 (n = 1) ( ) 45
101 #0x00000041 (n = 10) (*) 52
102 #0x0000003c (n = 1) (*) 53
103 #0x0000003e (n = 3) ( ) 56
104 #0x0000003d (n = 1) (*) 58
105 #0x00000040 (n = 5) (*) 60
106 #0x0000003f (n = 1) (*) 61
108 #0x00000024 (n = 2) (*) 1
109 #0x00000026 (n = 1) ( ) 4
110 #0x0000002b (n = 4) ( ) 13
111 #0x0000002a (n = 1) (*) 14
112 #0x00000037 (n = 8) (*) 16
113 #0x0000002d (n = 1) (*) 17
114 #0x00000030 (n = 3) ( ) 18
115 #0x0000002f (n = 1) (*) 19
116 #0x0000002e (n = 23) (*) 23
117 #0x00000036 (n = 1) (*) 24
118 #0x00000033 (n = 3) ( ) 32
119 #0x00000035 (n = 1) (*) 36
120 #0x00000034 (n = 5) (*) 37
121 #0x00000042 (n = 1) (*) 39
122 #0x0000003b (n = 14) ( ) 43
123 #0x0000003a (n = 2) (*) 44
124 #0x00000039 (n = 1) ( ) 45
125 #0x00000041 (n = 8) (*) 52
126 #0x0000003c (n = 2) (*) 53
127 #0x0000003e (n = 1) ( ) 56
128 #0x0000003d (n = 5) ( ) 58
129 #0x00000040 (n = 2) (*) 60
130 #0x0000003f (n = 1) ( ) 61
132 #0x00000025 (n = 1) ( ) 0
133 #0x00000027 (n = 3) (*) 3
134 #0x0000002c (n = 1) ( ) 6
135 #0x00000028 (n = 5) ( ) 11
136 #0x00000029 (n = 1) (*) 12
137 #0x00000031 (n = 8) (*) 28
138 #0x00000032 (n = 2) (*) 35
139 #0x00000038 (n = 1) ( ) 41
141 #0x00000012 (n = 1) ( ) 0
142 #0x00000013 (n = 2) (*) 3
143 #0x00000015 (n = 4) (*) 6
144 #0x00000014 (n = 1) (*) 9
145 #0x0000001d (n = 12) ( ) 11
146 #0x00000016 (n = 1) ( ) 12
147 #0x00000017 (n = 2) (*) 21
148 #0x0000001c (n = 7) (*) 22
149 #0x00000019 (n = 2) (*) 27
150 #0x00000018 (n = 1) ( ) 28
151 #0x0000001b (n = 4) ( ) 31
152 #0x0000001a (n = 1) (*) 35
153 #0x00000023 (n = 18) (*) 41
154 #0x0000001e (n = 1) ( ) 49
155 #0x00000020 (n = 3) (*) 50
156 #0x0000001f (n = 1) ( ) 55
157 #0x00000022 (n = 5) (*) 57
158 #0x00000021 (n = 1) (*) 59
160 ;; `rbtree_splitroot' just could not track subtree heights correctly.
162 #0x00000044 (n = 2) (*) 4
163 #0x00000043 (n = 1) ( ) 6
164 #0x00000046 (n = 4) (*) 10
165 #0x00000045 (n = 1) (*) 11
166 #0x0000004b (n = 9) ( ) 13
167 #0x00000047 (n = 1) (*) 17
168 #0x0000004a (n = 4) (*) 18
169 #0x00000048 (n = 1) ( ) 19
170 #0x00000049 (n = 2) (*) 20
171 #0x00000050 (n = 14) (*) 22
172 #0x0000004c (n = 1) (*) 23
173 #0x0000004f (n = 4) (*) 25
174 #0x0000004d (n = 1) ( ) 26
175 #0x0000004e (n = 2) (*) 27
176 #0x00000061 (n = 31) (*) 30
177 #0x00000051 (n = 1) ( ) 32
178 #0x00000052 (n = 2) (*) 33
179 #0x00000057 (n = 7) (*) 34
180 #0x00000054 (n = 2) (*) 36
181 #0x00000053 (n = 1) ( ) 38
182 #0x00000056 (n = 4) ( ) 40
183 #0x00000055 (n = 1) (*) 41
184 #0x00000060 (n = 16) (*) 43
185 #0x00000058 (n = 1) ( ) 45
186 #0x00000059 (n = 2) (*) 46
187 #0x0000005f (n = 8) (*) 48
188 #0x0000005a (n = 1) ( ) 49
189 #0x0000005b (n = 2) (*) 51
190 #0x0000005e (n = 5) ( ) 53
191 #0x0000005d (n = 2) (*) 61
192 #0x0000005c (n = 1) ( ) 62
194 #0x00000062 (n = 1) (*) 6
195 #0x00000064 (n = 3) ( ) 15
196 #0x00000063 (n = 1) (*) 16
197 #0x00000066 (n = 5) (*) 23
198 #0x00000065 (n = 1) (*) 24
199 #0x00000070 (n = 15) ( ) 33
200 #0x00000067 (n = 1) (*) 35
201 #0x0000006a (n = 4) ( ) 36
202 #0x00000069 (n = 2) (*) 37
203 #0x00000068 (n = 1) ( ) 39
204 #0x0000006f (n = 9) (*) 40
205 #0x0000006b (n = 1) (*) 43
206 #0x0000006e (n = 4) ( ) 47
207 #0x0000006d (n = 2) (*) 48
208 #0x0000006c (n = 1) ( ) 49
209 #0x00000075 (n = 20) (*) 50
210 #0x00000071 (n = 1) (*) 57
211 #0x00000074 (n = 4) (*) 59
212 #0x00000072 (n = 1) ( ) 61
213 #0x00000073 (n = 2) (*) 62
215 #0x00000044 (n = 1) ( ) 4
216 #0x00000043 (n = 2) (*) 6
217 #0x00000046 (n = 4) (*) 10
218 #0x00000045 (n = 1) (*) 11
219 #0x0000004b (n = 17) (*) 13
220 #0x00000064 (n = 1) ( ) 15
221 #0x00000063 (n = 3) (*) 16
222 #0x00000047 (n = 1) ( ) 17
223 #0x0000004a (n = 6) (*) 18
224 #0x00000048 (n = 1) ( ) 19
225 #0x00000049 (n = 2) (*) 20
226 #0x00000050 (n = 12) ( ) 22
227 #0x0000004c (n = 1) ( ) 23
228 #0x00000065 (n = 2) (*) 24
229 #0x0000004f (n = 5) (*) 25
230 #0x0000004d (n = 1) ( ) 26
231 #0x0000004e (n = 2) (*) 27
232 #0x00000061 (n = 28) ( ) 30
233 #0x00000051 (n = 2) (*) 32
234 #0x00000052 (n = 1) ( ) 33
235 #0x00000057 (n = 4) ( ) 34
236 #0x00000067 (n = 1) (*) 35
237 #0x00000054 (n = 6) (*) 36
238 #0x00000069 (n = 1) (*) 37
239 #0x00000053 (n = 10) (*) 38
240 #0x00000068 (n = 1) (*) 39
241 #0x00000056 (n = 3) (*) 40
242 #0x00000055 (n = 1) (*) 41
243 #0x00000060 (n = 41) (*) 43
244 #0x00000058 (n = 1) (*) 45
245 #0x00000059 (n = 3) (*) 46
246 #0x0000006e (n = 1) (*) 47
247 #0x0000005f (n = 12) (*) 48
248 #0x0000005a (n = 1) ( ) 49
249 #0x00000075 (n = 3) (*) 50
250 #0x0000005b (n = 1) ( ) 51
251 #0x0000005e (n = 6) ( ) 53
252 #0x00000071 (n = 2) (*) 57
253 #0x00000074 (n = 1) ( ) 59
254 #0x0000005d (n = 8) (*) 61
255 #0x0000005c (n = 1) (*) 62
257 #0x00000062 (n = 2) (*) 6
258 #0x00000066 (n = 1) ( ) 23
259 #0x00000070 (n = 5) ( ) 33
260 #0x0000006a (n = 2) (*) 36
261 #0x0000006f (n = 1) ( ) 40
262 #0x0000006b (n = 10) (*) 43
263 #0x0000006d (n = 1) ( ) 48
264 #0x0000006c (n = 2) (*) 49
265 #0x00000072 (n = 4) ( ) 61
266 #0x00000073 (n = 1) (*) 62
~mdw / xyla / blob