2 * Flexible B-tree implementation. Supports reference counting for
3 * copy-on-write, user-defined node properties, and variable
6 * This file is copyright 2001,2004 Simon Tatham.
8 * Permission is hereby granted, free of charge, to any person
9 * obtaining a copy of this software and associated documentation
10 * files (the "Software"), to deal in the Software without
11 * restriction, including without limitation the rights to use,
12 * copy, modify, merge, publish, distribute, sublicense, and/or
13 * sell copies of the Software, and to permit persons to whom the
14 * Software is furnished to do so, subject to the following
17 * The above copyright notice and this permission notice shall be
18 * included in all copies or substantial portions of the Software.
20 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
21 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
22 * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
23 * NONINFRINGEMENT. IN NO EVENT SHALL SIMON TATHAM BE LIABLE FOR
24 * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF
25 * CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
26 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
33 * Possibly TODO in future, but may not be sensible in this code
36 * - user write properties.
37 * * this all happens during write_unlock(), I think. Except
38 * that we'll now need an _internal_ write_unlock() which
39 * does everything except user write properties. Sigh.
40 * * note that we also need a transform function for elements
41 * (rot13 will certainly require this, and reverse will
42 * require it if the elements themselves are in some way
46 * - searching on user read properties.
47 * - user-supplied copy function.
48 * - bt_add when element already exists.
49 * - bt_del when element doesn't.
50 * - splitpos with before==TRUE.
51 * - split() on sorted elements (but it should be fine).
52 * - bt_replace, at all (it won't be useful until we get user read
54 * - bt_index_w (won't make much sense until we start using
55 * user-supplied copy fn).
70 static void set_invalid_property(void *prop
);
73 /* ----------------------------------------------------------------------
77 typedef union nodecomponent nodecomponent
;
78 typedef nodecomponent
*nodeptr
;
81 * For type-checking purposes, and to ensure I don't accidentally
82 * confuse node_addr with node_ptr during implementation, I'll
83 * define node_addr for the in-memory case as being a struct
84 * containing only a nodeptr.
86 * This unfortunately needs to go in btree.h so that clients
87 * writing user properties can know about the nodecomponent
95 * A B-tree node is a horrible thing when you're trying to be
96 * flexible. It is of variable size, and it contains a variety of
97 * distinct types of thing: nodes, elements, some counters, some
98 * user-defined properties ... it's a horrible thing. So we define
99 * it as an array of unions, each union being either an `int' or a
100 * `bt_element_t' or a `node_addr'...
103 union nodecomponent
{
109 static const node_addr NODE_ADDR_NULL
= { NULL
};
112 * The array of nodecomponents will take the following form:
114 * - (maxdegree) child pointers.
115 * - (maxdegree-1) element pointers.
116 * - one subtree count (current number of child pointers that are
117 * valid; note that `valid' doesn't imply non-NULL).
118 * - one element count.
119 * - one reference count.
123 int mindegree
; /* min number of subtrees */
124 int maxdegree
; /* max number of subtrees */
125 int depth
; /* helps to store this explicitly */
130 int propsize
, propalign
, propoffset
;
131 propmakefn_t propmake
;
132 propmergefn_t propmerge
;
133 void *userstate
; /* passed to all user functions */
136 /* ----------------------------------------------------------------------
137 * Memory management routines and other housekeeping.
140 # define ialloc(x) alloca(x)
143 # define ialloc(x) smalloc(x)
144 # define ifree(x) sfree(x)
147 #define new1(t) ( (t *) smalloc(sizeof(t)) )
148 #define newn(t, n) ( (t *) smalloc((n) * sizeof(t)) )
149 #define inew1(t) ( (t *) ialloc(sizeof(t)) )
150 #define inewn(t, n) ( (t *) ialloc((n) * sizeof(t)) )
152 static void *smalloc(size_t size
)
154 void *ret
= malloc(size
);
160 static void sfree(void *p
)
172 /* We could probably do with more compiler-specific branches of this #if. */
173 #if defined(__GNUC__)
174 #define INLINE __inline
179 /* Hooks into the low-level code for test purposes. */
181 void testlock(int write
, int set
, nodeptr n
);
183 #define testlock(w,s,n)
186 /* ----------------------------------------------------------------------
187 * Low-level helper routines, which understand the in-memory format
188 * of a node and know how to read-lock and write-lock.
192 * Read and write the node_addr of a child.
194 static INLINE node_addr
bt_child(btree
*bt
, nodeptr n
, int index
)
198 static INLINE
void bt_set_child(btree
*bt
, nodeptr n
,
199 int index
, node_addr value
)
205 * Read and write the address of an element.
207 static INLINE bt_element_t
bt_element(btree
*bt
, nodeptr n
, int index
)
209 return n
[bt
->maxdegree
+ index
].ep
;
211 static INLINE
void bt_set_element(btree
*bt
, nodeptr n
,
212 int index
, bt_element_t value
)
214 n
[bt
->maxdegree
+ index
].ep
= value
;
218 * Give the number of subtrees currently present in an element.
220 static INLINE
int bt_subtrees(btree
*bt
, nodeptr n
)
222 return n
[bt
->maxdegree
*2-1].i
;
224 #define bt_elements(bt,n) (bt_subtrees(bt,n) - 1)
227 * Give the minimum and maximum number of subtrees allowed in a
230 static INLINE
int bt_min_subtrees(btree
*bt
)
232 return bt
->mindegree
;
234 static INLINE
int bt_max_subtrees(btree
*bt
)
236 return bt
->maxdegree
;
240 * Return the count of items, and the user properties, in a
241 * particular subtree of a node.
243 * Note that in the in-memory form of the tree, this breaks the
244 * read-locking semantics, by reading the counts out of the child
245 * nodes without bothering to lock them. We're allowed to do this
246 * because this function is implemented at the same very low level
247 * as the implementation of bt_read_lock(), so we're allowed to
248 * know that read locking actually doesn't do anything.
250 static INLINE
int bt_child_count(btree
*bt
, nodeptr n
, int index
)
253 return n
[index
].na
.p
[bt
->maxdegree
*2].i
;
258 static INLINE
void *bt_child_prop(btree
*bt
, nodeptr n
, int index
)
261 return (char *)n
[index
].na
.p
+ bt
->propoffset
;
267 * Return the count of items in a whole node.
269 static INLINE
int bt_node_count(btree
*bt
, nodeptr n
)
271 return n
[bt
->maxdegree
*2].i
;
275 * Determine whether a node is a leaf node or not.
277 static INLINE
int bt_is_leaf(btree
*bt
, nodeptr n
)
279 return n
[0].na
.p
== NULL
;
283 * Create a new write-locked node, and return a pointer to it.
285 static INLINE nodeptr
bt_new_node(btree
*bt
, int nsubtrees
)
287 nodeptr ret
= (nodecomponent
*)smalloc(bt
->propoffset
+ bt
->propsize
);
288 ret
[bt
->maxdegree
*2-1].i
= nsubtrees
;
289 ret
[bt
->maxdegree
*2+1].i
= 1; /* reference count 1 */
291 set_invalid_property(ret
+ bt
->maxdegree
* 2 + 2);
293 memset((char *)ret
+ bt
->propoffset
, 0, bt
->propsize
);
295 testlock(TRUE
, TRUE
, ret
);
300 * Destroy a node (must be write-locked).
302 static INLINE
void bt_destroy_node(btree
*bt
, nodeptr n
)
304 testlock(TRUE
, FALSE
, n
);
305 /* Free the property. */
306 bt
->propmerge(bt
->userstate
, NULL
, NULL
, n
+ bt
->maxdegree
* 2 + 2);
311 * Take an existing node and prepare to re-use it in a new context.
313 static INLINE nodeptr
bt_reuse_node(btree
*bt
, nodeptr n
, int nsubtrees
)
315 testlock(TRUE
, FALSE
, n
);
316 testlock(TRUE
, TRUE
, n
);
317 n
[bt
->maxdegree
*2-1].i
= nsubtrees
;
322 * Return an extra reference to a node, for purposes of cloning. So
323 * we have to update its reference count as well.
325 static INLINE node_addr
bt_ref_node(btree
*bt
, node_addr n
)
328 n
.p
[bt
->maxdegree
*2+1].i
++;
333 * Drop a node's reference count, for purposes of freeing. Returns
334 * the new reference count. Typically this will be tested against
335 * zero to see if the node needs to be physically freed; hence a
336 * NULL node_addr causes a return of 1 (because this isn't
339 static INLINE
int bt_unref_node(btree
*bt
, node_addr n
)
342 n
.p
[bt
->maxdegree
*2+1].i
--;
343 return n
.p
[bt
->maxdegree
*2+1].i
;
345 return 1; /* a NULL node is considered OK */
349 * Clone a node during write unlocking, if its reference count is
352 static nodeptr
bt_clone_node(btree
*bt
, nodeptr n
)
355 nodeptr ret
= (nodecomponent
*)smalloc(bt
->propoffset
+ bt
->propsize
);
356 memcpy(ret
, n
, (bt
->maxdegree
*2+1) * sizeof(nodecomponent
));
358 for (i
= 0; i
< bt_elements(bt
, ret
); i
++) {
359 bt_element_t
*e
= bt_element(bt
, ret
, i
);
360 bt_set_element(bt
, ret
, i
, bt
->copy(bt
->userstate
, e
));
363 ret
[bt
->maxdegree
*2+1].i
= 1; /* clone has reference count 1 */
364 n
[bt
->maxdegree
*2+1].i
--; /* drop original's ref count by one */
366 * At this low level, we're allowed to reach directly into the
367 * subtrees to fiddle with their reference counts without
368 * having to lock them.
370 for (i
= 0; i
< bt_subtrees(bt
, ret
); i
++) {
371 node_addr na
= bt_child(bt
, ret
, i
);
373 na
.p
[bt
->maxdegree
*2+1].i
++; /* inc ref count of each child */
376 * Copy the user property explicitly (in case it contains a
377 * pointer to an allocated area).
379 memset((char *)ret
+ bt
->propoffset
, 0, bt
->propsize
);
380 bt
->propmerge(bt
->userstate
, NULL
, n
+ bt
->maxdegree
* 2 + 2,
381 ret
+ bt
->maxdegree
* 2 + 2);
386 * Return the node_addr for a currently locked node. NB that this
387 * means node movement must take place during _locking_ rather than
390 static INLINE node_addr
bt_node_addr(btree
*bt
, nodeptr n
)
398 * The bt_write_lock and bt_read_lock functions should gracefully
399 * handle being asked to write-lock a null node pointer, and just
400 * return a null nodeptr.
402 static INLINE nodeptr
bt_write_lock_child(btree
*bt
, nodeptr a
, int index
)
404 node_addr addr
= bt_child(bt
, a
, index
);
405 if (addr
.p
&& addr
.p
[bt
->maxdegree
*2+1].i
> 1) {
406 nodeptr clone
= bt_clone_node(bt
, addr
.p
);
407 bt_set_child(bt
, a
, index
, bt_node_addr(bt
, clone
));
408 testlock(TRUE
, TRUE
, clone
);
411 testlock(TRUE
, TRUE
, addr
.p
);
414 static INLINE nodeptr
bt_write_lock_root(btree
*bt
)
416 node_addr addr
= bt
->root
;
417 if (addr
.p
&& addr
.p
[bt
->maxdegree
*2+1].i
> 1) {
418 nodeptr clone
= bt_clone_node(bt
, addr
.p
);
419 bt
->root
= bt_node_addr(bt
, clone
);
420 testlock(TRUE
, TRUE
, clone
);
423 testlock(TRUE
, TRUE
, addr
.p
);
426 static INLINE nodeptr
bt_read_lock(btree
*bt
, node_addr a
)
428 testlock(FALSE
, TRUE
, a
.p
);
431 #define bt_read_lock_root(bt) (bt_read_lock(bt, (bt)->root))
432 #define bt_read_lock_child(bt,a,index) (bt_read_lock(bt,bt_child(bt,a,index)))
434 static INLINE
void bt_write_relock(btree
*bt
, nodeptr n
, int props
)
439 * Update the count in the node.
441 ns
= bt_subtrees(bt
, n
);
442 count
= ns
-1; /* count the elements */
443 for (i
= 0; i
< ns
; i
++)
444 count
+= bt_child_count(bt
, n
, i
);
445 n
[bt
->maxdegree
*2].i
= count
;
446 testlock(TRUE
, FALSE
, n
);
447 testlock(TRUE
, TRUE
, n
);
450 * Update user read properties.
452 if (props
&& bt
->propsize
) {
453 void *prevprop
, *eltprop
, *thisprop
, *childprop
;
456 eltprop
= ialloc(bt
->propsize
);
457 thisprop
= (void *)((char *)n
+ bt
->propoffset
);
459 for (i
= 0; i
< ns
; i
++) {
460 /* Merge a subtree's property into this one.
461 * Initially prevprop==NULL, meaning to just copy. */
462 if ( (childprop
= bt_child_prop(bt
, n
, i
)) != NULL
) {
463 bt
->propmerge(bt
->userstate
, prevprop
, childprop
, thisprop
);
468 /* Now merge in the separating element. */
469 bt
->propmake(bt
->userstate
, bt_element(bt
, n
, i
), eltprop
);
470 bt
->propmerge(bt
->userstate
, prevprop
, eltprop
, thisprop
);
479 static INLINE node_addr
bt_write_unlock_internal(btree
*bt
, nodeptr n
,
484 bt_write_relock(bt
, n
, props
);
486 testlock(TRUE
, FALSE
, n
);
492 static INLINE node_addr
bt_write_unlock(btree
*bt
, nodeptr n
)
494 return bt_write_unlock_internal(bt
, n
, TRUE
);
497 static INLINE
void bt_read_unlock(btree
*bt
, nodeptr n
)
500 * For trees in memory, we do nothing here, except run some
503 testlock(FALSE
, FALSE
, n
);
506 /* ----------------------------------------------------------------------
507 * Higher-level helper functions, which should be independent of
508 * the knowledge of precise node structure in the above code.
512 * Return the count of items below a node that appear before the
513 * start of a given subtree.
515 static int bt_child_startpos(btree
*bt
, nodeptr n
, int index
)
521 pos
+= bt_child_count(bt
, n
, index
) + 1; /* 1 for separating elt */
527 * Create a new root node for a tree.
529 static void bt_new_root(btree
*bt
, node_addr left
, node_addr right
,
530 bt_element_t element
)
533 n
= bt_new_node(bt
, 2);
534 bt_set_child(bt
, n
, 0, left
);
535 bt_set_child(bt
, n
, 1, right
);
536 bt_set_element(bt
, n
, 0, element
);
537 bt
->root
= bt_write_unlock(bt
, n
);
542 * Discard the root node of a tree, and enshrine a new node as the
543 * root. Expects to be passed a write-locked nodeptr to the old
546 static void bt_shift_root(btree
*bt
, nodeptr n
, node_addr na
)
548 bt_destroy_node(bt
, n
);
554 * Given a numeric index within a node, find which subtree we would
555 * descend to in order to find that index.
557 * Updates `pos' to give the numeric index within the subtree
558 * found. Also returns `ends' (if non-NULL), which has bit 0 set if
559 * the index is at the very left edge of the subtree, and/or bit 1
560 * if it's at the very right edge.
562 * Return value is the number of the subtree (0 upwards).
568 static int bt_lookup_pos(btree
*bt
, nodeptr n
, int *pos
, int *ends
)
571 int nchildren
= bt_subtrees(bt
, n
);
573 while (child
< nchildren
) {
574 int count
= bt_child_count(bt
, n
, child
);
585 *pos
-= count
+ 1; /* 1 for the separating element */
588 return -1; /* ran off the end; shouldn't happen */
592 * Given an element to search for within a node, find either the
593 * element, or which subtree we would descend to to continue
594 * searching for that element.
596 * Return value is either the index of the element, or the index of
597 * the subtree (both 0 upwards). `is_elt' returns FALSE or TRUE
600 * Since this may be used by bt_find() with an alternative cmpfn_t,
601 * we always pass the input element as the first argument to cmp.
603 static int bt_lookup_cmp(btree
*bt
, nodeptr n
, bt_element_t element
,
604 cmpfn_t cmp
, int *is_elt
)
606 int mintree
= 0, maxtree
= bt_subtrees(bt
, n
)-1;
608 while (mintree
< maxtree
) {
609 int elt
= (maxtree
+ mintree
) / 2;
610 int c
= cmp(bt
->userstate
, element
, bt_element(bt
, n
, elt
));
617 * `element' is less than element `elt'. So it can be
618 * in subtree number `elt' at the highest.
623 * `element' is greater than element `elt'. So it can
624 * be in subtree number (elt+1) at the lowest.
631 * If we reach here without returning, we must have narrowed
632 * our search to the point where mintree = maxtree. So the
633 * element is not in the node itself and we know which subtree
636 assert(mintree
== maxtree
);
642 * Generic transformations on B-tree nodes.
644 * This function divides essentially into an input side and an
645 * output side. The input side accumulates a list of items
646 * node,element,node,element,...,element,node; the output side
647 * writes those items into either one or two nodes.
651 * - NODE_AS_IS. The input list is the contents of in1, followed
652 * by inelt, followed by the contents of in2. The `extra'
653 * parameters are unused, as is `inaux'.
655 * - NODE_ADD_ELT. `in2' is unused. The input list is the contents
656 * of `in1', but with subtree pointer number `inaux' replaced by
657 * extra1/inelt/extra2.
659 * - NODE_DEL_ELT. `in2' and `inelt' are unused, as is `extra2'.
660 * The input list is the contents of `in1', but with element
661 * pointer number `inaux' and its surrounding two subtrees
662 * replaced by extra1.
664 * Having obtained the input list, it is then written to one or two
665 * output nodes. If `splitpos' is NODE_JOIN, everything is written
666 * into one output node `out1'. Otherwise, `splitpos' is treated as
667 * an element index within the input list; that element is returned
668 * in `outelt', and the contents of the list is divided there and
669 * returned in nodes `out1' and `out2'.
671 * This function will re-use nodes in the `obvious' order. If two
672 * nodes are passed in and two nodes are output, they'll be the
673 * same nodes; if one node is passed in and one node output, it
674 * will be the same node too. If two are passed in and only one
675 * output, the first one will be used and the second destroyed; if
676 * one node is passed in and two are output, the one passed in will
677 * be the first of those returned, and the second will be new.
680 #define NODE_ADD_ELT 2
681 #define NODE_DEL_ELT 3
683 static void bt_xform(btree
*bt
, int intype
, int inaux
,
684 nodeptr in1
, nodeptr in2
, bt_element_t inelt
,
685 node_addr extra1
, node_addr extra2
,
686 int splitpos
, nodeptr
*out1
, nodeptr
*out2
,
687 bt_element_t
*outelt
)
690 bt_element_t
*elements
;
692 int n1
, n2
, off2
, i
, j
;
694 nodes
= inewn(node_addr
, 2 * bt_max_subtrees(bt
));
695 elements
= inewn(bt_element_t
, 2 * bt_max_subtrees(bt
));
698 * Accumulate the input list.
702 n1
= bt_subtrees(bt
, in1
);
703 n2
= bt_subtrees(bt
, in2
);
709 n2
= bt_subtrees(bt
, in1
) - inaux
;
715 n2
= bt_subtrees(bt
, in1
) - inaux
- 1;
721 nodes
[i
] = bt_child(bt
, in1
, j
);
723 elements
[i
] = bt_element(bt
, in1
, j
);
726 if (intype
== NODE_DEL_ELT
) {
731 nodes
[i
] = bt_child(bt
, in2
, off2
+j
);
733 elements
[i
] = bt_element(bt
, in2
, off2
+j
);
738 elements
[n1
-1] = inelt
;
741 nodes
[n1
-1] = extra1
;
743 elements
[n1
-1] = inelt
;
746 nodes
[n1
-1] = extra1
;
751 * Now determine how many subtrees go in each output node, and
752 * actually create the nodes to be returned.
754 if (splitpos
!= NODE_JOIN
) {
755 n1
= splitpos
+1, n2
= i
- splitpos
- 1;
757 *outelt
= elements
[splitpos
];
762 ret1
= bt_reuse_node(bt
, in1
, n1
);
763 if (intype
== NODE_AS_IS
&& in2
) {
764 /* We have a second input node. */
766 ret2
= bt_reuse_node(bt
, in2
, n2
);
768 bt_destroy_node(bt
, in2
);
770 /* We have no second input node. */
772 ret2
= bt_new_node(bt
, n2
);
777 if (out1
) *out1
= ret1
;
778 if (out2
) *out2
= ret2
;
780 for (i
= 0; i
< n1
; i
++) {
781 bt_set_child(bt
, ret1
, i
, nodes
[i
]);
783 bt_set_element(bt
, ret1
, i
, elements
[i
]);
786 if (outelt
) *outelt
= elements
[n1
-1];
787 for (i
= 0; i
< n2
; i
++) {
788 bt_set_child(bt
, ret2
, i
, nodes
[n1
+i
]);
790 bt_set_element(bt
, ret2
, i
, elements
[n1
+i
]);
799 * Fiddly little compare functions for use in special cases of
800 * findrelpos. One always returns +1 (a > b), the other always
801 * returns -1 (a < b).
803 static int bt_cmp_greater(void *state
,
804 const bt_element_t a
, const bt_element_t b
)
808 static int bt_cmp_less(void *state
,
809 const bt_element_t a
, const bt_element_t b
)
814 /* ----------------------------------------------------------------------
815 * User-visible administration routines.
818 btree
*bt_new(cmpfn_t cmp
, copyfn_t copy
, freefn_t freeelt
,
819 int propsize
, int propalign
, propmakefn_t propmake
,
820 propmergefn_t propmerge
, void *state
, int mindegree
)
825 ret
->mindegree
= mindegree
;
826 ret
->maxdegree
= 2*mindegree
;
827 ret
->depth
= 0; /* not even a root right now */
828 ret
->root
= NODE_ADDR_NULL
;
831 ret
->freeelt
= freeelt
;
832 ret
->propsize
= propsize
;
833 ret
->propalign
= propalign
;
834 ret
->propoffset
= sizeof(nodecomponent
) * (ret
->maxdegree
*2 + 2);
836 ret
->propoffset
+= propalign
- 1;
837 ret
->propoffset
-= ret
->propoffset
% propalign
;
839 ret
->propmake
= propmake
;
840 ret
->propmerge
= propmerge
;
841 ret
->userstate
= state
;
846 static void bt_free_node(btree
*bt
, nodeptr n
)
850 for (i
= 0; i
< bt_subtrees(bt
, n
); i
++) {
854 na
= bt_child(bt
, n
, i
);
855 if (!bt_unref_node(bt
, na
)) {
856 n2
= bt_write_lock_child(bt
, n
, i
);
857 bt_free_node(bt
, n2
);
862 for (i
= 0; i
< bt_subtrees(bt
, n
)-1; i
++)
863 bt
->freeelt(bt
->userstate
, bt_element(bt
, n
, i
));
866 bt_destroy_node(bt
, n
);
869 void bt_free(btree
*bt
)
873 if (!bt_unref_node(bt
, bt
->root
)) {
874 n
= bt_write_lock_root(bt
);
881 btree
*bt_clone(btree
*bt
)
885 bt2
= bt_new(bt
->cmp
, bt
->copy
, bt
->freeelt
, bt
->propsize
, bt
->propalign
,
886 bt
->propmake
, bt
->propmerge
, bt
->userstate
, bt
->mindegree
);
887 bt2
->depth
= bt
->depth
;
888 bt2
->root
= bt_ref_node(bt
, bt
->root
);
893 * Nice simple function to count the size of a tree.
895 int bt_count(btree
*bt
)
900 n
= bt_read_lock_root(bt
);
902 count
= bt_node_count(bt
, n
);
903 bt_read_unlock(bt
, n
);
910 /* ----------------------------------------------------------------------
911 * Actual B-tree algorithms.
915 * Find an element by numeric index. bt_index_w is the same, but
916 * works with write locks instead of read locks, so it guarantees
917 * to return an element with only one reference to it. (You'd use
918 * this if you were using tree cloning, and wanted to modify the
919 * element once you'd found it.)
921 bt_element_t
bt_index(btree
*bt
, int index
)
926 n
= bt_read_lock_root(bt
);
928 if (index
< 0 || index
>= bt_node_count(bt
, n
)) {
929 bt_read_unlock(bt
, n
);
934 child
= bt_lookup_pos(bt
, n
, &index
, &ends
);
935 if (ends
& ENDS_RIGHT
) {
936 bt_element_t ret
= bt_element(bt
, n
, child
);
937 bt_read_unlock(bt
, n
);
940 n2
= bt_read_lock_child(bt
, n
, child
);
941 bt_read_unlock(bt
, n
);
947 bt_element_t
bt_index_w(btree
*bt
, int index
)
950 int nnodes
, child
, ends
;
954 nodes
= inewn(nodeptr
, bt
->depth
+1);
957 n
= bt_write_lock_root(bt
);
959 if (index
< 0 || index
>= bt_node_count(bt
, n
)) {
960 bt_write_unlock(bt
, n
);
966 child
= bt_lookup_pos(bt
, n
, &index
, &ends
);
967 if (ends
& ENDS_RIGHT
) {
968 ret
= bt_element(bt
, n
, child
);
971 n2
= bt_write_lock_child(bt
, n
, child
);
977 bt_write_unlock(bt
, nodes
[nnodes
]);
983 * Search for an element by sorted order.
985 bt_element_t
bt_findrelpos(btree
*bt
, bt_element_t element
, cmpfn_t cmp
,
986 int relation
, int *index
)
993 if (!cmp
) cmp
= bt
->cmp
;
996 * Special case: relation LT/GT and element NULL means get an
997 * extreme element of the tree. We do this by fudging the
998 * compare function so that our NULL element will be considered
999 * infinitely large or infinitely small.
1001 if (element
== NULL
) {
1002 assert(relation
== BT_REL_LT
|| relation
== BT_REL_GT
);
1003 if (relation
== BT_REL_LT
)
1004 cmp
= bt_cmp_greater
; /* always returns a > b */
1006 cmp
= bt_cmp_less
; /* always returns a < b */
1010 n
= bt_read_lock_root(bt
);
1014 child
= bt_lookup_cmp(bt
, n
, element
, cmp
, &is_elt
);
1016 pos
+= bt_child_startpos(bt
, n
, child
+1) - 1;
1017 gotit
= bt_element(bt
, n
, child
);
1018 bt_read_unlock(bt
, n
);
1021 pos
+= bt_child_startpos(bt
, n
, child
);
1022 n2
= bt_read_lock_child(bt
, n
, child
);
1023 bt_read_unlock(bt
, n
);
1029 * Now all nodes are unlocked, and we are _either_ (a) holding
1030 * an element in `gotit' whose index we have in `pos', _or_ (b)
1031 * holding nothing in `gotit' but we know the index of the
1032 * next-higher element.
1036 * We have the real element. For EQ, LE and GE relations we
1037 * can now just return it; otherwise we must return the
1038 * next element down or up.
1040 if (relation
== BT_REL_LT
)
1041 gotit
= bt_index(bt
, --pos
);
1042 else if (relation
== BT_REL_GT
)
1043 gotit
= bt_index(bt
, ++pos
);
1046 * We don't have the real element. For EQ relation we now
1047 * just give up; for everything else we return the next
1048 * element down or up.
1050 if (relation
== BT_REL_LT
|| relation
== BT_REL_LE
)
1051 gotit
= bt_index(bt
, --pos
);
1052 else if (relation
== BT_REL_GT
|| relation
== BT_REL_GE
)
1053 gotit
= bt_index(bt
, pos
);
1056 if (gotit
&& index
) *index
= pos
;
1059 bt_element_t
bt_findrel(btree
*bt
, bt_element_t element
, cmpfn_t cmp
,
1062 return bt_findrelpos(bt
, element
, cmp
, relation
, NULL
);
1064 bt_element_t
bt_findpos(btree
*bt
, bt_element_t element
, cmpfn_t cmp
,
1067 return bt_findrelpos(bt
, element
, cmp
, BT_REL_EQ
, index
);
1069 bt_element_t
bt_find(btree
*bt
, bt_element_t element
, cmpfn_t cmp
)
1071 return bt_findrelpos(bt
, element
, cmp
, BT_REL_EQ
, NULL
);
1075 * Find an element by property-based search. Returns the element
1076 * (if one is selected - the search can also terminate by
1077 * descending to a nonexistent subtree of a leaf node, equivalent
1078 * to selecting the _gap_ between two elements); also returns the
1079 * index of either the element or the gap in `*index' if `index' is
1082 bt_element_t
bt_propfind(btree
*bt
, searchfn_t search
, void *sstate
,
1086 int i
, j
, count
, is_elt
;
1090 bt_element_t
*e
= NULL
;
1092 props
= inewn(void *, bt
->maxdegree
);
1093 counts
= inewn(int, bt
->maxdegree
);
1094 elts
= inewn(bt_element_t
, bt
->maxdegree
);
1096 n
= bt_read_lock_root(bt
);
1101 int ntrees
= bt_subtrees(bt
, n
);
1104 * Prepare the arguments to the search function.
1106 for (i
= 0; i
< ntrees
; i
++) {
1107 props
[i
] = bt_child_prop(bt
, n
, i
);
1108 counts
[i
] = bt_child_count(bt
, n
, i
);
1110 elts
[i
] = bt_element(bt
, n
, i
);
1114 * Call the search function.
1116 i
= search(bt
->userstate
, sstate
, ntrees
,
1117 props
, counts
, elts
, &is_elt
);
1121 * Descend to subtree i. Update `count' to consider
1122 * everything (both subtrees and elements) before that
1125 for (j
= 0; j
< i
; j
++)
1126 count
+= 1 + bt_child_count(bt
, n
, j
);
1127 n2
= bt_read_lock_child(bt
, n
, i
);
1128 bt_read_unlock(bt
, n
);
1132 * Return element i. Update `count' to consider
1133 * everything (both subtrees and elements) before that
1136 for (j
= 0; j
<= i
; j
++)
1137 count
+= 1 + bt_child_count(bt
, n
, j
);
1138 count
--; /* don't count element i itself */
1139 e
= bt_element(bt
, n
, i
);
1140 bt_read_unlock(bt
, n
);
1149 if (index
) *index
= count
;
1154 * Replace the element at a numeric index by a new element. Returns
1157 * Can also be used when the new element is the _same_ as the old
1158 * element, but has changed in some way that will affect user
1161 bt_element_t
bt_replace(btree
*bt
, bt_element_t element
, int index
)
1166 int nnodes
, child
, ends
;
1168 nodes
= inewn(nodeptr
, bt
->depth
+1);
1171 n
= bt_write_lock_root(bt
);
1173 if (index
< 0 || index
>= bt_node_count(bt
, n
)) {
1174 bt_write_unlock(bt
, n
);
1179 nodes
[nnodes
++] = n
;
1180 child
= bt_lookup_pos(bt
, n
, &index
, &ends
);
1181 if (ends
& ENDS_RIGHT
) {
1182 ret
= bt_element(bt
, n
, child
);
1183 bt_set_element(bt
, n
, child
, element
);
1186 n
= bt_write_lock_child(bt
, n
, child
);
1190 while (nnodes
-- > 0)
1191 bt_write_unlock(bt
, nodes
[nnodes
]);
1197 * Add at a specific position. As we search down the tree we must
1198 * write-lock every node we meet, since otherwise we might fail to
1199 * clone nodes that will end up pointing to different things.
1201 void bt_addpos(btree
*bt
, bt_element_t element
, int pos
)
1204 node_addr left
, right
, single
;
1210 * Since in a reference-counted tree we can't have parent
1211 * links, we will have to use O(depth) space to store the list
1212 * of nodeptrs we have gone through, so we can un-write-lock
1213 * them when we've finished. We also store the subtree index we
1214 * descended to at each stage.
1216 nodes
= inewn(nodeptr
, bt
->depth
+1);
1217 childposns
= inewn(int, bt
->depth
+1);
1220 n
= bt_write_lock_root(bt
);
1222 assert(pos
>= 0 && pos
<= (n ?
bt_node_count(bt
, n
) : 0));
1225 * Scan down the tree, write-locking nodes, until we find the
1226 * empty subtree where we want to insert the item.
1230 child
= bt_lookup_pos(bt
, n
, &pos
, NULL
);
1231 childposns
[nnodes
] = child
;
1233 n
= bt_write_lock_child(bt
, n
, child
);
1236 left
= right
= NODE_ADDR_NULL
;
1239 * Now nodes[nnodes-1] wants to have subtree index
1240 * childposns[nnodes-1] replaced by the node/element/node triple
1241 * (left,element,right). Propagate this up the tree until we
1244 while (nnodes
-- > 0) {
1246 if (bt_subtrees(bt
, n
) == bt_max_subtrees(bt
)) {
1248 /* Split the node and carry on up. */
1249 bt_xform(bt
, NODE_ADD_ELT
, childposns
[nnodes
],
1250 n
, NULL
, element
, left
, right
,
1251 bt_min_subtrees(bt
), &lptr
, &rptr
, &element
);
1252 left
= bt_write_unlock(bt
, lptr
);
1253 right
= bt_write_unlock(bt
, rptr
);
1255 bt_xform(bt
, NODE_ADD_ELT
, childposns
[nnodes
],
1256 n
, NULL
, element
, left
, right
,
1257 NODE_JOIN
, &n
, NULL
, NULL
);
1258 single
= bt_write_unlock(bt
, n
);
1264 * If nnodes < 0, we have just split the root and we need to
1265 * build a new root node.
1268 bt_new_root(bt
, left
, right
, element
);
1271 * Now nodes[nnodes-1] just wants to have child pointer
1272 * child[nnodes-1] replaced by `single', in case the
1273 * subtree was moved. Propagate this back up to the root,
1274 * unlocking all nodes.
1276 while (nnodes
-- > 0) {
1277 bt_set_child(bt
, nodes
[nnodes
], childposns
[nnodes
], single
);
1278 single
= bt_write_unlock(bt
, nodes
[nnodes
]);
1287 * Add an element in sorted order. This is a wrapper on bt_addpos()
1288 * which finds the numeric index to add the item at and then calls
1289 * addpos. This isn't an optimal use of time, but it saves space by
1290 * avoiding starting to clone multiply-linked nodes until it's
1291 * known that the item _can_ be added to the tree (and isn't
1292 * duplicated in it already).
1294 bt_element_t
bt_add(btree
*bt
, bt_element_t element
)
1300 n
= bt_read_lock_root(bt
);
1302 child
= bt_lookup_cmp(bt
, n
, element
, bt
->cmp
, &is_elt
);
1304 bt_read_unlock(bt
, n
);
1305 return bt_element(bt
, n
, child
); /* element exists already */
1307 pos
+= bt_child_startpos(bt
, n
, child
);
1308 n2
= bt_read_lock_child(bt
, n
, child
);
1309 bt_read_unlock(bt
, n
);
1313 bt_addpos(bt
, element
, pos
);
1318 * Delete an element given its numeric position. Returns the
1321 bt_element_t
bt_delpos(btree
*bt
, int pos
)
1323 nodeptr n
, c
, c2
, saved_n
;
1325 int nnodes
, child
, nroot
, pos2
, ends
, st
, splitpoint
, saved_pos
;
1326 bt_element_t e
, ret
;
1329 * Just like in bt_add, we store the set of nodeptrs we
1330 * write-locked on the way down, so we can unlock them on the
1333 nodes
= inewn(nodeptr
, bt
->depth
+1);
1336 n
= bt_write_lock_root(bt
);
1340 if (!n
|| pos
< 0 || pos
>= bt_node_count(bt
, n
)) {
1342 bt_write_unlock(bt
, n
);
1347 nodes
[nnodes
++] = n
;
1350 * Find out which subtree to descend to.
1353 child
= bt_lookup_pos(bt
, n
, &pos
, &ends
);
1354 c
= bt_write_lock_child(bt
, n
, child
);
1355 if (c
&& bt_subtrees(bt
, c
) == bt_min_subtrees(bt
)) {
1357 * We're trying to descend to a subtree that's of
1358 * minimum size. Do something!
1362 * Either move a subtree from the left sibling, or
1363 * merge with it. (Traditionally we would only
1364 * merge if we can't move a subtree from _either_
1365 * sibling, but this way avoids too many extra
1369 c
= bt_write_lock_child(bt
, n
, child
-1);
1370 e
= bt_element(bt
, n
, child
-1);
1371 st
= bt_subtrees(bt
, c
);
1372 if (st
> bt_min_subtrees(bt
))
1373 splitpoint
= st
- 2;
1375 splitpoint
= NODE_JOIN
;
1379 * Likewise on the right-hand side.
1381 c2
= bt_write_lock_child(bt
, n
, child
+1);
1382 e
= bt_element(bt
, n
, child
);
1383 st
= bt_subtrees(bt
, c2
);
1384 if (st
> bt_min_subtrees(bt
))
1385 splitpoint
= bt_min_subtrees(bt
);
1387 splitpoint
= NODE_JOIN
;
1390 if (splitpoint
== NODE_JOIN
) {
1392 * So if we're merging nodes, go to it...
1394 bt_xform(bt
, NODE_AS_IS
, 0,
1395 c
, c2
, e
, NODE_ADDR_NULL
, NODE_ADDR_NULL
,
1396 NODE_JOIN
, &c
, NULL
, NULL
);
1397 bt_xform(bt
, NODE_DEL_ELT
, child
,
1398 n
, NULL
, NULL
, bt_node_addr(bt
, c
), NODE_ADDR_NULL
,
1399 NODE_JOIN
, &n
, NULL
, NULL
);
1400 if (nroot
&& bt_subtrees(bt
, n
) == 1) {
1402 * Whoops, we just merged the last two children
1403 * of the root. Better relocate the root.
1405 bt_shift_root(bt
, n
, bt_node_addr(bt
, c
));
1406 nnodes
--; /* don't leave it in nodes[]! */
1408 bt_write_relock(bt
, c
, TRUE
);
1410 bt_write_unlock(bt
, c
);
1413 * Or if we're redistributing subtrees, go to that.
1415 bt_xform(bt
, NODE_AS_IS
, 0,
1416 c
, c2
, e
, NODE_ADDR_NULL
, NODE_ADDR_NULL
,
1417 splitpoint
, &c
, &c2
, &e
);
1418 bt_set_element(bt
, n
, child
, e
);
1419 bt_write_unlock(bt
, c
);
1420 bt_write_unlock(bt
, c2
);
1424 /* Recompute the counts in n so we can do lookups again. */
1425 bt_write_relock(bt
, n
, TRUE
);
1427 /* Having done the transform, redo the position lookup. */
1429 child
= bt_lookup_pos(bt
, n
, &pos
, &ends
);
1430 c
= bt_write_lock_child(bt
, n
, child
);
1437 * Now see if this node contains the element we're
1440 if (n
&& (ends
& ENDS_RIGHT
)) {
1442 * It does. Element number `child' is the element we
1443 * want to delete. See if this is a leaf node...
1445 if (!bt_is_leaf(bt
, n
)) {
1447 * It's not a leaf node. So we save the nodeptr and
1448 * element index for later reference, and decrement
1449 * `pos' so that we're searching for the element to its
1450 * left, which _will_ be in a leaf node.
1457 * We've reached a leaf node. Check to see if an
1458 * internal-node position was stored in saved_n and
1459 * saved_pos, and move this element there if so.
1462 ret
= bt_element(bt
, saved_n
, saved_pos
);
1463 bt_set_element(bt
, saved_n
, saved_pos
,
1464 bt_element(bt
, n
, child
));
1466 ret
= bt_element(bt
, n
, child
);
1468 /* Then delete it from the leaf node. */
1469 bt_xform(bt
, NODE_DEL_ELT
, child
,
1470 n
, NULL
, NULL
, NODE_ADDR_NULL
, NODE_ADDR_NULL
,
1471 NODE_JOIN
, &n
, NULL
, NULL
);
1473 * Final special case: if this is the root node and
1474 * we've just deleted its last element, we should
1475 * destroy it and leave a completely empty tree.
1477 if (nroot
&& bt_subtrees(bt
, n
) == 1) {
1478 bt_shift_root(bt
, n
, NODE_ADDR_NULL
);
1479 nnodes
--; /* and take it out of nodes[] */
1481 /* Now we're done */
1486 /* Descend to the child and go round again. */
1492 * All done. Zip back up the tree un-write-locking nodes.
1494 while (nnodes
-- > 0)
1495 bt_write_unlock(bt
, nodes
[nnodes
]);
1503 * Delete an element in sorted order.
1505 bt_element_t
bt_del(btree
*bt
, bt_element_t element
)
1508 if (!bt_findrelpos(bt
, element
, NULL
, BT_REL_EQ
, &index
))
1509 return NULL
; /* wasn't there */
1510 return bt_delpos(bt
, index
);
1514 * Join two trees together, given their respective depths and a
1515 * middle element. Puts the resulting tree in the root of `bt'.
1517 * This internal routine assumes that the trees have the same
1520 * The input nodeptrs are assumed to be write-locked, but none of
1521 * their children are yet write-locked.
1523 static void bt_join_internal(btree
*bt
, nodeptr lp
, nodeptr rp
,
1524 bt_element_t sep
, int ld
, int rd
)
1528 int nnodes
, nodessize
;
1532 * We will need to store parent nodes up to the difference
1533 * between ld and rd.
1535 nodessize
= (ld
< rd ? rd
-ld
: ld
-rd
);
1536 if (nodessize
) { /* we may not need _any_! */
1537 nodes
= inewn(nodeptr
, nodessize
);
1538 childposns
= inewn(int, nodessize
);
1543 bt
->root
= bt_node_addr(bt
, lp
);
1545 /* If the left tree is taller, search down its right-hand edge. */
1547 int child
= bt_subtrees(bt
, lp
) - 1;
1548 nodeptr n
= bt_write_lock_child(bt
, lp
, child
);
1550 childposns
[nnodes
] = child
;
1556 bt
->root
= bt_node_addr(bt
, rp
);
1558 /* If the right tree is taller, search down its left-hand edge. */
1560 nodeptr n
= bt_write_lock_child(bt
, rp
, 0);
1562 childposns
[nnodes
] = 0;
1570 * So we now want to combine nodes lp and rp into either one or
1571 * two plausibly-sized nodes, whichever is feasible. We have a
1572 * joining element `sep'.
1574 lsub
= (lp ?
bt_subtrees(bt
, lp
) : 0);
1575 rsub
= (rp ?
bt_subtrees(bt
, rp
) : 0);
1576 if (lp
&& rp
&& lsub
+ rsub
<= bt_max_subtrees(bt
)) {
1578 /* Join the nodes into one. */
1579 bt_xform(bt
, NODE_AS_IS
, 0, lp
, rp
, sep
,
1580 NODE_ADDR_NULL
, NODE_ADDR_NULL
,
1581 NODE_JOIN
, &lp
, NULL
, NULL
);
1582 /* Unlock the node. */
1583 la
= bt_write_unlock(bt
, lp
);
1584 /* Update the child pointer in the next node up. */
1586 bt_set_child(bt
, nodes
[nnodes
-1], childposns
[nnodes
-1], la
);
1592 la
= NODE_ADDR_NULL
;
1593 ra
= NODE_ADDR_NULL
;
1596 /* Re-split the nodes into two plausibly sized ones. */
1597 lsize
= lsub
+ rsub
;
1600 bt_xform(bt
, NODE_AS_IS
, 0, lp
, rp
, sep
,
1601 NODE_ADDR_NULL
, NODE_ADDR_NULL
,
1602 lsize
-1, &lp
, &rp
, &sep
);
1603 /* Unlock the nodes. */
1604 la
= bt_write_unlock(bt
, lp
);
1605 ra
= bt_write_unlock(bt
, rp
);
1609 * Now we have to do the addition thing: progress up the
1610 * tree replacing a single subtree pointer with the
1611 * la/sep/ra assembly, until no more nodes have to split as
1614 while (nnodes
-- > 0) {
1615 nodeptr n
= nodes
[nnodes
];
1616 if (bt_subtrees(bt
, n
) == bt_max_subtrees(bt
)) {
1617 /* Split the node and carry on up. */
1618 bt_xform(bt
, NODE_ADD_ELT
, childposns
[nnodes
],
1619 n
, NULL
, sep
, la
, ra
,
1620 bt_min_subtrees(bt
), &lp
, &rp
, &sep
);
1621 la
= bt_write_unlock(bt
, lp
);
1622 ra
= bt_write_unlock(bt
, rp
);
1624 bt_xform(bt
, NODE_ADD_ELT
, childposns
[nnodes
],
1625 n
, NULL
, sep
, la
, ra
,
1626 NODE_JOIN
, &n
, NULL
, NULL
);
1627 bt_write_unlock(bt
, n
);
1633 * If nnodes < 0, we have just split the root and we need
1634 * to build a new root node.
1637 bt_new_root(bt
, la
, ra
, sep
);
1641 * Now we just need to go back up and unlock any remaining
1642 * nodes. Also here we ensure the root points where it should.
1644 while (nnodes
-- > 0) {
1646 na
= bt_write_unlock(bt
, nodes
[nnodes
]);
1658 * External interfaces to the join functionality: join and joinr
1659 * (differing only in which B-tree structure they leave without any
1660 * elements, and which they return the combined tree in).
1662 btree
*bt_join(btree
*bt1
, btree
*bt2
)
1664 nodeptr root1
, root2
;
1667 size2
= bt_count(bt2
);
1673 * The trees are ordered, so verify the ordering
1674 * condition: ensure nothing in bt1 is greater than or
1675 * equal to the minimum element in bt2.
1677 sep
= bt_index(bt2
, 0);
1678 sep
= bt_findrelpos(bt1
, sep
, NULL
, BT_REL_GE
, NULL
);
1683 sep
= bt_delpos(bt2
, 0);
1684 root1
= bt_write_lock_root(bt1
);
1685 root2
= bt_write_lock_root(bt2
);
1686 bt_join_internal(bt1
, root1
, root2
, sep
, bt1
->depth
, bt2
->depth
);
1687 bt2
->root
= NODE_ADDR_NULL
;
1693 btree
*bt_joinr(btree
*bt1
, btree
*bt2
)
1695 nodeptr root1
, root2
;
1698 size1
= bt_count(bt1
);
1704 * The trees are ordered, so verify the ordering
1705 * condition: ensure nothing in bt2 is less than or
1706 * equal to the maximum element in bt1.
1708 sep
= bt_index(bt1
, size1
-1);
1709 sep
= bt_findrelpos(bt2
, sep
, NULL
, BT_REL_LE
, NULL
);
1714 sep
= bt_delpos(bt1
, size1
-1);
1715 root1
= bt_write_lock_root(bt1
);
1716 root2
= bt_write_lock_root(bt2
);
1717 bt_join_internal(bt2
, root1
, root2
, sep
, bt1
->depth
, bt2
->depth
);
1718 bt1
->root
= NODE_ADDR_NULL
;
1725 * Perform the healing process after a tree has been split. `rhs'
1726 * is set if the cut edge is the one on the right.
1728 static void bt_split_heal(btree
*bt
, int rhs
)
1734 nodes
= inewn(nodeptr
, bt
->depth
);
1737 n
= bt_write_lock_root(bt
);
1740 * First dispense with completely trivial cases: a root node
1741 * containing only one subtree can be thrown away instantly.
1743 while (n
&& bt_subtrees(bt
, n
) == 1) {
1744 nodeptr n2
= bt_write_lock_child(bt
, n
, 0);
1745 bt_shift_root(bt
, n
, bt_node_addr(bt
, n2
));
1750 * Now we have a plausible root node. Start going down the cut
1751 * edge looking for undersized or minimum nodes, and arranging
1752 * for them to be above minimum size.
1755 int edge
, next
, elt
, size_e
, size_n
, size_total
;
1756 nodeptr ne
, nn
, nl
, nr
;
1759 nodes
[nnodes
++] = n
;
1762 edge
= bt_subtrees(bt
, n
) - 1;
1771 ne
= bt_write_lock_child(bt
, n
, edge
);
1775 size_e
= bt_subtrees(bt
, ne
);
1777 if (size_e
<= bt_min_subtrees(bt
)) {
1778 nn
= bt_write_lock_child(bt
, n
, next
);
1779 el
= bt_element(bt
, n
, elt
);
1780 size_n
= bt_subtrees(bt
, nn
);
1785 size_total
= size_e
+ size_n
;
1786 if (size_e
+ size_n
<= bt_max_subtrees(bt
)) {
1788 * Merge the edge node and its sibling together.
1790 bt_xform(bt
, NODE_AS_IS
, 0, nl
, nr
, el
,
1791 NODE_ADDR_NULL
, NODE_ADDR_NULL
,
1792 NODE_JOIN
, &ne
, NULL
, NULL
);
1793 bt_xform(bt
, NODE_DEL_ELT
, elt
, n
, NULL
, NULL
,
1794 bt_node_addr(bt
, ne
), NODE_ADDR_NULL
,
1795 NODE_JOIN
, &n
, NULL
, NULL
);
1797 * It's possible we've just trashed the root of the
1800 if (bt_subtrees(bt
, n
) == 1) {
1801 bt_shift_root(bt
, n
, bt_node_addr(bt
, ne
));
1802 nnodes
--; /* and take it out of nodes[] */
1806 * Redistribute subtrees between the edge node and
1810 size_e
= (size_total
+ 1) / 2;
1811 assert(size_e
> bt_min_subtrees(bt
));
1813 split
= size_total
- size_e
- 1;
1816 bt_xform(bt
, NODE_AS_IS
, 0, nl
, nr
, el
,
1817 NODE_ADDR_NULL
, NODE_ADDR_NULL
,
1818 split
, &nl
, &nr
, &el
);
1819 bt_write_unlock(bt
, nn
);
1820 bt_set_element(bt
, n
, elt
, el
);
1828 * Now we just need to go back up and unlock any remaining
1831 while (nnodes
-- > 0)
1832 bt_write_unlock(bt
, nodes
[nnodes
]);
1838 * Split a tree by numeric position. The new tree returned is the
1839 * one on the right; the original tree contains the stuff on the
1842 static btree
*bt_split_internal(btree
*bt1
, int index
)
1845 nodeptr
*lnodes
, *rnodes
;
1849 bt2
= bt_new(bt1
->cmp
, bt1
->copy
, bt1
->freeelt
, bt1
->propsize
,
1850 bt1
->propalign
, bt1
->propmake
, bt1
->propmerge
,
1851 bt1
->userstate
, bt1
->mindegree
);
1852 bt2
->depth
= bt1
->depth
;
1854 lnodes
= inewn(nodeptr
, bt1
->depth
);
1855 rnodes
= inewn(nodeptr
, bt2
->depth
);
1858 n1
= bt_write_lock_root(bt1
);
1860 child
= bt_lookup_pos(bt1
, n1
, &index
, NULL
);
1861 n
= bt_write_lock_child(bt1
, n1
, child
);
1862 bt_xform(bt1
, NODE_ADD_ELT
, child
, n1
, NULL
, NULL
,
1863 bt_node_addr(bt1
, n
), NODE_ADDR_NULL
,
1864 child
, &n1
, &n2
, NULL
);
1865 lnodes
[nnodes
] = n1
;
1866 rnodes
[nnodes
] = n2
;
1868 bt_set_child(bt2
, rnodes
[nnodes
-1], 0, bt_node_addr(bt2
, n2
));
1870 bt2
->root
= bt_node_addr(bt2
, n2
);
1876 * Now we go back up and unlock all the nodes. At this point we
1877 * don't mess with user properties, because there's the danger
1878 * of a node containing no subtrees _or_ elements and hence us
1879 * having to invent a notation for an empty property. We're
1880 * going to make a second healing pass in a moment anyway,
1881 * which will sort all that out for us.
1883 while (nnodes
-- > 0) {
1884 bt_write_unlock_internal(bt1
, lnodes
[nnodes
], FALSE
);
1885 bt_write_unlock_internal(bt2
, rnodes
[nnodes
], FALSE
);
1889 * Then we make a healing pass down each side of the tree.
1891 bt_split_heal(bt1
, TRUE
);
1892 bt_split_heal(bt2
, FALSE
);
1901 * Split a tree at a numeric index.
1903 btree
*bt_splitpos(btree
*bt
, int index
, int before
)
1910 n
= bt_read_lock_root(bt
);
1911 count
= (n ?
bt_node_count(bt
, n
) : 0);
1912 bt_read_unlock(bt
, n
);
1914 if (index
< 0 || index
> count
)
1917 ret
= bt_split_internal(bt
, index
);
1920 bt
->root
= ret
->root
;
1924 bt
->depth
= ret
->depth
;
1931 * Split a tree at a position dictated by the sorting order.
1933 btree
*bt_split(btree
*bt
, bt_element_t element
, cmpfn_t cmp
, int rel
)
1937 assert(rel
!= BT_REL_EQ
); /* has to be an inequality */
1939 if (rel
== BT_REL_GT
|| rel
== BT_REL_GE
) {
1941 rel
= (rel
== BT_REL_GT ? BT_REL_LE
: BT_REL_LT
);
1945 if (!bt_findrelpos(bt
, element
, cmp
, rel
, &index
))
1947 return bt_splitpos(bt
, index
+1, before
);
1952 #define TEST_DEGREE 4
1953 #define BT_COPY bt_clone
1954 #define MAXTREESIZE 10000
1955 #define MAXLOCKS 100
1960 * Error reporting function.
1962 void error(char *fmt
, ...) {
1964 fprintf(stderr
, "ERROR: ");
1966 vfprintf(stderr
, fmt
, ap
);
1968 fprintf(stderr
, "\n");
1973 * See if a tree has a 2-element root node.
1975 static int bt_tworoot(btree
*bt
)
1979 n
= bt_read_lock_root(bt
);
1980 i
= bt_subtrees(bt
, n
);
1981 bt_read_unlock(bt
, n
);
1982 return (i
== 2 ? TRUE
: FALSE
);
1986 * Physically copy an entire B-tree. (NB this appears as a test
1987 * routine rather than a production one, since reference counting
1988 * and bt_clone() provide a better way to do this for real code. If
1989 * anyone really needs a genuine physical copy for anything other
1990 * than testing reasons, I suppose they could always lift this into
1991 * the admin section above.)
1994 static nodeptr
bt_copy_node(btree
*bt
, nodeptr n
)
1999 children
= bt_subtrees(bt
, n
);
2000 ret
= bt_new_node(bt
, children
);
2002 for (i
= 0; i
< children
; i
++) {
2003 nodeptr n2
= bt_read_lock_child(bt
, n
, i
);
2006 n3
= bt_copy_node(bt
, n2
);
2007 bt_set_child(bt
, ret
, i
, bt_write_unlock(bt
, n3
));
2009 bt_set_child(bt
, ret
, i
, NODE_ADDR_NULL
);
2011 bt_read_unlock(bt
, n2
);
2013 if (i
< children
-1) {
2014 bt_element_t e
= bt_element(bt
, n
, i
);
2016 e
= bt
->copy(bt
->userstate
, e
);
2017 bt_set_element(bt
, ret
, i
, e
);
2024 btree
*bt_copy(btree
*bt
)
2029 bt2
= bt_new(bt
->cmp
, bt
->copy
, bt
->freeelt
, bt
->propsize
, bt
->propalign
,
2030 bt
->propmake
, bt
->propmerge
, bt
->userstate
, bt
->mindegree
);
2031 bt2
->depth
= bt
->depth
;
2033 n
= bt_read_lock_root(bt
);
2035 bt2
->root
= bt_write_unlock(bt2
, bt_copy_node(bt
, n
));
2036 bt_read_unlock(bt
, n
);
2042 * This function is intended to be called from gdb when debugging
2045 void bt_dump_nodes(btree
*bt
, ...)
2053 n
= va_arg(ap
, nodeptr
);
2056 printf("%p [%d]:", n
, n
[bt
->maxdegree
*2+1].i
);
2057 children
= bt_subtrees(bt
, n
);
2058 for (i
= 0; i
< children
; i
++) {
2059 printf(" %p", bt_child(bt
, n
, i
).p
);
2061 printf(" %s", (char *)bt_element(bt
, n
, i
));
2069 * Verify a tree against an array. Checks that:
2071 * - every node has a valid number of subtrees
2072 * - subtrees are either all present (internal node) or all absent
2074 * - elements are all present
2075 * - every leaf is at exactly the depth claimed by the tree
2076 * - the tree represents the correct list of elements in the
2077 * correct order. (This also tests the ordering constraint,
2078 * assuming the array is correctly constructed.)
2081 void verifynode(btree
*bt
, nodeptr n
, bt_element_t
*array
, int *arraypos
,
2084 int subtrees
, min
, max
, i
, before
, after
, count
;
2086 /* Check the subtree count. The root can have as few as 2 subtrees. */
2087 subtrees
= bt_subtrees(bt
, n
);
2088 max
= bt_max_subtrees(bt
);
2089 min
= (depth
== 1) ?
2 : bt_min_subtrees(bt
);
2091 error("node %p has too many subtrees (%d > %d)", n
, subtrees
, max
);
2093 error("node %p has too few subtrees (%d < %d)", n
, subtrees
, min
);
2095 /* Check that subtrees are present or absent as required. */
2096 for (i
= 0; i
< subtrees
; i
++) {
2097 node_addr child
= bt_child(bt
, n
, i
);
2098 if (depth
== bt
->depth
&& child
.p
!= NULL
)
2099 error("leaf node %p child %d is %p not NULL\n", n
, i
, child
);
2100 if (depth
!= bt
->depth
&& child
.p
== NULL
)
2101 error("non-leaf node %p child %d is NULL\n", n
, i
);
2104 /* Check that elements are all present. */
2105 for (i
= 0; i
< subtrees
-1; i
++) {
2106 bt_element_t elt
= bt_element(bt
, n
, i
);
2108 error("node %p element %d is NULL\n", n
, i
);
2113 /* Now verify the subtrees, and simultaneously check the ordering. */
2114 for (i
= 0; i
< subtrees
; i
++) {
2115 if (depth
< bt
->depth
) {
2116 nodeptr child
= bt_read_lock_child(bt
, n
, i
);
2117 verifynode(bt
, child
, array
, arraypos
, depth
+1);
2118 bt_read_unlock(bt
, child
);
2120 if (i
< subtrees
-1) {
2121 bt_element_t elt
= bt_element(bt
, n
, i
);
2122 if (array
[*arraypos
] != elt
) {
2123 error("node %p element %d is \"%s\", but array[%d]=\"%s\"",
2124 n
, i
, elt
, *arraypos
, array
[*arraypos
]);
2132 /* Check the node count. */
2133 count
= bt_node_count(bt
, n
);
2134 if (count
!= after
- before
)
2135 error("node %p count is %d, should be %d", n
, count
, after
- before
);
2138 * Check the user properties.
2141 nodecomponent
*prop
;
2143 int max
= 0, total
= 0;
2145 prop
= n
+ bt
->maxdegree
* 2 + 2;
2147 for (i
= before
; i
< after
; i
++) {
2148 int c
= (unsigned char)*(char *)array
[i
];
2150 if (max
< c
) max
= c
;
2154 if (prop
[0].i
!= total
)
2155 error("node %p total prop is %d, should be %d", n
,
2157 if (prop
[1].i
!= max
)
2158 error("node %p max prop is %d, should be %d", n
,
2163 void verifytree(btree
*bt
, bt_element_t
*array
, int arraylen
)
2167 n
= bt_read_lock_root(bt
);
2169 verifynode(bt
, n
, array
, &i
, 1);
2170 bt_read_unlock(bt
, n
);
2172 if (bt
->depth
!= 0) {
2173 error("tree has null root but depth is %d not zero", bt
->depth
);
2177 error("tree contains %d elements, array contains %d",
2179 testlock(-1, 0, NULL
);
2182 int mycmp(void *state
, void *av
, void *bv
) {
2183 char const *a
= (char const *)av
;
2184 char const *b
= (char const *)bv
;
2185 return strcmp(a
, b
);
2188 static void set_invalid_property(void *propv
)
2190 int *prop
= (int *)propv
;
2191 prop
[0] = prop
[1] = -1;
2194 void mypropmake(void *state
, void *av
, void *destv
)
2196 char const *a
= (char const *)av
;
2197 int *dest
= (int *)destv
;
2198 dest
[0] = dest
[1] = (unsigned char)*a
;
2201 void mypropmerge(void *state
, void *s1v
, void *s2v
, void *destv
)
2203 int *s1
= (int *)s1v
;
2204 int *s2
= (int *)s2v
;
2205 int *dest
= (int *)destv
;
2207 /* Special `destroy' case. */
2208 set_invalid_property(destv
);
2211 assert(s2
[0] >= 0 && s2
[1] >= 0);
2212 assert(s1
== NULL
|| (s1
[0] >= 0 && s1
[1] >= 0));
2213 dest
[0] = s2
[0] + (s1 ? s1
[0] : 0);
2214 dest
[1] = (s1
&& s1
[1] > s2
[1] ? s1
[1] : s2
[1]);
2217 void array_addpos(bt_element_t
*array
, int *arraylen
, bt_element_t e
, int i
)
2220 int len
= *arraylen
;
2222 assert(len
< MAXTREESIZE
);
2234 void array_add(bt_element_t
*array
, int *arraylen
, bt_element_t e
)
2237 int len
= *arraylen
;
2239 for (i
= 0; i
< len
; i
++)
2240 if (mycmp(NULL
, array
[i
], e
) >= 0)
2242 assert(i
== len
|| mycmp(NULL
, array
[i
], e
) != 0);
2243 array_addpos(array
, arraylen
, e
, i
);
2246 void array_delpos(bt_element_t
*array
, int *arraylen
, int i
)
2248 int len
= *arraylen
;
2251 array
[i
] = array
[i
+1];
2257 bt_element_t
array_del(bt_element_t
*array
, int *arraylen
, bt_element_t e
)
2260 int len
= *arraylen
;
2263 for (i
= 0; i
< len
; i
++)
2264 if (mycmp(NULL
, array
[i
], e
) >= 0)
2266 if (i
< len
&& mycmp(NULL
, array
[i
], e
) == 0) {
2268 array_delpos(array
, arraylen
, i
);
2274 /* A sample data set and test utility. Designed for pseudo-randomness,
2275 * and yet repeatability. */
2278 * This random number generator uses the `portable implementation'
2279 * given in ANSI C99 draft N869. It assumes `unsigned' is 32 bits;
2282 int randomnumber(unsigned *seed
) {
2283 *seed
*= 1103515245;
2285 return ((*seed
) / 65536) % 32768;
2288 #define lenof(x) ( sizeof((x)) / sizeof(*(x)) )
2291 "0", "2", "3", "I", "K", "d", "H", "J", "Q", "N", "n", "q", "j", "i",
2292 "7", "G", "F", "D", "b", "x", "g", "B", "e", "v", "V", "T", "f", "E",
2293 "S", "8", "A", "k", "X", "p", "C", "R", "a", "o", "r", "O", "Z", "u",
2294 "6", "1", "w", "L", "P", "M", "c", "U", "h", "9", "t", "5", "W", "Y",
2298 #define NSTR lenof(strings)
2300 void findtest(btree
*tree
, bt_element_t
*array
, int arraylen
)
2302 static const int rels
[] = {
2303 BT_REL_EQ
, BT_REL_GE
, BT_REL_LE
, BT_REL_LT
, BT_REL_GT
2305 static const char *const relnames
[] = {
2306 "EQ", "GE", "LE", "LT", "GT"
2308 int i
, j
, rel
, index
;
2309 char *p
, *ret
, *realret
, *realret2
;
2312 for (i
= 0; i
< (int)NSTR
; i
++) {
2314 for (j
= 0; j
< (int)(sizeof(rels
)/sizeof(*rels
)); j
++) {
2317 lo
= 0; hi
= arraylen
-1;
2319 mid
= (lo
+ hi
) / 2;
2320 c
= strcmp(p
, array
[mid
]);
2330 if (rel
== BT_REL_LT
)
2331 ret
= (mid
> 0 ? array
[--mid
] : NULL
);
2332 else if (rel
== BT_REL_GT
)
2333 ret
= (mid
< arraylen
-1 ? array
[++mid
] : NULL
);
2338 if (rel
== BT_REL_LT
|| rel
== BT_REL_LE
) {
2340 ret
= (hi
>= 0 ? array
[hi
] : NULL
);
2341 } else if (rel
== BT_REL_GT
|| rel
== BT_REL_GE
) {
2343 ret
= (lo
< arraylen ? array
[lo
] : NULL
);
2348 realret
= bt_findrelpos(tree
, p
, NULL
, rel
, &index
);
2349 testlock(-1, 0, NULL
);
2350 if (realret
!= ret
) {
2351 error("find(\"%s\",%s) gave %s should be %s",
2352 p
, relnames
[j
], realret
, ret
);
2354 if (realret
&& index
!= mid
) {
2355 error("find(\"%s\",%s) gave %d should be %d",
2356 p
, relnames
[j
], index
, mid
);
2358 if (realret
&& rel
== BT_REL_EQ
) {
2359 realret2
= bt_index(tree
, index
);
2360 if (realret2
!= realret
) {
2361 error("find(\"%s\",%s) gave %s(%d) but %d -> %s",
2362 p
, relnames
[j
], realret
, index
, index
, realret2
);
2368 realret
= bt_findrelpos(tree
, NULL
, NULL
, BT_REL_GT
, &index
);
2369 testlock(-1, 0, NULL
);
2370 if (arraylen
&& (realret
!= array
[0] || index
!= 0)) {
2371 error("find(NULL,GT) gave %s(%d) should be %s(0)",
2372 realret
, index
, array
[0]);
2373 } else if (!arraylen
&& (realret
!= NULL
)) {
2374 error("find(NULL,GT) gave %s(%d) should be NULL",
2378 realret
= bt_findrelpos(tree
, NULL
, NULL
, BT_REL_LT
, &index
);
2379 testlock(-1, 0, NULL
);
2380 if (arraylen
&& (realret
!= array
[arraylen
-1] || index
!= arraylen
-1)) {
2381 error("find(NULL,LT) gave %s(%d) should be %s(0)",
2382 realret
, index
, array
[arraylen
-1]);
2383 } else if (!arraylen
&& (realret
!= NULL
)) {
2384 error("find(NULL,LT) gave %s(%d) should be NULL",
2389 void splittest(btree
*tree
, bt_element_t
*array
, int arraylen
)
2392 btree
*tree3
, *tree4
;
2393 for (i
= 0; i
<= arraylen
; i
++) {
2394 printf("splittest: %d\n", i
);
2395 tree3
= BT_COPY(tree
);
2396 testlock(-1, 0, NULL
);
2397 tree4
= bt_splitpos(tree3
, i
, 0);
2398 testlock(-1, 0, NULL
);
2399 verifytree(tree3
, array
, i
);
2400 verifytree(tree4
, array
+i
, arraylen
-i
);
2401 bt_join(tree3
, tree4
);
2402 testlock(-1, 0, NULL
);
2403 verifytree(tree4
, NULL
, 0);
2404 bt_free(tree4
); /* left empty by join */
2405 testlock(-1, 0, NULL
);
2406 verifytree(tree3
, array
, arraylen
);
2408 testlock(-1, 0, NULL
);
2413 * Called to track read and write locks on nodes.
2415 void testlock(int write
, int set
, nodeptr n
)
2417 static nodeptr readlocks
[MAXLOCKS
], writelocks
[MAXLOCKS
];
2418 static int nreadlocks
= 0, nwritelocks
= 0;
2423 /* Called after an operation to ensure all locks are unlocked. */
2424 if (nreadlocks
!= 0 || nwritelocks
!= 0)
2425 error("at least one left-behind lock exists!");
2429 /* Locking NULL does nothing. Unlocking it is an error. */
2432 error("attempting to %s-unlock NULL", write ?
"write" : "read");
2436 assert(nreadlocks
< MAXLOCKS
&& nwritelocks
< MAXLOCKS
);
2438 /* First look for the node in both lock lists. */
2440 for (i
= 0; i
< nreadlocks
; i
++)
2441 if (readlocks
[i
] == n
)
2443 for (i
= 0; i
< nwritelocks
; i
++)
2444 if (writelocks
[i
] == n
)
2447 /* Now diverge based on what we're supposed to be up to. */
2449 /* Setting a lock. Should not already be locked in either list. */
2450 if (rp
!= -1 || wp
!= -1) {
2451 error("attempt to %s-lock node %p, already %s-locked",
2452 (write ?
"write" : "read"), n
, (rp
==-1 ?
"write" : "read"));
2455 writelocks
[nwritelocks
++] = n
;
2457 readlocks
[nreadlocks
++] = n
;
2459 /* Clearing a lock. Should exist in exactly the correct list. */
2460 if (write
&& rp
!= -1)
2461 error("attempt to write-unlock node %p which is read-locked", n
);
2462 if (!write
&& wp
!= -1)
2463 error("attempt to read-unlock node %p which is write-locked", n
);
2466 for (i
= wp
; i
< nwritelocks
; i
++)
2467 writelocks
[i
] = writelocks
[i
+1];
2471 for (i
= rp
; i
< nreadlocks
; i
++)
2472 readlocks
[i
] = readlocks
[i
+1];
2480 int tworoot
, tmplen
;
2482 bt_element_t
*array
;
2484 bt_element_t ret
, ret2
, item
;
2485 btree
*tree
, *tree2
, *tree3
, *tree4
;
2487 setvbuf(stdout
, NULL
, _IOLBF
, 0);
2488 setvbuf(stderr
, NULL
, _IOLBF
, 0);
2491 for (i
= 0; i
< (int)NSTR
; i
++) in
[i
] = 0;
2492 array
= newn(bt_element_t
, MAXTREESIZE
);
2494 tree
= bt_new(mycmp
, NULL
, NULL
, 2*sizeof(int), alignof(int),
2495 mypropmake
, mypropmerge
, NULL
, TEST_DEGREE
);
2497 verifytree(tree
, array
, arraylen
);
2498 for (i
= 0; i
< 10000; i
++) {
2499 j
= randomnumber(&seed
);
2501 printf("trial: %d\n", i
);
2503 printf("deleting %s (%d)\n", strings
[j
], j
);
2504 ret2
= array_del(array
, &arraylen
, strings
[j
]);
2505 ret
= bt_del(tree
, strings
[j
]);
2506 testlock(-1, 0, NULL
);
2507 assert((bt_element_t
)strings
[j
] == ret
&& ret
== ret2
);
2508 verifytree(tree
, array
, arraylen
);
2511 printf("adding %s (%d)\n", strings
[j
], j
);
2512 array_add(array
, &arraylen
, strings
[j
]);
2513 ret
= bt_add(tree
, strings
[j
]);
2514 testlock(-1, 0, NULL
);
2515 assert(strings
[j
] == ret
);
2516 verifytree(tree
, array
, arraylen
);
2519 /* disptree(tree); */
2520 findtest(tree
, array
, arraylen
);
2523 while (arraylen
> 0) {
2524 j
= randomnumber(&seed
);
2527 ret2
= array_del(array
, &arraylen
, item
);
2528 ret
= bt_del(tree
, item
);
2529 testlock(-1, 0, NULL
);
2530 assert(ret2
== ret
);
2531 verifytree(tree
, array
, arraylen
);
2535 testlock(-1, 0, NULL
);
2538 * Now try an unsorted tree. We don't really need to test
2539 * delpos because we know del is based on it, so it's already
2540 * been tested in the above sorted-tree code; but for
2541 * completeness we'll use it to tear down our unsorted tree
2542 * once we've built it.
2544 tree
= bt_new(NULL
, NULL
, NULL
, 2*sizeof(int), alignof(int),
2545 mypropmake
, mypropmerge
, NULL
, TEST_DEGREE
);
2546 verifytree(tree
, array
, arraylen
);
2547 for (i
= 0; i
< 1000; i
++) {
2548 printf("trial: %d\n", i
);
2549 j
= randomnumber(&seed
);
2551 k
= randomnumber(&seed
);
2552 k
%= bt_count(tree
)+1;
2553 testlock(-1, 0, NULL
);
2554 printf("adding string %s at index %d\n", strings
[j
], k
);
2555 array_addpos(array
, &arraylen
, strings
[j
], k
);
2556 bt_addpos(tree
, strings
[j
], k
);
2557 testlock(-1, 0, NULL
);
2558 verifytree(tree
, array
, arraylen
);
2562 * While we have this tree in its full form, we'll take a copy
2563 * of it to use in split and join testing.
2565 tree2
= BT_COPY(tree
);
2566 testlock(-1, 0, NULL
);
2567 verifytree(tree2
, array
, arraylen
);/* check the copy is accurate */
2569 * Split tests. Split the tree at every possible point and
2570 * check the resulting subtrees.
2572 tworoot
= bt_tworoot(tree2
); /* see if it has a 2-root */
2573 testlock(-1, 0, NULL
);
2574 splittest(tree2
, array
, arraylen
);
2576 * Now do the split test again, but on a tree that has a 2-root
2577 * (if the previous one didn't) or doesn't (if the previous one
2581 while (bt_tworoot(tree2
) == tworoot
) {
2582 bt_delpos(tree2
, --tmplen
);
2583 testlock(-1, 0, NULL
);
2585 printf("now trying splits on second tree\n");
2586 splittest(tree2
, array
, tmplen
);
2588 testlock(-1, 0, NULL
);
2591 * Back to the main testing of uncounted trees.
2593 while (bt_count(tree
) > 0) {
2594 printf("cleanup: tree size %d\n", bt_count(tree
));
2595 j
= randomnumber(&seed
);
2596 j
%= bt_count(tree
);
2597 printf("deleting string %s from index %d\n", (char *)array
[j
], j
);
2598 ret
= bt_delpos(tree
, j
);
2599 testlock(-1, 0, NULL
);
2600 assert((bt_element_t
)array
[j
] == ret
);
2601 array_delpos(array
, &arraylen
, j
);
2602 verifytree(tree
, array
, arraylen
);
2605 testlock(-1, 0, NULL
);
2608 * Finally, do some testing on split/join on _sorted_ trees. At
2609 * the same time, we'll be testing split on very small trees.
2611 tree
= bt_new(mycmp
, NULL
, NULL
, 2*sizeof(int), alignof(int),
2612 mypropmake
, mypropmerge
, NULL
, TEST_DEGREE
);
2614 for (i
= 0; i
< 16; i
++) {
2615 array_add(array
, &arraylen
, strings
[i
]);
2616 ret
= bt_add(tree
, strings
[i
]);
2617 testlock(-1, 0, NULL
);
2618 assert(strings
[i
] == ret
);
2619 verifytree(tree
, array
, arraylen
);
2620 tree2
= BT_COPY(tree
);
2621 splittest(tree2
, array
, arraylen
);
2622 testlock(-1, 0, NULL
);
2624 testlock(-1, 0, NULL
);
2627 testlock(-1, 0, NULL
);
2630 * Test silly cases of join: join(emptytree, emptytree), and
2631 * also ensure join correctly spots when sorted trees fail the
2632 * ordering constraint.
2634 tree
= bt_new(mycmp
, NULL
, NULL
, 2*sizeof(int), alignof(int),
2635 mypropmake
, mypropmerge
, NULL
, TEST_DEGREE
);
2636 tree2
= bt_new(mycmp
, NULL
, NULL
, 2*sizeof(int), alignof(int),
2637 mypropmake
, mypropmerge
, NULL
, TEST_DEGREE
);
2638 tree3
= bt_new(mycmp
, NULL
, NULL
, 2*sizeof(int), alignof(int),
2639 mypropmake
, mypropmerge
, NULL
, TEST_DEGREE
);
2640 tree4
= bt_new(mycmp
, NULL
, NULL
, 2*sizeof(int), alignof(int),
2641 mypropmake
, mypropmerge
, NULL
, TEST_DEGREE
);
2642 assert(mycmp(NULL
, strings
[0], strings
[1]) < 0); /* just in case :-) */
2643 bt_add(tree2
, strings
[1]);
2644 testlock(-1, 0, NULL
);
2645 bt_add(tree4
, strings
[0]);
2646 testlock(-1, 0, NULL
);
2647 array
[0] = strings
[0];
2648 array
[1] = strings
[1];
2649 verifytree(tree
, array
, 0);
2650 verifytree(tree2
, array
+1, 1);
2651 verifytree(tree3
, array
, 0);
2652 verifytree(tree4
, array
, 1);
2656 * - join(tree,tree3) should leave both tree and tree3 unchanged.
2657 * - joinr(tree,tree2) should leave both tree and tree2 unchanged.
2658 * - join(tree4,tree3) should leave both tree3 and tree4 unchanged.
2659 * - join(tree, tree2) should move the element from tree2 to tree.
2660 * - joinr(tree4, tree3) should move the element from tree4 to tree3.
2661 * - join(tree,tree3) should return NULL and leave both unchanged.
2662 * - join(tree3,tree) should work and create a bigger tree in tree3.
2664 assert(tree
== bt_join(tree
, tree3
));
2665 testlock(-1, 0, NULL
);
2666 verifytree(tree
, array
, 0);
2667 verifytree(tree3
, array
, 0);
2668 assert(tree2
== bt_joinr(tree
, tree2
));
2669 testlock(-1, 0, NULL
);
2670 verifytree(tree
, array
, 0);
2671 verifytree(tree2
, array
+1, 1);
2672 assert(tree4
== bt_join(tree4
, tree3
));
2673 testlock(-1, 0, NULL
);
2674 verifytree(tree3
, array
, 0);
2675 verifytree(tree4
, array
, 1);
2676 assert(tree
== bt_join(tree
, tree2
));
2677 testlock(-1, 0, NULL
);
2678 verifytree(tree
, array
+1, 1);
2679 verifytree(tree2
, array
, 0);
2680 assert(tree3
== bt_joinr(tree4
, tree3
));
2681 testlock(-1, 0, NULL
);
2682 verifytree(tree3
, array
, 1);
2683 verifytree(tree4
, array
, 0);
2684 assert(NULL
== bt_join(tree
, tree3
));
2685 testlock(-1, 0, NULL
);
2686 verifytree(tree
, array
+1, 1);
2687 verifytree(tree3
, array
, 1);
2688 assert(tree3
== bt_join(tree3
, tree
));
2689 testlock(-1, 0, NULL
);
2690 verifytree(tree3
, array
, 2);
2691 verifytree(tree
, array
, 0);
2694 testlock(-1, 0, NULL
);
2696 testlock(-1, 0, NULL
);
2698 testlock(-1, 0, NULL
);
2700 testlock(-1, 0, NULL
);
2705 fprintf(stderr
, "%d errors!\n", errors
);
2706 return (errors
!= 0 ?
1 : 0);