1/*
2 * Copyright 1997-1999, 2001 John-Mark Gurney.
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 * notice, this list of conditions and the following disclaimer in the
12 * documentation and/or other materials provided with the distribution.
13 */
14
15#include <assert.h>
16#include <limits.h>
17#include <stdlib.h>
18#include <stdio.h>
19#include <string.h>
20#include <strings.h>
21
22#include "bt.h"
23#include "bt_iterator.h"
24#include "stream.h"
25
26#include <citrusleaf/alloc.h>
27
28/* CACHE TODO LIST
29 8.) U128PK/FK CACHE:[EVICT,MISS] support
30
31 11.) DS as stream -\/
32 7.) DS in rdbSave/Load (dependency on 11)
33
34 12.) slab allocator for ALL btn's
35
36 14.) btFind() in setUniqIndexVal() -> btFindD() + TESTING
37
38 18.) CREATE TABLE () DIRTY
39
40 19.) btreesplitchild dirty math (only set dirty if new split child has dirty)
41*/
42
43// DEBUG DEBUG DEBUG DEBUG DEBUG DEBUG DEBUG DEBUG DEBUG DEBUG DEBUG
44
45//#define DEBUG_DEL_CASE_STATS
46//#define BT_MEM_PROFILE
47#ifdef BT_MEM_PROFILE
48static ulong tot_bt_data = 0; static ulong tot_bt_data_mem = 0;
49static ulong tot_num_bt_ns = 0; static ulong tnbtnmem = 0;
50static ulong tot_num_bts = 0; static ulong tot_num_bt_mem = 0;
51 #define BT_MEM_PROFILE_BT {tot_num_bts++; tot_num_bt_mem += size;}
52 #define BT_MEM_PROFILE_NODE {tot_num_bt_ns++; tnbtnmem += size;}
53#else
54 #define BT_MEM_PROFILE_BT
55 #define BT_MEM_PROFILE_NODE
56#endif
57
58/* PROTOYPES */
59static void release_dirty_stream(bt *btr, bt_n *x);
60static int real_log2 (unsigned int a, int nbits);
61static bt_data_t findminkey (bt *btr, bt_n *x);
62static bt_data_t findmaxkey (bt *btr, bt_n *x);
63
64// HELPER HELPER HELPER HELPER HELPER HELPER HELPER HELPER HELPER HELPER
65static ulong getNumKey(bt *btr, bt_n *x, int i) { //TODO U128 support
66 if (i < 0 || i >= x->n) return 0;
67 else {
68 ai_obj akey; void *be = KEYS(btr, x, i);
69 convertStream2Key(be, &akey, btr);
70 return akey.l;
71 }
72}
73
74// MEMORY_MANAGEMENT MEMORY_MANAGEMENT MEMORY_MANAGEMENT MEMORY_MANAGEMENT
75/* NOTE used-memory bookkeeping maintained at the Btree level */
76static void bt_increment_used_memory(bt *btr, size_t size) { //DEBUG_INCR_MEM
77 btr->msize += (ull)size;
78}
79static void bt_decrement_used_memory(bt *btr, size_t size) { //DEBUG_DECR_MEM
80 btr->msize -= (ull)size;
81}
82// DIRTY_STREAM DIRTY_STREAM DIRTY_STREAM DIRTY_STREAM DIRTY_STREAM
83static uint32 get_dssize(bt *btr, char dirty) {
84 assert(dirty > 0);
85 uint32 drsize = (dirty == 3) ? sizeof(uint32) :
86 (dirty == 2) ? sizeof(ushort16) : sizeof(uchar); // 1
87 //DEBUG_GETDSSIZE
88 return (btr->t * 2) * drsize;
89}
90static void alloc_ds(bt *btr, bt_n *x, size_t size, char dirty) {
91 assert(dirty != -1);
92 void **dsp = (void *)((char *)x + size);
93 if (!dirty) { *dsp = NULL; return; }
94 size_t dssize = get_dssize(btr, dirty);
95 void *ds = cf_malloc(dssize); bzero(ds, dssize); // FREEME 108
96 bt_increment_used_memory(btr, dssize);
97 *dsp = ds; //DEBUG_ALLOC_DS
98}
99void incr_ds(bt *btr, bt_n *x) {//USE: when a DR is too big for its DS (incr_ds)
100 assert(x->dirty > 0);
101 GET_BTN_SIZE(x->leaf)
102 void *ods = GET_DS(x, nsize);
103 uint32 osize = get_dssize(btr, x->dirty);
104 uint32 num = (x->leaf ? (btr->t * 2) : btr->t); //DEBUG_RESIZE_DS_1
105 alloc_ds(btr, x, nsize, x->dirty + 1);
106 void *nds = GET_DS(x, nsize);
107 if (x->dirty == 1) {
108 uchar *s_ds = (uchar *)ods; ushort16 *d_ds = (ushort16 *)nds;
109 for (uint32 i = 0; i < num; i++) d_ds[i] = (ushort16)s_ds[i];
110 } else if (x->dirty == 2) {
111 ushort16 *s_ds = (ushort16 *)ods; uint32 *d_ds = (uint32 *)nds;
112 for (uint32 i = 0; i < num; i++) d_ds[i] = (uint32 )s_ds[i];
113 } else assert(!"incr_ds ERROR");
114 x->dirty++; //DEBUG_RESIZE_DS_2
115 cf_free(ods); bt_decrement_used_memory(btr, osize);
116}
117
118// BT_ALLOC_BTREE BT_ALLOC_BTREE BT_ALLOC_BTREE BT_ALLOC_BTREE BT_ALLOC_BTREE
119// BT_ALLOC_BTREE BT_ALLOC_BTREE BT_ALLOC_BTREE BT_ALLOC_BTREE BT_ALLOC_BTREE
120static bt_n *allocbtreenode(bt *btr, bool leaf, char dirty) {
121 btr->numnodes++;
122 GET_BTN_SIZES(leaf, dirty) BT_MEM_PROFILE_NODE //DEBUG_ALLOC_BTN
123 bt_n *x = cf_malloc(msize); bzero(x, msize);
124 bt_increment_used_memory(btr, msize);
125 x->leaf = -1;
126 x->dirty = dirty;
127 if (dirty != -1) alloc_ds(btr, x, nsize, dirty);
128 return x;
129}
130static bt *allocbtree() {
131 int size = sizeof(struct btree);
132 BT_MEM_PROFILE_BT
133 bt *btr = (bt *) cf_malloc(size); bzero(btr, size); // FREE ME 035
134 bt_increment_used_memory(btr, size); //DEBUG_ALLOC_BTREE
135 return btr;
136}
137
138static void release_dirty_stream(bt *btr, bt_n *x) { //DEBUG_BTF_BTN_DIRTY
139 assert(x->dirty > 0);
140 GET_BTN_SIZE(x->leaf)
141 bt_decrement_used_memory(btr, get_dssize(btr, x->dirty));
142 void **dsp = GET_DS(x, nsize); cf_free(dsp); // FREED 108
143 x->dirty = 0;
144}
145static void bt_free_btreenode(bt *btr, bt_n *x) {
146 GET_BTN_SIZES(x->leaf, x->dirty) bt_decrement_used_memory(btr, msize);
147 if (x->dirty > 0) release_dirty_stream(btr, x);
148 cf_free(x); // FREED 035
149}
150static void bt_free_btree(bt *btr) { cf_free(btr); }
151
152// BT_CREATE BT_CREATE BT_CREATE BT_CREATE BT_CREATE BT_CREATE BT_CREATE
153bt *bt_create(bt_cmp_t cmp, bts_t *s, char dirty) {
154 int n = BTREE_LONG_TYPE_DEGREE;
155
156 if (C_IS_L(s->ktype) || C_IS_G(s->ktype)) {
157 n = BTREE_LONG_TYPE_DEGREE;
158 }
159 else if (C_IS_DG(s->ktype)) {
160 n = BTREE_STRING_TYPE_DEGREE;
161 }
162
163 uchar t = (uchar)((int)(n + 1) / 2);
164 int kbyte = sizeof(bt_n) + n * s->ksize;
165 int nbyte = kbyte + (n + 1) * VOIDSIZE;
166 bt *btr = allocbtree();
167 if (!btr) return NULL;
168 memcpy(&btr->s, s, sizeof(bts_t)); /* ktype, btype, ksize, bflag, num */
169 btr->cmp = cmp;
170 btr->keyofst = sizeof(bt_n);
171 uint32 nodeofst = btr->keyofst + n * s->ksize;
172 btr->nodeofst = (ushort16)nodeofst;
173 btr->t = t;
174 int nbits = real_log2(n, sizeof(int) * 8) + 1;
175 nbits = 1 << (real_log2(nbits, sizeof(int) * 8) + 1);
176 btr->nbits = (uchar)nbits;
177 btr->nbyte = nbyte;
178 btr->kbyte = kbyte;
179 btr->dirty = dirty;
180 btr->root = allocbtreenode(btr, 1, dirty ? 0: -1);
181 if (!btr->root) return NULL;
182 btr->numnodes = 1; //printf("bt_create\n"); bt_dump_info(printf, btr);
183 return btr;
184}
185
186// BINARY_SEARCH BINARY_SEARCH BINARY_SEARCH BINARY_SEARCH BINARY_SEARCH
187/* This is the real log2 function. It is only called when we don't have
188 * a value in the table. -> which is basically never */
189static inline int real_log2(unsigned int a, int nbits) {
190 uint32 i = 0;
191 uint32 b = (nbits + 1) / 2; /* divide in half rounding up */
192 while (b) {
193 i = (i << 1);
194 if (a >= (unsigned int)(1 << b)) { // select top half and mark this bit
195 a /= (1 << b);
196 i = i | 1;
197 } else { // select bottom half & dont set bit
198 a &= (1 << b) - 1;
199 }
200 b /= 2;
201 }
202 return i;
203}
204
205#if 0
206
207// TODO: global table is pain disabled for avoiding issue
208// open it up later
209/* Implement a lookup table for the log values. This will only allocate
210 * memory that we need. This is much faster than calling the log2 routine
211 * every time. Doing 1 million insert, searches, and deletes will generate
212 * ~58 million calls to log2. Using a lookup table IS NECESSARY!
213 -> memory usage of this is trivial, like less than 1KB */
214static inline int _log2(unsigned int a, int nbits) {
215 static char *table = NULL;
216 static uint32 alloced = 0;
217 uint32 i;
218 if (a >= alloced) {
219 table = cf_realloc(table, (a + 1) * sizeof *table);
220 for (i = alloced; i < a + 1; i++) table[i] = -1;
221 alloced = a + 1;
222 }
223 if (table[a] == -1) table[a] = real_log2(a, nbits);
224 return table[a];
225}
226#endif
227
228static inline int _log2(unsigned int a, int nbits) {
229 return real_log2(a, nbits);
230}
231
232static int findkindex(bt *btr, bt_n *x, bt_data_t k, int *r, btIterator *iter) {
233 if (x->n == 0) return -1;
234 int b, tr;
235 int *rr = r ? r : &tr ; /* rr: key is greater than current entry */
236 int i = 0;
237 int a = x->n - 1;
238 while (a > 0) {
239 b = _log2(a, (int)btr->nbits);
240 int slot = (1 << b) + i;
241 bt_data_t k2 = KEYS(btr, x, slot);
242 if ((*rr = btr->cmp(k, k2)) < 0) {
243 a = (1 << b) - 1;
244 } else {
245 a -= (1 << b);
246 i |= (1 << b);
247 }
248 }
249 if ((*rr = btr->cmp(k, KEYS(btr, x, i))) < 0) i--;
250 if (iter) { iter->bln->in = iter->bln->ik = (i > 0) ? i : 0; }
251 return i;
252}
253
254// KEY_SHUFFLING KEY_SHUFFLING KEY_SHUFFLING KEY_SHUFFLING KEY_SHUFFLING
255// NOTE: KEYS are variable sizes: [4,8,12,16,20,24,32 bytes]
256#define ISVOID(btr) (btr->s.ksize == VOIDSIZE)
257
258static inline void **AKEYS(bt *btr, bt_n *x, int i) {
259 int ofst = (i * btr->s.ksize);
260 char *v = (char *)x + btr->keyofst + ofst; //DEBUG_AKEYS
261 return (void **)v;
262}
263#define OKEYS(btr, x) ((void **)((char *)x + btr->keyofst))
264inline void *KEYS(bt *btr, bt_n *x, int i) { //DEBUG_KEYS
265 if ISVOID(btr) return OKEYS(btr, x)[i];
266 else /* OTHER_BT */ return (void *) AKEYS(btr, x, i);
267}
268
269// SCION SCION SCION SCION SCION SCION SCION SCION SCION SCION SCION SCION
270static inline void incr_scion(bt_n *x, int n) { x->scion += n; }
271static inline void decr_scion(bt_n *x, int n) { x->scion -= n; }
272static inline void move_scion(bt *btr, bt_n *y, bt_n *z, int n) {
273 for (int i = 0; i < n; i++) { incr_scion(y, NODES(btr, z)[i]->scion); }
274}
275static inline int get_scion_range(bt *btr, bt_n *x, int beg, int end) {
276 if (x->dirty <= 0) return end - beg;
277 int scion = 0;
278 for (int i = beg; i < end; i++) scion += 1 + getDR(btr, x, i);
279 return scion;
280}
281
282// DIRTY DIRTY DIRTY DIRTY DIRTY DIRTY DIRTY DIRTY DIRTY DIRTY DIRTY DIRTY
283typedef struct btn_pos {
284 bt_n *x; int i;
285} bp_t;
286typedef struct two_bp_gens {
287 bp_t p; /* parent */ bp_t c; /* child */
288} tbg_t;
289static inline void free_bp(void *v) { cf_free(v); }
290
291typedef struct ll_ai_bp_element_s {
292 cf_ll_element ele;
293 bp_t * value;
294} ll_ai_bp_element;
295
296void
297ll_ai_bp_destroy_fn(cf_ll_element * ele)
298{
299 cf_free(((ll_ai_bp_element *)ele)->value);
300 cf_free((ll_ai_bp_element *)ele);
301}
302int
303ll_ai_bp_reduce_fn(cf_ll_element *ele, void *udata)
304{
305 return CF_LL_REDUCE_DELETE;
306}
307
308//TODO inline
309bt_n *addDStoBTN(bt *btr, bt_n *x, bt_n *p, int pi, char dirty) {
310 bt_n *y = allocbtreenode(btr, x->leaf, dirty);
311 GET_BTN_SIZE(x->leaf) memcpy(y, x, nsize);
312 y->dirty = dirty; btr->dirty = 1;
313 if (x == btr->root) btr->root = y;
314 else NODES(btr, p)[pi] = y; // update parent NODE bookkeeping
315 bt_free_btreenode(btr, x); //DEBUG_ADD_DS_TO_BTN
316 return y;
317}
318uint32 getDR(bt *btr, bt_n *x, int i) {
319 if (x->dirty <= 0) return 0;
320 GET_BTN_SIZE(x->leaf)
321 void *dsp = GET_DS(x, nsize);;
322 if (x->dirty == 1) {
323 uchar *ds = (uchar *)dsp; return (uint32)ds[i];
324 } else if (x->dirty == 2) {
325 ushort16 *ds = (ushort16 *)dsp; return (uint32)ds[i];
326 } else if (x->dirty == 3) {
327 uint32 *ds = (uint32 *)dsp; return ds[i];
328 } else assert(!"getDR ERROR");
329}
330#define INCR_DS_SET_DR \
331 { incr_ds(btr, x); __setDR(btr, x, i, dr); return; }
332
333static void __setDR(bt *btr, bt_n *x, int i, uint32 dr) {
334 uint32 odr; GET_BTN_SIZE(x->leaf)
335 void *dsp = GET_DS(x, nsize);
336 if (x->dirty == 1) {
337 uchar *ds = (uchar *)dsp; if (dr > UCHAR_MAX) INCR_DS_SET_DR
338 odr = ds[i]; ds[i] = dr;
339 } else if (x->dirty == 2) {
340 ushort16 *ds = (ushort16 *)dsp; if (dr > USHRT_MAX) INCR_DS_SET_DR
341 odr = ds[i]; ds[i] = dr;
342 } else if (x->dirty == 3) {
343 uint32 *ds = (uint32 *)dsp;
344 odr = ds[i]; ds[i] = dr;
345 } else assert(!"setDR ERROR");
346 (void) odr; // silence compiler warnings
347}
348static bt_n *setDR(bt *btr, bt_n *x, int i, uint32 dr, bt_n *p, int pi) {
349 if (!dr) return x;
350 if (x->dirty <= 0) x = addDStoBTN(btr, x, p, pi, 1);
351 __setDR(btr, x, i, dr); return x;
352}
353static bt_n *zeroDR(bt *btr, bt_n *x, int i, bt_n *p, int pi) {
354 (void)p; (void) pi; // compiler warnings - these will be used later
355 if (x->dirty <= 0) return x;
356 __setDR(btr, x, i, 0); return x;
357}
358static bt_n *incrDR(bt *btr, bt_n *x, int i, uint32 dr, bt_n *p, int pi) {
359 if (!dr) return x;
360 if (x->dirty <= 0) x = addDStoBTN(btr, x, p, pi, 1);
361 uint32 odr = getDR(btr, x, i);
362 odr += dr;
363 return setDR(btr, x, i, odr, p, pi);
364}
365static bt_n *overwriteDR(bt *btr, bt_n *x, int i, uint32 dr, bt_n *p, int pi) {
366 if (dr) return setDR (btr, x, i, dr, p, pi);
367 else return zeroDR(btr, x, i, p, pi);
368}
369
370// DEL_CASE_DR DEL_CASE_DR DEL_CASE_DR DEL_CASE_DR DEL_CASE_DR DEL_CASE_DR
371static bt_n *incrPrevDR(bt *btr, bt_n *x, int i, uint32 dr,
372 bt_n *p, int pi, cf_ll *plist) {
373 if (!dr) return x; //DEBUG_INCR_PREV_DR
374 if (i > 0) return incrDR(btr, x, i - 1, dr, p, pi); // prev sibling
375 else {
376 //TODO findminnode() is too inefficient -> needs to be a part of btr
377 if (x == findminnode(btr, btr->root)) { // MIN KEY
378 btr->dirty_left += dr; btr->dirty = 1; return x;
379 }
380 cf_ll_element * ele;
381 cf_ll_iterator * iter = cf_ll_getIterator(plist, true);
382 bt_n *rx = btr->root; int ri = 0;
383
384 while ((ele = cf_ll_getNext(iter))) {
385 bp_t *bp = ((ll_ai_bp_element *)ele)->value;
386 if (bp->i) { rx = bp->x; ri = bp->i - 1; break; }
387 }
388 bt_n *prx = btr->root; int pri = 0;
389 if (rx != btr->root) { // get parent
390 ele = cf_ll_getNext(iter);
391 bp_t *bp = ((ll_ai_bp_element *)ele)->value;
392 prx = bp->x; pri = bp->i;
393 }
394 cf_ll_releaseIterator(iter);
395 //printf("rx: %p ri: %d prx: %p pri: %d\n", rx, ri, prx, pri);
396 incrDR(btr, rx, ri, dr, prx, pri);
397 return x; // x not modified (only rx)
398 }
399}
400static tbg_t get_prev_child_recurse(bt *btr, bt_n *x, int i) {
401 bt_n *xp = NODES(btr, x)[i]; //DEBUG_GET_C_REC_1
402 if (!xp->leaf) return get_prev_child_recurse(btr, xp, xp->n);
403 tbg_t tbg;
404 tbg.p.x = x; tbg.p.i = i;
405 tbg.c.x = xp; tbg.c.i = xp->n - 1; //DEBUG_GET_C_REC_2
406 return tbg;
407}
408static bt_n *incrCase2B(bt *btr, bt_n *x, int i, int dr) { //DEBUG_INCR_CASE2B
409 tbg_t tbg = get_prev_child_recurse(btr, x, i); //DEBUG_INCR_PREV
410 bt_n *nc = incrDR(btr, tbg.c.x, tbg.c.i, dr, tbg.p.x, tbg.p.i);
411 incr_scion(nc, dr);
412 return x; // x not modified (only tbg.c.x)
413}
414
415// SET_BT_KEY SET_BT_KEY SET_BT_KEY SET_BT_KEY SET_BT_KEY SET_BT_KEY
416static void setBTKeyRaw(bt *btr, bt_n *x, int i, void *src) { //PRIVATE
417 void **dest = AKEYS(btr, x, i);
418 if ISVOID(btr) *dest = src;
419 else memcpy(dest, src, btr->s.ksize);
420 //DEBUG_SET_KEY
421}
422static bt_n *setBTKey(bt *btr, bt_n *dx, int di, bt_n *sx, int si,
423 bool drt, bt_n *pd, int pdi, bt_n *ps, int psi) {
424 if (drt) {
425 uint32 dr = getDR (btr, sx, si); //DEBUG_SET_BTKEY
426 dx = overwriteDR(btr, dx, di, dr, pd, pdi);
427 sx = zeroDR (btr, sx, si, ps, psi);
428 } else sx = zeroDR (btr, sx, si, ps, psi);
429 setBTKeyRaw(btr, dx, di, KEYS(btr, sx, si)); return dx;
430}
431
432static void mvXKeys(bt *btr, bt_n **dx, int di,
433 bt_n **sx, int si, uint32 num, uint32 ks,
434 bt_n *pd, int pdi,
435 bt_n *ps, int psi) {
436 if (!num) return;
437 bool x2x = (*dx == *sx); bool forward = (di >= si);
438 int i = forward ? (int)num - 1: 0;
439 int end = forward ? -1 : (int)num;
440 while (i != end) { // DS remove destDR from dx @i, add srcDR to sx @i
441 int sii = si + i; int dii = di + i;
442 uint32 drs = getDR(btr, *sx, sii), drd = getDR(btr, *dx, dii);
443 if (drs) { //DEBUG_MV_X_KEYS_1
444 *dx = setDR (btr, *dx, dii, drs, pd, pdi);
445 if (x2x && *dx != *sx) *sx = *dx;
446 *sx = zeroDR(btr, *sx, sii, ps, psi);
447 if (x2x && *dx != *sx) *dx = *sx;
448 } else if (drd) { //DEBUG_MV_X_KEYS_2
449 *dx = zeroDR(btr, *dx, dii, pd, pdi);
450 if (x2x && *dx != *sx) *sx = *dx;
451 }
452 bt_data_t *dest = AKEYS(btr, *dx, di);
453 bt_data_t *src = AKEYS(btr, *sx, si);
454 void *dk = (char *)dest + (i * ks);
455 void *sk = (char *)src + (i * ks);
456 memcpy(dk, sk, ks);
457 if (forward) i--; else i++;
458 }
459}
460static inline void mvXNodes(bt *btr, bt_n *x, int xofst,
461 bt_n *z, int zofst, int num) {
462 memmove(NODES(btr, x) + xofst, NODES(btr, z) + zofst, (num) * VOIDSIZE);
463}
464
465//NOTE: trimBTN*() do not ever dirty btn's -- TODO they could UN-dirty
466static bt_n *trimBTN(bt *btr, bt_n *x, bool drt, bt_n *p, int pi) {
467 //DEBUG_TRIM_BTN
468 if (drt) x = zeroDR(btr, x, x->n, p, pi);
469 x->n--; return x;
470}
471static bt_n *trimBTN_n(bt *btr, bt_n *x, int n, bool drt, bt_n *p, int pi) {
472 if (drt) {
473 for (int i = x->n; i >= (x->n - n); i--) x = zeroDR(btr, x, i, p, pi);
474 }
475 x->n -= n; return x;
476}
477
478// INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT INSERT
479static bool btreesplitchild(bt *btr, bt_n *x, int i, bt_n *y, bt_n *p, int pi) {
480 ushort16 t = btr->t; //TODO dirtymath
481 bt_n *z = allocbtreenode(btr, y->leaf, y->dirty); if (!z) return 0;
482 z->leaf = y->leaf; /* duplicate leaf setting */
483 for (int j = 0; j < t - 1; j++) {
484 z = setBTKey(btr, z, j, y, j + t, 1, p, pi, p, pi);
485 }
486 z->scion = get_scion_range(btr, z, 0, t - 1); decr_scion(y, z->scion);
487 z->n = t - 1; y = trimBTN_n(btr, y, t - 1, 0, p, pi);
488 if (!y->leaf) { // if it's an internal node, copy the ptr's too
489 for (int j = 0; j < t; j++) {
490 uint32_t scion = NODES(btr, y)[j + t]->scion;
491 decr_scion(y, scion); incr_scion(z, scion);
492 NODES(btr, z)[j] = NODES(btr, y)[j + t];
493 }
494 }
495 for (int j = x->n; j > i; j--) { // move nodes in parent down one
496 NODES(btr, x)[j + 1] = NODES(btr, x)[j];
497 }
498 NODES(btr, x)[i + 1] = z; // store new node
499 for (int j = x->n - 1; j >= i; j--) { // adjust the keys from previous move
500 x = setBTKey(btr, x, j + 1, x, j, 1, p, pi, p, pi);
501 }
502 decr_scion(y, 1 + getDR(btr, y, y->n - 1)); //NEXT LINE: store new key
503 x = setBTKey(btr, x, i, y, y->n - 1, 1, p, pi, p, pi); x->n++;
504 trimBTN(btr, y, 0, p, pi);
505 return 1;
506}
507
508#define GETN(btr) ((2 * btr->t) - 1)
509static bool bt_insertnonfull(bt *btr, bt_n *x, bt_data_t k, bt_n *p, int pi,
510 int dr) {
511 if (x->leaf) { /* we are a leaf, just add it in */
512 int i = findkindex(btr, x, k, NULL, NULL);
513 if (i != x->n - 1) {
514 mvXKeys(btr, &x, i + 2, &x, i + 1, (x->n - i - 1), btr->s.ksize,
515 p, pi, p, pi);
516 }
517 x = overwriteDR(btr, x, i + 1, dr, p, pi);
518 setBTKeyRaw(btr, x, i + 1, k); x->n++; incr_scion(x, 1);
519 } else { /* not leaf */
520 int i = findkindex(btr, x, k, NULL, NULL) + 1;
521 if (NODES(btr, x)[i]->n == GETN(btr)) { // if next node is full
522 if (!btreesplitchild(btr, x, i, NODES(btr, x)[i], x, i)) return 0;
523 if (btr->cmp(k, KEYS(btr, x, i)) > 0) i++;
524 }
525 bt_insertnonfull(btr, NODES(btr, x)[i], k, x, i, dr); incr_scion(x, 1);
526 }
527 return 1;
528}
529bool bt_insert(bt *btr, bt_data_t k, uint32 dr) {
530 bt_n *r = btr->root;
531 bt_n *p = r;
532 int pi = 0;
533 if (r->n == GETN(btr)) { /* NOTE: tree increase height */
534 bt_n *s = allocbtreenode(btr, 0, r->dirty); if (!s) return 0;
535 btr->root = s;
536 s->leaf = 0;
537 s->n = 0;
538 incr_scion(s, r->scion);
539 NODES(btr, s)[0] = r;
540 if (!btreesplitchild(btr, s, 0, r, p, pi)) return 0;
541 p = r = s;
542 btr->numnodes++;
543 }
544 if (!bt_insertnonfull(btr, r, k, p, pi, dr)) return 0;
545 btr->numkeys++;
546 return 1;
547}
548
549// DELETE DELETE DELETE DELETE DELETE DELETE DELETE DELETE DELETE DELETE
550static bt_n *replaceKeyWithGhost(bt *btr, bt_n *x, int i, bt_data_t k,
551 uint32 dr, bt_n *p, int pi) {
552 //printf("replaceKeyWithGhost\n");
553 ai_obj akey; convertStream2Key(k, &akey, btr);
554 crs_t crs; uint32 ssize; DECLARE_BT_KEY(&akey, x)
555 char *stream = createStream(btr, NULL, btkey, ksize, &ssize, &crs);//DEST027
556 x = overwriteDR(btr, x, i, dr, p, pi);
557 setBTKeyRaw(btr, x, i, stream);
558 return x;
559}
560
561#define ADD_BP(plist, p, pi) /* used to trace path to deleted key */ \
562 if (plist) { \
563 bp_t *bp = (bp_t *) cf_malloc(sizeof(bp_t)); /* FREE ME 109 */ \
564 bp->x = p; bp->i = pi; \
565 ll_ai_bp_element * node = cf_malloc(sizeof(ll_ai_bp_element)); \
566 node->value = bp; \
567 cf_ll_append(plist, (cf_ll_element *)node); \
568 }
569
570#define CREATE_RETURN_DELETED_KEY(btr, kp, dr) \
571 dwd_t dwd; bzero(&dwd, sizeof(dwd_t)); dwd.dr = dr; \
572 if (BIG_BT(btr)) { memcpy(delbuf, kp, btr->s.ksize); } \
573 dwd.k = BIG_BT(btr) ? delbuf : kp;
574
575/* NOTE: ksize > 8 bytes needs buffer for CASE 1 */
576#define MAX_KEY_SIZE (AS_DIGEST_KEY_SZ *2)
577
578#define DK_NONE 0
579#define DK_2A 1
580#define DK_2B 2
581
582/* remove an existing key from the tree. KEY MUST EXIST
583 the s parameter:
584 1.) for normal operation pass it as DK_NONE,
585 2.) delete the max node, pass it as DK_2A,
586 3.) delete the min node, pass it as DK_2B.
587 */
588typedef struct btds_t {
589 ulong leaf_del_hits; ulong leaf_del_noop;
590 ulong ndel; ulong del_calls;
591 ulong case1_del;
592 ulong case2A_del; ulong case2B_del; ulong case2C_del;
593 ulong case3_del;
594 ulong case3A1_del; ulong case3A2_del; ulong case3B1_del; ulong case3B2_del;
595} btds_t;
596
597btds_t *btds = NULL;
598
599static dwd_t deletekey(bt *btr, bt_n *x, bt_data_t k, int s, bool drt,
600 bt_n *p, int pi, cf_ll *plist, void **c2Cp,
601 bool leafd, char delbuf[]) { btds->del_calls++;
602 bt_n *xp, *y, *z; bt_data_t kp;
603 int yn, zn, i = 0, r = -1, ks = btr->s.ksize;
604 if (s != DK_NONE) { /* min or max node deletion */
605 if (x->leaf) r = 0;
606 else {
607 if (s == DK_2A) r = 1; // max node
608 else if (s == DK_2B) r = -1; // min node
609 }
610 if (s == DK_2A) i = x->n - 1; // max node/leaf
611 else if (s == DK_2B) i = -1; // min node/leaf
612 } else i = findkindex(btr, x, k, &r, NULL); //DEBUG_DEL_POST_S
613
614 if (!drt) decr_scion(x, 1); // scion reduced by 1 every DELETE
615
616 /* Case 1:
617 * If the key k is in node x and x is a leaf, delete the key k from x. */
618 if (x->leaf) { btds->case1_del++;
619 bool rgst = 0;
620 if (s == DK_2B) i++; //DEBUG_DEL_CASE_1
621 kp = KEYS (btr, x, i);
622 int dr = getDR(btr, x, i);
623 CREATE_RETURN_DELETED_KEY(btr, kp, dr)
624 if (drt) { // CASE: EVICT
625 if (s == DK_NONE) { //NOTE: only place DR grows
626 x = incrPrevDR(btr, x, i, (dr + 1), p, pi, plist);
627 } else decr_scion(x, 1 + dr); //NOTE: key FOR Case2A/B
628 } else if (s == DK_NONE) { // CASE: DELETE NOT CASE2A/B
629 if (dr) {
630 if (NBT(btr)) { x = incrPrevDR(btr, x, i, dr, p, pi, plist); }
631 else { rgst = 1; // DELETE DataBT KEY w/ DR -> REPLACE w/ GHOST
632 x = replaceKeyWithGhost(btr, x, i, kp, dr, p, pi);
633 }
634 }
635 } else if (dr) decr_scion(x, dr); // CASE: DELETE CASE2A/B
636 if (!rgst) { // IF NO REPLACE_W_GHOST -> Remove from BTREE
637 mvXKeys(btr, &x, i, &x, i + 1, (x->n - i - 1), ks, p, pi, p, pi);
638 x = trimBTN(btr, x, drt, p, pi);
639 }
640 return dwd;
641 }
642 dwd_t dwde; bzero(&dwde, sizeof(dwd_t));
643 if (r == 0) { /* (r==0) means key found, but in node */ //DEBUG_DEL_CASE_2
644 kp = KEYS(btr, x, i);
645 if (!drt) { // ON DELETE
646 int dr = getDR(btr, x, i);
647 if (dr) { // IF DR -> REPLACE_W_GHOST, no recursive delete
648 x = replaceKeyWithGhost(btr, x, i, kp, dr, p, pi);
649 CREATE_RETURN_DELETED_KEY(btr, kp, dr)
650 return dwd;
651 }
652 }
653 /* Case 2:
654 * if the key k is in the node x, and x is an internal node */
655 if ((yn = NODES(btr, x)[i]->n) >= btr->t) { //DEBUG_DEL_CASE_2a
656 btds->case2A_del++;
657 if (leafd) return dwde;
658 /* Case 2a:
659 * if the node y that precedes k in node x has at least t keys,
660 * then find the previous sequential key (kp) of k.
661 * Recursively delete kp, and replace k with kp in x. */
662 xp = NODES(btr, x)[i];
663 ADD_BP(plist, x, i)
664 //printf("CASE2A recurse: key: "); printKey(btr, x, i);
665 dwd_t dwd = deletekey(btr, xp, NULL, DK_2A, drt,
666 x, i, plist, c2Cp, leafd, delbuf);
667 //DEBUG_SET_BTKEY_2A
668 if (drt) x = incrDR(btr, x, i, ++dwd.dr, p, pi);
669 else x = setDR (btr, x, i, dwd.dr, p, pi);
670 setBTKeyRaw(btr, x, i, dwd.k);
671 dwd.k = kp; // swap back in KPs original value
672 return dwd;
673 }
674 if ((zn = NODES(btr, x)[i + 1]->n) >= btr->t) { //DEBUG_DEL_CASE_2b
675 btds->case2B_del++;
676 if (leafd) return dwde;
677 /* Case 2b:
678 * if the node z that follows k in node x has at least t keys,
679 * then find the next sequential key (kp) of k. Recursively delete
680 * kp, and replace k with kp in x. */
681 xp = NODES(btr, x)[i + 1];
682 ADD_BP(plist, x, i + 1)
683 //printf("CASE2B recurse: key: "); printKey(btr, x, i);
684 dwd_t dwd = deletekey(btr, xp, NULL, DK_2B, drt,
685 x, i + 1, plist, c2Cp, leafd, delbuf);
686 //DEBUG_SET_BTKEY_2B
687 if (drt) { // prev key inherits DR+1
688 x = incrCase2B (btr, x, i, (getDR(btr, x, i) + 1));
689 }
690 x = overwriteDR(btr, x, i, dwd.dr, p, pi);
691 setBTKeyRaw(btr, x, i, dwd.k);
692 dwd.k = kp; // swap back in KPs original value
693 return dwd;
694 }
695 if (yn == btr->t - 1 && zn == btr->t - 1) { //DEBUG_DEL_CASE_2c
696 btds->case2C_del++;
697 if (leafd) return dwde;
698 /* Case 2c:
699 * if both y and z have only t - 1 keys, merge k
700 * then all of z into y, so that x loses both k and
701 * the pointer to z, and y now contains 2t - 1 keys. */
702 if (!*c2Cp) *c2Cp = KEYS(btr, x, i); //used in remove_key()
703 y = NODES(btr, x)[i];
704 z = NODES(btr, x)[i + 1];
705 dwd_t dwd; dwd.k = k; dwd.dr = getDR(btr, x, i);
706 incr_scion(y, 1 + dwd.dr); //DEBUG_SET_BTKEY_2C
707 y = setDR (btr, y, y->n, dwd.dr, x, i);
708 setBTKeyRaw(btr, y, y->n, dwd.k); y->n++;
709 incr_scion(y, get_scion_range(btr, z, 0, z->n));
710 mvXKeys(btr, &y, y->n, &z, 0, z->n, ks, x, i, x, i + 1);
711 if (!y->leaf) {
712 move_scion(btr, y, z, z->n + 1);
713 mvXNodes (btr, y, y->n, z, 0, (z->n + 1));
714 }
715 y->n += z->n;
716 mvXKeys (btr, &x, i, &x, i + 1, (x->n - i - 1), ks, p, pi, p, pi);
717 mvXNodes(btr, x, i + 1, x, i + 2, (x->n - i - 1));
718 x = trimBTN(btr, x, drt, p, pi);
719 bt_free_btreenode(btr, z);
720 ADD_BP(plist, x, i)
721 //printf("CASE2C key: "); printKey(btr, x, i);
722 return deletekey(btr, y, k, s, drt, x, i, plist, c2Cp, leafd, delbuf);
723 }
724 }
725 /* Case 3:
726 * if k is not present in internal node x, determine the root xp of
727 * the appropriate subtree that must contain k, if k is in the tree
728 * at all. If xp has only t - 1 keys, execute step 3a or 3b as
729 * necessary to guarantee that we descend to a node containing at
730 * least t keys. Finish by recursing on the appropriate node of x. */
731 i++;
732 if ((xp = NODES(btr, x)[i])->n == btr->t - 1) { /* case 3a-c are !x->leaf */
733 /* Case 3a:
734 * If xp has only (t-1) keys but has a sibling(y) with at least t keys,
735 give xp an extra key by moving a key from x down into xp,
736 moving a key from xp's immediate left or right sibling(y) up into x,
737 & moving the appropriate node from the sibling(y) into xp. */
738 if (i > 0 && (y = NODES(btr, x)[i - 1])->n >= btr->t) {
739 btds->case3A1_del++;
740 //printf("CASE3A1 key: "); printKey(btr, x, i);
741 if (leafd) return dwde;
742 /* left sibling has t keys */ //DEBUG_DEL_CASE_3a1
743 mvXKeys(btr, &xp, 1, &xp, 0, xp->n, ks, x, i, x, i);
744 if (!xp->leaf) mvXNodes(btr, xp, 1, xp, 0, (xp->n + 1));
745 incr_scion(xp, 1 + getDR(btr, x, i - 1));
746 xp = setBTKey(btr, xp, 0, x, i - 1, drt, x, i, p, pi); xp->n++;
747 decr_scion(y, 1 + getDR(btr, y, y->n - 1));
748 x = setBTKey(btr, x, i - 1, y, y->n - 1, drt, p, pi, x, i - 1);
749 if (!xp->leaf) {
750 int dscion = NODES(btr, y)[y->n]->scion;
751 incr_scion(xp, dscion); decr_scion(y, dscion);
752 NODES(btr, xp)[0] = NODES(btr, y)[y->n];
753 }
754 y = trimBTN(btr, y, drt, x, i - 1);
755 } else if (i < x->n && (y = NODES(btr, x)[i + 1])->n >= btr->t) {
756 btds->case3A2_del++;
757 //printf("CASE3A2 key: "); printKey(btr, x, i);
758 if (leafd) return dwde;
759 /* right sibling has t keys */ //DEBUG_DEL_CASE_3a2
760 incr_scion(xp, 1 + getDR(btr, x, i));
761 xp = setBTKey(btr, xp, xp->n++, x, i, drt, x, i, p, pi);
762 decr_scion(y, 1 + getDR(btr, y, 0));
763 x = setBTKey(btr, x, i, y, 0, drt, p, pi, x, i + 1);
764 if (!xp->leaf) {
765 int dscion = NODES(btr, y)[0]->scion;
766 incr_scion(xp, dscion); decr_scion(y, dscion);
767 NODES(btr, xp)[xp->n] = NODES(btr, y)[0];
768 }
769 mvXKeys(btr, &y, 0, &y, 1, y->n - 1, ks, x, i + 1, x, i + 1);
770 if (!y->leaf) mvXNodes(btr, y, 0, y, 1, y->n);
771 y = trimBTN(btr, y, drt, x, i + 1);
772 }
773 /* Case 3b:
774 * If xp and all of xp's siblings have t - 1 keys, merge xp with
775 one sibling, which involves moving a key from x down into the
776 new merged node to become the median key for that node. */
777 else if (i > 0 && (y = NODES(btr, x)[i - 1])->n == btr->t - 1) {
778 btds->case3B1_del++;
779 //printf("CASE3B1 key: "); printKey(btr, x, i);
780 if (leafd) return dwde;
781 /* merge i with left sibling */ //DEBUG_DEL_CASE_3b1
782 incr_scion(y, 1 + getDR(btr, x, i - 1));
783 y = setBTKey(btr, y, y->n++, x, i - 1, drt, x, i - 1, p, pi);
784 incr_scion(y, get_scion_range(btr, xp, 0, xp->n));
785 mvXKeys(btr, &y, y->n, &xp, 0, xp->n, ks, x, i - 1, x, i);
786 if (!xp->leaf) {
787 move_scion(btr, y, xp, xp->n + 1);
788 mvXNodes (btr, y, y->n, xp, 0, (xp->n + 1));
789 }
790 y->n += xp->n;
791 mvXKeys (btr, &x, i - 1, &x, i, (x->n - i), ks, p, pi, p, pi);
792 mvXNodes(btr, x, i, x, i + 1, (x->n - i));
793 x = trimBTN(btr, x, drt, p, pi);
794 bt_free_btreenode(btr, xp);
795 xp = y; i--; // i-- for parent-arg in recursion (below)
796 } else if (i < x->n && (y = NODES(btr, x)[i + 1])->n == btr->t - 1) {
797 btds->case3B2_del++;
798 //printf("CASE3B2 key: "); printKey(btr, x, i);
799 if (leafd) return dwde;
800 /* merge i with right sibling */ //DEBUG_DEL_CASE_3b2
801 incr_scion(xp, 1 + getDR(btr, x, i));
802 xp = setBTKey(btr, xp, xp->n++, x, i, drt, x, i, p, pi);
803 incr_scion(xp, get_scion_range(btr, y, 0, y->n));
804 mvXKeys(btr, &xp, xp->n, &y, 0, y->n, ks, x, i, x, i + 1);
805 if (!xp->leaf) {
806 move_scion(btr, xp, y, y->n + 1);
807 mvXNodes (btr, xp, xp->n, y, 0, (y->n + 1));
808 }
809 xp->n += y->n;
810 mvXKeys (btr, &x, i, &x, i + 1, (x->n - i - 1), ks, p, pi, p, pi);
811 mvXNodes(btr, x, i + 1, x, i + 2, (x->n - i - 1));
812 x = trimBTN(btr, x, drt, p, pi);
813 bt_free_btreenode(btr, y);
814 }
815 } //printf("RECURSE CASE 3\n");
816 btds->case3_del++;
817 ADD_BP(plist, x, i) //DEBUG_DEL_POST_CASE_3
818 dwd_t dwd = deletekey(btr, xp, k, s, drt, x, i, plist, c2Cp, leafd, delbuf);
819 // CASE2A/B pull keys up from depths, scion must be decremented
820 if (s != DK_NONE) {
821 if (drt) decr_scion(x, 1 + dwd.dr);
822 else decr_scion(x, dwd.dr); // DELETE already decr_scion()ed 1
823 }
824 return dwd;
825}
826
827#ifdef DEBUG_DEL_CASE_STATS
828static void print_del_case_stats(bool leafd, dwd_t dwd, bt *btr) {
829 if (leafd) {
830 if (!dwd.k) btds->leaf_del_noop++;
831 else btds->leaf_del_hits++;
832 printf("deletes: %lu noop: %lu ratio: %f numkeys: %d\n",
833 btds->leaf_del_hits, btds->leaf_del_noop,
834 (btds->leaf_del_noop && btds->leaf_del_hits) ?
835 (double)((double)btds->leaf_del_hits /
836 (double)btds->leaf_del_noop) : 0,
837 btr->numkeys);
838 } else
839 printf("ndel: %lu ncalls: %lu C1: %lu(%.2f) C2A: %lu(%.2f) "
840 "C2B: %lu(%.2f) C2C: %lu(%.2f) C3: %lu(%.2f) "
841 "C3A1: %lu(%.2f) C3A2: %lu(%.2f) C3B1: %lu(%.2f) "
842 "C3B2: %lu(%.2f)\n",
843 btds->ndel, btds->del_calls,
844 btds->case1_del,
845 (double)((double)btds->case1_del / (double)btds->del_calls),
846 btds->case2A_del,
847 (double)((double)btds->case2A_del / (double)btds->del_calls),
848 btds->case2B_del,
849 (double)((double)btds->case2B_del / (double)btds->del_calls),
850 btds->case2C_del,
851 (double)((double)btds->case2C_del / (double)btds->del_calls),
852 btds->case3_del,
853 (double)((double)btds->case3_del / (double)btds->del_calls),
854 btds->case3A1_del,
855 (double)((double)btds->case3A1_del / (double)btds->del_calls),
856 btds->case3A2_del,
857 (double)((double)btds->case3A2_del / (double)btds->del_calls),
858 btds->case3B1_del,
859 (double)((double)btds->case3B1_del / (double)btds->del_calls),
860 btds->case3B2_del,
861 (double)((double)btds->case3B2_del / (double)btds->del_calls));
862 fflush(NULL);
863}
864#endif
865
866static dwd_t remove_key(bt *btr, bt_data_t k, bool drt, bool leafd) {
867 if (!btds) { btds = cf_malloc(sizeof(btds_t)); bzero(btds, sizeof(btds_t)); }
868 btds->ndel++;
869 if (!btr->root) { dwd_t dwde; bzero(&dwde, sizeof(dwd_t)); return dwde; }
870 void *c2Cp = NULL; /* NOTE: c2Cp gets lost in recursion */ //DEBUG_DEL_START
871 bt_n *p = btr->root; int pi = 0;
872 cf_ll plist_tmp;
873 cf_ll * plist = &plist_tmp; // NOTE: plist stores ancestor line during recursive delete
874 if (drt) {
875 cf_ll_init(plist, ll_ai_bp_destroy_fn, false);
876 ADD_BP(plist, p, pi);//FR110
877 } else plist = NULL;
878 char delbuf[MAX_KEY_SIZE]; // NOTE: ksize > 8B needs buffer for CASE 1
879 dwd_t dwd = deletekey(btr, btr->root, k, DK_NONE, drt,
880 p, pi, plist, &c2Cp, leafd, delbuf);
881#ifdef DEBUG_DEL_CASE_STATS
882 print_del_case_stats(leafd, dwd, btr);
883#endif
884 if (!dwd.k) return dwd; // leafd NO-OP
885 btr->numkeys--; //DEBUG_DEL_END
886 /* remove empty non-leaf node from root, */
887 if (!btr->root->n && !btr->root->leaf) { /* NOTE: tree decrease height */
888 btr->numnodes--;
889 bt_n *x = btr->root;
890 btr->root = NODES(btr, x)[0];
891 bt_free_btreenode(btr, x);
892 }
893 if (c2Cp) dwd.k = c2Cp;
894 if (plist) {
895 cf_ll_reduce(plist, true, ll_ai_bp_reduce_fn, NULL);
896 plist = NULL;
897 }; // FREED 110
898 return dwd;
899}
900dwd_t bt_delete(bt *btr, bt_data_t k, bool leafd) {
901 return remove_key(btr, k, 0, leafd);
902}
903
904// ACCESSORS ACCESSORS ACCESSORS ACCESSORS ACCESSORS ACCESSORS ACCESSORS
905static inline bool key_covers_miss(bt *btr, bt_n *x, int i, ai_obj *akey) {
906 if (!(C_IS_NUM(btr->s.ktype))) return 0;
907 if (i < 0) i = 0;
908 ulong mkey = getNumKey(btr, x, i);
909 ulong dr = (ulong)getDR(btr, x, i);
910 if (mkey && dr) {
911 ulong qkey = akey->l;
912 ulong span = mkey + dr;
913 //DEBUG_CURRKEY_MISS
914 if (qkey >= mkey && qkey <= span) return 1;
915 }
916 return 0;
917}
918#define SET_DWM_XIP { dwm.x = x; dwm.i = i; dwm.p = p; dwm.pi = pi; }
919dwm_t findnodekey(bt *btr, bt_n *x, bt_data_t k, ai_obj *akey) {
920 int r = -1, i = 0;
921 bt_n *p = btr->root; int pi = 0;
922 dwm_t dwm; bzero(&dwm, sizeof(dwm_t)); SET_DWM_XIP
923 while (x) {
924 i = findkindex(btr, x, k, &r, NULL); //DEBUG_FIND_NODE_KEY
925 if (i >= 0 && !r) { SET_DWM_XIP dwm.k = KEYS(btr, x, i); return dwm; }
926 if (key_covers_miss(btr, x, i, akey)) { SET_DWM_XIP dwm.miss = 1; }
927 if (x->leaf) { dwm.k = NULL; return dwm; }
928 p = x; pi = i + 1; x = NODES(btr, x)[i + 1];
929 }
930 return dwm;
931}
932bt_data_t bt_find(bt *btr, bt_data_t k, ai_obj *akey) { //Indexes still use this
933 dwm_t dwm = findnodekey(btr, btr->root, k, akey);
934 return dwm.k;
935}
936
937static bool check_min_miss(bt *btr, ai_obj *alow) {
938 if (!btr->dirty_left) return 0;
939 ai_obj amin; convertStream2Key(bt_min(btr), &amin, btr);
940 return ai_objEQ(alow, &amin);
941}
942int bt_init_iterator(bt *btr, bt_data_t k, btIterator *iter, ai_obj *alow) {
943 if (!btr->root) return II_FAIL;
944 int r = -1;
945 bool lmiss = check_min_miss(btr, alow);
946 bool miss = 0;
947 uchar only_right = 1;
948 bt_n *x = btr->root;
949 while (x) {
950 int i = findkindex(btr, x, k, &r, iter);
951 if (i >= 0 && r == 0) return lmiss ? II_L_MISS : II_OK;
952 if (key_covers_miss(btr, x, i, alow)) miss = 1; //DEBUG_BT_II
953 if (miss) return II_MISS;
954 if (r < 0 || i != (x->n - 1)) only_right = 0;
955 if (x->leaf) {
956 if (i != (x->n - 1)) only_right = 0;
957 return only_right ? II_ONLY_RIGHT : II_LEAF_EXIT;
958 }
959 iter->bln->child = get_new_iter_child(iter);
960 x = NODES(btr, x)[i + 1];
961 to_child(iter, x);
962 }
963 return II_FAIL;
964}
965
966bool bt_exist(bt *btr, bt_data_t k, ai_obj *akey) {
967 int r = -1;
968 bt_n *x = btr->root;
969 while (x) {
970 int i = findkindex(btr, x, k, &r, NULL);
971 if (i >= 0 && r == 0) return 1;
972 if (key_covers_miss(btr, x, i, akey)) return 1;
973 if (x->leaf) return 0;
974 x = NODES(btr, x)[i + 1];
975 }
976 return 0;
977}
978
979static bt_data_t findminkey(bt *btr, bt_n *x) {
980 if (x->leaf) return KEYS(btr, x, 0);
981 else return findminkey(btr, NODES(btr, x)[0]);
982}
983bt_n *findminnode(bt *btr, bt_n *x) {
984 if (x->leaf) return x;
985 else return findminnode(btr, NODES(btr, x)[0]);
986}
987static bt_data_t findmaxkey(bt *btr, bt_n *x) {
988 if (x->leaf) return KEYS(btr, x, x->n - 1);
989 else return findmaxkey(btr, NODES(btr, x)[x->n]);
990}
991bt_data_t bt_min(bt *btr) {
992 if (!btr->root || !btr->numkeys) return NULL;
993 else return findminkey(btr, btr->root);
994}
995bt_data_t bt_max(bt *btr) {
996 if (!btr->root || !btr->numkeys) return NULL;
997 else return findmaxkey(btr, btr->root);
998}
999
1000// DESTRUCTOR DESTRUCTOR DESTRUCTOR DESTRUCTOR DESTRUCTOR DESTRUCTOR
1001static void destroy_bt_node(bt *btr, bt_n *x) {
1002 if (!x->leaf) {
1003 for (int i = 0; i <= x->n; i++) {
1004 destroy_bt_node(btr, NODES(btr, x)[i]);
1005 }
1006 }
1007 bt_free_btreenode(btr, x); /* memory management in btr */
1008}
1009void bt_destroy(bt *btr) {
1010 if (btr->root) {
1011 if (btr->numkeys) destroy_bt_node (btr, btr->root);
1012 else bt_free_btreenode(btr, btr->root);
1013 btr->root = NULL;
1014 }
1015 bt_free_btree(btr);
1016}
1017