diff options
author | Franklin Wei <git@fwei.tk> | 2017-04-29 18:21:56 -0400 |
---|---|---|
committer | Franklin Wei <git@fwei.tk> | 2017-04-29 18:24:42 -0400 |
commit | 881746789a489fad85aae8317555f73dbe261556 (patch) | |
tree | cec2946362c4698c8db3c10f3242ef546c2c22dd /apps/plugins/puzzles/src/tree234.c | |
parent | 03dd4b92be7dcd5c8ab06da3810887060e06abd5 (diff) | |
download | rockbox-881746789a489fad85aae8317555f73dbe261556.tar.gz rockbox-881746789a489fad85aae8317555f73dbe261556.zip |
puzzles: refactor and resync with upstream
This brings puzzles up-to-date with upstream revision
2d333750272c3967cfd5cd3677572cddeaad5932, though certain changes made
by me, including cursor-only Untangle and some compilation fixes
remain. Upstream code has been moved to its separate subdirectory and
future syncs can be done by simply copying over the new sources.
Change-Id: Ia6506ca5f78c3627165ea6791d38db414ace0804
Diffstat (limited to 'apps/plugins/puzzles/src/tree234.c')
-rw-r--r-- | apps/plugins/puzzles/src/tree234.c | 2200 |
1 files changed, 2200 insertions, 0 deletions
diff --git a/apps/plugins/puzzles/src/tree234.c b/apps/plugins/puzzles/src/tree234.c new file mode 100644 index 0000000000..4b3151ee2f --- /dev/null +++ b/apps/plugins/puzzles/src/tree234.c | |||
@@ -0,0 +1,2200 @@ | |||
1 | /* | ||
2 | * tree234.c: reasonably generic counted 2-3-4 tree routines. | ||
3 | * | ||
4 | * This file is copyright 1999-2001 Simon Tatham. | ||
5 | * | ||
6 | * Permission is hereby granted, free of charge, to any person | ||
7 | * obtaining a copy of this software and associated documentation | ||
8 | * files (the "Software"), to deal in the Software without | ||
9 | * restriction, including without limitation the rights to use, | ||
10 | * copy, modify, merge, publish, distribute, sublicense, and/or | ||
11 | * sell copies of the Software, and to permit persons to whom the | ||
12 | * Software is furnished to do so, subject to the following | ||
13 | * conditions: | ||
14 | * | ||
15 | * The above copyright notice and this permission notice shall be | ||
16 | * included in all copies or substantial portions of the Software. | ||
17 | * | ||
18 | * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, | ||
19 | * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES | ||
20 | * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND | ||
21 | * NONINFRINGEMENT. IN NO EVENT SHALL SIMON TATHAM BE LIABLE FOR | ||
22 | * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF | ||
23 | * CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN | ||
24 | * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE | ||
25 | * SOFTWARE. | ||
26 | */ | ||
27 | |||
28 | #include <stdio.h> | ||
29 | #include <stdlib.h> | ||
30 | #include <assert.h> | ||
31 | |||
32 | #include "tree234.h" | ||
33 | |||
34 | #include "puzzles.h" /* for smalloc/sfree */ | ||
35 | |||
36 | #ifdef TEST | ||
37 | #define LOG(x) (printf x) | ||
38 | #define smalloc malloc | ||
39 | #define srealloc realloc | ||
40 | #define sfree free | ||
41 | #else | ||
42 | #define LOG(x) | ||
43 | #endif | ||
44 | |||
45 | typedef struct node234_Tag node234; | ||
46 | |||
47 | struct tree234_Tag { | ||
48 | node234 *root; | ||
49 | cmpfn234 cmp; | ||
50 | }; | ||
51 | |||
52 | struct node234_Tag { | ||
53 | node234 *parent; | ||
54 | node234 *kids[4]; | ||
55 | int counts[4]; | ||
56 | void *elems[3]; | ||
57 | }; | ||
58 | |||
59 | /* | ||
60 | * Create a 2-3-4 tree. | ||
61 | */ | ||
62 | tree234 *newtree234(cmpfn234 cmp) { | ||
63 | tree234 *ret = snew(tree234); | ||
64 | LOG(("created tree %p\n", ret)); | ||
65 | ret->root = NULL; | ||
66 | ret->cmp = cmp; | ||
67 | return ret; | ||
68 | } | ||
69 | |||
70 | /* | ||
71 | * Free a 2-3-4 tree (not including freeing the elements). | ||
72 | */ | ||
73 | static void freenode234(node234 *n) { | ||
74 | if (!n) | ||
75 | return; | ||
76 | freenode234(n->kids[0]); | ||
77 | freenode234(n->kids[1]); | ||
78 | freenode234(n->kids[2]); | ||
79 | freenode234(n->kids[3]); | ||
80 | sfree(n); | ||
81 | } | ||
82 | void freetree234(tree234 *t) { | ||
83 | freenode234(t->root); | ||
84 | sfree(t); | ||
85 | } | ||
86 | |||
87 | /* | ||
88 | * Internal function to count a node. | ||
89 | */ | ||
90 | static int countnode234(node234 *n) { | ||
91 | int count = 0; | ||
92 | int i; | ||
93 | if (!n) | ||
94 | return 0; | ||
95 | for (i = 0; i < 4; i++) | ||
96 | count += n->counts[i]; | ||
97 | for (i = 0; i < 3; i++) | ||
98 | if (n->elems[i]) | ||
99 | count++; | ||
100 | return count; | ||
101 | } | ||
102 | |||
103 | /* | ||
104 | * Count the elements in a tree. | ||
105 | */ | ||
106 | int count234(tree234 *t) { | ||
107 | if (t->root) | ||
108 | return countnode234(t->root); | ||
109 | else | ||
110 | return 0; | ||
111 | } | ||
112 | |||
113 | /* | ||
114 | * Propagate a node overflow up a tree until it stops. Returns 0 or | ||
115 | * 1, depending on whether the root had to be split or not. | ||
116 | */ | ||
117 | static int add234_insert(node234 *left, void *e, node234 *right, | ||
118 | node234 **root, node234 *n, int ki) { | ||
119 | int lcount, rcount; | ||
120 | /* | ||
121 | * We need to insert the new left/element/right set in n at | ||
122 | * child position ki. | ||
123 | */ | ||
124 | lcount = countnode234(left); | ||
125 | rcount = countnode234(right); | ||
126 | while (n) { | ||
127 | LOG((" at %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n", | ||
128 | n, | ||
129 | n->kids[0], n->counts[0], n->elems[0], | ||
130 | n->kids[1], n->counts[1], n->elems[1], | ||
131 | n->kids[2], n->counts[2], n->elems[2], | ||
132 | n->kids[3], n->counts[3])); | ||
133 | LOG((" need to insert %p/%d \"%s\" %p/%d at position %d\n", | ||
134 | left, lcount, e, right, rcount, ki)); | ||
135 | if (n->elems[1] == NULL) { | ||
136 | /* | ||
137 | * Insert in a 2-node; simple. | ||
138 | */ | ||
139 | if (ki == 0) { | ||
140 | LOG((" inserting on left of 2-node\n")); | ||
141 | n->kids[2] = n->kids[1]; n->counts[2] = n->counts[1]; | ||
142 | n->elems[1] = n->elems[0]; | ||
143 | n->kids[1] = right; n->counts[1] = rcount; | ||
144 | n->elems[0] = e; | ||
145 | n->kids[0] = left; n->counts[0] = lcount; | ||
146 | } else { /* ki == 1 */ | ||
147 | LOG((" inserting on right of 2-node\n")); | ||
148 | n->kids[2] = right; n->counts[2] = rcount; | ||
149 | n->elems[1] = e; | ||
150 | n->kids[1] = left; n->counts[1] = lcount; | ||
151 | } | ||
152 | if (n->kids[0]) n->kids[0]->parent = n; | ||
153 | if (n->kids[1]) n->kids[1]->parent = n; | ||
154 | if (n->kids[2]) n->kids[2]->parent = n; | ||
155 | LOG((" done\n")); | ||
156 | break; | ||
157 | } else if (n->elems[2] == NULL) { | ||
158 | /* | ||
159 | * Insert in a 3-node; simple. | ||
160 | */ | ||
161 | if (ki == 0) { | ||
162 | LOG((" inserting on left of 3-node\n")); | ||
163 | n->kids[3] = n->kids[2]; n->counts[3] = n->counts[2]; | ||
164 | n->elems[2] = n->elems[1]; | ||
165 | n->kids[2] = n->kids[1]; n->counts[2] = n->counts[1]; | ||
166 | n->elems[1] = n->elems[0]; | ||
167 | n->kids[1] = right; n->counts[1] = rcount; | ||
168 | n->elems[0] = e; | ||
169 | n->kids[0] = left; n->counts[0] = lcount; | ||
170 | } else if (ki == 1) { | ||
171 | LOG((" inserting in middle of 3-node\n")); | ||
172 | n->kids[3] = n->kids[2]; n->counts[3] = n->counts[2]; | ||
173 | n->elems[2] = n->elems[1]; | ||
174 | n->kids[2] = right; n->counts[2] = rcount; | ||
175 | n->elems[1] = e; | ||
176 | n->kids[1] = left; n->counts[1] = lcount; | ||
177 | } else { /* ki == 2 */ | ||
178 | LOG((" inserting on right of 3-node\n")); | ||
179 | n->kids[3] = right; n->counts[3] = rcount; | ||
180 | n->elems[2] = e; | ||
181 | n->kids[2] = left; n->counts[2] = lcount; | ||
182 | } | ||
183 | if (n->kids[0]) n->kids[0]->parent = n; | ||
184 | if (n->kids[1]) n->kids[1]->parent = n; | ||
185 | if (n->kids[2]) n->kids[2]->parent = n; | ||
186 | if (n->kids[3]) n->kids[3]->parent = n; | ||
187 | LOG((" done\n")); | ||
188 | break; | ||
189 | } else { | ||
190 | node234 *m = snew(node234); | ||
191 | m->parent = n->parent; | ||
192 | LOG((" splitting a 4-node; created new node %p\n", m)); | ||
193 | /* | ||
194 | * Insert in a 4-node; split into a 2-node and a | ||
195 | * 3-node, and move focus up a level. | ||
196 | * | ||
197 | * I don't think it matters which way round we put the | ||
198 | * 2 and the 3. For simplicity, we'll put the 3 first | ||
199 | * always. | ||
200 | */ | ||
201 | if (ki == 0) { | ||
202 | m->kids[0] = left; m->counts[0] = lcount; | ||
203 | m->elems[0] = e; | ||
204 | m->kids[1] = right; m->counts[1] = rcount; | ||
205 | m->elems[1] = n->elems[0]; | ||
206 | m->kids[2] = n->kids[1]; m->counts[2] = n->counts[1]; | ||
207 | e = n->elems[1]; | ||
208 | n->kids[0] = n->kids[2]; n->counts[0] = n->counts[2]; | ||
209 | n->elems[0] = n->elems[2]; | ||
210 | n->kids[1] = n->kids[3]; n->counts[1] = n->counts[3]; | ||
211 | } else if (ki == 1) { | ||
212 | m->kids[0] = n->kids[0]; m->counts[0] = n->counts[0]; | ||
213 | m->elems[0] = n->elems[0]; | ||
214 | m->kids[1] = left; m->counts[1] = lcount; | ||
215 | m->elems[1] = e; | ||
216 | m->kids[2] = right; m->counts[2] = rcount; | ||
217 | e = n->elems[1]; | ||
218 | n->kids[0] = n->kids[2]; n->counts[0] = n->counts[2]; | ||
219 | n->elems[0] = n->elems[2]; | ||
220 | n->kids[1] = n->kids[3]; n->counts[1] = n->counts[3]; | ||
221 | } else if (ki == 2) { | ||
222 | m->kids[0] = n->kids[0]; m->counts[0] = n->counts[0]; | ||
223 | m->elems[0] = n->elems[0]; | ||
224 | m->kids[1] = n->kids[1]; m->counts[1] = n->counts[1]; | ||
225 | m->elems[1] = n->elems[1]; | ||
226 | m->kids[2] = left; m->counts[2] = lcount; | ||
227 | /* e = e; */ | ||
228 | n->kids[0] = right; n->counts[0] = rcount; | ||
229 | n->elems[0] = n->elems[2]; | ||
230 | n->kids[1] = n->kids[3]; n->counts[1] = n->counts[3]; | ||
231 | } else { /* ki == 3 */ | ||
232 | m->kids[0] = n->kids[0]; m->counts[0] = n->counts[0]; | ||
233 | m->elems[0] = n->elems[0]; | ||
234 | m->kids[1] = n->kids[1]; m->counts[1] = n->counts[1]; | ||
235 | m->elems[1] = n->elems[1]; | ||
236 | m->kids[2] = n->kids[2]; m->counts[2] = n->counts[2]; | ||
237 | n->kids[0] = left; n->counts[0] = lcount; | ||
238 | n->elems[0] = e; | ||
239 | n->kids[1] = right; n->counts[1] = rcount; | ||
240 | e = n->elems[2]; | ||
241 | } | ||
242 | m->kids[3] = n->kids[3] = n->kids[2] = NULL; | ||
243 | m->counts[3] = n->counts[3] = n->counts[2] = 0; | ||
244 | m->elems[2] = n->elems[2] = n->elems[1] = NULL; | ||
245 | if (m->kids[0]) m->kids[0]->parent = m; | ||
246 | if (m->kids[1]) m->kids[1]->parent = m; | ||
247 | if (m->kids[2]) m->kids[2]->parent = m; | ||
248 | if (n->kids[0]) n->kids[0]->parent = n; | ||
249 | if (n->kids[1]) n->kids[1]->parent = n; | ||
250 | LOG((" left (%p): %p/%d \"%s\" %p/%d \"%s\" %p/%d\n", m, | ||
251 | m->kids[0], m->counts[0], m->elems[0], | ||
252 | m->kids[1], m->counts[1], m->elems[1], | ||
253 | m->kids[2], m->counts[2])); | ||
254 | LOG((" right (%p): %p/%d \"%s\" %p/%d\n", n, | ||
255 | n->kids[0], n->counts[0], n->elems[0], | ||
256 | n->kids[1], n->counts[1])); | ||
257 | left = m; lcount = countnode234(left); | ||
258 | right = n; rcount = countnode234(right); | ||
259 | } | ||
260 | if (n->parent) | ||
261 | ki = (n->parent->kids[0] == n ? 0 : | ||
262 | n->parent->kids[1] == n ? 1 : | ||
263 | n->parent->kids[2] == n ? 2 : 3); | ||
264 | n = n->parent; | ||
265 | } | ||
266 | |||
267 | /* | ||
268 | * If we've come out of here by `break', n will still be | ||
269 | * non-NULL and all we need to do is go back up the tree | ||
270 | * updating counts. If we've come here because n is NULL, we | ||
271 | * need to create a new root for the tree because the old one | ||
272 | * has just split into two. */ | ||
273 | if (n) { | ||
274 | while (n->parent) { | ||
275 | int count = countnode234(n); | ||
276 | int childnum; | ||
277 | childnum = (n->parent->kids[0] == n ? 0 : | ||
278 | n->parent->kids[1] == n ? 1 : | ||
279 | n->parent->kids[2] == n ? 2 : 3); | ||
280 | n->parent->counts[childnum] = count; | ||
281 | n = n->parent; | ||
282 | } | ||
283 | return 0; /* root unchanged */ | ||
284 | } else { | ||
285 | LOG((" root is overloaded, split into two\n")); | ||
286 | (*root) = snew(node234); | ||
287 | (*root)->kids[0] = left; (*root)->counts[0] = lcount; | ||
288 | (*root)->elems[0] = e; | ||
289 | (*root)->kids[1] = right; (*root)->counts[1] = rcount; | ||
290 | (*root)->elems[1] = NULL; | ||
291 | (*root)->kids[2] = NULL; (*root)->counts[2] = 0; | ||
292 | (*root)->elems[2] = NULL; | ||
293 | (*root)->kids[3] = NULL; (*root)->counts[3] = 0; | ||
294 | (*root)->parent = NULL; | ||
295 | if ((*root)->kids[0]) (*root)->kids[0]->parent = (*root); | ||
296 | if ((*root)->kids[1]) (*root)->kids[1]->parent = (*root); | ||
297 | LOG((" new root is %p/%d \"%s\" %p/%d\n", | ||
298 | (*root)->kids[0], (*root)->counts[0], | ||
299 | (*root)->elems[0], | ||
300 | (*root)->kids[1], (*root)->counts[1])); | ||
301 | return 1; /* root moved */ | ||
302 | } | ||
303 | } | ||
304 | |||
305 | /* | ||
306 | * Add an element e to a 2-3-4 tree t. Returns e on success, or if | ||
307 | * an existing element compares equal, returns that. | ||
308 | */ | ||
309 | static void *add234_internal(tree234 *t, void *e, int index) { | ||
310 | node234 *n; | ||
311 | int ki; | ||
312 | void *orig_e = e; | ||
313 | int c; | ||
314 | |||
315 | LOG(("adding element \"%s\" to tree %p\n", e, t)); | ||
316 | if (t->root == NULL) { | ||
317 | t->root = snew(node234); | ||
318 | t->root->elems[1] = t->root->elems[2] = NULL; | ||
319 | t->root->kids[0] = t->root->kids[1] = NULL; | ||
320 | t->root->kids[2] = t->root->kids[3] = NULL; | ||
321 | t->root->counts[0] = t->root->counts[1] = 0; | ||
322 | t->root->counts[2] = t->root->counts[3] = 0; | ||
323 | t->root->parent = NULL; | ||
324 | t->root->elems[0] = e; | ||
325 | LOG((" created root %p\n", t->root)); | ||
326 | return orig_e; | ||
327 | } | ||
328 | |||
329 | n = t->root; | ||
330 | while (n) { | ||
331 | LOG((" node %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n", | ||
332 | n, | ||
333 | n->kids[0], n->counts[0], n->elems[0], | ||
334 | n->kids[1], n->counts[1], n->elems[1], | ||
335 | n->kids[2], n->counts[2], n->elems[2], | ||
336 | n->kids[3], n->counts[3])); | ||
337 | if (index >= 0) { | ||
338 | if (!n->kids[0]) { | ||
339 | /* | ||
340 | * Leaf node. We want to insert at kid position | ||
341 | * equal to the index: | ||
342 | * | ||
343 | * 0 A 1 B 2 C 3 | ||
344 | */ | ||
345 | ki = index; | ||
346 | } else { | ||
347 | /* | ||
348 | * Internal node. We always descend through it (add | ||
349 | * always starts at the bottom, never in the | ||
350 | * middle). | ||
351 | */ | ||
352 | if (index <= n->counts[0]) { | ||
353 | ki = 0; | ||
354 | } else if (index -= n->counts[0] + 1, index <= n->counts[1]) { | ||
355 | ki = 1; | ||
356 | } else if (index -= n->counts[1] + 1, index <= n->counts[2]) { | ||
357 | ki = 2; | ||
358 | } else if (index -= n->counts[2] + 1, index <= n->counts[3]) { | ||
359 | ki = 3; | ||
360 | } else | ||
361 | return NULL; /* error: index out of range */ | ||
362 | } | ||
363 | } else { | ||
364 | if ((c = t->cmp(e, n->elems[0])) < 0) | ||
365 | ki = 0; | ||
366 | else if (c == 0) | ||
367 | return n->elems[0]; /* already exists */ | ||
368 | else if (n->elems[1] == NULL || (c = t->cmp(e, n->elems[1])) < 0) | ||
369 | ki = 1; | ||
370 | else if (c == 0) | ||
371 | return n->elems[1]; /* already exists */ | ||
372 | else if (n->elems[2] == NULL || (c = t->cmp(e, n->elems[2])) < 0) | ||
373 | ki = 2; | ||
374 | else if (c == 0) | ||
375 | return n->elems[2]; /* already exists */ | ||
376 | else | ||
377 | ki = 3; | ||
378 | } | ||
379 | LOG((" moving to child %d (%p)\n", ki, n->kids[ki])); | ||
380 | if (!n->kids[ki]) | ||
381 | break; | ||
382 | n = n->kids[ki]; | ||
383 | } | ||
384 | |||
385 | add234_insert(NULL, e, NULL, &t->root, n, ki); | ||
386 | |||
387 | return orig_e; | ||
388 | } | ||
389 | |||
390 | void *add234(tree234 *t, void *e) { | ||
391 | if (!t->cmp) /* tree is unsorted */ | ||
392 | return NULL; | ||
393 | |||
394 | return add234_internal(t, e, -1); | ||
395 | } | ||
396 | void *addpos234(tree234 *t, void *e, int index) { | ||
397 | if (index < 0 || /* index out of range */ | ||
398 | t->cmp) /* tree is sorted */ | ||
399 | return NULL; /* return failure */ | ||
400 | |||
401 | return add234_internal(t, e, index); /* this checks the upper bound */ | ||
402 | } | ||
403 | |||
404 | /* | ||
405 | * Look up the element at a given numeric index in a 2-3-4 tree. | ||
406 | * Returns NULL if the index is out of range. | ||
407 | */ | ||
408 | void *index234(tree234 *t, int index) { | ||
409 | node234 *n; | ||
410 | |||
411 | if (!t->root) | ||
412 | return NULL; /* tree is empty */ | ||
413 | |||
414 | if (index < 0 || index >= countnode234(t->root)) | ||
415 | return NULL; /* out of range */ | ||
416 | |||
417 | n = t->root; | ||
418 | |||
419 | while (n) { | ||
420 | if (index < n->counts[0]) | ||
421 | n = n->kids[0]; | ||
422 | else if (index -= n->counts[0] + 1, index < 0) | ||
423 | return n->elems[0]; | ||
424 | else if (index < n->counts[1]) | ||
425 | n = n->kids[1]; | ||
426 | else if (index -= n->counts[1] + 1, index < 0) | ||
427 | return n->elems[1]; | ||
428 | else if (index < n->counts[2]) | ||
429 | n = n->kids[2]; | ||
430 | else if (index -= n->counts[2] + 1, index < 0) | ||
431 | return n->elems[2]; | ||
432 | else | ||
433 | n = n->kids[3]; | ||
434 | } | ||
435 | |||
436 | /* We shouldn't ever get here. I wonder how we did. */ | ||
437 | return NULL; | ||
438 | } | ||
439 | |||
440 | /* | ||
441 | * Find an element e in a sorted 2-3-4 tree t. Returns NULL if not | ||
442 | * found. e is always passed as the first argument to cmp, so cmp | ||
443 | * can be an asymmetric function if desired. cmp can also be passed | ||
444 | * as NULL, in which case the compare function from the tree proper | ||
445 | * will be used. | ||
446 | */ | ||
447 | void *findrelpos234(tree234 *t, void *e, cmpfn234 cmp, | ||
448 | int relation, int *index) { | ||
449 | node234 *n; | ||
450 | void *ret; | ||
451 | int c; | ||
452 | int idx, ecount, kcount, cmpret; | ||
453 | |||
454 | if (t->root == NULL) | ||
455 | return NULL; | ||
456 | |||
457 | if (cmp == NULL) | ||
458 | cmp = t->cmp; | ||
459 | |||
460 | n = t->root; | ||
461 | /* | ||
462 | * Attempt to find the element itself. | ||
463 | */ | ||
464 | idx = 0; | ||
465 | ecount = -1; | ||
466 | /* | ||
467 | * Prepare a fake `cmp' result if e is NULL. | ||
468 | */ | ||
469 | cmpret = 0; | ||
470 | if (e == NULL) { | ||
471 | assert(relation == REL234_LT || relation == REL234_GT); | ||
472 | if (relation == REL234_LT) | ||
473 | cmpret = +1; /* e is a max: always greater */ | ||
474 | else if (relation == REL234_GT) | ||
475 | cmpret = -1; /* e is a min: always smaller */ | ||
476 | } | ||
477 | while (1) { | ||
478 | for (kcount = 0; kcount < 4; kcount++) { | ||
479 | if (kcount >= 3 || n->elems[kcount] == NULL || | ||
480 | (c = cmpret ? cmpret : cmp(e, n->elems[kcount])) < 0) { | ||
481 | break; | ||
482 | } | ||
483 | if (n->kids[kcount]) idx += n->counts[kcount]; | ||
484 | if (c == 0) { | ||
485 | ecount = kcount; | ||
486 | break; | ||
487 | } | ||
488 | idx++; | ||
489 | } | ||
490 | if (ecount >= 0) | ||
491 | break; | ||
492 | if (n->kids[kcount]) | ||
493 | n = n->kids[kcount]; | ||
494 | else | ||
495 | break; | ||
496 | } | ||
497 | |||
498 | if (ecount >= 0) { | ||
499 | /* | ||
500 | * We have found the element we're looking for. It's | ||
501 | * n->elems[ecount], at tree index idx. If our search | ||
502 | * relation is EQ, LE or GE we can now go home. | ||
503 | */ | ||
504 | if (relation != REL234_LT && relation != REL234_GT) { | ||
505 | if (index) *index = idx; | ||
506 | return n->elems[ecount]; | ||
507 | } | ||
508 | |||
509 | /* | ||
510 | * Otherwise, we'll do an indexed lookup for the previous | ||
511 | * or next element. (It would be perfectly possible to | ||
512 | * implement these search types in a non-counted tree by | ||
513 | * going back up from where we are, but far more fiddly.) | ||
514 | */ | ||
515 | if (relation == REL234_LT) | ||
516 | idx--; | ||
517 | else | ||
518 | idx++; | ||
519 | } else { | ||
520 | /* | ||
521 | * We've found our way to the bottom of the tree and we | ||
522 | * know where we would insert this node if we wanted to: | ||
523 | * we'd put it in in place of the (empty) subtree | ||
524 | * n->kids[kcount], and it would have index idx | ||
525 | * | ||
526 | * But the actual element isn't there. So if our search | ||
527 | * relation is EQ, we're doomed. | ||
528 | */ | ||
529 | if (relation == REL234_EQ) | ||
530 | return NULL; | ||
531 | |||
532 | /* | ||
533 | * Otherwise, we must do an index lookup for index idx-1 | ||
534 | * (if we're going left - LE or LT) or index idx (if we're | ||
535 | * going right - GE or GT). | ||
536 | */ | ||
537 | if (relation == REL234_LT || relation == REL234_LE) { | ||
538 | idx--; | ||
539 | } | ||
540 | } | ||
541 | |||
542 | /* | ||
543 | * We know the index of the element we want; just call index234 | ||
544 | * to do the rest. This will return NULL if the index is out of | ||
545 | * bounds, which is exactly what we want. | ||
546 | */ | ||
547 | ret = index234(t, idx); | ||
548 | if (ret && index) *index = idx; | ||
549 | return ret; | ||
550 | } | ||
551 | void *find234(tree234 *t, void *e, cmpfn234 cmp) { | ||
552 | return findrelpos234(t, e, cmp, REL234_EQ, NULL); | ||
553 | } | ||
554 | void *findrel234(tree234 *t, void *e, cmpfn234 cmp, int relation) { | ||
555 | return findrelpos234(t, e, cmp, relation, NULL); | ||
556 | } | ||
557 | void *findpos234(tree234 *t, void *e, cmpfn234 cmp, int *index) { | ||
558 | return findrelpos234(t, e, cmp, REL234_EQ, index); | ||
559 | } | ||
560 | |||
561 | /* | ||
562 | * Tree transformation used in delete and split: move a subtree | ||
563 | * right, from child ki of a node to the next child. Update k and | ||
564 | * index so that they still point to the same place in the | ||
565 | * transformed tree. Assumes the destination child is not full, and | ||
566 | * that the source child does have a subtree to spare. Can cope if | ||
567 | * the destination child is undersized. | ||
568 | * | ||
569 | * . C . . B . | ||
570 | * / \ -> / \ | ||
571 | * [more] a A b B c d D e [more] a A b c C d D e | ||
572 | * | ||
573 | * . C . . B . | ||
574 | * / \ -> / \ | ||
575 | * [more] a A b B c d [more] a A b c C d | ||
576 | */ | ||
577 | static void trans234_subtree_right(node234 *n, int ki, int *k, int *index) { | ||
578 | node234 *src, *dest; | ||
579 | int i, srclen, adjust; | ||
580 | |||
581 | src = n->kids[ki]; | ||
582 | dest = n->kids[ki+1]; | ||
583 | |||
584 | LOG((" trans234_subtree_right(%p, %d):\n", n, ki)); | ||
585 | LOG((" parent %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n", | ||
586 | n, | ||
587 | n->kids[0], n->counts[0], n->elems[0], | ||
588 | n->kids[1], n->counts[1], n->elems[1], | ||
589 | n->kids[2], n->counts[2], n->elems[2], | ||
590 | n->kids[3], n->counts[3])); | ||
591 | LOG((" src %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n", | ||
592 | src, | ||
593 | src->kids[0], src->counts[0], src->elems[0], | ||
594 | src->kids[1], src->counts[1], src->elems[1], | ||
595 | src->kids[2], src->counts[2], src->elems[2], | ||
596 | src->kids[3], src->counts[3])); | ||
597 | LOG((" dest %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n", | ||
598 | dest, | ||
599 | dest->kids[0], dest->counts[0], dest->elems[0], | ||
600 | dest->kids[1], dest->counts[1], dest->elems[1], | ||
601 | dest->kids[2], dest->counts[2], dest->elems[2], | ||
602 | dest->kids[3], dest->counts[3])); | ||
603 | /* | ||
604 | * Move over the rest of the destination node to make space. | ||
605 | */ | ||
606 | dest->kids[3] = dest->kids[2]; dest->counts[3] = dest->counts[2]; | ||
607 | dest->elems[2] = dest->elems[1]; | ||
608 | dest->kids[2] = dest->kids[1]; dest->counts[2] = dest->counts[1]; | ||
609 | dest->elems[1] = dest->elems[0]; | ||
610 | dest->kids[1] = dest->kids[0]; dest->counts[1] = dest->counts[0]; | ||
611 | |||
612 | /* which element to move over */ | ||
613 | i = (src->elems[2] ? 2 : src->elems[1] ? 1 : 0); | ||
614 | |||
615 | dest->elems[0] = n->elems[ki]; | ||
616 | n->elems[ki] = src->elems[i]; | ||
617 | src->elems[i] = NULL; | ||
618 | |||
619 | dest->kids[0] = src->kids[i+1]; dest->counts[0] = src->counts[i+1]; | ||
620 | src->kids[i+1] = NULL; src->counts[i+1] = 0; | ||
621 | |||
622 | if (dest->kids[0]) dest->kids[0]->parent = dest; | ||
623 | |||
624 | adjust = dest->counts[0] + 1; | ||
625 | |||
626 | n->counts[ki] -= adjust; | ||
627 | n->counts[ki+1] += adjust; | ||
628 | |||
629 | srclen = n->counts[ki]; | ||
630 | |||
631 | if (k) { | ||
632 | LOG((" before: k,index = %d,%d\n", (*k), (*index))); | ||
633 | if ((*k) == ki && (*index) > srclen) { | ||
634 | (*index) -= srclen + 1; | ||
635 | (*k)++; | ||
636 | } else if ((*k) == ki+1) { | ||
637 | (*index) += adjust; | ||
638 | } | ||
639 | LOG((" after: k,index = %d,%d\n", (*k), (*index))); | ||
640 | } | ||
641 | |||
642 | LOG((" parent %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n", | ||
643 | n, | ||
644 | n->kids[0], n->counts[0], n->elems[0], | ||
645 | n->kids[1], n->counts[1], n->elems[1], | ||
646 | n->kids[2], n->counts[2], n->elems[2], | ||
647 | n->kids[3], n->counts[3])); | ||
648 | LOG((" src %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n", | ||
649 | src, | ||
650 | src->kids[0], src->counts[0], src->elems[0], | ||
651 | src->kids[1], src->counts[1], src->elems[1], | ||
652 | src->kids[2], src->counts[2], src->elems[2], | ||
653 | src->kids[3], src->counts[3])); | ||
654 | LOG((" dest %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n", | ||
655 | dest, | ||
656 | dest->kids[0], dest->counts[0], dest->elems[0], | ||
657 | dest->kids[1], dest->counts[1], dest->elems[1], | ||
658 | dest->kids[2], dest->counts[2], dest->elems[2], | ||
659 | dest->kids[3], dest->counts[3])); | ||
660 | } | ||
661 | |||
662 | /* | ||
663 | * Tree transformation used in delete and split: move a subtree | ||
664 | * left, from child ki of a node to the previous child. Update k | ||
665 | * and index so that they still point to the same place in the | ||
666 | * transformed tree. Assumes the destination child is not full, and | ||
667 | * that the source child does have a subtree to spare. Can cope if | ||
668 | * the destination child is undersized. | ||
669 | * | ||
670 | * . B . . C . | ||
671 | * / \ -> / \ | ||
672 | * a A b c C d D e [more] a A b B c d D e [more] | ||
673 | * | ||
674 | * . A . . B . | ||
675 | * / \ -> / \ | ||
676 | * a b B c C d [more] a A b c C d [more] | ||
677 | */ | ||
678 | static void trans234_subtree_left(node234 *n, int ki, int *k, int *index) { | ||
679 | node234 *src, *dest; | ||
680 | int i, adjust; | ||
681 | |||
682 | src = n->kids[ki]; | ||
683 | dest = n->kids[ki-1]; | ||
684 | |||
685 | LOG((" trans234_subtree_left(%p, %d):\n", n, ki)); | ||
686 | LOG((" parent %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n", | ||
687 | n, | ||
688 | n->kids[0], n->counts[0], n->elems[0], | ||
689 | n->kids[1], n->counts[1], n->elems[1], | ||
690 | n->kids[2], n->counts[2], n->elems[2], | ||
691 | n->kids[3], n->counts[3])); | ||
692 | LOG((" dest %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n", | ||
693 | dest, | ||
694 | dest->kids[0], dest->counts[0], dest->elems[0], | ||
695 | dest->kids[1], dest->counts[1], dest->elems[1], | ||
696 | dest->kids[2], dest->counts[2], dest->elems[2], | ||
697 | dest->kids[3], dest->counts[3])); | ||
698 | LOG((" src %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n", | ||
699 | src, | ||
700 | src->kids[0], src->counts[0], src->elems[0], | ||
701 | src->kids[1], src->counts[1], src->elems[1], | ||
702 | src->kids[2], src->counts[2], src->elems[2], | ||
703 | src->kids[3], src->counts[3])); | ||
704 | |||
705 | /* where in dest to put it */ | ||
706 | i = (dest->elems[1] ? 2 : dest->elems[0] ? 1 : 0); | ||
707 | dest->elems[i] = n->elems[ki-1]; | ||
708 | n->elems[ki-1] = src->elems[0]; | ||
709 | |||
710 | dest->kids[i+1] = src->kids[0]; dest->counts[i+1] = src->counts[0]; | ||
711 | |||
712 | if (dest->kids[i+1]) dest->kids[i+1]->parent = dest; | ||
713 | |||
714 | /* | ||
715 | * Move over the rest of the source node. | ||
716 | */ | ||
717 | src->kids[0] = src->kids[1]; src->counts[0] = src->counts[1]; | ||
718 | src->elems[0] = src->elems[1]; | ||
719 | src->kids[1] = src->kids[2]; src->counts[1] = src->counts[2]; | ||
720 | src->elems[1] = src->elems[2]; | ||
721 | src->kids[2] = src->kids[3]; src->counts[2] = src->counts[3]; | ||
722 | src->elems[2] = NULL; | ||
723 | src->kids[3] = NULL; src->counts[3] = 0; | ||
724 | |||
725 | adjust = dest->counts[i+1] + 1; | ||
726 | |||
727 | n->counts[ki] -= adjust; | ||
728 | n->counts[ki-1] += adjust; | ||
729 | |||
730 | if (k) { | ||
731 | LOG((" before: k,index = %d,%d\n", (*k), (*index))); | ||
732 | if ((*k) == ki) { | ||
733 | (*index) -= adjust; | ||
734 | if ((*index) < 0) { | ||
735 | (*index) += n->counts[ki-1] + 1; | ||
736 | (*k)--; | ||
737 | } | ||
738 | } | ||
739 | LOG((" after: k,index = %d,%d\n", (*k), (*index))); | ||
740 | } | ||
741 | |||
742 | LOG((" parent %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n", | ||
743 | n, | ||
744 | n->kids[0], n->counts[0], n->elems[0], | ||
745 | n->kids[1], n->counts[1], n->elems[1], | ||
746 | n->kids[2], n->counts[2], n->elems[2], | ||
747 | n->kids[3], n->counts[3])); | ||
748 | LOG((" dest %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n", | ||
749 | dest, | ||
750 | dest->kids[0], dest->counts[0], dest->elems[0], | ||
751 | dest->kids[1], dest->counts[1], dest->elems[1], | ||
752 | dest->kids[2], dest->counts[2], dest->elems[2], | ||
753 | dest->kids[3], dest->counts[3])); | ||
754 | LOG((" src %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n", | ||
755 | src, | ||
756 | src->kids[0], src->counts[0], src->elems[0], | ||
757 | src->kids[1], src->counts[1], src->elems[1], | ||
758 | src->kids[2], src->counts[2], src->elems[2], | ||
759 | src->kids[3], src->counts[3])); | ||
760 | } | ||
761 | |||
762 | /* | ||
763 | * Tree transformation used in delete and split: merge child nodes | ||
764 | * ki and ki+1 of a node. Update k and index so that they still | ||
765 | * point to the same place in the transformed tree. Assumes both | ||
766 | * children _are_ sufficiently small. | ||
767 | * | ||
768 | * . B . . | ||
769 | * / \ -> | | ||
770 | * a A b c C d a A b B c C d | ||
771 | * | ||
772 | * This routine can also cope with either child being undersized: | ||
773 | * | ||
774 | * . A . . | ||
775 | * / \ -> | | ||
776 | * a b B c a A b B c | ||
777 | * | ||
778 | * . A . . | ||
779 | * / \ -> | | ||
780 | * a b B c C d a A b B c C d | ||
781 | */ | ||
782 | static void trans234_subtree_merge(node234 *n, int ki, int *k, int *index) { | ||
783 | node234 *left, *right; | ||
784 | int i, leftlen, rightlen, lsize, rsize; | ||
785 | |||
786 | left = n->kids[ki]; leftlen = n->counts[ki]; | ||
787 | right = n->kids[ki+1]; rightlen = n->counts[ki+1]; | ||
788 | |||
789 | LOG((" trans234_subtree_merge(%p, %d):\n", n, ki)); | ||
790 | LOG((" parent %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n", | ||
791 | n, | ||
792 | n->kids[0], n->counts[0], n->elems[0], | ||
793 | n->kids[1], n->counts[1], n->elems[1], | ||
794 | n->kids[2], n->counts[2], n->elems[2], | ||
795 | n->kids[3], n->counts[3])); | ||
796 | LOG((" left %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n", | ||
797 | left, | ||
798 | left->kids[0], left->counts[0], left->elems[0], | ||
799 | left->kids[1], left->counts[1], left->elems[1], | ||
800 | left->kids[2], left->counts[2], left->elems[2], | ||
801 | left->kids[3], left->counts[3])); | ||
802 | LOG((" right %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n", | ||
803 | right, | ||
804 | right->kids[0], right->counts[0], right->elems[0], | ||
805 | right->kids[1], right->counts[1], right->elems[1], | ||
806 | right->kids[2], right->counts[2], right->elems[2], | ||
807 | right->kids[3], right->counts[3])); | ||
808 | |||
809 | assert(!left->elems[2] && !right->elems[2]); /* neither is large! */ | ||
810 | lsize = (left->elems[1] ? 2 : left->elems[0] ? 1 : 0); | ||
811 | rsize = (right->elems[1] ? 2 : right->elems[0] ? 1 : 0); | ||
812 | |||
813 | left->elems[lsize] = n->elems[ki]; | ||
814 | |||
815 | for (i = 0; i < rsize+1; i++) { | ||
816 | left->kids[lsize+1+i] = right->kids[i]; | ||
817 | left->counts[lsize+1+i] = right->counts[i]; | ||
818 | if (left->kids[lsize+1+i]) | ||
819 | left->kids[lsize+1+i]->parent = left; | ||
820 | if (i < rsize) | ||
821 | left->elems[lsize+1+i] = right->elems[i]; | ||
822 | } | ||
823 | |||
824 | n->counts[ki] += rightlen + 1; | ||
825 | |||
826 | sfree(right); | ||
827 | |||
828 | /* | ||
829 | * Move the rest of n up by one. | ||
830 | */ | ||
831 | for (i = ki+1; i < 3; i++) { | ||
832 | n->kids[i] = n->kids[i+1]; | ||
833 | n->counts[i] = n->counts[i+1]; | ||
834 | } | ||
835 | for (i = ki; i < 2; i++) { | ||
836 | n->elems[i] = n->elems[i+1]; | ||
837 | } | ||
838 | n->kids[3] = NULL; | ||
839 | n->counts[3] = 0; | ||
840 | n->elems[2] = NULL; | ||
841 | |||
842 | if (k) { | ||
843 | LOG((" before: k,index = %d,%d\n", (*k), (*index))); | ||
844 | if ((*k) == ki+1) { | ||
845 | (*k)--; | ||
846 | (*index) += leftlen + 1; | ||
847 | } else if ((*k) > ki+1) { | ||
848 | (*k)--; | ||
849 | } | ||
850 | LOG((" after: k,index = %d,%d\n", (*k), (*index))); | ||
851 | } | ||
852 | |||
853 | LOG((" parent %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n", | ||
854 | n, | ||
855 | n->kids[0], n->counts[0], n->elems[0], | ||
856 | n->kids[1], n->counts[1], n->elems[1], | ||
857 | n->kids[2], n->counts[2], n->elems[2], | ||
858 | n->kids[3], n->counts[3])); | ||
859 | LOG((" merged %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n", | ||
860 | left, | ||
861 | left->kids[0], left->counts[0], left->elems[0], | ||
862 | left->kids[1], left->counts[1], left->elems[1], | ||
863 | left->kids[2], left->counts[2], left->elems[2], | ||
864 | left->kids[3], left->counts[3])); | ||
865 | |||
866 | } | ||
867 | |||
868 | /* | ||
869 | * Delete an element e in a 2-3-4 tree. Does not free the element, | ||
870 | * merely removes all links to it from the tree nodes. | ||
871 | */ | ||
872 | static void *delpos234_internal(tree234 *t, int index) { | ||
873 | node234 *n; | ||
874 | void *retval; | ||
875 | int ki, i; | ||
876 | |||
877 | retval = NULL; | ||
878 | |||
879 | n = t->root; /* by assumption this is non-NULL */ | ||
880 | LOG(("deleting item %d from tree %p\n", index, t)); | ||
881 | while (1) { | ||
882 | node234 *sub; | ||
883 | |||
884 | LOG((" node %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d index=%d\n", | ||
885 | n, | ||
886 | n->kids[0], n->counts[0], n->elems[0], | ||
887 | n->kids[1], n->counts[1], n->elems[1], | ||
888 | n->kids[2], n->counts[2], n->elems[2], | ||
889 | n->kids[3], n->counts[3], | ||
890 | index)); | ||
891 | if (index <= n->counts[0]) { | ||
892 | ki = 0; | ||
893 | } else if (index -= n->counts[0]+1, index <= n->counts[1]) { | ||
894 | ki = 1; | ||
895 | } else if (index -= n->counts[1]+1, index <= n->counts[2]) { | ||
896 | ki = 2; | ||
897 | } else if (index -= n->counts[2]+1, index <= n->counts[3]) { | ||
898 | ki = 3; | ||
899 | } else { | ||
900 | assert(0); /* can't happen */ | ||
901 | } | ||
902 | |||
903 | if (!n->kids[0]) | ||
904 | break; /* n is a leaf node; we're here! */ | ||
905 | |||
906 | /* | ||
907 | * Check to see if we've found our target element. If so, | ||
908 | * we must choose a new target (we'll use the old target's | ||
909 | * successor, which will be in a leaf), move it into the | ||
910 | * place of the old one, continue down to the leaf and | ||
911 | * delete the old copy of the new target. | ||
912 | */ | ||
913 | if (index == n->counts[ki]) { | ||
914 | node234 *m; | ||
915 | LOG((" found element in internal node, index %d\n", ki)); | ||
916 | assert(n->elems[ki]); /* must be a kid _before_ an element */ | ||
917 | ki++; index = 0; | ||
918 | for (m = n->kids[ki]; m->kids[0]; m = m->kids[0]) | ||
919 | continue; | ||
920 | LOG((" replacing with element \"%s\" from leaf node %p\n", | ||
921 | m->elems[0], m)); | ||
922 | retval = n->elems[ki-1]; | ||
923 | n->elems[ki-1] = m->elems[0]; | ||
924 | } | ||
925 | |||
926 | /* | ||
927 | * Recurse down to subtree ki. If it has only one element, | ||
928 | * we have to do some transformation to start with. | ||
929 | */ | ||
930 | LOG((" moving to subtree %d\n", ki)); | ||
931 | sub = n->kids[ki]; | ||
932 | if (!sub->elems[1]) { | ||
933 | LOG((" subtree has only one element!\n")); | ||
934 | if (ki > 0 && n->kids[ki-1]->elems[1]) { | ||
935 | /* | ||
936 | * Child ki has only one element, but child | ||
937 | * ki-1 has two or more. So we need to move a | ||
938 | * subtree from ki-1 to ki. | ||
939 | */ | ||
940 | trans234_subtree_right(n, ki-1, &ki, &index); | ||
941 | } else if (ki < 3 && n->kids[ki+1] && | ||
942 | n->kids[ki+1]->elems[1]) { | ||
943 | /* | ||
944 | * Child ki has only one element, but ki+1 has | ||
945 | * two or more. Move a subtree from ki+1 to ki. | ||
946 | */ | ||
947 | trans234_subtree_left(n, ki+1, &ki, &index); | ||
948 | } else { | ||
949 | /* | ||
950 | * ki is small with only small neighbours. Pick a | ||
951 | * neighbour and merge with it. | ||
952 | */ | ||
953 | trans234_subtree_merge(n, ki>0 ? ki-1 : ki, &ki, &index); | ||
954 | sub = n->kids[ki]; | ||
955 | |||
956 | if (!n->elems[0]) { | ||
957 | /* | ||
958 | * The root is empty and needs to be | ||
959 | * removed. | ||
960 | */ | ||
961 | LOG((" shifting root!\n")); | ||
962 | t->root = sub; | ||
963 | sub->parent = NULL; | ||
964 | sfree(n); | ||
965 | n = NULL; | ||
966 | } | ||
967 | } | ||
968 | } | ||
969 | |||
970 | if (n) | ||
971 | n->counts[ki]--; | ||
972 | n = sub; | ||
973 | } | ||
974 | |||
975 | /* | ||
976 | * Now n is a leaf node, and ki marks the element number we | ||
977 | * want to delete. We've already arranged for the leaf to be | ||
978 | * bigger than minimum size, so let's just go to it. | ||
979 | */ | ||
980 | assert(!n->kids[0]); | ||
981 | if (!retval) | ||
982 | retval = n->elems[ki]; | ||
983 | |||
984 | for (i = ki; i < 2 && n->elems[i+1]; i++) | ||
985 | n->elems[i] = n->elems[i+1]; | ||
986 | n->elems[i] = NULL; | ||
987 | |||
988 | /* | ||
989 | * It's just possible that we have reduced the leaf to zero | ||
990 | * size. This can only happen if it was the root - so destroy | ||
991 | * it and make the tree empty. | ||
992 | */ | ||
993 | if (!n->elems[0]) { | ||
994 | LOG((" removed last element in tree, destroying empty root\n")); | ||
995 | assert(n == t->root); | ||
996 | sfree(n); | ||
997 | t->root = NULL; | ||
998 | } | ||
999 | |||
1000 | return retval; /* finished! */ | ||
1001 | } | ||
1002 | void *delpos234(tree234 *t, int index) { | ||
1003 | if (index < 0 || index >= countnode234(t->root)) | ||
1004 | return NULL; | ||
1005 | return delpos234_internal(t, index); | ||
1006 | } | ||
1007 | void *del234(tree234 *t, void *e) { | ||
1008 | int index; | ||
1009 | if (!findrelpos234(t, e, NULL, REL234_EQ, &index)) | ||
1010 | return NULL; /* it wasn't in there anyway */ | ||
1011 | return delpos234_internal(t, index); /* it's there; delete it. */ | ||
1012 | } | ||
1013 | |||
1014 | /* | ||
1015 | * Join two subtrees together with a separator element between | ||
1016 | * them, given their relative height. | ||
1017 | * | ||
1018 | * (Height<0 means the left tree is shorter, >0 means the right | ||
1019 | * tree is shorter, =0 means (duh) they're equal.) | ||
1020 | * | ||
1021 | * It is assumed that any checks needed on the ordering criterion | ||
1022 | * have _already_ been done. | ||
1023 | * | ||
1024 | * The value returned in `height' is 0 or 1 depending on whether the | ||
1025 | * resulting tree is the same height as the original larger one, or | ||
1026 | * one higher. | ||
1027 | */ | ||
1028 | static node234 *join234_internal(node234 *left, void *sep, | ||
1029 | node234 *right, int *height) { | ||
1030 | node234 *root, *node; | ||
1031 | int relht = *height; | ||
1032 | int ki; | ||
1033 | |||
1034 | LOG((" join: joining %p \"%s\" %p, relative height is %d\n", | ||
1035 | left, sep, right, relht)); | ||
1036 | if (relht == 0) { | ||
1037 | /* | ||
1038 | * The trees are the same height. Create a new one-element | ||
1039 | * root containing the separator and pointers to the two | ||
1040 | * nodes. | ||
1041 | */ | ||
1042 | node234 *newroot; | ||
1043 | newroot = snew(node234); | ||
1044 | newroot->kids[0] = left; newroot->counts[0] = countnode234(left); | ||
1045 | newroot->elems[0] = sep; | ||
1046 | newroot->kids[1] = right; newroot->counts[1] = countnode234(right); | ||
1047 | newroot->elems[1] = NULL; | ||
1048 | newroot->kids[2] = NULL; newroot->counts[2] = 0; | ||
1049 | newroot->elems[2] = NULL; | ||
1050 | newroot->kids[3] = NULL; newroot->counts[3] = 0; | ||
1051 | newroot->parent = NULL; | ||
1052 | if (left) left->parent = newroot; | ||
1053 | if (right) right->parent = newroot; | ||
1054 | *height = 1; | ||
1055 | LOG((" join: same height, brand new root\n")); | ||
1056 | return newroot; | ||
1057 | } | ||
1058 | |||
1059 | /* | ||
1060 | * This now works like the addition algorithm on the larger | ||
1061 | * tree. We're replacing a single kid pointer with two kid | ||
1062 | * pointers separated by an element; if that causes the node to | ||
1063 | * overload, we split it in two, move a separator element up to | ||
1064 | * the next node, and repeat. | ||
1065 | */ | ||
1066 | if (relht < 0) { | ||
1067 | /* | ||
1068 | * Left tree is shorter. Search down the right tree to find | ||
1069 | * the pointer we're inserting at. | ||
1070 | */ | ||
1071 | node = root = right; | ||
1072 | while (++relht < 0) { | ||
1073 | node = node->kids[0]; | ||
1074 | } | ||
1075 | ki = 0; | ||
1076 | right = node->kids[ki]; | ||
1077 | } else { | ||
1078 | /* | ||
1079 | * Right tree is shorter; search down the left to find the | ||
1080 | * pointer we're inserting at. | ||
1081 | */ | ||
1082 | node = root = left; | ||
1083 | while (--relht > 0) { | ||
1084 | if (node->elems[2]) | ||
1085 | node = node->kids[3]; | ||
1086 | else if (node->elems[1]) | ||
1087 | node = node->kids[2]; | ||
1088 | else | ||
1089 | node = node->kids[1]; | ||
1090 | } | ||
1091 | if (node->elems[2]) | ||
1092 | ki = 3; | ||
1093 | else if (node->elems[1]) | ||
1094 | ki = 2; | ||
1095 | else | ||
1096 | ki = 1; | ||
1097 | left = node->kids[ki]; | ||
1098 | } | ||
1099 | |||
1100 | /* | ||
1101 | * Now proceed as for addition. | ||
1102 | */ | ||
1103 | *height = add234_insert(left, sep, right, &root, node, ki); | ||
1104 | |||
1105 | return root; | ||
1106 | } | ||
1107 | static int height234(tree234 *t) { | ||
1108 | int level = 0; | ||
1109 | node234 *n = t->root; | ||
1110 | while (n) { | ||
1111 | level++; | ||
1112 | n = n->kids[0]; | ||
1113 | } | ||
1114 | return level; | ||
1115 | } | ||
1116 | tree234 *join234(tree234 *t1, tree234 *t2) { | ||
1117 | int size2 = countnode234(t2->root); | ||
1118 | if (size2 > 0) { | ||
1119 | void *element; | ||
1120 | int relht; | ||
1121 | |||
1122 | if (t1->cmp) { | ||
1123 | element = index234(t2, 0); | ||
1124 | element = findrelpos234(t1, element, NULL, REL234_GE, NULL); | ||
1125 | if (element) | ||
1126 | return NULL; | ||
1127 | } | ||
1128 | |||
1129 | element = delpos234(t2, 0); | ||
1130 | relht = height234(t1) - height234(t2); | ||
1131 | t1->root = join234_internal(t1->root, element, t2->root, &relht); | ||
1132 | t2->root = NULL; | ||
1133 | } | ||
1134 | return t1; | ||
1135 | } | ||
1136 | tree234 *join234r(tree234 *t1, tree234 *t2) { | ||
1137 | int size1 = countnode234(t1->root); | ||
1138 | if (size1 > 0) { | ||
1139 | void *element; | ||
1140 | int relht; | ||
1141 | |||
1142 | if (t2->cmp) { | ||
1143 | element = index234(t1, size1-1); | ||
1144 | element = findrelpos234(t2, element, NULL, REL234_LE, NULL); | ||
1145 | if (element) | ||
1146 | return NULL; | ||
1147 | } | ||
1148 | |||
1149 | element = delpos234(t1, size1-1); | ||
1150 | relht = height234(t1) - height234(t2); | ||
1151 | t2->root = join234_internal(t1->root, element, t2->root, &relht); | ||
1152 | t1->root = NULL; | ||
1153 | } | ||
1154 | return t2; | ||
1155 | } | ||
1156 | |||
1157 | /* | ||
1158 | * Split out the first <index> elements in a tree and return a | ||
1159 | * pointer to the root node. Leave the root node of the remainder | ||
1160 | * in t. | ||
1161 | */ | ||
1162 | static node234 *split234_internal(tree234 *t, int index) { | ||
1163 | node234 *halves[2] = { NULL, NULL }, *n, *sib, *sub; | ||
1164 | node234 *lparent, *rparent; | ||
1165 | int ki, pki, i, half, lcount, rcount; | ||
1166 | |||
1167 | n = t->root; | ||
1168 | LOG(("splitting tree %p at point %d\n", t, index)); | ||
1169 | |||
1170 | /* | ||
1171 | * Easy special cases. After this we have also dealt completely | ||
1172 | * with the empty-tree case and we can assume the root exists. | ||
1173 | */ | ||
1174 | if (index == 0) /* return nothing */ | ||
1175 | return NULL; | ||
1176 | if (index == countnode234(t->root)) { /* return the whole tree */ | ||
1177 | node234 *ret = t->root; | ||
1178 | t->root = NULL; | ||
1179 | return ret; | ||
1180 | } | ||
1181 | |||
1182 | /* | ||
1183 | * Search down the tree to find the split point. | ||
1184 | */ | ||
1185 | halves[0] = halves[1] = NULL; | ||
1186 | lparent = rparent = NULL; | ||
1187 | pki = -1; | ||
1188 | while (n) { | ||
1189 | LOG((" node %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d index=%d\n", | ||
1190 | n, | ||
1191 | n->kids[0], n->counts[0], n->elems[0], | ||
1192 | n->kids[1], n->counts[1], n->elems[1], | ||
1193 | n->kids[2], n->counts[2], n->elems[2], | ||
1194 | n->kids[3], n->counts[3], | ||
1195 | index)); | ||
1196 | lcount = index; | ||
1197 | rcount = countnode234(n) - lcount; | ||
1198 | if (index <= n->counts[0]) { | ||
1199 | ki = 0; | ||
1200 | } else if (index -= n->counts[0]+1, index <= n->counts[1]) { | ||
1201 | ki = 1; | ||
1202 | } else if (index -= n->counts[1]+1, index <= n->counts[2]) { | ||
1203 | ki = 2; | ||
1204 | } else { | ||
1205 | index -= n->counts[2]+1; | ||
1206 | ki = 3; | ||
1207 | } | ||
1208 | |||
1209 | LOG((" splitting at subtree %d\n", ki)); | ||
1210 | sub = n->kids[ki]; | ||
1211 | |||
1212 | LOG((" splitting at child index %d\n", ki)); | ||
1213 | |||
1214 | /* | ||
1215 | * Split the node, put halves[0] on the right of the left | ||
1216 | * one and halves[1] on the left of the right one, put the | ||
1217 | * new node pointers in halves[0] and halves[1], and go up | ||
1218 | * a level. | ||
1219 | */ | ||
1220 | sib = snew(node234); | ||
1221 | for (i = 0; i < 3; i++) { | ||
1222 | if (i+ki < 3 && n->elems[i+ki]) { | ||
1223 | sib->elems[i] = n->elems[i+ki]; | ||
1224 | sib->kids[i+1] = n->kids[i+ki+1]; | ||
1225 | if (sib->kids[i+1]) sib->kids[i+1]->parent = sib; | ||
1226 | sib->counts[i+1] = n->counts[i+ki+1]; | ||
1227 | n->elems[i+ki] = NULL; | ||
1228 | n->kids[i+ki+1] = NULL; | ||
1229 | n->counts[i+ki+1] = 0; | ||
1230 | } else { | ||
1231 | sib->elems[i] = NULL; | ||
1232 | sib->kids[i+1] = NULL; | ||
1233 | sib->counts[i+1] = 0; | ||
1234 | } | ||
1235 | } | ||
1236 | if (lparent) { | ||
1237 | lparent->kids[pki] = n; | ||
1238 | lparent->counts[pki] = lcount; | ||
1239 | n->parent = lparent; | ||
1240 | rparent->kids[0] = sib; | ||
1241 | rparent->counts[0] = rcount; | ||
1242 | sib->parent = rparent; | ||
1243 | } else { | ||
1244 | halves[0] = n; | ||
1245 | n->parent = NULL; | ||
1246 | halves[1] = sib; | ||
1247 | sib->parent = NULL; | ||
1248 | } | ||
1249 | lparent = n; | ||
1250 | rparent = sib; | ||
1251 | pki = ki; | ||
1252 | LOG((" left node %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n", | ||
1253 | n, | ||
1254 | n->kids[0], n->counts[0], n->elems[0], | ||
1255 | n->kids[1], n->counts[1], n->elems[1], | ||
1256 | n->kids[2], n->counts[2], n->elems[2], | ||
1257 | n->kids[3], n->counts[3])); | ||
1258 | LOG((" right node %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n", | ||
1259 | sib, | ||
1260 | sib->kids[0], sib->counts[0], sib->elems[0], | ||
1261 | sib->kids[1], sib->counts[1], sib->elems[1], | ||
1262 | sib->kids[2], sib->counts[2], sib->elems[2], | ||
1263 | sib->kids[3], sib->counts[3])); | ||
1264 | |||
1265 | n = sub; | ||
1266 | } | ||
1267 | |||
1268 | /* | ||
1269 | * We've come off the bottom here, so we've successfully split | ||
1270 | * the tree into two equally high subtrees. The only problem is | ||
1271 | * that some of the nodes down the fault line will be smaller | ||
1272 | * than the minimum permitted size. (Since this is a 2-3-4 | ||
1273 | * tree, that means they'll be zero-element one-child nodes.) | ||
1274 | */ | ||
1275 | LOG((" fell off bottom, lroot is %p, rroot is %p\n", | ||
1276 | halves[0], halves[1])); | ||
1277 | assert(halves[0] != NULL); | ||
1278 | assert(halves[1] != NULL); | ||
1279 | lparent->counts[pki] = rparent->counts[0] = 0; | ||
1280 | lparent->kids[pki] = rparent->kids[0] = NULL; | ||
1281 | |||
1282 | /* | ||
1283 | * So now we go back down the tree from each of the two roots, | ||
1284 | * fixing up undersize nodes. | ||
1285 | */ | ||
1286 | for (half = 0; half < 2; half++) { | ||
1287 | /* | ||
1288 | * Remove the root if it's undersize (it will contain only | ||
1289 | * one child pointer, so just throw it away and replace it | ||
1290 | * with its child). This might happen several times. | ||
1291 | */ | ||
1292 | while (halves[half] && !halves[half]->elems[0]) { | ||
1293 | LOG((" root %p is undersize, throwing away\n", halves[half])); | ||
1294 | halves[half] = halves[half]->kids[0]; | ||
1295 | sfree(halves[half]->parent); | ||
1296 | halves[half]->parent = NULL; | ||
1297 | LOG((" new root is %p\n", halves[half])); | ||
1298 | } | ||
1299 | |||
1300 | n = halves[half]; | ||
1301 | while (n) { | ||
1302 | void (*toward)(node234 *n, int ki, int *k, int *index); | ||
1303 | int ni, merge; | ||
1304 | |||
1305 | /* | ||
1306 | * Now we have a potentially undersize node on the | ||
1307 | * right (if half==0) or left (if half==1). Sort it | ||
1308 | * out, by merging with a neighbour or by transferring | ||
1309 | * subtrees over. At this time we must also ensure that | ||
1310 | * nodes are bigger than minimum, in case we need an | ||
1311 | * element to merge two nodes below. | ||
1312 | */ | ||
1313 | LOG((" node %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n", | ||
1314 | n, | ||
1315 | n->kids[0], n->counts[0], n->elems[0], | ||
1316 | n->kids[1], n->counts[1], n->elems[1], | ||
1317 | n->kids[2], n->counts[2], n->elems[2], | ||
1318 | n->kids[3], n->counts[3])); | ||
1319 | if (half == 1) { | ||
1320 | ki = 0; /* the kid we're interested in */ | ||
1321 | ni = 1; /* the neighbour */ | ||
1322 | merge = 0; /* for merge: leftmost of the two */ | ||
1323 | toward = trans234_subtree_left; | ||
1324 | } else { | ||
1325 | ki = (n->kids[3] ? 3 : n->kids[2] ? 2 : 1); | ||
1326 | ni = ki-1; | ||
1327 | merge = ni; | ||
1328 | toward = trans234_subtree_right; | ||
1329 | } | ||
1330 | |||
1331 | sub = n->kids[ki]; | ||
1332 | if (sub && !sub->elems[1]) { | ||
1333 | /* | ||
1334 | * This node is undersized or minimum-size. If we | ||
1335 | * can merge it with its neighbour, we do so; | ||
1336 | * otherwise we must be able to transfer subtrees | ||
1337 | * over to it until it is greater than minimum | ||
1338 | * size. | ||
1339 | */ | ||
1340 | int undersized = (!sub->elems[0]); | ||
1341 | LOG((" child %d is %ssize\n", ki, | ||
1342 | undersized ? "under" : "minimum-")); | ||
1343 | LOG((" neighbour is %s\n", | ||
1344 | n->kids[ni]->elems[2] ? "large" : | ||
1345 | n->kids[ni]->elems[1] ? "medium" : "small")); | ||
1346 | if (!n->kids[ni]->elems[1] || | ||
1347 | (undersized && !n->kids[ni]->elems[2])) { | ||
1348 | /* | ||
1349 | * Neighbour is small, or possibly neighbour is | ||
1350 | * medium and we are undersize. | ||
1351 | */ | ||
1352 | trans234_subtree_merge(n, merge, NULL, NULL); | ||
1353 | sub = n->kids[merge]; | ||
1354 | if (!n->elems[0]) { | ||
1355 | /* | ||
1356 | * n is empty, and hence must have been the | ||
1357 | * root and needs to be removed. | ||
1358 | */ | ||
1359 | assert(!n->parent); | ||
1360 | LOG((" shifting root!\n")); | ||
1361 | halves[half] = sub; | ||
1362 | halves[half]->parent = NULL; | ||
1363 | sfree(n); | ||
1364 | } | ||
1365 | } else { | ||
1366 | /* Neighbour is big enough to move trees over. */ | ||
1367 | toward(n, ni, NULL, NULL); | ||
1368 | if (undersized) | ||
1369 | toward(n, ni, NULL, NULL); | ||
1370 | } | ||
1371 | } | ||
1372 | n = sub; | ||
1373 | } | ||
1374 | } | ||
1375 | |||
1376 | t->root = halves[1]; | ||
1377 | return halves[0]; | ||
1378 | } | ||
1379 | tree234 *splitpos234(tree234 *t, int index, int before) { | ||
1380 | tree234 *ret; | ||
1381 | node234 *n; | ||
1382 | int count; | ||
1383 | |||
1384 | count = countnode234(t->root); | ||
1385 | if (index < 0 || index > count) | ||
1386 | return NULL; /* error */ | ||
1387 | ret = newtree234(t->cmp); | ||
1388 | n = split234_internal(t, index); | ||
1389 | if (before) { | ||
1390 | /* We want to return the ones before the index. */ | ||
1391 | ret->root = n; | ||
1392 | } else { | ||
1393 | /* | ||
1394 | * We want to keep the ones before the index and return the | ||
1395 | * ones after. | ||
1396 | */ | ||
1397 | ret->root = t->root; | ||
1398 | t->root = n; | ||
1399 | } | ||
1400 | return ret; | ||
1401 | } | ||
1402 | tree234 *split234(tree234 *t, void *e, cmpfn234 cmp, int rel) { | ||
1403 | int before; | ||
1404 | int index; | ||
1405 | |||
1406 | assert(rel != REL234_EQ); | ||
1407 | |||
1408 | if (rel == REL234_GT || rel == REL234_GE) { | ||
1409 | before = 1; | ||
1410 | rel = (rel == REL234_GT ? REL234_LE : REL234_LT); | ||
1411 | } else { | ||
1412 | before = 0; | ||
1413 | } | ||
1414 | if (!findrelpos234(t, e, cmp, rel, &index)) | ||
1415 | index = 0; | ||
1416 | |||
1417 | return splitpos234(t, index+1, before); | ||
1418 | } | ||
1419 | |||
1420 | static node234 *copynode234(node234 *n, copyfn234 copyfn, void *copyfnstate) { | ||
1421 | int i; | ||
1422 | node234 *n2 = snew(node234); | ||
1423 | |||
1424 | for (i = 0; i < 3; i++) { | ||
1425 | if (n->elems[i] && copyfn) | ||
1426 | n2->elems[i] = copyfn(copyfnstate, n->elems[i]); | ||
1427 | else | ||
1428 | n2->elems[i] = n->elems[i]; | ||
1429 | } | ||
1430 | |||
1431 | for (i = 0; i < 4; i++) { | ||
1432 | if (n->kids[i]) { | ||
1433 | n2->kids[i] = copynode234(n->kids[i], copyfn, copyfnstate); | ||
1434 | n2->kids[i]->parent = n2; | ||
1435 | } else { | ||
1436 | n2->kids[i] = NULL; | ||
1437 | } | ||
1438 | n2->counts[i] = n->counts[i]; | ||
1439 | } | ||
1440 | |||
1441 | return n2; | ||
1442 | } | ||
1443 | tree234 *copytree234(tree234 *t, copyfn234 copyfn, void *copyfnstate) { | ||
1444 | tree234 *t2; | ||
1445 | |||
1446 | t2 = newtree234(t->cmp); | ||
1447 | if (t->root) { | ||
1448 | t2->root = copynode234(t->root, copyfn, copyfnstate); | ||
1449 | t2->root->parent = NULL; | ||
1450 | } else | ||
1451 | t2->root = NULL; | ||
1452 | |||
1453 | return t2; | ||
1454 | } | ||
1455 | |||
1456 | #ifdef TEST | ||
1457 | |||
1458 | /* | ||
1459 | * Test code for the 2-3-4 tree. This code maintains an alternative | ||
1460 | * representation of the data in the tree, in an array (using the | ||
1461 | * obvious and slow insert and delete functions). After each tree | ||
1462 | * operation, the verify() function is called, which ensures all | ||
1463 | * the tree properties are preserved: | ||
1464 | * - node->child->parent always equals node | ||
1465 | * - tree->root->parent always equals NULL | ||
1466 | * - number of kids == 0 or number of elements + 1; | ||
1467 | * - tree has the same depth everywhere | ||
1468 | * - every node has at least one element | ||
1469 | * - subtree element counts are accurate | ||
1470 | * - any NULL kid pointer is accompanied by a zero count | ||
1471 | * - in a sorted tree: ordering property between elements of a | ||
1472 | * node and elements of its children is preserved | ||
1473 | * and also ensures the list represented by the tree is the same | ||
1474 | * list it should be. (This last check also doubly verifies the | ||
1475 | * ordering properties, because the `same list it should be' is by | ||
1476 | * definition correctly ordered. It also ensures all nodes are | ||
1477 | * distinct, because the enum functions would get caught in a loop | ||
1478 | * if not.) | ||
1479 | */ | ||
1480 | |||
1481 | #include <string.h> | ||
1482 | #include <stdarg.h> | ||
1483 | |||
1484 | #define srealloc realloc | ||
1485 | |||
1486 | /* | ||
1487 | * Error reporting function. | ||
1488 | */ | ||
1489 | void error(char *fmt, ...) { | ||
1490 | va_list ap; | ||
1491 | printf("ERROR: "); | ||
1492 | va_start(ap, fmt); | ||
1493 | vfprintf(stdout, fmt, ap); | ||
1494 | va_end(ap); | ||
1495 | printf("\n"); | ||
1496 | } | ||
1497 | |||
1498 | /* The array representation of the data. */ | ||
1499 | void **array; | ||
1500 | int arraylen, arraysize; | ||
1501 | cmpfn234 cmp; | ||
1502 | |||
1503 | /* The tree representation of the same data. */ | ||
1504 | tree234 *tree; | ||
1505 | |||
1506 | /* | ||
1507 | * Routines to provide a diagnostic printout of a tree. Currently | ||
1508 | * relies on every element in the tree being a one-character string | ||
1509 | * :-) | ||
1510 | */ | ||
1511 | typedef struct { | ||
1512 | char **levels; | ||
1513 | } dispctx; | ||
1514 | |||
1515 | int dispnode(node234 *n, int level, dispctx *ctx) { | ||
1516 | if (level == 0) { | ||
1517 | int xpos = strlen(ctx->levels[0]); | ||
1518 | int len; | ||
1519 | |||
1520 | if (n->elems[2]) | ||
1521 | len = sprintf(ctx->levels[0]+xpos, " %s%s%s", | ||
1522 | n->elems[0], n->elems[1], n->elems[2]); | ||
1523 | else if (n->elems[1]) | ||
1524 | len = sprintf(ctx->levels[0]+xpos, " %s%s", | ||
1525 | n->elems[0], n->elems[1]); | ||
1526 | else | ||
1527 | len = sprintf(ctx->levels[0]+xpos, " %s", | ||
1528 | n->elems[0]); | ||
1529 | return xpos + 1 + (len-1) / 2; | ||
1530 | } else { | ||
1531 | int xpos[4], nkids; | ||
1532 | int nodelen, mypos, myleft, x, i; | ||
1533 | |||
1534 | xpos[0] = dispnode(n->kids[0], level-3, ctx); | ||
1535 | xpos[1] = dispnode(n->kids[1], level-3, ctx); | ||
1536 | nkids = 2; | ||
1537 | if (n->kids[2]) { | ||
1538 | xpos[2] = dispnode(n->kids[2], level-3, ctx); | ||
1539 | nkids = 3; | ||
1540 | } | ||
1541 | if (n->kids[3]) { | ||
1542 | xpos[3] = dispnode(n->kids[3], level-3, ctx); | ||
1543 | nkids = 4; | ||
1544 | } | ||
1545 | |||
1546 | if (nkids == 4) | ||
1547 | mypos = (xpos[1] + xpos[2]) / 2; | ||
1548 | else if (nkids == 3) | ||
1549 | mypos = xpos[1]; | ||
1550 | else | ||
1551 | mypos = (xpos[0] + xpos[1]) / 2; | ||
1552 | nodelen = nkids * 2 - 1; | ||
1553 | myleft = mypos - ((nodelen-1)/2); | ||
1554 | assert(myleft >= xpos[0]); | ||
1555 | assert(myleft + nodelen-1 <= xpos[nkids-1]); | ||
1556 | |||
1557 | x = strlen(ctx->levels[level]); | ||
1558 | while (x <= xpos[0] && x < myleft) | ||
1559 | ctx->levels[level][x++] = ' '; | ||
1560 | while (x < myleft) | ||
1561 | ctx->levels[level][x++] = '_'; | ||
1562 | if (nkids==4) | ||
1563 | x += sprintf(ctx->levels[level]+x, ".%s.%s.%s.", | ||
1564 | n->elems[0], n->elems[1], n->elems[2]); | ||
1565 | else if (nkids==3) | ||
1566 | x += sprintf(ctx->levels[level]+x, ".%s.%s.", | ||
1567 | n->elems[0], n->elems[1]); | ||
1568 | else | ||
1569 | x += sprintf(ctx->levels[level]+x, ".%s.", | ||
1570 | n->elems[0]); | ||
1571 | while (x < xpos[nkids-1]) | ||
1572 | ctx->levels[level][x++] = '_'; | ||
1573 | ctx->levels[level][x] = '\0'; | ||
1574 | |||
1575 | x = strlen(ctx->levels[level-1]); | ||
1576 | for (i = 0; i < nkids; i++) { | ||
1577 | int rpos, pos; | ||
1578 | rpos = xpos[i]; | ||
1579 | if (i > 0 && i < nkids-1) | ||
1580 | pos = myleft + 2*i; | ||
1581 | else | ||
1582 | pos = rpos; | ||
1583 | if (rpos < pos) | ||
1584 | rpos++; | ||
1585 | while (x < pos && x < rpos) | ||
1586 | ctx->levels[level-1][x++] = ' '; | ||
1587 | if (x == pos) | ||
1588 | ctx->levels[level-1][x++] = '|'; | ||
1589 | while (x < pos || x < rpos) | ||
1590 | ctx->levels[level-1][x++] = '_'; | ||
1591 | if (x == pos) | ||
1592 | ctx->levels[level-1][x++] = '|'; | ||
1593 | } | ||
1594 | ctx->levels[level-1][x] = '\0'; | ||
1595 | |||
1596 | x = strlen(ctx->levels[level-2]); | ||
1597 | for (i = 0; i < nkids; i++) { | ||
1598 | int rpos = xpos[i]; | ||
1599 | |||
1600 | while (x < rpos) | ||
1601 | ctx->levels[level-2][x++] = ' '; | ||
1602 | ctx->levels[level-2][x++] = '|'; | ||
1603 | } | ||
1604 | ctx->levels[level-2][x] = '\0'; | ||
1605 | |||
1606 | return mypos; | ||
1607 | } | ||
1608 | } | ||
1609 | |||
1610 | void disptree(tree234 *t) { | ||
1611 | dispctx ctx; | ||
1612 | char *leveldata; | ||
1613 | int width = count234(t); | ||
1614 | int ht = height234(t) * 3 - 2; | ||
1615 | int i; | ||
1616 | |||
1617 | if (!t->root) { | ||
1618 | printf("[empty tree]\n"); | ||
1619 | } | ||
1620 | |||
1621 | leveldata = smalloc(ht * (width+2)); | ||
1622 | ctx.levels = smalloc(ht * sizeof(char *)); | ||
1623 | for (i = 0; i < ht; i++) { | ||
1624 | ctx.levels[i] = leveldata + i * (width+2); | ||
1625 | ctx.levels[i][0] = '\0'; | ||
1626 | } | ||
1627 | |||
1628 | (void) dispnode(t->root, ht-1, &ctx); | ||
1629 | |||
1630 | for (i = ht; i-- ;) | ||
1631 | printf("%s\n", ctx.levels[i]); | ||
1632 | |||
1633 | sfree(ctx.levels); | ||
1634 | sfree(leveldata); | ||
1635 | } | ||
1636 | |||
1637 | typedef struct { | ||
1638 | int treedepth; | ||
1639 | int elemcount; | ||
1640 | } chkctx; | ||
1641 | |||
1642 | int chknode(chkctx *ctx, int level, node234 *node, | ||
1643 | void *lowbound, void *highbound) { | ||
1644 | int nkids, nelems; | ||
1645 | int i; | ||
1646 | int count; | ||
1647 | |||
1648 | /* Count the non-NULL kids. */ | ||
1649 | for (nkids = 0; nkids < 4 && node->kids[nkids]; nkids++); | ||
1650 | /* Ensure no kids beyond the first NULL are non-NULL. */ | ||
1651 | for (i = nkids; i < 4; i++) | ||
1652 | if (node->kids[i]) { | ||
1653 | error("node %p: nkids=%d but kids[%d] non-NULL", | ||
1654 | node, nkids, i); | ||
1655 | } else if (node->counts[i]) { | ||
1656 | error("node %p: kids[%d] NULL but count[%d]=%d nonzero", | ||
1657 | node, i, i, node->counts[i]); | ||
1658 | } | ||
1659 | |||
1660 | /* Count the non-NULL elements. */ | ||
1661 | for (nelems = 0; nelems < 3 && node->elems[nelems]; nelems++); | ||
1662 | /* Ensure no elements beyond the first NULL are non-NULL. */ | ||
1663 | for (i = nelems; i < 3; i++) | ||
1664 | if (node->elems[i]) { | ||
1665 | error("node %p: nelems=%d but elems[%d] non-NULL", | ||
1666 | node, nelems, i); | ||
1667 | } | ||
1668 | |||
1669 | if (nkids == 0) { | ||
1670 | /* | ||
1671 | * If nkids==0, this is a leaf node; verify that the tree | ||
1672 | * depth is the same everywhere. | ||
1673 | */ | ||
1674 | if (ctx->treedepth < 0) | ||
1675 | ctx->treedepth = level; /* we didn't know the depth yet */ | ||
1676 | else if (ctx->treedepth != level) | ||
1677 | error("node %p: leaf at depth %d, previously seen depth %d", | ||
1678 | node, level, ctx->treedepth); | ||
1679 | } else { | ||
1680 | /* | ||
1681 | * If nkids != 0, then it should be nelems+1, unless nelems | ||
1682 | * is 0 in which case nkids should also be 0 (and so we | ||
1683 | * shouldn't be in this condition at all). | ||
1684 | */ | ||
1685 | int shouldkids = (nelems ? nelems+1 : 0); | ||
1686 | if (nkids != shouldkids) { | ||
1687 | error("node %p: %d elems should mean %d kids but has %d", | ||
1688 | node, nelems, shouldkids, nkids); | ||
1689 | } | ||
1690 | } | ||
1691 | |||
1692 | /* | ||
1693 | * nelems should be at least 1. | ||
1694 | */ | ||
1695 | if (nelems == 0) { | ||
1696 | error("node %p: no elems", node, nkids); | ||
1697 | } | ||
1698 | |||
1699 | /* | ||
1700 | * Add nelems to the running element count of the whole tree. | ||
1701 | */ | ||
1702 | ctx->elemcount += nelems; | ||
1703 | |||
1704 | /* | ||
1705 | * Check ordering property: all elements should be strictly > | ||
1706 | * lowbound, strictly < highbound, and strictly < each other in | ||
1707 | * sequence. (lowbound and highbound are NULL at edges of tree | ||
1708 | * - both NULL at root node - and NULL is considered to be < | ||
1709 | * everything and > everything. IYSWIM.) | ||
1710 | */ | ||
1711 | if (cmp) { | ||
1712 | for (i = -1; i < nelems; i++) { | ||
1713 | void *lower = (i == -1 ? lowbound : node->elems[i]); | ||
1714 | void *higher = (i+1 == nelems ? highbound : node->elems[i+1]); | ||
1715 | if (lower && higher && cmp(lower, higher) >= 0) { | ||
1716 | error("node %p: kid comparison [%d=%s,%d=%s] failed", | ||
1717 | node, i, lower, i+1, higher); | ||
1718 | } | ||
1719 | } | ||
1720 | } | ||
1721 | |||
1722 | /* | ||
1723 | * Check parent pointers: all non-NULL kids should have a | ||
1724 | * parent pointer coming back to this node. | ||
1725 | */ | ||
1726 | for (i = 0; i < nkids; i++) | ||
1727 | if (node->kids[i]->parent != node) { | ||
1728 | error("node %p kid %d: parent ptr is %p not %p", | ||
1729 | node, i, node->kids[i]->parent, node); | ||
1730 | } | ||
1731 | |||
1732 | |||
1733 | /* | ||
1734 | * Now (finally!) recurse into subtrees. | ||
1735 | */ | ||
1736 | count = nelems; | ||
1737 | |||
1738 | for (i = 0; i < nkids; i++) { | ||
1739 | void *lower = (i == 0 ? lowbound : node->elems[i-1]); | ||
1740 | void *higher = (i >= nelems ? highbound : node->elems[i]); | ||
1741 | int subcount = chknode(ctx, level+1, node->kids[i], lower, higher); | ||
1742 | if (node->counts[i] != subcount) { | ||
1743 | error("node %p kid %d: count says %d, subtree really has %d", | ||
1744 | node, i, node->counts[i], subcount); | ||
1745 | } | ||
1746 | count += subcount; | ||
1747 | } | ||
1748 | |||
1749 | return count; | ||
1750 | } | ||
1751 | |||
1752 | void verifytree(tree234 *tree, void **array, int arraylen) { | ||
1753 | chkctx ctx; | ||
1754 | int i; | ||
1755 | void *p; | ||
1756 | |||
1757 | ctx.treedepth = -1; /* depth unknown yet */ | ||
1758 | ctx.elemcount = 0; /* no elements seen yet */ | ||
1759 | /* | ||
1760 | * Verify validity of tree properties. | ||
1761 | */ | ||
1762 | if (tree->root) { | ||
1763 | if (tree->root->parent != NULL) | ||
1764 | error("root->parent is %p should be null", tree->root->parent); | ||
1765 | chknode(&ctx, 0, tree->root, NULL, NULL); | ||
1766 | } | ||
1767 | printf("tree depth: %d\n", ctx.treedepth); | ||
1768 | /* | ||
1769 | * Enumerate the tree and ensure it matches up to the array. | ||
1770 | */ | ||
1771 | for (i = 0; NULL != (p = index234(tree, i)); i++) { | ||
1772 | if (i >= arraylen) | ||
1773 | error("tree contains more than %d elements", arraylen); | ||
1774 | if (array[i] != p) | ||
1775 | error("enum at position %d: array says %s, tree says %s", | ||
1776 | i, array[i], p); | ||
1777 | } | ||
1778 | if (ctx.elemcount != i) { | ||
1779 | error("tree really contains %d elements, enum gave %d", | ||
1780 | ctx.elemcount, i); | ||
1781 | } | ||
1782 | if (i < arraylen) { | ||
1783 | error("enum gave only %d elements, array has %d", i, arraylen); | ||
1784 | } | ||
1785 | i = count234(tree); | ||
1786 | if (ctx.elemcount != i) { | ||
1787 | error("tree really contains %d elements, count234 gave %d", | ||
1788 | ctx.elemcount, i); | ||
1789 | } | ||
1790 | } | ||
1791 | void verify(void) { verifytree(tree, array, arraylen); } | ||
1792 | |||
1793 | void internal_addtest(void *elem, int index, void *realret) { | ||
1794 | int i, j; | ||
1795 | void *retval; | ||
1796 | |||
1797 | if (arraysize < arraylen+1) { | ||
1798 | arraysize = arraylen+1+256; | ||
1799 | array = (array == NULL ? smalloc(arraysize*sizeof(*array)) : | ||
1800 | srealloc(array, arraysize*sizeof(*array))); | ||
1801 | } | ||
1802 | |||
1803 | i = index; | ||
1804 | /* now i points to the first element >= elem */ | ||
1805 | retval = elem; /* expect elem returned (success) */ | ||
1806 | for (j = arraylen; j > i; j--) | ||
1807 | array[j] = array[j-1]; | ||
1808 | array[i] = elem; /* add elem to array */ | ||
1809 | arraylen++; | ||
1810 | |||
1811 | if (realret != retval) { | ||
1812 | error("add: retval was %p expected %p", realret, retval); | ||
1813 | } | ||
1814 | |||
1815 | verify(); | ||
1816 | } | ||
1817 | |||
1818 | void addtest(void *elem) { | ||
1819 | int i; | ||
1820 | void *realret; | ||
1821 | |||
1822 | realret = add234(tree, elem); | ||
1823 | |||
1824 | i = 0; | ||
1825 | while (i < arraylen && cmp(elem, array[i]) > 0) | ||
1826 | i++; | ||
1827 | if (i < arraylen && !cmp(elem, array[i])) { | ||
1828 | void *retval = array[i]; /* expect that returned not elem */ | ||
1829 | if (realret != retval) { | ||
1830 | error("add: retval was %p expected %p", realret, retval); | ||
1831 | } | ||
1832 | } else | ||
1833 | internal_addtest(elem, i, realret); | ||
1834 | } | ||
1835 | |||
1836 | void addpostest(void *elem, int i) { | ||
1837 | void *realret; | ||
1838 | |||
1839 | realret = addpos234(tree, elem, i); | ||
1840 | |||
1841 | internal_addtest(elem, i, realret); | ||
1842 | } | ||
1843 | |||
1844 | void delpostest(int i) { | ||
1845 | int index = i; | ||
1846 | void *elem = array[i], *ret; | ||
1847 | |||
1848 | /* i points to the right element */ | ||
1849 | while (i < arraylen-1) { | ||
1850 | array[i] = array[i+1]; | ||
1851 | i++; | ||
1852 | } | ||
1853 | arraylen--; /* delete elem from array */ | ||
1854 | |||
1855 | if (tree->cmp) | ||
1856 | ret = del234(tree, elem); | ||
1857 | else | ||
1858 | ret = delpos234(tree, index); | ||
1859 | |||
1860 | if (ret != elem) { | ||
1861 | error("del returned %p, expected %p", ret, elem); | ||
1862 | } | ||
1863 | |||
1864 | verify(); | ||
1865 | } | ||
1866 | |||
1867 | void deltest(void *elem) { | ||
1868 | int i; | ||
1869 | |||
1870 | i = 0; | ||
1871 | while (i < arraylen && cmp(elem, array[i]) > 0) | ||
1872 | i++; | ||
1873 | if (i >= arraylen || cmp(elem, array[i]) != 0) | ||
1874 | return; /* don't do it! */ | ||
1875 | delpostest(i); | ||
1876 | } | ||
1877 | |||
1878 | /* A sample data set and test utility. Designed for pseudo-randomness, | ||
1879 | * and yet repeatability. */ | ||
1880 | |||
1881 | /* | ||
1882 | * This random number generator uses the `portable implementation' | ||
1883 | * given in ANSI C99 draft N869. It assumes `unsigned' is 32 bits; | ||
1884 | * change it if not. | ||
1885 | */ | ||
1886 | int randomnumber(unsigned *seed) { | ||
1887 | *seed *= 1103515245; | ||
1888 | *seed += 12345; | ||
1889 | return ((*seed) / 65536) % 32768; | ||
1890 | } | ||
1891 | |||
1892 | int mycmp(void *av, void *bv) { | ||
1893 | char const *a = (char const *)av; | ||
1894 | char const *b = (char const *)bv; | ||
1895 | return strcmp(a, b); | ||
1896 | } | ||
1897 | |||
1898 | char *strings[] = { | ||
1899 | "0", "2", "3", "I", "K", "d", "H", "J", "Q", "N", "n", "q", "j", "i", | ||
1900 | "7", "G", "F", "D", "b", "x", "g", "B", "e", "v", "V", "T", "f", "E", | ||
1901 | "S", "8", "A", "k", "X", "p", "C", "R", "a", "o", "r", "O", "Z", "u", | ||
1902 | "6", "1", "w", "L", "P", "M", "c", "U", "h", "9", "t", "5", "W", "Y", | ||
1903 | "m", "s", "l", "4", | ||
1904 | #if 0 | ||
1905 | "a", "ab", "absque", "coram", "de", | ||
1906 | "palam", "clam", "cum", "ex", "e", | ||
1907 | "sine", "tenus", "pro", "prae", | ||
1908 | "banana", "carrot", "cabbage", "broccoli", "onion", "zebra", | ||
1909 | "penguin", "blancmange", "pangolin", "whale", "hedgehog", | ||
1910 | "giraffe", "peanut", "bungee", "foo", "bar", "baz", "quux", | ||
1911 | "murfl", "spoo", "breen", "flarn", "octothorpe", | ||
1912 | "snail", "tiger", "elephant", "octopus", "warthog", "armadillo", | ||
1913 | "aardvark", "wyvern", "dragon", "elf", "dwarf", "orc", "goblin", | ||
1914 | "pixie", "basilisk", "warg", "ape", "lizard", "newt", "shopkeeper", | ||
1915 | "wand", "ring", "amulet" | ||
1916 | #endif | ||
1917 | }; | ||
1918 | |||
1919 | #define NSTR lenof(strings) | ||
1920 | |||
1921 | void findtest(void) { | ||
1922 | static const int rels[] = { | ||
1923 | REL234_EQ, REL234_GE, REL234_LE, REL234_LT, REL234_GT | ||
1924 | }; | ||
1925 | static const char *const relnames[] = { | ||
1926 | "EQ", "GE", "LE", "LT", "GT" | ||
1927 | }; | ||
1928 | int i, j, rel, index; | ||
1929 | char *p, *ret, *realret, *realret2; | ||
1930 | int lo, hi, mid, c; | ||
1931 | |||
1932 | for (i = 0; i < (int)NSTR; i++) { | ||
1933 | p = strings[i]; | ||
1934 | for (j = 0; j < (int)(sizeof(rels)/sizeof(*rels)); j++) { | ||
1935 | rel = rels[j]; | ||
1936 | |||
1937 | lo = 0; hi = arraylen-1; | ||
1938 | while (lo <= hi) { | ||
1939 | mid = (lo + hi) / 2; | ||
1940 | c = strcmp(p, array[mid]); | ||
1941 | if (c < 0) | ||
1942 | hi = mid-1; | ||
1943 | else if (c > 0) | ||
1944 | lo = mid+1; | ||
1945 | else | ||
1946 | break; | ||
1947 | } | ||
1948 | |||
1949 | if (c == 0) { | ||
1950 | if (rel == REL234_LT) | ||
1951 | ret = (mid > 0 ? array[--mid] : NULL); | ||
1952 | else if (rel == REL234_GT) | ||
1953 | ret = (mid < arraylen-1 ? array[++mid] : NULL); | ||
1954 | else | ||
1955 | ret = array[mid]; | ||
1956 | } else { | ||
1957 | assert(lo == hi+1); | ||
1958 | if (rel == REL234_LT || rel == REL234_LE) { | ||
1959 | mid = hi; | ||
1960 | ret = (hi >= 0 ? array[hi] : NULL); | ||
1961 | } else if (rel == REL234_GT || rel == REL234_GE) { | ||
1962 | mid = lo; | ||
1963 | ret = (lo < arraylen ? array[lo] : NULL); | ||
1964 | } else | ||
1965 | ret = NULL; | ||
1966 | } | ||
1967 | |||
1968 | realret = findrelpos234(tree, p, NULL, rel, &index); | ||
1969 | if (realret != ret) { | ||
1970 | error("find(\"%s\",%s) gave %s should be %s", | ||
1971 | p, relnames[j], realret, ret); | ||
1972 | } | ||
1973 | if (realret && index != mid) { | ||
1974 | error("find(\"%s\",%s) gave %d should be %d", | ||
1975 | p, relnames[j], index, mid); | ||
1976 | } | ||
1977 | if (realret && rel == REL234_EQ) { | ||
1978 | realret2 = index234(tree, index); | ||
1979 | if (realret2 != realret) { | ||
1980 | error("find(\"%s\",%s) gave %s(%d) but %d -> %s", | ||
1981 | p, relnames[j], realret, index, index, realret2); | ||
1982 | } | ||
1983 | } | ||
1984 | #if 0 | ||
1985 | printf("find(\"%s\",%s) gave %s(%d)\n", p, relnames[j], | ||
1986 | realret, index); | ||
1987 | #endif | ||
1988 | } | ||
1989 | } | ||
1990 | |||
1991 | realret = findrelpos234(tree, NULL, NULL, REL234_GT, &index); | ||
1992 | if (arraylen && (realret != array[0] || index != 0)) { | ||
1993 | error("find(NULL,GT) gave %s(%d) should be %s(0)", | ||
1994 | realret, index, array[0]); | ||
1995 | } else if (!arraylen && (realret != NULL)) { | ||
1996 | error("find(NULL,GT) gave %s(%d) should be NULL", | ||
1997 | realret, index); | ||
1998 | } | ||
1999 | |||
2000 | realret = findrelpos234(tree, NULL, NULL, REL234_LT, &index); | ||
2001 | if (arraylen && (realret != array[arraylen-1] || index != arraylen-1)) { | ||
2002 | error("find(NULL,LT) gave %s(%d) should be %s(0)", | ||
2003 | realret, index, array[arraylen-1]); | ||
2004 | } else if (!arraylen && (realret != NULL)) { | ||
2005 | error("find(NULL,LT) gave %s(%d) should be NULL", | ||
2006 | realret, index); | ||
2007 | } | ||
2008 | } | ||
2009 | |||
2010 | void splittest(tree234 *tree, void **array, int arraylen) { | ||
2011 | int i; | ||
2012 | tree234 *tree3, *tree4; | ||
2013 | for (i = 0; i <= arraylen; i++) { | ||
2014 | tree3 = copytree234(tree, NULL, NULL); | ||
2015 | tree4 = splitpos234(tree3, i, 0); | ||
2016 | verifytree(tree3, array, i); | ||
2017 | verifytree(tree4, array+i, arraylen-i); | ||
2018 | join234(tree3, tree4); | ||
2019 | freetree234(tree4); /* left empty by join */ | ||
2020 | verifytree(tree3, array, arraylen); | ||
2021 | freetree234(tree3); | ||
2022 | } | ||
2023 | } | ||
2024 | |||
2025 | int main(void) { | ||
2026 | int in[NSTR]; | ||
2027 | int i, j, k; | ||
2028 | int tworoot, tmplen; | ||
2029 | unsigned seed = 0; | ||
2030 | tree234 *tree2, *tree3, *tree4; | ||
2031 | int c; | ||
2032 | |||
2033 | setvbuf(stdout, NULL, _IOLBF, 0); | ||
2034 | |||
2035 | for (i = 0; i < (int)NSTR; i++) in[i] = 0; | ||
2036 | array = NULL; | ||
2037 | arraylen = arraysize = 0; | ||
2038 | tree = newtree234(mycmp); | ||
2039 | cmp = mycmp; | ||
2040 | |||
2041 | verify(); | ||
2042 | for (i = 0; i < 10000; i++) { | ||
2043 | j = randomnumber(&seed); | ||
2044 | j %= NSTR; | ||
2045 | printf("trial: %d\n", i); | ||
2046 | if (in[j]) { | ||
2047 | printf("deleting %s (%d)\n", strings[j], j); | ||
2048 | deltest(strings[j]); | ||
2049 | in[j] = 0; | ||
2050 | } else { | ||
2051 | printf("adding %s (%d)\n", strings[j], j); | ||
2052 | addtest(strings[j]); | ||
2053 | in[j] = 1; | ||
2054 | } | ||
2055 | disptree(tree); | ||
2056 | findtest(); | ||
2057 | } | ||
2058 | |||
2059 | while (arraylen > 0) { | ||
2060 | j = randomnumber(&seed); | ||
2061 | j %= arraylen; | ||
2062 | deltest(array[j]); | ||
2063 | } | ||
2064 | |||
2065 | freetree234(tree); | ||
2066 | |||
2067 | /* | ||
2068 | * Now try an unsorted tree. We don't really need to test | ||
2069 | * delpos234 because we know del234 is based on it, so it's | ||
2070 | * already been tested in the above sorted-tree code; but for | ||
2071 | * completeness we'll use it to tear down our unsorted tree | ||
2072 | * once we've built it. | ||
2073 | */ | ||
2074 | tree = newtree234(NULL); | ||
2075 | cmp = NULL; | ||
2076 | verify(); | ||
2077 | for (i = 0; i < 1000; i++) { | ||
2078 | printf("trial: %d\n", i); | ||
2079 | j = randomnumber(&seed); | ||
2080 | j %= NSTR; | ||
2081 | k = randomnumber(&seed); | ||
2082 | k %= count234(tree)+1; | ||
2083 | printf("adding string %s at index %d\n", strings[j], k); | ||
2084 | addpostest(strings[j], k); | ||
2085 | } | ||
2086 | |||
2087 | /* | ||
2088 | * While we have this tree in its full form, we'll take a copy | ||
2089 | * of it to use in split and join testing. | ||
2090 | */ | ||
2091 | tree2 = copytree234(tree, NULL, NULL); | ||
2092 | verifytree(tree2, array, arraylen);/* check the copy is accurate */ | ||
2093 | /* | ||
2094 | * Split tests. Split the tree at every possible point and | ||
2095 | * check the resulting subtrees. | ||
2096 | */ | ||
2097 | tworoot = (!tree2->root->elems[1]);/* see if it has a 2-root */ | ||
2098 | splittest(tree2, array, arraylen); | ||
2099 | /* | ||
2100 | * Now do the split test again, but on a tree that has a 2-root | ||
2101 | * (if the previous one didn't) or doesn't (if the previous one | ||
2102 | * did). | ||
2103 | */ | ||
2104 | tmplen = arraylen; | ||
2105 | while ((!tree2->root->elems[1]) == tworoot) { | ||
2106 | delpos234(tree2, --tmplen); | ||
2107 | } | ||
2108 | printf("now trying splits on second tree\n"); | ||
2109 | splittest(tree2, array, tmplen); | ||
2110 | freetree234(tree2); | ||
2111 | |||
2112 | /* | ||
2113 | * Back to the main testing of uncounted trees. | ||
2114 | */ | ||
2115 | while (count234(tree) > 0) { | ||
2116 | printf("cleanup: tree size %d\n", count234(tree)); | ||
2117 | j = randomnumber(&seed); | ||
2118 | j %= count234(tree); | ||
2119 | printf("deleting string %s from index %d\n", (char *)array[j], j); | ||
2120 | delpostest(j); | ||
2121 | } | ||
2122 | freetree234(tree); | ||
2123 | |||
2124 | /* | ||
2125 | * Finally, do some testing on split/join on _sorted_ trees. At | ||
2126 | * the same time, we'll be testing split on very small trees. | ||
2127 | */ | ||
2128 | tree = newtree234(mycmp); | ||
2129 | cmp = mycmp; | ||
2130 | arraylen = 0; | ||
2131 | for (i = 0; i < 17; i++) { | ||
2132 | tree2 = copytree234(tree, NULL, NULL); | ||
2133 | splittest(tree2, array, arraylen); | ||
2134 | freetree234(tree2); | ||
2135 | if (i < 16) | ||
2136 | addtest(strings[i]); | ||
2137 | } | ||
2138 | freetree234(tree); | ||
2139 | |||
2140 | /* | ||
2141 | * Test silly cases of join: join(emptytree, emptytree), and | ||
2142 | * also ensure join correctly spots when sorted trees fail the | ||
2143 | * ordering constraint. | ||
2144 | */ | ||
2145 | tree = newtree234(mycmp); | ||
2146 | tree2 = newtree234(mycmp); | ||
2147 | tree3 = newtree234(mycmp); | ||
2148 | tree4 = newtree234(mycmp); | ||
2149 | assert(mycmp(strings[0], strings[1]) < 0); /* just in case :-) */ | ||
2150 | add234(tree2, strings[1]); | ||
2151 | add234(tree4, strings[0]); | ||
2152 | array[0] = strings[0]; | ||
2153 | array[1] = strings[1]; | ||
2154 | verifytree(tree, array, 0); | ||
2155 | verifytree(tree2, array+1, 1); | ||
2156 | verifytree(tree3, array, 0); | ||
2157 | verifytree(tree4, array, 1); | ||
2158 | |||
2159 | /* | ||
2160 | * So: | ||
2161 | * - join(tree,tree3) should leave both tree and tree3 unchanged. | ||
2162 | * - joinr(tree,tree2) should leave both tree and tree2 unchanged. | ||
2163 | * - join(tree4,tree3) should leave both tree3 and tree4 unchanged. | ||
2164 | * - join(tree, tree2) should move the element from tree2 to tree. | ||
2165 | * - joinr(tree4, tree3) should move the element from tree4 to tree3. | ||
2166 | * - join(tree,tree3) should return NULL and leave both unchanged. | ||
2167 | * - join(tree3,tree) should work and create a bigger tree in tree3. | ||
2168 | */ | ||
2169 | assert(tree == join234(tree, tree3)); | ||
2170 | verifytree(tree, array, 0); | ||
2171 | verifytree(tree3, array, 0); | ||
2172 | assert(tree2 == join234r(tree, tree2)); | ||
2173 | verifytree(tree, array, 0); | ||
2174 | verifytree(tree2, array+1, 1); | ||
2175 | assert(tree4 == join234(tree4, tree3)); | ||
2176 | verifytree(tree3, array, 0); | ||
2177 | verifytree(tree4, array, 1); | ||
2178 | assert(tree == join234(tree, tree2)); | ||
2179 | verifytree(tree, array+1, 1); | ||
2180 | verifytree(tree2, array, 0); | ||
2181 | assert(tree3 == join234r(tree4, tree3)); | ||
2182 | verifytree(tree3, array, 1); | ||
2183 | verifytree(tree4, array, 0); | ||
2184 | assert(NULL == join234(tree, tree3)); | ||
2185 | verifytree(tree, array+1, 1); | ||
2186 | verifytree(tree3, array, 1); | ||
2187 | assert(tree3 == join234(tree3, tree)); | ||
2188 | verifytree(tree3, array, 2); | ||
2189 | verifytree(tree, array, 0); | ||
2190 | |||
2191 | return 0; | ||
2192 | } | ||
2193 | |||
2194 | #endif | ||
2195 | |||
2196 | #if 0 /* sorted list of strings might be useful */ | ||
2197 | { | ||
2198 | "0", "1", "2", "3", "4", "5", "6", "7", "8", "9", "A", "B", "C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O", "P", "Q", "R", "S", "T", "U", "V", "W", "X", "Y", "Z", "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", | ||
2199 | } | ||
2200 | #endif | ||