tsiry-sandratraina.com
A modern Music Player Daemon based on Rockbox open source high quality audio player
libadwaita
audio
rust
zig
deno
mpris
rockbox
mpd
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#define TREE234_INTERNALS
33#include "tree234.h"
34
35#include "puzzles.h" /* for smalloc/sfree */
36
37#ifdef DEBUG_TREE234
38#include <stdarg.h>
39static void logprintf(const char *fmt, ...)
40{
41 va_list ap;
42 va_start(ap, fmt);
43 vprintf(fmt, ap);
44 va_end(ap);
45}
46#define LOG(x) (logprintf x)
47#else
48#define LOG(x)
49#endif
50
51/*
52 * Create a 2-3-4 tree.
53 */
54tree234 *newtree234(cmpfn234 cmp) {
55 tree234 *ret = snew(tree234);
56 LOG(("created tree %p\n", ret));
57 ret->root = NULL;
58 ret->cmp = cmp;
59 return ret;
60}
61
62/*
63 * Free a 2-3-4 tree (not including freeing the elements).
64 */
65static void freenode234(node234 *n) {
66 if (!n)
67 return;
68 freenode234(n->kids[0]);
69 freenode234(n->kids[1]);
70 freenode234(n->kids[2]);
71 freenode234(n->kids[3]);
72 sfree(n);
73}
74void freetree234(tree234 *t) {
75 freenode234(t->root);
76 sfree(t);
77}
78
79/*
80 * Internal function to count a node.
81 */
82static int countnode234(node234 *n) {
83 int count = 0;
84 int i;
85 if (!n)
86 return 0;
87 for (i = 0; i < 4; i++)
88 count += n->counts[i];
89 for (i = 0; i < 3; i++)
90 if (n->elems[i])
91 count++;
92 return count;
93}
94
95/*
96 * Count the elements in a tree.
97 */
98int count234(tree234 *t) {
99 if (t->root)
100 return countnode234(t->root);
101 else
102 return 0;
103}
104
105/*
106 * Propagate a node overflow up a tree until it stops. Returns 0 or
107 * 1, depending on whether the root had to be split or not.
108 */
109static int add234_insert(node234 *left, void *e, node234 *right,
110 node234 **root, node234 *n, int ki) {
111 int lcount, rcount;
112 /*
113 * We need to insert the new left/element/right set in n at
114 * child position ki.
115 */
116 lcount = countnode234(left);
117 rcount = countnode234(right);
118 while (n) {
119 LOG((" at %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
120 n,
121 n->kids[0], n->counts[0], n->elems[0],
122 n->kids[1], n->counts[1], n->elems[1],
123 n->kids[2], n->counts[2], n->elems[2],
124 n->kids[3], n->counts[3]));
125 LOG((" need to insert %p/%d \"%s\" %p/%d at position %d\n",
126 left, lcount, e, right, rcount, ki));
127 if (n->elems[1] == NULL) {
128 /*
129 * Insert in a 2-node; simple.
130 */
131 if (ki == 0) {
132 LOG((" inserting on left of 2-node\n"));
133 n->kids[2] = n->kids[1]; n->counts[2] = n->counts[1];
134 n->elems[1] = n->elems[0];
135 n->kids[1] = right; n->counts[1] = rcount;
136 n->elems[0] = e;
137 n->kids[0] = left; n->counts[0] = lcount;
138 } else { /* ki == 1 */
139 LOG((" inserting on right of 2-node\n"));
140 n->kids[2] = right; n->counts[2] = rcount;
141 n->elems[1] = e;
142 n->kids[1] = left; n->counts[1] = lcount;
143 }
144 if (n->kids[0]) n->kids[0]->parent = n;
145 if (n->kids[1]) n->kids[1]->parent = n;
146 if (n->kids[2]) n->kids[2]->parent = n;
147 LOG((" done\n"));
148 break;
149 } else if (n->elems[2] == NULL) {
150 /*
151 * Insert in a 3-node; simple.
152 */
153 if (ki == 0) {
154 LOG((" inserting on left of 3-node\n"));
155 n->kids[3] = n->kids[2]; n->counts[3] = n->counts[2];
156 n->elems[2] = n->elems[1];
157 n->kids[2] = n->kids[1]; n->counts[2] = n->counts[1];
158 n->elems[1] = n->elems[0];
159 n->kids[1] = right; n->counts[1] = rcount;
160 n->elems[0] = e;
161 n->kids[0] = left; n->counts[0] = lcount;
162 } else if (ki == 1) {
163 LOG((" inserting in middle of 3-node\n"));
164 n->kids[3] = n->kids[2]; n->counts[3] = n->counts[2];
165 n->elems[2] = n->elems[1];
166 n->kids[2] = right; n->counts[2] = rcount;
167 n->elems[1] = e;
168 n->kids[1] = left; n->counts[1] = lcount;
169 } else { /* ki == 2 */
170 LOG((" inserting on right of 3-node\n"));
171 n->kids[3] = right; n->counts[3] = rcount;
172 n->elems[2] = e;
173 n->kids[2] = left; n->counts[2] = lcount;
174 }
175 if (n->kids[0]) n->kids[0]->parent = n;
176 if (n->kids[1]) n->kids[1]->parent = n;
177 if (n->kids[2]) n->kids[2]->parent = n;
178 if (n->kids[3]) n->kids[3]->parent = n;
179 LOG((" done\n"));
180 break;
181 } else {
182 node234 *m = snew(node234);
183 m->parent = n->parent;
184 LOG((" splitting a 4-node; created new node %p\n", m));
185 /*
186 * Insert in a 4-node; split into a 2-node and a
187 * 3-node, and move focus up a level.
188 *
189 * I don't think it matters which way round we put the
190 * 2 and the 3. For simplicity, we'll put the 3 first
191 * always.
192 */
193 if (ki == 0) {
194 m->kids[0] = left; m->counts[0] = lcount;
195 m->elems[0] = e;
196 m->kids[1] = right; m->counts[1] = rcount;
197 m->elems[1] = n->elems[0];
198 m->kids[2] = n->kids[1]; m->counts[2] = n->counts[1];
199 e = n->elems[1];
200 n->kids[0] = n->kids[2]; n->counts[0] = n->counts[2];
201 n->elems[0] = n->elems[2];
202 n->kids[1] = n->kids[3]; n->counts[1] = n->counts[3];
203 } else if (ki == 1) {
204 m->kids[0] = n->kids[0]; m->counts[0] = n->counts[0];
205 m->elems[0] = n->elems[0];
206 m->kids[1] = left; m->counts[1] = lcount;
207 m->elems[1] = e;
208 m->kids[2] = right; m->counts[2] = rcount;
209 e = n->elems[1];
210 n->kids[0] = n->kids[2]; n->counts[0] = n->counts[2];
211 n->elems[0] = n->elems[2];
212 n->kids[1] = n->kids[3]; n->counts[1] = n->counts[3];
213 } else if (ki == 2) {
214 m->kids[0] = n->kids[0]; m->counts[0] = n->counts[0];
215 m->elems[0] = n->elems[0];
216 m->kids[1] = n->kids[1]; m->counts[1] = n->counts[1];
217 m->elems[1] = n->elems[1];
218 m->kids[2] = left; m->counts[2] = lcount;
219 /* e = e; */
220 n->kids[0] = right; n->counts[0] = rcount;
221 n->elems[0] = n->elems[2];
222 n->kids[1] = n->kids[3]; n->counts[1] = n->counts[3];
223 } else { /* ki == 3 */
224 m->kids[0] = n->kids[0]; m->counts[0] = n->counts[0];
225 m->elems[0] = n->elems[0];
226 m->kids[1] = n->kids[1]; m->counts[1] = n->counts[1];
227 m->elems[1] = n->elems[1];
228 m->kids[2] = n->kids[2]; m->counts[2] = n->counts[2];
229 n->kids[0] = left; n->counts[0] = lcount;
230 n->elems[0] = e;
231 n->kids[1] = right; n->counts[1] = rcount;
232 e = n->elems[2];
233 }
234 m->kids[3] = n->kids[3] = n->kids[2] = NULL;
235 m->counts[3] = n->counts[3] = n->counts[2] = 0;
236 m->elems[2] = n->elems[2] = n->elems[1] = NULL;
237 if (m->kids[0]) m->kids[0]->parent = m;
238 if (m->kids[1]) m->kids[1]->parent = m;
239 if (m->kids[2]) m->kids[2]->parent = m;
240 if (n->kids[0]) n->kids[0]->parent = n;
241 if (n->kids[1]) n->kids[1]->parent = n;
242 LOG((" left (%p): %p/%d \"%s\" %p/%d \"%s\" %p/%d\n", m,
243 m->kids[0], m->counts[0], m->elems[0],
244 m->kids[1], m->counts[1], m->elems[1],
245 m->kids[2], m->counts[2]));
246 LOG((" right (%p): %p/%d \"%s\" %p/%d\n", n,
247 n->kids[0], n->counts[0], n->elems[0],
248 n->kids[1], n->counts[1]));
249 left = m; lcount = countnode234(left);
250 right = n; rcount = countnode234(right);
251 }
252 if (n->parent)
253 ki = (n->parent->kids[0] == n ? 0 :
254 n->parent->kids[1] == n ? 1 :
255 n->parent->kids[2] == n ? 2 : 3);
256 n = n->parent;
257 }
258
259 /*
260 * If we've come out of here by `break', n will still be
261 * non-NULL and all we need to do is go back up the tree
262 * updating counts. If we've come here because n is NULL, we
263 * need to create a new root for the tree because the old one
264 * has just split into two. */
265 if (n) {
266 while (n->parent) {
267 int count = countnode234(n);
268 int childnum;
269 childnum = (n->parent->kids[0] == n ? 0 :
270 n->parent->kids[1] == n ? 1 :
271 n->parent->kids[2] == n ? 2 : 3);
272 n->parent->counts[childnum] = count;
273 n = n->parent;
274 }
275 return 0; /* root unchanged */
276 } else {
277 LOG((" root is overloaded, split into two\n"));
278 (*root) = snew(node234);
279 (*root)->kids[0] = left; (*root)->counts[0] = lcount;
280 (*root)->elems[0] = e;
281 (*root)->kids[1] = right; (*root)->counts[1] = rcount;
282 (*root)->elems[1] = NULL;
283 (*root)->kids[2] = NULL; (*root)->counts[2] = 0;
284 (*root)->elems[2] = NULL;
285 (*root)->kids[3] = NULL; (*root)->counts[3] = 0;
286 (*root)->parent = NULL;
287 if ((*root)->kids[0]) (*root)->kids[0]->parent = (*root);
288 if ((*root)->kids[1]) (*root)->kids[1]->parent = (*root);
289 LOG((" new root is %p/%d \"%s\" %p/%d\n",
290 (*root)->kids[0], (*root)->counts[0],
291 (*root)->elems[0],
292 (*root)->kids[1], (*root)->counts[1]));
293 return 1; /* root moved */
294 }
295}
296
297/*
298 * Add an element e to a 2-3-4 tree t. Returns e on success, or if
299 * an existing element compares equal, returns that.
300 */
301static void *add234_internal(tree234 *t, void *e, int index) {
302 node234 *n;
303 int ki;
304 void *orig_e = e;
305 int c;
306
307 LOG(("adding element \"%s\" to tree %p\n", e, t));
308 if (t->root == NULL) {
309 t->root = snew(node234);
310 t->root->elems[1] = t->root->elems[2] = NULL;
311 t->root->kids[0] = t->root->kids[1] = NULL;
312 t->root->kids[2] = t->root->kids[3] = NULL;
313 t->root->counts[0] = t->root->counts[1] = 0;
314 t->root->counts[2] = t->root->counts[3] = 0;
315 t->root->parent = NULL;
316 t->root->elems[0] = e;
317 LOG((" created root %p\n", t->root));
318 return orig_e;
319 }
320
321 n = t->root;
322 do {
323 LOG((" node %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
324 n,
325 n->kids[0], n->counts[0], n->elems[0],
326 n->kids[1], n->counts[1], n->elems[1],
327 n->kids[2], n->counts[2], n->elems[2],
328 n->kids[3], n->counts[3]));
329 if (index >= 0) {
330 if (!n->kids[0]) {
331 /*
332 * Leaf node. We want to insert at kid position
333 * equal to the index:
334 *
335 * 0 A 1 B 2 C 3
336 */
337 ki = index;
338 } else {
339 /*
340 * Internal node. We always descend through it (add
341 * always starts at the bottom, never in the
342 * middle).
343 */
344 if (index <= n->counts[0]) {
345 ki = 0;
346 } else if (index -= n->counts[0] + 1, index <= n->counts[1]) {
347 ki = 1;
348 } else if (index -= n->counts[1] + 1, index <= n->counts[2]) {
349 ki = 2;
350 } else if (index -= n->counts[2] + 1, index <= n->counts[3]) {
351 ki = 3;
352 } else
353 return NULL; /* error: index out of range */
354 }
355 } else {
356 if ((c = t->cmp(e, n->elems[0])) < 0)
357 ki = 0;
358 else if (c == 0)
359 return n->elems[0]; /* already exists */
360 else if (n->elems[1] == NULL || (c = t->cmp(e, n->elems[1])) < 0)
361 ki = 1;
362 else if (c == 0)
363 return n->elems[1]; /* already exists */
364 else if (n->elems[2] == NULL || (c = t->cmp(e, n->elems[2])) < 0)
365 ki = 2;
366 else if (c == 0)
367 return n->elems[2]; /* already exists */
368 else
369 ki = 3;
370 }
371 LOG((" moving to child %d (%p)\n", ki, n->kids[ki]));
372 if (!n->kids[ki])
373 break;
374 n = n->kids[ki];
375 } while (n);
376
377 add234_insert(NULL, e, NULL, &t->root, n, ki);
378
379 return orig_e;
380}
381
382void *add234(tree234 *t, void *e) {
383 if (!t->cmp) /* tree is unsorted */
384 return NULL;
385
386 return add234_internal(t, e, -1);
387}
388void *addpos234(tree234 *t, void *e, int index) {
389 if (index < 0 || /* index out of range */
390 t->cmp) /* tree is sorted */
391 return NULL; /* return failure */
392
393 return add234_internal(t, e, index); /* this checks the upper bound */
394}
395
396/*
397 * Look up the element at a given numeric index in a 2-3-4 tree.
398 * Returns NULL if the index is out of range.
399 */
400void *index234(tree234 *t, int index) {
401 node234 *n;
402
403 if (!t->root)
404 return NULL; /* tree is empty */
405
406 if (index < 0 || index >= countnode234(t->root))
407 return NULL; /* out of range */
408
409 n = t->root;
410
411 while (n) {
412 if (index < n->counts[0])
413 n = n->kids[0];
414 else if (index -= n->counts[0] + 1, index < 0)
415 return n->elems[0];
416 else if (index < n->counts[1])
417 n = n->kids[1];
418 else if (index -= n->counts[1] + 1, index < 0)
419 return n->elems[1];
420 else if (index < n->counts[2])
421 n = n->kids[2];
422 else if (index -= n->counts[2] + 1, index < 0)
423 return n->elems[2];
424 else
425 n = n->kids[3];
426 }
427
428 /* We shouldn't ever get here. I wonder how we did. */
429 return NULL;
430}
431
432/*
433 * Find an element e in a sorted 2-3-4 tree t. Returns NULL if not
434 * found. e is always passed as the first argument to cmp, so cmp
435 * can be an asymmetric function if desired. cmp can also be passed
436 * as NULL, in which case the compare function from the tree proper
437 * will be used.
438 */
439void *findrelpos234(tree234 *t, void *e, cmpfn234 cmp,
440 int relation, int *index) {
441 node234 *n;
442 void *ret;
443 int c;
444 int idx, ecount, kcount, cmpret;
445
446 if (t->root == NULL)
447 return NULL;
448
449 if (cmp == NULL)
450 cmp = t->cmp;
451
452 n = t->root;
453 /*
454 * Attempt to find the element itself.
455 */
456 idx = 0;
457 ecount = -1;
458 /*
459 * Prepare a fake `cmp' result if e is NULL.
460 */
461 cmpret = 0;
462 if (e == NULL) {
463 assert(relation == REL234_LT || relation == REL234_GT);
464 if (relation == REL234_LT)
465 cmpret = +1; /* e is a max: always greater */
466 else if (relation == REL234_GT)
467 cmpret = -1; /* e is a min: always smaller */
468 }
469 while (1) {
470 for (kcount = 0; kcount < 4; kcount++) {
471 if (kcount >= 3 || n->elems[kcount] == NULL ||
472 (c = cmpret ? cmpret : cmp(e, n->elems[kcount])) < 0) {
473 break;
474 }
475 if (n->kids[kcount]) idx += n->counts[kcount];
476 if (c == 0) {
477 ecount = kcount;
478 break;
479 }
480 idx++;
481 }
482 if (ecount >= 0)
483 break;
484 if (n->kids[kcount])
485 n = n->kids[kcount];
486 else
487 break;
488 }
489
490 if (ecount >= 0) {
491 /*
492 * We have found the element we're looking for. It's
493 * n->elems[ecount], at tree index idx. If our search
494 * relation is EQ, LE or GE we can now go home.
495 */
496 if (relation != REL234_LT && relation != REL234_GT) {
497 if (index) *index = idx;
498 return n->elems[ecount];
499 }
500
501 /*
502 * Otherwise, we'll do an indexed lookup for the previous
503 * or next element. (It would be perfectly possible to
504 * implement these search types in a non-counted tree by
505 * going back up from where we are, but far more fiddly.)
506 */
507 if (relation == REL234_LT)
508 idx--;
509 else
510 idx++;
511 } else {
512 /*
513 * We've found our way to the bottom of the tree and we
514 * know where we would insert this node if we wanted to:
515 * we'd put it in in place of the (empty) subtree
516 * n->kids[kcount], and it would have index idx
517 *
518 * But the actual element isn't there. So if our search
519 * relation is EQ, we're doomed.
520 */
521 if (relation == REL234_EQ)
522 return NULL;
523
524 /*
525 * Otherwise, we must do an index lookup for index idx-1
526 * (if we're going left - LE or LT) or index idx (if we're
527 * going right - GE or GT).
528 */
529 if (relation == REL234_LT || relation == REL234_LE) {
530 idx--;
531 }
532 }
533
534 /*
535 * We know the index of the element we want; just call index234
536 * to do the rest. This will return NULL if the index is out of
537 * bounds, which is exactly what we want.
538 */
539 ret = index234(t, idx);
540 if (ret && index) *index = idx;
541 return ret;
542}
543void *find234(tree234 *t, void *e, cmpfn234 cmp) {
544 return findrelpos234(t, e, cmp, REL234_EQ, NULL);
545}
546void *findrel234(tree234 *t, void *e, cmpfn234 cmp, int relation) {
547 return findrelpos234(t, e, cmp, relation, NULL);
548}
549void *findpos234(tree234 *t, void *e, cmpfn234 cmp, int *index) {
550 return findrelpos234(t, e, cmp, REL234_EQ, index);
551}
552
553/*
554 * Tree transformation used in delete and split: move a subtree
555 * right, from child ki of a node to the next child. Update k and
556 * index so that they still point to the same place in the
557 * transformed tree. Assumes the destination child is not full, and
558 * that the source child does have a subtree to spare. Can cope if
559 * the destination child is undersized.
560 *
561 * . C . . B .
562 * / \ -> / \
563 * [more] a A b B c d D e [more] a A b c C d D e
564 *
565 * . C . . B .
566 * / \ -> / \
567 * [more] a A b B c d [more] a A b c C d
568 */
569static void trans234_subtree_right(node234 *n, int ki, int *k, int *index) {
570 node234 *src, *dest;
571 int i, srclen, adjust;
572
573 src = n->kids[ki];
574 dest = n->kids[ki+1];
575
576 LOG((" trans234_subtree_right(%p, %d):\n", n, ki));
577 LOG((" parent %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
578 n,
579 n->kids[0], n->counts[0], n->elems[0],
580 n->kids[1], n->counts[1], n->elems[1],
581 n->kids[2], n->counts[2], n->elems[2],
582 n->kids[3], n->counts[3]));
583 LOG((" src %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
584 src,
585 src->kids[0], src->counts[0], src->elems[0],
586 src->kids[1], src->counts[1], src->elems[1],
587 src->kids[2], src->counts[2], src->elems[2],
588 src->kids[3], src->counts[3]));
589 LOG((" dest %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
590 dest,
591 dest->kids[0], dest->counts[0], dest->elems[0],
592 dest->kids[1], dest->counts[1], dest->elems[1],
593 dest->kids[2], dest->counts[2], dest->elems[2],
594 dest->kids[3], dest->counts[3]));
595 /*
596 * Move over the rest of the destination node to make space.
597 */
598 dest->kids[3] = dest->kids[2]; dest->counts[3] = dest->counts[2];
599 dest->elems[2] = dest->elems[1];
600 dest->kids[2] = dest->kids[1]; dest->counts[2] = dest->counts[1];
601 dest->elems[1] = dest->elems[0];
602 dest->kids[1] = dest->kids[0]; dest->counts[1] = dest->counts[0];
603
604 /* which element to move over */
605 i = (src->elems[2] ? 2 : src->elems[1] ? 1 : 0);
606
607 dest->elems[0] = n->elems[ki];
608 n->elems[ki] = src->elems[i];
609 src->elems[i] = NULL;
610
611 dest->kids[0] = src->kids[i+1]; dest->counts[0] = src->counts[i+1];
612 src->kids[i+1] = NULL; src->counts[i+1] = 0;
613
614 if (dest->kids[0]) dest->kids[0]->parent = dest;
615
616 adjust = dest->counts[0] + 1;
617
618 n->counts[ki] -= adjust;
619 n->counts[ki+1] += adjust;
620
621 srclen = n->counts[ki];
622
623 if (k) {
624 LOG((" before: k,index = %d,%d\n", (*k), (*index)));
625 if ((*k) == ki && (*index) > srclen) {
626 (*index) -= srclen + 1;
627 (*k)++;
628 } else if ((*k) == ki+1) {
629 (*index) += adjust;
630 }
631 LOG((" after: k,index = %d,%d\n", (*k), (*index)));
632 }
633
634 LOG((" parent %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
635 n,
636 n->kids[0], n->counts[0], n->elems[0],
637 n->kids[1], n->counts[1], n->elems[1],
638 n->kids[2], n->counts[2], n->elems[2],
639 n->kids[3], n->counts[3]));
640 LOG((" src %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
641 src,
642 src->kids[0], src->counts[0], src->elems[0],
643 src->kids[1], src->counts[1], src->elems[1],
644 src->kids[2], src->counts[2], src->elems[2],
645 src->kids[3], src->counts[3]));
646 LOG((" dest %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
647 dest,
648 dest->kids[0], dest->counts[0], dest->elems[0],
649 dest->kids[1], dest->counts[1], dest->elems[1],
650 dest->kids[2], dest->counts[2], dest->elems[2],
651 dest->kids[3], dest->counts[3]));
652}
653
654/*
655 * Tree transformation used in delete and split: move a subtree
656 * left, from child ki of a node to the previous child. Update k
657 * and index so that they still point to the same place in the
658 * transformed tree. Assumes the destination child is not full, and
659 * that the source child does have a subtree to spare. Can cope if
660 * the destination child is undersized.
661 *
662 * . B . . C .
663 * / \ -> / \
664 * a A b c C d D e [more] a A b B c d D e [more]
665 *
666 * . A . . B .
667 * / \ -> / \
668 * a b B c C d [more] a A b c C d [more]
669 */
670static void trans234_subtree_left(node234 *n, int ki, int *k, int *index) {
671 node234 *src, *dest;
672 int i, adjust;
673
674 src = n->kids[ki];
675 dest = n->kids[ki-1];
676
677 LOG((" trans234_subtree_left(%p, %d):\n", n, ki));
678 LOG((" parent %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
679 n,
680 n->kids[0], n->counts[0], n->elems[0],
681 n->kids[1], n->counts[1], n->elems[1],
682 n->kids[2], n->counts[2], n->elems[2],
683 n->kids[3], n->counts[3]));
684 LOG((" dest %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
685 dest,
686 dest->kids[0], dest->counts[0], dest->elems[0],
687 dest->kids[1], dest->counts[1], dest->elems[1],
688 dest->kids[2], dest->counts[2], dest->elems[2],
689 dest->kids[3], dest->counts[3]));
690 LOG((" src %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
691 src,
692 src->kids[0], src->counts[0], src->elems[0],
693 src->kids[1], src->counts[1], src->elems[1],
694 src->kids[2], src->counts[2], src->elems[2],
695 src->kids[3], src->counts[3]));
696
697 /* where in dest to put it */
698 i = (dest->elems[1] ? 2 : dest->elems[0] ? 1 : 0);
699 dest->elems[i] = n->elems[ki-1];
700 n->elems[ki-1] = src->elems[0];
701
702 dest->kids[i+1] = src->kids[0]; dest->counts[i+1] = src->counts[0];
703
704 if (dest->kids[i+1]) dest->kids[i+1]->parent = dest;
705
706 /*
707 * Move over the rest of the source node.
708 */
709 src->kids[0] = src->kids[1]; src->counts[0] = src->counts[1];
710 src->elems[0] = src->elems[1];
711 src->kids[1] = src->kids[2]; src->counts[1] = src->counts[2];
712 src->elems[1] = src->elems[2];
713 src->kids[2] = src->kids[3]; src->counts[2] = src->counts[3];
714 src->elems[2] = NULL;
715 src->kids[3] = NULL; src->counts[3] = 0;
716
717 adjust = dest->counts[i+1] + 1;
718
719 n->counts[ki] -= adjust;
720 n->counts[ki-1] += adjust;
721
722 if (k) {
723 LOG((" before: k,index = %d,%d\n", (*k), (*index)));
724 if ((*k) == ki) {
725 (*index) -= adjust;
726 if ((*index) < 0) {
727 (*index) += n->counts[ki-1] + 1;
728 (*k)--;
729 }
730 }
731 LOG((" after: k,index = %d,%d\n", (*k), (*index)));
732 }
733
734 LOG((" parent %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
735 n,
736 n->kids[0], n->counts[0], n->elems[0],
737 n->kids[1], n->counts[1], n->elems[1],
738 n->kids[2], n->counts[2], n->elems[2],
739 n->kids[3], n->counts[3]));
740 LOG((" dest %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
741 dest,
742 dest->kids[0], dest->counts[0], dest->elems[0],
743 dest->kids[1], dest->counts[1], dest->elems[1],
744 dest->kids[2], dest->counts[2], dest->elems[2],
745 dest->kids[3], dest->counts[3]));
746 LOG((" src %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
747 src,
748 src->kids[0], src->counts[0], src->elems[0],
749 src->kids[1], src->counts[1], src->elems[1],
750 src->kids[2], src->counts[2], src->elems[2],
751 src->kids[3], src->counts[3]));
752}
753
754/*
755 * Tree transformation used in delete and split: merge child nodes
756 * ki and ki+1 of a node. Update k and index so that they still
757 * point to the same place in the transformed tree. Assumes both
758 * children _are_ sufficiently small.
759 *
760 * . B . .
761 * / \ -> |
762 * a A b c C d a A b B c C d
763 *
764 * This routine can also cope with either child being undersized:
765 *
766 * . A . .
767 * / \ -> |
768 * a b B c a A b B c
769 *
770 * . A . .
771 * / \ -> |
772 * a b B c C d a A b B c C d
773 */
774static void trans234_subtree_merge(node234 *n, int ki, int *k, int *index) {
775 node234 *left, *right;
776 int i, leftlen, rightlen, lsize, rsize;
777
778 left = n->kids[ki]; leftlen = n->counts[ki];
779 right = n->kids[ki+1]; rightlen = n->counts[ki+1];
780
781 LOG((" trans234_subtree_merge(%p, %d):\n", n, ki));
782 LOG((" parent %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
783 n,
784 n->kids[0], n->counts[0], n->elems[0],
785 n->kids[1], n->counts[1], n->elems[1],
786 n->kids[2], n->counts[2], n->elems[2],
787 n->kids[3], n->counts[3]));
788 LOG((" left %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
789 left,
790 left->kids[0], left->counts[0], left->elems[0],
791 left->kids[1], left->counts[1], left->elems[1],
792 left->kids[2], left->counts[2], left->elems[2],
793 left->kids[3], left->counts[3]));
794 LOG((" right %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
795 right,
796 right->kids[0], right->counts[0], right->elems[0],
797 right->kids[1], right->counts[1], right->elems[1],
798 right->kids[2], right->counts[2], right->elems[2],
799 right->kids[3], right->counts[3]));
800
801 assert(!left->elems[2] && !right->elems[2]); /* neither is large! */
802 lsize = (left->elems[1] ? 2 : left->elems[0] ? 1 : 0);
803 rsize = (right->elems[1] ? 2 : right->elems[0] ? 1 : 0);
804
805 left->elems[lsize] = n->elems[ki];
806
807 for (i = 0; i < rsize+1; i++) {
808 left->kids[lsize+1+i] = right->kids[i];
809 left->counts[lsize+1+i] = right->counts[i];
810 if (left->kids[lsize+1+i])
811 left->kids[lsize+1+i]->parent = left;
812 if (i < rsize)
813 left->elems[lsize+1+i] = right->elems[i];
814 }
815
816 n->counts[ki] += rightlen + 1;
817
818 sfree(right);
819
820 /*
821 * Move the rest of n up by one.
822 */
823 for (i = ki+1; i < 3; i++) {
824 n->kids[i] = n->kids[i+1];
825 n->counts[i] = n->counts[i+1];
826 }
827 for (i = ki; i < 2; i++) {
828 n->elems[i] = n->elems[i+1];
829 }
830 n->kids[3] = NULL;
831 n->counts[3] = 0;
832 n->elems[2] = NULL;
833
834 if (k) {
835 LOG((" before: k,index = %d,%d\n", (*k), (*index)));
836 if ((*k) == ki+1) {
837 (*k)--;
838 (*index) += leftlen + 1;
839 } else if ((*k) > ki+1) {
840 (*k)--;
841 }
842 LOG((" after: k,index = %d,%d\n", (*k), (*index)));
843 }
844
845 LOG((" parent %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
846 n,
847 n->kids[0], n->counts[0], n->elems[0],
848 n->kids[1], n->counts[1], n->elems[1],
849 n->kids[2], n->counts[2], n->elems[2],
850 n->kids[3], n->counts[3]));
851 LOG((" merged %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
852 left,
853 left->kids[0], left->counts[0], left->elems[0],
854 left->kids[1], left->counts[1], left->elems[1],
855 left->kids[2], left->counts[2], left->elems[2],
856 left->kids[3], left->counts[3]));
857
858}
859
860/*
861 * Delete an element e in a 2-3-4 tree. Does not free the element,
862 * merely removes all links to it from the tree nodes.
863 */
864static void *delpos234_internal(tree234 *t, int index) {
865 node234 *n;
866 void *retval;
867 int ki, i;
868
869 retval = NULL;
870
871 n = t->root; /* by assumption this is non-NULL */
872 LOG(("deleting item %d from tree %p\n", index, t));
873 while (1) {
874 node234 *sub;
875
876 LOG((" node %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d index=%d\n",
877 n,
878 n->kids[0], n->counts[0], n->elems[0],
879 n->kids[1], n->counts[1], n->elems[1],
880 n->kids[2], n->counts[2], n->elems[2],
881 n->kids[3], n->counts[3],
882 index));
883 if (index <= n->counts[0]) {
884 ki = 0;
885 } else if (index -= n->counts[0]+1, index <= n->counts[1]) {
886 ki = 1;
887 } else if (index -= n->counts[1]+1, index <= n->counts[2]) {
888 ki = 2;
889 } else if (index -= n->counts[2]+1, index <= n->counts[3]) {
890 ki = 3;
891 } else {
892 assert(0); /* can't happen */
893 }
894
895 if (!n->kids[0])
896 break; /* n is a leaf node; we're here! */
897
898 /*
899 * Check to see if we've found our target element. If so,
900 * we must choose a new target (we'll use the old target's
901 * successor, which will be in a leaf), move it into the
902 * place of the old one, continue down to the leaf and
903 * delete the old copy of the new target.
904 */
905 if (index == n->counts[ki]) {
906 node234 *m;
907 LOG((" found element in internal node, index %d\n", ki));
908 assert(n->elems[ki]); /* must be a kid _before_ an element */
909 ki++; index = 0;
910 for (m = n->kids[ki]; m->kids[0]; m = m->kids[0])
911 continue;
912 LOG((" replacing with element \"%s\" from leaf node %p\n",
913 m->elems[0], m));
914 retval = n->elems[ki-1];
915 n->elems[ki-1] = m->elems[0];
916 }
917
918 /*
919 * Recurse down to subtree ki. If it has only one element,
920 * we have to do some transformation to start with.
921 */
922 LOG((" moving to subtree %d\n", ki));
923 sub = n->kids[ki];
924 if (!sub->elems[1]) {
925 LOG((" subtree has only one element!\n"));
926 if (ki > 0 && n->kids[ki-1]->elems[1]) {
927 /*
928 * Child ki has only one element, but child
929 * ki-1 has two or more. So we need to move a
930 * subtree from ki-1 to ki.
931 */
932 trans234_subtree_right(n, ki-1, &ki, &index);
933 } else if (ki < 3 && n->kids[ki+1] &&
934 n->kids[ki+1]->elems[1]) {
935 /*
936 * Child ki has only one element, but ki+1 has
937 * two or more. Move a subtree from ki+1 to ki.
938 */
939 trans234_subtree_left(n, ki+1, &ki, &index);
940 } else {
941 /*
942 * ki is small with only small neighbours. Pick a
943 * neighbour and merge with it.
944 */
945 trans234_subtree_merge(n, ki>0 ? ki-1 : ki, &ki, &index);
946 sub = n->kids[ki];
947
948 if (!n->elems[0]) {
949 /*
950 * The root is empty and needs to be
951 * removed.
952 */
953 LOG((" shifting root!\n"));
954 t->root = sub;
955 sub->parent = NULL;
956 sfree(n);
957 n = NULL;
958 }
959 }
960 }
961
962 if (n)
963 n->counts[ki]--;
964 n = sub;
965 }
966
967 /*
968 * Now n is a leaf node, and ki marks the element number we
969 * want to delete. We've already arranged for the leaf to be
970 * bigger than minimum size, so let's just go to it.
971 */
972 assert(!n->kids[0]);
973 if (!retval)
974 retval = n->elems[ki];
975
976 for (i = ki; i < 2 && n->elems[i+1]; i++)
977 n->elems[i] = n->elems[i+1];
978 n->elems[i] = NULL;
979
980 /*
981 * It's just possible that we have reduced the leaf to zero
982 * size. This can only happen if it was the root - so destroy
983 * it and make the tree empty.
984 */
985 if (!n->elems[0]) {
986 LOG((" removed last element in tree, destroying empty root\n"));
987 assert(n == t->root);
988 sfree(n);
989 t->root = NULL;
990 }
991
992 return retval; /* finished! */
993}
994void *delpos234(tree234 *t, int index) {
995 if (index < 0 || index >= countnode234(t->root))
996 return NULL;
997 return delpos234_internal(t, index);
998}
999void *del234(tree234 *t, void *e) {
1000 int index;
1001 if (!findrelpos234(t, e, NULL, REL234_EQ, &index))
1002 return NULL; /* it wasn't in there anyway */
1003 return delpos234_internal(t, index); /* it's there; delete it. */
1004}
1005
1006/*
1007 * Join two subtrees together with a separator element between
1008 * them, given their relative height.
1009 *
1010 * (Height<0 means the left tree is shorter, >0 means the right
1011 * tree is shorter, =0 means (duh) they're equal.)
1012 *
1013 * It is assumed that any checks needed on the ordering criterion
1014 * have _already_ been done.
1015 *
1016 * The value returned in `height' is 0 or 1 depending on whether the
1017 * resulting tree is the same height as the original larger one, or
1018 * one higher.
1019 */
1020static node234 *join234_internal(node234 *left, void *sep,
1021 node234 *right, int *height) {
1022 node234 *root, *node;
1023 int relht = *height;
1024 int ki;
1025
1026 LOG((" join: joining %p \"%s\" %p, relative height is %d\n",
1027 left, sep, right, relht));
1028 if (relht == 0) {
1029 /*
1030 * The trees are the same height. Create a new one-element
1031 * root containing the separator and pointers to the two
1032 * nodes.
1033 */
1034 node234 *newroot;
1035 newroot = snew(node234);
1036 newroot->kids[0] = left; newroot->counts[0] = countnode234(left);
1037 newroot->elems[0] = sep;
1038 newroot->kids[1] = right; newroot->counts[1] = countnode234(right);
1039 newroot->elems[1] = NULL;
1040 newroot->kids[2] = NULL; newroot->counts[2] = 0;
1041 newroot->elems[2] = NULL;
1042 newroot->kids[3] = NULL; newroot->counts[3] = 0;
1043 newroot->parent = NULL;
1044 if (left) left->parent = newroot;
1045 if (right) right->parent = newroot;
1046 *height = 1;
1047 LOG((" join: same height, brand new root\n"));
1048 return newroot;
1049 }
1050
1051 /*
1052 * This now works like the addition algorithm on the larger
1053 * tree. We're replacing a single kid pointer with two kid
1054 * pointers separated by an element; if that causes the node to
1055 * overload, we split it in two, move a separator element up to
1056 * the next node, and repeat.
1057 */
1058 if (relht < 0) {
1059 /*
1060 * Left tree is shorter. Search down the right tree to find
1061 * the pointer we're inserting at.
1062 */
1063 node = root = right;
1064 while (++relht < 0) {
1065 node = node->kids[0];
1066 }
1067 ki = 0;
1068 right = node->kids[ki];
1069 } else {
1070 /*
1071 * Right tree is shorter; search down the left to find the
1072 * pointer we're inserting at.
1073 */
1074 node = root = left;
1075 while (--relht > 0) {
1076 if (node->elems[2])
1077 node = node->kids[3];
1078 else if (node->elems[1])
1079 node = node->kids[2];
1080 else
1081 node = node->kids[1];
1082 }
1083 if (node->elems[2])
1084 ki = 3;
1085 else if (node->elems[1])
1086 ki = 2;
1087 else
1088 ki = 1;
1089 left = node->kids[ki];
1090 }
1091
1092 /*
1093 * Now proceed as for addition.
1094 */
1095 *height = add234_insert(left, sep, right, &root, node, ki);
1096
1097 return root;
1098}
1099int height234(tree234 *t) {
1100 int level = 0;
1101 node234 *n = t->root;
1102 while (n) {
1103 level++;
1104 n = n->kids[0];
1105 }
1106 return level;
1107}
1108tree234 *join234(tree234 *t1, tree234 *t2) {
1109 int size2 = countnode234(t2->root);
1110 if (size2 > 0) {
1111 void *element;
1112 int relht;
1113
1114 if (t1->cmp) {
1115 element = index234(t2, 0);
1116 element = findrelpos234(t1, element, NULL, REL234_GE, NULL);
1117 if (element)
1118 return NULL;
1119 }
1120
1121 element = delpos234(t2, 0);
1122 relht = height234(t1) - height234(t2);
1123 t1->root = join234_internal(t1->root, element, t2->root, &relht);
1124 t2->root = NULL;
1125 }
1126 return t1;
1127}
1128tree234 *join234r(tree234 *t1, tree234 *t2) {
1129 int size1 = countnode234(t1->root);
1130 if (size1 > 0) {
1131 void *element;
1132 int relht;
1133
1134 if (t2->cmp) {
1135 element = index234(t1, size1-1);
1136 element = findrelpos234(t2, element, NULL, REL234_LE, NULL);
1137 if (element)
1138 return NULL;
1139 }
1140
1141 element = delpos234(t1, size1-1);
1142 relht = height234(t1) - height234(t2);
1143 t2->root = join234_internal(t1->root, element, t2->root, &relht);
1144 t1->root = NULL;
1145 }
1146 return t2;
1147}
1148
1149/*
1150 * Split out the first <index> elements in a tree and return a
1151 * pointer to the root node. Leave the root node of the remainder
1152 * in t.
1153 */
1154static node234 *split234_internal(tree234 *t, int index) {
1155 node234 *halves[2] = { NULL, NULL }, *n, *sib, *sub;
1156 node234 *lparent, *rparent;
1157 int ki, pki, i, half, lcount, rcount;
1158
1159 n = t->root;
1160 LOG(("splitting tree %p at point %d\n", t, index));
1161
1162 /*
1163 * Easy special cases. After this we have also dealt completely
1164 * with the empty-tree case and we can assume the root exists.
1165 */
1166 if (index == 0) /* return nothing */
1167 return NULL;
1168 if (index == countnode234(t->root)) { /* return the whole tree */
1169 node234 *ret = t->root;
1170 t->root = NULL;
1171 return ret;
1172 }
1173
1174 /*
1175 * Search down the tree to find the split point.
1176 */
1177 halves[0] = halves[1] = NULL;
1178 lparent = rparent = NULL;
1179 pki = -1;
1180 while (n) {
1181 LOG((" node %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d index=%d\n",
1182 n,
1183 n->kids[0], n->counts[0], n->elems[0],
1184 n->kids[1], n->counts[1], n->elems[1],
1185 n->kids[2], n->counts[2], n->elems[2],
1186 n->kids[3], n->counts[3],
1187 index));
1188 lcount = index;
1189 rcount = countnode234(n) - lcount;
1190 if (index <= n->counts[0]) {
1191 ki = 0;
1192 } else if (index -= n->counts[0]+1, index <= n->counts[1]) {
1193 ki = 1;
1194 } else if (index -= n->counts[1]+1, index <= n->counts[2]) {
1195 ki = 2;
1196 } else {
1197 index -= n->counts[2]+1;
1198 ki = 3;
1199 }
1200
1201 LOG((" splitting at subtree %d\n", ki));
1202 sub = n->kids[ki];
1203
1204 LOG((" splitting at child index %d\n", ki));
1205
1206 /*
1207 * Split the node, put halves[0] on the right of the left
1208 * one and halves[1] on the left of the right one, put the
1209 * new node pointers in halves[0] and halves[1], and go up
1210 * a level.
1211 */
1212 sib = snew(node234);
1213 for (i = 0; i < 3; i++) {
1214 if (i+ki < 3 && n->elems[i+ki]) {
1215 sib->elems[i] = n->elems[i+ki];
1216 sib->kids[i+1] = n->kids[i+ki+1];
1217 if (sib->kids[i+1]) sib->kids[i+1]->parent = sib;
1218 sib->counts[i+1] = n->counts[i+ki+1];
1219 n->elems[i+ki] = NULL;
1220 n->kids[i+ki+1] = NULL;
1221 n->counts[i+ki+1] = 0;
1222 } else {
1223 sib->elems[i] = NULL;
1224 sib->kids[i+1] = NULL;
1225 sib->counts[i+1] = 0;
1226 }
1227 }
1228 if (lparent) {
1229 lparent->kids[pki] = n;
1230 lparent->counts[pki] = lcount;
1231 n->parent = lparent;
1232 rparent->kids[0] = sib;
1233 rparent->counts[0] = rcount;
1234 sib->parent = rparent;
1235 } else {
1236 halves[0] = n;
1237 n->parent = NULL;
1238 halves[1] = sib;
1239 sib->parent = NULL;
1240 }
1241 lparent = n;
1242 rparent = sib;
1243 pki = ki;
1244 LOG((" left node %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
1245 n,
1246 n->kids[0], n->counts[0], n->elems[0],
1247 n->kids[1], n->counts[1], n->elems[1],
1248 n->kids[2], n->counts[2], n->elems[2],
1249 n->kids[3], n->counts[3]));
1250 LOG((" right node %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
1251 sib,
1252 sib->kids[0], sib->counts[0], sib->elems[0],
1253 sib->kids[1], sib->counts[1], sib->elems[1],
1254 sib->kids[2], sib->counts[2], sib->elems[2],
1255 sib->kids[3], sib->counts[3]));
1256
1257 n = sub;
1258 }
1259
1260 /*
1261 * We've come off the bottom here, so we've successfully split
1262 * the tree into two equally high subtrees. The only problem is
1263 * that some of the nodes down the fault line will be smaller
1264 * than the minimum permitted size. (Since this is a 2-3-4
1265 * tree, that means they'll be zero-element one-child nodes.)
1266 */
1267 LOG((" fell off bottom, lroot is %p, rroot is %p\n",
1268 halves[0], halves[1]));
1269 assert(halves[0] != NULL);
1270 assert(halves[1] != NULL);
1271 lparent->counts[pki] = rparent->counts[0] = 0;
1272 lparent->kids[pki] = rparent->kids[0] = NULL;
1273
1274 /*
1275 * So now we go back down the tree from each of the two roots,
1276 * fixing up undersize nodes.
1277 */
1278 for (half = 0; half < 2; half++) {
1279 /*
1280 * Remove the root if it's undersize (it will contain only
1281 * one child pointer, so just throw it away and replace it
1282 * with its child). This might happen several times.
1283 */
1284 while (halves[half] && !halves[half]->elems[0]) {
1285 LOG((" root %p is undersize, throwing away\n", halves[half]));
1286 halves[half] = halves[half]->kids[0];
1287 sfree(halves[half]->parent);
1288 halves[half]->parent = NULL;
1289 LOG((" new root is %p\n", halves[half]));
1290 }
1291
1292 n = halves[half];
1293 while (n) {
1294 void (*toward)(node234 *n, int ki, int *k, int *index);
1295 int ni, merge;
1296
1297 /*
1298 * Now we have a potentially undersize node on the
1299 * right (if half==0) or left (if half==1). Sort it
1300 * out, by merging with a neighbour or by transferring
1301 * subtrees over. At this time we must also ensure that
1302 * nodes are bigger than minimum, in case we need an
1303 * element to merge two nodes below.
1304 */
1305 LOG((" node %p: %p/%d \"%s\" %p/%d \"%s\" %p/%d \"%s\" %p/%d\n",
1306 n,
1307 n->kids[0], n->counts[0], n->elems[0],
1308 n->kids[1], n->counts[1], n->elems[1],
1309 n->kids[2], n->counts[2], n->elems[2],
1310 n->kids[3], n->counts[3]));
1311 if (half == 1) {
1312 ki = 0; /* the kid we're interested in */
1313 ni = 1; /* the neighbour */
1314 merge = 0; /* for merge: leftmost of the two */
1315 toward = trans234_subtree_left;
1316 } else {
1317 ki = (n->kids[3] ? 3 : n->kids[2] ? 2 : 1);
1318 ni = ki-1;
1319 merge = ni;
1320 toward = trans234_subtree_right;
1321 }
1322
1323 sub = n->kids[ki];
1324 if (sub && !sub->elems[1]) {
1325 /*
1326 * This node is undersized or minimum-size. If we
1327 * can merge it with its neighbour, we do so;
1328 * otherwise we must be able to transfer subtrees
1329 * over to it until it is greater than minimum
1330 * size.
1331 */
1332 bool undersized = (!sub->elems[0]);
1333 LOG((" child %d is %ssize\n", ki,
1334 undersized ? "under" : "minimum-"));
1335 LOG((" neighbour is %s\n",
1336 n->kids[ni]->elems[2] ? "large" :
1337 n->kids[ni]->elems[1] ? "medium" : "small"));
1338 if (!n->kids[ni]->elems[1] ||
1339 (undersized && !n->kids[ni]->elems[2])) {
1340 /*
1341 * Neighbour is small, or possibly neighbour is
1342 * medium and we are undersize.
1343 */
1344 trans234_subtree_merge(n, merge, NULL, NULL);
1345 sub = n->kids[merge];
1346 if (!n->elems[0]) {
1347 /*
1348 * n is empty, and hence must have been the
1349 * root and needs to be removed.
1350 */
1351 assert(!n->parent);
1352 LOG((" shifting root!\n"));
1353 halves[half] = sub;
1354 halves[half]->parent = NULL;
1355 sfree(n);
1356 }
1357 } else {
1358 /* Neighbour is big enough to move trees over. */
1359 toward(n, ni, NULL, NULL);
1360 if (undersized)
1361 toward(n, ni, NULL, NULL);
1362 }
1363 }
1364 n = sub;
1365 }
1366 }
1367
1368 t->root = halves[1];
1369 return halves[0];
1370}
1371tree234 *splitpos234(tree234 *t, int index, bool before) {
1372 tree234 *ret;
1373 node234 *n;
1374 int count;
1375
1376 count = countnode234(t->root);
1377 if (index < 0 || index > count)
1378 return NULL; /* error */
1379 ret = newtree234(t->cmp);
1380 n = split234_internal(t, index);
1381 if (before) {
1382 /* We want to return the ones before the index. */
1383 ret->root = n;
1384 } else {
1385 /*
1386 * We want to keep the ones before the index and return the
1387 * ones after.
1388 */
1389 ret->root = t->root;
1390 t->root = n;
1391 }
1392 return ret;
1393}
1394tree234 *split234(tree234 *t, void *e, cmpfn234 cmp, int rel) {
1395 bool before;
1396 int index;
1397
1398 assert(rel != REL234_EQ);
1399
1400 if (rel == REL234_GT || rel == REL234_GE) {
1401 before = true;
1402 rel = (rel == REL234_GT ? REL234_LE : REL234_LT);
1403 } else {
1404 before = false;
1405 }
1406 if (!findrelpos234(t, e, cmp, rel, &index))
1407 index = 0;
1408
1409 return splitpos234(t, index+1, before);
1410}
1411
1412static node234 *copynode234(node234 *n, copyfn234 copyfn, void *copyfnstate) {
1413 int i;
1414 node234 *n2 = snew(node234);
1415
1416 for (i = 0; i < 3; i++) {
1417 if (n->elems[i] && copyfn)
1418 n2->elems[i] = copyfn(copyfnstate, n->elems[i]);
1419 else
1420 n2->elems[i] = n->elems[i];
1421 }
1422
1423 for (i = 0; i < 4; i++) {
1424 if (n->kids[i]) {
1425 n2->kids[i] = copynode234(n->kids[i], copyfn, copyfnstate);
1426 n2->kids[i]->parent = n2;
1427 } else {
1428 n2->kids[i] = NULL;
1429 }
1430 n2->counts[i] = n->counts[i];
1431 }
1432
1433 return n2;
1434}
1435tree234 *copytree234(tree234 *t, copyfn234 copyfn, void *copyfnstate) {
1436 tree234 *t2;
1437
1438 t2 = newtree234(t->cmp);
1439 if (t->root) {
1440 t2->root = copynode234(t->root, copyfn, copyfnstate);
1441 t2->root->parent = NULL;
1442 } else
1443 t2->root = NULL;
1444
1445 return t2;
1446}