bpp_tree.c
Go to the documentation of this file.
1 /******************************************************************************/
34 /******************************************************************************/
35 
36 #include "bpp_tree.h"
37 
38 /*************
39  * internals *
40  *************/
41 
42 /*
43  * algorithm:
44  * A B+tree implementation, with keys stored in internal nodes,
45  * and keys/record addresses stored in leaf nodes. Each node is
46  * one sector in length, except the root node whose length is
47  * 3 sectors. When traversing the tree to insert a key, full
48  * children are adjusted to make room for possible new entries.
49  * Similarly, on deletion, half-full nodes are adjusted to allow for
50  * possible deleted entries. Adjustments are first done by
51  * examining 2 nearest neighbors at the same level, and redistibuting
52  * the keys if possible. If redistribution won't solve the problem,
53  * nodes are split/joined as needed. Typically, a node is 3/4 full.
54  * On insertion, if 3 nodes are full, they are split into 4 nodes,
55  * each 3/4 full. On deletion, if 3 nodes are 1/2 full, they are
56  * joined to create 2 nodes 3/4 full.
57  *
58  * A LRR (least-recently-read) buffering scheme for nodes is used to
59  * simplify storage management, and, assuming some locality of reference,
60  * improve performance.
61  *
62  * To simplify matters, both internal nodes and leafs contain the
63  * same fields.
64  *
65 */
66 
67 /* macros for addressing fields */
68 
69 /* primitives */
70 #define bAdr(p) *(ion_bpp_address_t *) (p)
71 #define eAdr(p) *(ion_bpp_external_address_t *) (p)
72 
73 /* based on k = &[key,rec,childGE] */
74 #define childLT(k) bAdr((char *) k - sizeof(ion_bpp_address_t))
75 #define key(k) (k)
76 #define rec(k) eAdr((char *) (k) + h->keySize)
77 #define childGE(k) bAdr((char *) (k) + h->keySize + sizeof(ion_bpp_external_address_t))
78 
79 /* based on b = &ion_bpp_buffer_t */
80 #define leaf(b) b->p->leaf
81 #define ct(b) b->p->ct
82 #define next(b) b->p->next
83 #define prev(b) b->p->prev
84 #define fkey(b) & b->p->fkey
85 #define lkey(b) (fkey(b) + ks((ct(b) - 1)))
86 #define p(b) (char *) (b->p)
87 
88 /* shortcuts */
89 #define ks(ct) ((ct) * h->ks)
90 
91 typedef char ion_bpp_key_t; /* keys entries are treated as char arrays */
92 
93 typedef struct {
94 #if 0
95 
96  char leaf; /* first bit = 1 if leaf */
97  uint16_t ct; /* count of keys present */
98 
99 #endif
100 
101  unsigned int leaf : 1;
102  unsigned int ct : 15;
103  ion_bpp_address_t prev; /* prev node in sequence (leaf) */
104  ion_bpp_address_t next; /* next node in sequence (leaf) */
105  ion_bpp_address_t childLT; /* child LT first key */
106  /* ct occurrences of [key,rec,childGE] */
107  ion_bpp_key_t fkey; /* first occurrence */
109 
110 typedef struct ion_bpp_buffer_tag {
111  /* location of node */
112  struct ion_bpp_buffer_tag *next; /* next */
113  struct ion_bpp_buffer_tag *prev; /* previous */
114  ion_bpp_address_t adr; /* on disk */
115  ion_bpp_node_t *p; /* in memory */
116  ion_bpp_bool_t valid; /* true if buffer contents valid */
117  ion_bpp_bool_t modified; /* true if buffer modified */
119 
120 /* one node for each open handle */
121 typedef struct ion_bpp_h_node_tag {
122  ion_file_handle_t fp; /* idx file */
123  int keySize;/* key length */
124  ion_bpp_bool_t dupKeys;/* true if duplicate keys */
125  int sectorSize; /* block size for idx records */
126  ion_bpp_comparison_t comp; /* pointer to compare routine */
127  ion_bpp_buffer_t root; /* root of b-tree, room for 3 sets */
128  ion_bpp_buffer_t bufList; /* head of buf list */
129  void *malloc1; /* malloc'd resources */
130  void *malloc2; /* malloc'd resources */
131  ion_bpp_buffer_t gbuf; /* gather buffer, room for 3 sets */
132  ion_bpp_buffer_t *curBuf; /* current location */
133  ion_bpp_key_t *curKey; /* current key in current node */
134  unsigned int maxCt; /* minimum # keys in node */
135  int ks; /* sizeof key entry */
136  ion_bpp_address_t nextFreeAdr;/* next free b-tree record address */
138 
139 #define error(rc) lineError(__LINE__, rc)
140 
141 static ion_bpp_err_t
143  int lineno,
144  ion_bpp_err_t rc
145 ) {
146  if ((rc == bErrIO) || (rc == bErrMemory)) {
147  if (!bErrLineNo) {
148  bErrLineNo = lineno;
149  }
150  }
151 
152  return rc;
153 }
154 
155 static ion_bpp_address_t
157  ion_bpp_handle_t handle
158 ) {
159  ion_bpp_h_node_t *h = handle;
161 
162  adr = h->nextFreeAdr;
163  h->nextFreeAdr += h->sectorSize;
164  return adr;
165 }
166 
167 static ion_bpp_err_t
169  ion_bpp_handle_t handle,
170  ion_bpp_buffer_t *buf
171 ) {
172  ion_bpp_h_node_t *h = handle;
173  int len;/* number of bytes to write */
174  ion_err_t err;
175 
176  /* flush buffer to disk */
177  len = h->sectorSize;
178 
179  if (buf->adr == 0) {
180  len *= 3; /* root */
181  }
182 
183  err = ion_fwrite_at(h->fp, buf->adr, len, (ion_byte_t *) buf->p);
184 
185  if (err_ok != err) {
186  return error(bErrIO);
187  }
188 
189 #if 0
190  /* flush buffer to disk */
191  len = 1;
192 
193  if (buf->adr == 0) {
194  len = 3;/* root */
195  }
196 
197  if (0 != fseek(h->fp, buf->adr, SEEK_SET)) {
198  return error(bErrIO);
199  }
200 
201  for (i = 0; i < len; i++) {
202  if (1 != fwrite(&buf[i].p->leaf, sizeof(buf->p->leaf), 1, h->fp)) {
203  return error(bErrIO);
204  }
205 
206  if (1 != fwrite(&buf[i].p->ct, sizeof(buf->p->ct), 1, h->fp)) {
207  return error(bErrIO);
208  }
209 
210  if (1 != fwrite(&buf[i].p->prev, sizeof(buf->p->prev), 1, h->fp)) {
211  return error(bErrIO);
212  }
213 
214  if (1 != fwrite(&buf[i].p->next, sizeof(buf->p->next), 1, h->fp)) {
215  return error(bErrIO);
216  }
217 
218  if (1 != fwrite(&buf[i].p->childLT, sizeof(buf->p->childLT), 1, h->fp)) {
219  return error(bErrIO);
220  }
221 
222  if (1 != fwrite(&buf[i].p->fkey, sizeof(buf->p->fkey), 1, h->fp)) {
223  return error(bErrIO);
224  }
225  }
226 
227 #endif
228 
229  buf->modified = boolean_false;
230  nDiskWrites++;
231  return bErrOk;
232 }
233 
234 static ion_bpp_err_t
236  ion_bpp_handle_t handle
237 ) {
238  ion_bpp_h_node_t *h = handle;
239  ion_bpp_err_t rc; /* return code */
240  ion_bpp_buffer_t *buf; /* buffer */
241 
242  if (h->root.modified) {
243  if ((rc = flush(handle, &h->root)) != 0) {
244  return rc;
245  }
246  }
247 
248  buf = h->bufList.next;
249 
250  while (buf != &h->bufList) {
251  if (buf->modified) {
252  if ((rc = flush(handle, buf)) != 0) {
253  return rc;
254  }
255  }
256 
257  buf = buf->next;
258  }
259 
260  return bErrOk;
261 }
262 
263 static ion_bpp_err_t
265  ion_bpp_handle_t handle,
267  ion_bpp_buffer_t **b
268 ) {
269  ion_bpp_h_node_t *h = handle;
270  /* assign buf to adr */
271  ion_bpp_buffer_t *buf; /* buffer */
272  ion_bpp_err_t rc; /* return code */
273 
274  if (adr == 0) {
275  *b = &h->root;
276  return bErrOk;
277  }
278 
279  /* search for buf with matching adr */
280  buf = h->bufList.next;
281 
282  while (buf->next != &h->bufList) {
283  if (buf->valid && (buf->adr == adr)) {
284  break;
285  }
286 
287  buf = buf->next;
288  }
289 
290  /* either buf points to a match, or it's last one in list (LRR) */
291  if (buf->valid) {
292  if (buf->adr != adr) {
293  if (buf->modified) {
294  if ((rc = flush(handle, buf)) != 0) {
295  return rc;
296  }
297  }
298 
299  buf->adr = adr;
300  buf->valid = boolean_false;
301  }
302  }
303  else {
304  buf->adr = adr;
305  }
306 
307  /* remove from current position and place at front of list */
308  buf->next->prev = buf->prev;
309  buf->prev->next = buf->next;
310  buf->next = h->bufList.next;
311  buf->prev = &h->bufList;
312  buf->next->prev = buf;
313  buf->prev->next = buf;
314  *b = buf;
315  return bErrOk;
316 }
317 
318 static ion_bpp_err_t
320  ion_bpp_buffer_t *buf
321 ) {
322  /* write buf to disk */
323  buf->valid = boolean_true;
324  buf->modified = boolean_true;
325  return bErrOk;
326 }
327 
328 static ion_bpp_err_t
330  ion_bpp_handle_t handle,
332  ion_bpp_buffer_t **b
333 ) {
334  ion_bpp_h_node_t *h = handle;
335  /* read data into buf */
336  int len;
337  ion_bpp_buffer_t *buf; /* buffer */
338  ion_bpp_err_t rc; /* return code */
339 
340  if ((rc = assignBuf(handle, adr, &buf)) != 0) {
341  return rc;
342  }
343 
344  if (!buf->valid) {
345  len = h->sectorSize;
346 
347  if (adr == 0) {
348  len *= 3; /* root */
349  }
350 
351  ion_err_t err = ion_fread_at(h->fp, adr, len, (ion_byte_t *) buf->p);
352 
353  if (err_ok != err) {
354  return error(bErrIO);
355  }
356 
357  buf->modified = boolean_false;
358  buf->valid = boolean_true;
359  nDiskReads++;
360 
361 #if 0
362  len = 1;
363 
364  if (adr == 0) {
365  len = 3;/* root */
366  }
367 
368  if (0 != fseek(h->fp, buf->adr, SEEK_SET)) {
369  return error(bErrIO);
370  }
371 
372  for (i = 0; i < len; i++) {
373  if (1 != fread(&buf[i].p->leaf, sizeof(buf->p->leaf), 1, h->fp)) {
374  return error(bErrIO);
375  }
376 
377  if (1 != fread(&buf[i].p->ct, sizeof(buf->p->ct), 1, h->fp)) {
378  return error(bErrIO);
379  }
380 
381  if (1 != fread(&buf[i].p->prev, sizeof(buf->p->prev), 1, h->fp)) {
382  return error(bErrIO);
383  }
384 
385  if (1 != fread(&buf[i].p->next, sizeof(buf->p->next), 1, h->fp)) {
386  return error(bErrIO);
387  }
388 
389  if (1 != fread(&buf[i].p->childLT, sizeof(buf->p->childLT), 1, h->fp)) {
390  return error(bErrIO);
391  }
392 
393  if (1 != fread(&buf[i].p->fkey, sizeof(buf->p->fkey), 1, h->fp)) {
394  return error(bErrIO);
395  }
396  }
397 
398 #endif
399 
400  buf->modified = boolean_false;
401  buf->valid = boolean_true;
402  nDiskReads++;
403  }
404 
405  *b = buf;
406  return bErrOk;
407 }
408 
410 
411 static int
413  ion_bpp_handle_t handle,
414  ion_bpp_buffer_t *buf,
415  void *key,
417  ion_bpp_key_t **mkey,
418  ion_bpp_mode_e mode
419 ) {
420  /*
421  * input:
422  * p pointer to node
423  * key key to find
424  * rec record address (dupkey only)
425  * output:
426  * k pointer to ion_bpp_key_t info
427  * returns:
428  * CC_EQ key = mkey
429  * CC_LT key < mkey
430  * CC_GT key > mkey
431  */
432  ion_bpp_h_node_t *h = handle;
433  int cc; /* condition code */
434  int m; /* midpoint of search */
435  int lb; /* lower-bound of binary search */
436  int ub; /* upper-bound of binary search */
437  ion_bpp_bool_t foundDup; /* true if found a duplicate key */
438 
439  /* scan current node for key using binary search */
440  foundDup = boolean_false;
441  lb = 0;
442  ub = ct(buf) - 1;
443 
444  while (lb <= ub) {
445  m = (lb + ub) / 2;
446  *mkey = fkey(buf) + ks(m);
447  cc = h->comp(key, key(*mkey), (ion_key_size_t) (h->keySize));
448 
449  if ((cc < 0) || ((cc == 0) && (MODE_FGEQ == mode))) {
450  /* key less than key[m] */
451  ub = m - 1;
452  }
453  else if ((cc > 0) || ((cc == 0) && (MODE_LLEQ == mode))) {
454  /* key greater than key[m] */
455  lb = m + 1;
456  }
457  else {
458  /* keys match */
459  if (h->dupKeys) {
460  switch (mode) {
461  case MODE_FIRST:
462  /* backtrack to first key */
463  ub = m - 1;
464 
465  if (lb > ub) {
466  return ION_CC_EQ;
467  }
468 
469  foundDup = boolean_true;
470  break;
471 
472  case MODE_MATCH:
473 
474  /* rec's must also match */
475  if (rec < rec(*mkey)) {
476  ub = m - 1;
477  cc = ION_CC_LT;
478  }
479  else if (rec > rec(*mkey)) {
480  lb = m + 1;
481  cc = ION_CC_GT;
482  }
483  else {
484  return ION_CC_EQ;
485  }
486 
487  break;
488 
489  case MODE_FGEQ:
490  case MODE_LLEQ: /* nop */
491  break;
492  }
493  }
494  else {
495  return cc;
496  }
497  }
498  }
499 
500  if (ct(buf) == 0) {
501  /* empty list */
502  *mkey = fkey(buf);
503  return ION_CC_LT;
504  }
505 
506  if (h->dupKeys && (mode == MODE_FIRST) && foundDup) {
507  /* next key is first key in set of duplicates */
508  *mkey += ks(1);
509  return ION_CC_EQ;
510  }
511 
512  if (MODE_LLEQ == mode) {
513  *mkey = fkey(buf) + ks(ub + 1);
514  cc = h->comp(key, key(*mkey), (ion_key_size_t) (h->keySize));
515 
516  if ((ub == ct(buf) - 1) || ((ub != -1) && (cc <= 0))) {
517  *mkey = fkey(buf) + ks(ub);
518  cc = h->comp(key, key(*mkey), (ion_key_size_t) (h->keySize));
519  }
520 
521  return cc;
522  }
523 
524  if (MODE_FGEQ == mode) {
525  *mkey = fkey(buf) + ks(lb);
526  cc = h->comp(key, key(*mkey), (ion_key_size_t) (h->keySize));
527 
528  if ((lb < ct(buf) - 1) && (cc < 0)) {
529  *mkey = fkey(buf) + ks(lb + 1);
530  cc = h->comp(key, key(*mkey), (ion_key_size_t) (h->keySize));
531  }
532 
533  return cc;
534  }
535 
536  /* didn't find key */
537  return cc;
538 }
539 
540 static ion_bpp_err_t
542  ion_bpp_handle_t handle
543 ) {
544  ion_bpp_h_node_t *h = handle;
545  ion_bpp_buffer_t *gbuf;
546  ion_bpp_buffer_t *root;
547 
548  /* scatter gbuf to root */
549 
550  root = &h->root;
551  gbuf = &h->gbuf;
552  memcpy(fkey(root), fkey(gbuf), ks(ct(gbuf)));
553  childLT(fkey(root)) = childLT(fkey(gbuf));
554  ct(root) = ct(gbuf);
555  leaf(root) = leaf(gbuf);
556  return bErrOk;
557 }
558 
559 static ion_bpp_err_t
561  ion_bpp_handle_t handle,
562  ion_bpp_buffer_t *pbuf,
563  ion_bpp_key_t *pkey,
564  int is,
565  ion_bpp_buffer_t **tmp
566 ) {
567  ion_bpp_h_node_t *h = handle;
568  ion_bpp_buffer_t *gbuf; /* gather buf */
569  ion_bpp_key_t *gkey; /* gather buf key */
570  ion_bpp_err_t rc; /* return code */
571  int iu; /* number of tmp's used */
572  int k0Min; /* min #keys that can be mapped to tmp[0] */
573  int knMin; /* min #keys that can be mapped to tmp[1..3] */
574  int k0Max; /* max #keys that can be mapped to tmp[0] */
575  int knMax; /* max #keys that can be mapped to tmp[1..3] */
576  int sw; /* shift width */
577  int len; /* length of remainder of buf */
578  int base; /* base count distributed to tmps */
579  int extra; /* extra counts */
580  int ct;
581  int i;
582 
583  /*
584  * input:
585  * pbuf parent buffer of gathered keys
586  * pkey where we insert a key if needed in parent
587  * is number of supplied tmps
588  * tmp array of tmp's to be used for scattering
589  * output:
590  * tmp array of tmp's used for scattering
591  */
592 
593  /* scatter gbuf to tmps, placing 3/4 max in each tmp */
594 
595  gbuf = &h->gbuf;
596  gkey = fkey(gbuf);
597  ct = ct(gbuf);
598 
599  /****************************************
600  * determine number of tmps to use (iu) *
601  ****************************************/
602  iu = is;
603 
604  /* determine limits */
605  if (leaf(gbuf)) {
606  /* minus 1 to allow for insertion */
607  k0Max = h->maxCt - 1;
608  knMax = h->maxCt - 1;
609  /* plus 1 to allow for deletion */
610  k0Min = (h->maxCt / 2) + 1;
611  knMin = (h->maxCt / 2) + 1;
612  }
613  else {
614  /* can hold an extra gbuf key as it's translated to a LT pointer */
615  k0Max = h->maxCt - 1;
616  knMax = h->maxCt;
617  k0Min = (h->maxCt / 2) + 1;
618  knMin = ((h->maxCt + 1) / 2) + 1;
619  }
620 
621  /* calculate iu, number of tmps to use */
622  while (1) {
623  if ((iu == 0) || (ct > (k0Max + (iu - 1) * knMax))) {
624  /* add a buffer */
625  if ((rc = assignBuf(handle, allocAdr(handle), &tmp[iu])) != 0) {
626  return rc;
627  }
628 
629  /* update sequential links */
630  if (leaf(gbuf)) {
631  /* adjust sequential links */
632  if (iu == 0) {
633  /* no tmps supplied when splitting root for first time */
634  prev(tmp[0]) = 0;
635  next(tmp[0]) = 0;
636  }
637  else {
638  prev(tmp[iu]) = tmp[iu - 1]->adr;
639  next(tmp[iu]) = next(tmp[iu - 1]);
640  next(tmp[iu - 1]) = tmp[iu]->adr;
641  }
642  }
643 
644  iu++;
645  nNodesIns++;
646  }
647  else if ((iu > 1) && (ct < (k0Min + (iu - 1) * knMin))) {
648  /* del a buffer */
649  iu--;
650 
651  /* adjust sequential links */
652  if (leaf(gbuf) && tmp[iu - 1]->adr) {
653  next(tmp[iu - 1]) = next(tmp[iu]);
654  }
655 
656  next(tmp[iu - 1]) = next(tmp[iu]);
657  nNodesDel++;
658  }
659  else {
660  break;
661  }
662  }
663 
664  /* establish count for each tmp used */
665  base = ct / iu;
666  extra = ct % iu;
667 
668  for (i = 0; i < iu; i++) {
669  int n;
670 
671  n = base;
672 
673  /* distribute extras, one at a time */
674  /* don't do to 1st node, as it may be internal and can't hold it */
675  if (i && extra) {
676  n++;
677  extra--;
678  }
679 
680  ct(tmp[i]) = n;
681  }
682 
683  /**************************************
684  * update sequential links and parent *
685  **************************************/
686  if (iu != is) {
687  /* link last node to next */
688  if (leaf(gbuf) && next(tmp[iu - 1])) {
689  ion_bpp_buffer_t *buf;
690 
691  if ((rc = readDisk(handle, next(tmp[iu - 1]), &buf)) != 0) {
692  return rc;
693  }
694 
695  prev(buf) = tmp[iu - 1]->adr;
696 
697  if ((rc = writeDisk(buf)) != 0) {
698  return rc;
699  }
700  }
701 
702  /* shift keys in parent */
703  sw = ks(iu - is);
704 
705  if (sw < 0) {
706  len = ks(ct(pbuf)) - (pkey - fkey(pbuf)) + sw;
707  memmove(pkey, pkey - sw, len);
708  }
709  else {
710  len = ks(ct(pbuf)) - (pkey - fkey(pbuf));
711  memmove(pkey + sw, pkey, len);
712  }
713 
714  /* don't count LT buffer for empty parent */
715  if (ct(pbuf)) {
716  ct(pbuf) += iu - is;
717  }
718  else {
719  ct(pbuf) += iu - is - 1;
720  }
721  }
722 
723  /*******************************
724  * distribute keys to children *
725  *******************************/
726  for (i = 0; i < iu; i++) {
727  /* update LT pointer and parent nodes */
728  if (leaf(gbuf)) {
729  /* update LT, tmp[i] */
730  childLT(fkey(tmp[i])) = 0;
731 
732  /* update parent */
733  if (i == 0) {
734  childLT(pkey) = tmp[i]->adr;
735  }
736  else {
737  memcpy(pkey, gkey, ks(1));
738  childGE(pkey) = tmp[i]->adr;
739  pkey += ks(1);
740  }
741  }
742  else {
743  if (i == 0) {
744  /* update LT, tmp[0] */
745  childLT(fkey(tmp[i])) = childLT(gkey);
746  /* update LT, parent */
747  childLT(pkey) = tmp[i]->adr;
748  }
749  else {
750  /* update LT, tmp[i] */
751  childLT(fkey(tmp[i])) = childGE(gkey);
752  /* update parent key */
753  memcpy(pkey, gkey, ks(1));
754  childGE(pkey) = tmp[i]->adr;
755  gkey += ks(1);
756  pkey += ks(1);
757  ct(tmp[i])--;
758  }
759  }
760 
761  /* install keys, tmp[i] */
762  memcpy(fkey(tmp[i]), gkey, ks(ct(tmp[i])));
763  leaf(tmp[i]) = leaf(gbuf);
764 
765  gkey += ks(ct(tmp[i]));
766  }
767 
768  leaf(pbuf) = boolean_false;
769 
770  /************************
771  * write modified nodes *
772  ************************/
773  if ((rc = writeDisk(pbuf)) != 0) {
774  return rc;
775  }
776 
777  for (i = 0; i < iu; i++) {
778  if ((rc = writeDisk(tmp[i])) != 0) {
779  return rc;
780  }
781  }
782 
783  return bErrOk;
784 }
785 
786 static ion_bpp_err_t
788  ion_bpp_handle_t handle
789 ) {
790  ion_bpp_h_node_t *h = handle;
791  ion_bpp_buffer_t *gbuf;
792  ion_bpp_buffer_t *root;
793 
794  /* gather root to gbuf */
795  root = &h->root;
796  gbuf = &h->gbuf;
797  memcpy(p(gbuf), root->p, 3 * h->sectorSize);
798  leaf(gbuf) = leaf(root);
799  ct(root) = 0;
800  return bErrOk;
801 }
802 
803 static ion_bpp_err_t
805  ion_bpp_handle_t handle,
806  ion_bpp_buffer_t *pbuf,
807  ion_bpp_key_t **pkey,
808  ion_bpp_buffer_t **tmp
809 ) {
810  ion_bpp_h_node_t *h = handle;
811  ion_bpp_err_t rc; /* return code */
812  ion_bpp_buffer_t *gbuf;
813  ion_bpp_key_t *gkey;
814 
815  /*
816  * input:
817  * pbuf parent buffer
818  * pkey pointer to match key in parent
819  * output:
820  * tmp buffers to use for scatter
821  * pkey pointer to match key in parent
822  * returns:
823  * bErrOk operation successful
824  * notes:
825  * Gather 3 buffers to gbuf. Setup for subsequent scatter by
826  * doing the following:
827  * - setup tmp buffer array for scattered buffers
828  * - adjust pkey to point to first key of 3 buffers
829  */
830 
831  /* find 3 adjacent buffers */
832  if (*pkey == lkey(pbuf)) {
833  *pkey -= ks(1);
834  }
835 
836  if ((rc = readDisk(handle, childLT(*pkey), &tmp[0])) != 0) {
837  return rc;
838  }
839 
840  if ((rc = readDisk(handle, childGE(*pkey), &tmp[1])) != 0) {
841  return rc;
842  }
843 
844  if ((rc = readDisk(handle, childGE(*pkey + ks(1)), &tmp[2])) != 0) {
845  return rc;
846  }
847 
848  /* gather nodes to gbuf */
849  gbuf = &h->gbuf;
850  gkey = fkey(gbuf);
851 
852  /* tmp[0] */
853  childLT(gkey) = childLT(fkey(tmp[0]));
854  memcpy(gkey, fkey(tmp[0]), ks(ct(tmp[0])));
855  gkey += ks(ct(tmp[0]));
856  ct(gbuf) = ct(tmp[0]);
857 
858  /* tmp[1] */
859  if (!leaf(tmp[1])) {
860  memcpy(gkey, *pkey, ks(1));
861  childGE(gkey) = childLT(fkey(tmp[1]));
862  ct(gbuf)++;
863  gkey += ks(1);
864  }
865 
866  memcpy(gkey, fkey(tmp[1]), ks(ct(tmp[1])));
867  gkey += ks(ct(tmp[1]));
868  ct(gbuf) += ct(tmp[1]);
869 
870  /* tmp[2] */
871  if (!leaf(tmp[2])) {
872  memcpy(gkey, *pkey + ks(1), ks(1));
873  childGE(gkey) = childLT(fkey(tmp[2]));
874  ct(gbuf)++;
875  gkey += ks(1);
876  }
877 
878  memcpy(gkey, fkey(tmp[2]), ks(ct(tmp[2])));
879  ct(gbuf) += ct(tmp[2]);
880 
881  leaf(gbuf) = leaf(tmp[0]);
882 
883  return bErrOk;
884 }
885 
888  ion_bpp_open_t info,
889  ion_bpp_handle_t *handle
890 ) {
891  ion_bpp_h_node_t *h;
892  ion_bpp_err_t rc; /* return code */
893  int bufCt; /* number of tmp buffers */
894  ion_bpp_buffer_t *buf; /* buffer */
895  int maxCt; /* maximum number of keys in a node */
896  ion_bpp_buffer_t *root;
897  int i;
898  ion_bpp_node_t *p;
899 
900  if ((info.sectorSize < sizeof(ion_bpp_h_node_t)) || (0 != info.sectorSize % 4)) {
901  return bErrSectorSize;
902  }
903 
904  /* determine sizes and offsets */
905  /* leaf/n, prev, next, [childLT,key,rec]... childGE */
906  /* ensure that there are at least 3 children/parent for gather/scatter */
907  maxCt = info.sectorSize - (sizeof(ion_bpp_node_t) - sizeof(ion_bpp_key_t));
908  maxCt /= sizeof(ion_bpp_address_t) + info.keySize + sizeof(ion_bpp_external_address_t);
909 
910  if (maxCt < 6) {
911  return bErrSectorSize;
912  }
913 
914  /* copy parms to ion_bpp_h_node_t */
915  if ((h = calloc(1, sizeof(ion_bpp_h_node_t))) == NULL) {
916  return error(bErrMemory);
917  }
918 
919  h->keySize = info.keySize;
920  h->dupKeys = info.dupKeys;
921  h->sectorSize = info.sectorSize;
922  h->comp = info.comp;
923 
924  /* childLT, key, rec */
925  h->ks = sizeof(ion_bpp_address_t) + h->keySize + sizeof(ion_bpp_external_address_t);
926  h->maxCt = maxCt;
927 
928  /* Allocate buflist.
929  * During insert/delete, need simultaneous access to 7 buffers:
930  * - 4 adjacent child bufs
931  * - 1 parent buf
932  * - 1 next sequential link
933  * - 1 lastGE
934  */
935  bufCt = 7;
936 
937  if ((h->malloc1 = calloc(bufCt, sizeof(ion_bpp_buffer_t))) == NULL) {
938  return error(bErrMemory);
939  }
940 
941  buf = h->malloc1;
942 
943  /*
944  * Allocate bufs.
945  * We need space for the following:
946  * - bufCt buffers, of size sectorSize
947  * - 1 buffer for root, of size 3*sectorSize
948  * - 1 buffer for gbuf, size 3*sectorsize + 2 extra keys
949  * to allow for LT pointers in last 2 nodes when gathering 3 full nodes
950  */
951  if ((h->malloc2 = malloc((bufCt + 6) * h->sectorSize + 2 * h->ks)) == NULL) {
952  return error(bErrMemory);
953  }
954 
955  for (i = 0; i < (bufCt + 6) * h->sectorSize + 2 * h->ks; i++) {
956  ((char *) h->malloc2)[i] = 0;
957  }
958 
959  p = h->malloc2;
960 
961  /* initialize buflist */
962  h->bufList.next = buf;
963  h->bufList.prev = buf + (bufCt - 1);
964 
965  for (i = 0; i < bufCt; i++) {
966  buf->next = buf + 1;
967  buf->prev = buf - 1;
968  buf->modified = boolean_false;
969  buf->valid = boolean_false;
970  buf->p = p;
971  p = (ion_bpp_node_t *) ((char *) p + h->sectorSize);
972  buf++;
973  }
974 
975  h->bufList.next->prev = &h->bufList;
976  h->bufList.prev->next = &h->bufList;
977 
978  /* initialize root */
979  root = &h->root;
980  root->p = p;
981  p = (ion_bpp_node_t *) ((char *) p + 3 * h->sectorSize);
982  h->gbuf.p = p;/* done last to include extra 2 keys */
983 
984  h->curBuf = NULL;
985  h->curKey = NULL;
986 
987  /* initialize root */
988  if (ion_fexists(info.iName)) {
989  /* open an existing database */
990  h->fp = ion_fopen(info.iName);
991 
992  if ((rc = readDisk(h, 0, &root)) != 0) {
993  return rc;
994  }
995 
996  if (ion_fseek(h->fp, 0, ION_FILE_END)) {
997  return error(bErrIO);
998  }
999 
1000  if ((h->nextFreeAdr = ion_ftell(h->fp)) == -1) {
1001  return error(bErrIO);
1002  }
1003  }
1004 
1005 #if defined(ARDUINO)
1006  else if (NULL != (h->fp = ion_fopen(info.iName)).file) {
1007 #else
1008  else if (NULL != (h->fp = ion_fopen(info.iName))) {
1009 #endif
1010  /* initialize root */
1011  memset(root->p, 0, 3 * h->sectorSize);
1012  leaf(root) = 1;
1013  h->nextFreeAdr = 3 * h->sectorSize;
1014  root->modified = 1;
1015  flushAll(h);
1016  }
1017  else {
1018  /* something's wrong */
1019  free(h);
1020  return bErrFileNotOpen;
1021  }
1022 
1023  *handle = h;
1024  return bErrOk;
1025 }
1026 
1029  ion_bpp_handle_t handle
1030 ) {
1031  ion_bpp_h_node_t *h = handle;
1032 
1033  if (h == NULL) {
1034  return bErrOk;
1035  }
1036 
1037  /* flush idx */
1038 #if defined(ARDUINO)
1039 
1040  if (h->fp.file) {
1041 #else
1042 
1043  if (h->fp) {
1044 #endif
1045  flushAll(handle);
1046  ion_fclose(h->fp);
1047  }
1048 
1049  if (h->malloc2) {
1050  free(h->malloc2);
1051  }
1052 
1053  if (h->malloc1) {
1054  free(h->malloc1);
1055  }
1056 
1057  free(h);
1058  return bErrOk;
1059 }
1060 
1063  ion_bpp_handle_t handle,
1064  void *key,
1066 ) {
1067  ion_bpp_key_t *mkey; /* matched key */
1068  ion_bpp_buffer_t *buf; /* buffer */
1069  ion_bpp_err_t rc; /* return code */
1070 
1071  ion_bpp_h_node_t *h = handle;
1072 
1073  buf = &h->root;
1074 
1075  /* find key, and return address */
1076  while (1) {
1077  if (leaf(buf)) {
1078  if (search(handle, buf, key, 0, &mkey, MODE_FIRST) == 0) {
1079  *rec = rec(mkey);
1080  h->curBuf = buf;
1081  h->curKey = mkey;
1082  return bErrOk;
1083  }
1084  else {
1085  return bErrKeyNotFound;
1086  }
1087  }
1088  else {
1089  if (search(handle, buf, key, 0, &mkey, MODE_MATCH) < 0) {
1090  if ((rc = readDisk(handle, childLT(mkey), &buf)) != 0) {
1091  return rc;
1092  }
1093  }
1094  else {
1095  if ((rc = readDisk(handle, childGE(mkey), &buf)) != 0) {
1096  return rc;
1097  }
1098  }
1099  }
1100  }
1101 }
1102 
1105  ion_bpp_handle_t handle,
1106  void *key,
1107  void *mkey,
1109 ) {
1110  ion_bpp_key_t *lgeqkey; /* matched key */
1111  ion_bpp_buffer_t *buf; /* buffer */
1112  ion_bpp_err_t rc; /* return code */
1113  int cc;
1114 
1115  ion_bpp_h_node_t *h = handle;
1116 
1117  buf = &h->root;
1118 
1119  /* find key, and return address */
1120  while (1) {
1121  if (leaf(buf)) {
1122  if ((cc = search(handle, buf, key, 0, &lgeqkey, MODE_LLEQ)) > 0) {
1123  if ((lgeqkey - fkey(buf)) / (h->ks) == (ct(buf))) {
1124  return bErrKeyNotFound;
1125  }
1126 
1127  lgeqkey += ks(1);
1128  }
1129 
1130  h->curBuf = buf;
1131  h->curKey = lgeqkey;
1132  memcpy(mkey, key(lgeqkey), h->keySize);
1133  *rec = rec(lgeqkey);
1134 
1135  return bErrOk;
1136  }
1137  else {
1138  cc = search(handle, buf, key, 0, &lgeqkey, MODE_LLEQ);
1139 
1140  if (cc < 0) {
1141  if ((rc = readDisk(handle, childLT(lgeqkey), &buf)) != 0) {
1142  return rc;
1143  }
1144  }
1145  else {
1146  if ((rc = readDisk(handle, childGE(lgeqkey), &buf)) != 0) {
1147  return rc;
1148  }
1149  }
1150  }
1151  }
1152 }
1153 
1156  ion_bpp_handle_t handle,
1157  void *key,
1159 ) {
1160  int rc; /* return code */
1161  ion_bpp_key_t *mkey; /* match key */
1162  int len; /* length to shift */
1163  int cc; /* condition code */
1164  ion_bpp_buffer_t *buf, *root;
1165  ion_bpp_buffer_t *tmp[4];
1166  unsigned int keyOff;
1167  ion_bpp_bool_t lastGEvalid; /* true if GE branch taken */
1168  ion_bpp_bool_t lastLTvalid; /* true if LT branch taken after GE branch */
1169  ion_bpp_address_t lastGE; /* last childGE traversed */
1170  unsigned int lastGEkey; /* last childGE key traversed */
1171  int height; /* height of tree */
1172 
1173  ion_bpp_h_node_t *h = handle;
1174 
1175  root = &h->root;
1176  lastGEvalid = boolean_false;
1177  lastLTvalid = boolean_false;
1178 
1179  /* check for full root */
1180  if (ct(root) == 3 * h->maxCt) {
1181  /* gather root and scatter to 4 bufs */
1182  /* this increases b-tree height by 1 */
1183  if ((rc = gatherRoot(handle)) != 0) {
1184  return rc;
1185  }
1186 
1187  if ((rc = scatter(handle, root, fkey(root), 0, tmp)) != 0) {
1188  return rc;
1189  }
1190  }
1191 
1192  buf = root;
1193  height = 0;
1194 
1195  while (1) {
1196  if (leaf(buf)) {
1197  /* in leaf, and there' room guaranteed */
1198 
1199  if (height > maxHeight) {
1200  maxHeight = height;
1201  }
1202 
1203  /* set mkey to point to insertion point */
1204  switch (search(handle, buf, key, rec, &mkey, MODE_MATCH)) {
1205  case ION_CC_LT: /* key < mkey */
1206 
1207  if (!h->dupKeys && (0 != ct(buf)) && (h->comp(key, mkey, (ion_key_size_t) (h->keySize)) == ION_CC_EQ)) {
1208  return bErrDupKeys;
1209  }
1210 
1211  break;
1212 
1213  case ION_CC_EQ: /* key = mkey */
1214  return bErrDupKeys;
1215  break;
1216 
1217  case ION_CC_GT: /* key > mkey */
1218 
1219  if (!h->dupKeys && (h->comp(key, mkey, (ion_key_size_t) (h->keySize)) == ION_CC_EQ)) {
1220  return bErrDupKeys;
1221  }
1222 
1223  mkey += ks(1);
1224  break;
1225  }
1226 
1227  /* shift items GE key to right */
1228  keyOff = mkey - fkey(buf);
1229  len = ks(ct(buf)) - keyOff;
1230 
1231  if (len) {
1232  memmove(mkey + ks(1), mkey, len);
1233  }
1234 
1235  /* insert new key */
1236  memcpy(key(mkey), key, h->keySize);
1237  rec(mkey) = rec;
1238  childGE(mkey) = 0;
1239  ct(buf)++;
1240 
1241  if ((rc = writeDisk(buf)) != 0) {
1242  return rc;
1243  }
1244 
1245  /* if new key is first key, then fixup lastGE key */
1246  if (!keyOff && lastLTvalid) {
1247  ion_bpp_buffer_t *tbuf;
1248  ion_bpp_key_t *tkey;
1249 
1250  if ((rc = readDisk(handle, lastGE, &tbuf)) != 0) {
1251  return rc;
1252  }
1253 
1254  /* tkey = fkey(tbuf) + lastGEkey; */
1255  tkey = fkey(tbuf);
1256  memcpy(key(tkey), key, h->keySize);
1257  rec(tkey) = rec;
1258 
1259  if ((rc = writeDisk(tbuf)) != 0) {
1260  return rc;
1261  }
1262  }
1263 
1264  nKeysIns++;
1265  break;
1266  }
1267  else {
1268  /* internal node, descend to child */
1269  ion_bpp_buffer_t *cbuf; /* child buf */
1270 
1271  height++;
1272 
1273  /* read child */
1274  if ((cc = search(handle, buf, key, rec, &mkey, MODE_MATCH)) < 0) {
1275  if ((rc = readDisk(handle, childLT(mkey), &cbuf)) != 0) {
1276  return rc;
1277  }
1278  }
1279  else {
1280  if ((rc = readDisk(handle, childGE(mkey), &cbuf)) != 0) {
1281  return rc;
1282  }
1283  }
1284 
1285  /* check for room in child */
1286  if (ct(cbuf) == h->maxCt) {
1287  /* gather 3 bufs and scatter */
1288  if ((rc = gather(handle, buf, &mkey, tmp)) != 0) {
1289  return rc;
1290  }
1291 
1292  if ((rc = scatter(handle, buf, mkey, 3, tmp)) != 0) {
1293  return rc;
1294  }
1295 
1296  /* read child */
1297  if ((cc = search(handle, buf, key, rec, &mkey, MODE_MATCH)) < 0) {
1298  if ((rc = readDisk(handle, childLT(mkey), &cbuf)) != 0) {
1299  return rc;
1300  }
1301  }
1302  else {
1303  if ((rc = readDisk(handle, childGE(mkey), &cbuf)) != 0) {
1304  return rc;
1305  }
1306  }
1307  }
1308 
1309  if ((cc >= 0) || (mkey != fkey(buf))) {
1310  lastGEvalid = boolean_true;
1311  lastLTvalid = boolean_false;
1312  lastGE = buf->adr;
1313  lastGEkey = mkey - fkey(buf);
1314 
1315  if (cc < 0) {
1316  lastGEkey -= ks(1);
1317  }
1318  }
1319  else {
1320  if (lastGEvalid) {
1321  lastLTvalid = boolean_true;
1322  }
1323  }
1324 
1325  buf = cbuf;
1326  }
1327  }
1328 
1329  return bErrOk;
1330 }
1331 
1334  ion_bpp_handle_t handle,
1335  void *key,
1337 ) {
1338  int rc; /* return code */
1339  ion_bpp_key_t *mkey; /* match key */
1340  int cc; /* condition code */
1341  ion_bpp_buffer_t *buf, *root;
1342  ion_bpp_buffer_t *tmp[4];
1343  int height; /* height of tree */
1344 
1345  ion_bpp_h_node_t *h = handle;
1346 
1347  root = &h->root;
1348 
1349  /* check for full root */
1350  if (ct(root) == 3 * h->maxCt) {
1351  /* gather root and scatter to 4 bufs */
1352  /* this increases b-tree height by 1 */
1353  if ((rc = gatherRoot(handle)) != 0) {
1354  return rc;
1355  }
1356 
1357  if ((rc = scatter(handle, root, fkey(root), 0, tmp)) != 0) {
1358  return rc;
1359  }
1360  }
1361 
1362  buf = root;
1363  height = 0;
1364 
1365  while (1) {
1366  if (leaf(buf)) {
1367  /* in leaf, and there' room guaranteed */
1368 
1369  if (height > maxHeight) {
1370  maxHeight = height;
1371  }
1372 
1373  /* set mkey to point to update point */
1374  switch (search(handle, buf, key, rec, &mkey, MODE_MATCH)) {
1375  case ION_CC_LT: /* key < mkey */
1376  return bErrKeyNotFound;
1377  break;
1378 
1379  case ION_CC_EQ: /* key = mkey */
1380  break;
1381 
1382  case ION_CC_GT: /* key > mkey */
1383  return bErrKeyNotFound;
1384  break;
1385  }
1386 
1387  /* update key */
1388  rec(mkey) = rec;
1389  break;
1390  }
1391  else {
1392  /* internal node, descend to child */
1393  ion_bpp_buffer_t *cbuf; /* child buf */
1394 
1395  height++;
1396 
1397  /* read child */
1398  if ((cc = search(handle, buf, key, rec, &mkey, MODE_MATCH)) < 0) {
1399  if ((rc = readDisk(handle, childLT(mkey), &cbuf)) != 0) {
1400  return rc;
1401  }
1402  }
1403  else {
1404  if ((rc = readDisk(handle, childGE(mkey), &cbuf)) != 0) {
1405  return rc;
1406  }
1407  }
1408 
1409  /* check for room in child */
1410  if (ct(cbuf) == h->maxCt) {
1411  /* gather 3 bufs and scatter */
1412  if ((rc = gather(handle, buf, &mkey, tmp)) != 0) {
1413  return rc;
1414  }
1415 
1416  if ((rc = scatter(handle, buf, mkey, 3, tmp)) != 0) {
1417  return rc;
1418  }
1419 
1420  /* read child */
1421  if ((cc = search(handle, buf, key, rec, &mkey, MODE_MATCH)) < 0) {
1422  if ((rc = readDisk(handle, childLT(mkey), &cbuf)) != 0) {
1423  return rc;
1424  }
1425  }
1426  else {
1427  if ((rc = readDisk(handle, childGE(mkey), &cbuf)) != 0) {
1428  return rc;
1429  }
1430  }
1431  }
1432 
1433  buf = cbuf;
1434  }
1435  }
1436 
1437  return bErrOk;
1438 }
1439 
1442  ion_bpp_handle_t handle,
1443  void *key,
1445 ) {
1446  int rc; /* return code */
1447  ion_bpp_key_t *mkey; /* match key */
1448  int len; /* length to shift */
1449  int cc; /* condition code */
1450  ion_bpp_buffer_t *buf; /* buffer */
1451  ion_bpp_buffer_t *tmp[4];
1452  unsigned int keyOff;
1453  ion_bpp_bool_t lastGEvalid; /* true if GE branch taken */
1454  ion_bpp_bool_t lastLTvalid; /* true if LT branch taken after GE branch */
1455  ion_bpp_address_t lastGE; /* last childGE traversed */
1456  unsigned int lastGEkey; /* last childGE key traversed */
1457  ion_bpp_buffer_t *root;
1458  ion_bpp_buffer_t *gbuf;
1459 
1460  ion_bpp_h_node_t *h = handle;
1461 
1462  root = &h->root;
1463  gbuf = &h->gbuf;
1464  lastGEvalid = boolean_false;
1465  lastLTvalid = boolean_false;
1466 
1467  buf = root;
1468 
1469  while (1) {
1470  if (leaf(buf)) {
1471  /* set mkey to point to deletion point */
1472  if (search(handle, buf, key, *rec, &mkey, MODE_MATCH) == 0) {
1473  *rec = rec(mkey);
1474  }
1475  else {
1476  return bErrKeyNotFound;
1477  }
1478 
1479  /* shift items GT key to left */
1480  keyOff = mkey - fkey(buf);
1481  len = ks(ct(buf) - 1) - keyOff;
1482 
1483  if (len) {
1484  memmove(mkey, mkey + ks(1), len);
1485  }
1486 
1487  ct(buf)--;
1488 
1489  if ((rc = writeDisk(buf)) != 0) {
1490  return rc;
1491  }
1492 
1493  /* if deleted key is first key, then fixup lastGE key */
1494  if (!keyOff && lastLTvalid) {
1495  ion_bpp_buffer_t *tbuf;
1496  ion_bpp_key_t *tkey;
1497 
1498  if ((rc = readDisk(handle, lastGE, &tbuf)) != 0) {
1499  return rc;
1500  }
1501 
1502  tkey = fkey(tbuf) + lastGEkey;
1503  memcpy(key(tkey), mkey, h->keySize);
1504  rec(tkey) = rec(mkey);
1505 
1506  if ((rc = writeDisk(tbuf)) != 0) {
1507  return rc;
1508  }
1509  }
1510 
1511  nKeysDel++;
1512  break;
1513  }
1514  else {
1515  /* internal node, descend to child */
1516  ion_bpp_buffer_t *cbuf; /* child buf */
1517 
1518  /* read child */
1519  if ((cc = search(handle, buf, key, *rec, &mkey, MODE_MATCH)) < 0) {
1520  if ((rc = readDisk(handle, childLT(mkey), &cbuf)) != 0) {
1521  return rc;
1522  }
1523  }
1524  else {
1525  if ((rc = readDisk(handle, childGE(mkey), &cbuf)) != 0) {
1526  return rc;
1527  }
1528  }
1529 
1530  /* check for room to delete */
1531  if (ct(cbuf) == h->maxCt / 2) {
1532  /* gather 3 bufs and scatter */
1533  if ((rc = gather(handle, buf, &mkey, tmp)) != 0) {
1534  return rc;
1535  }
1536 
1537  /* if last 3 bufs in root, and count is low enough... */
1538  if ((buf == root) && (ct(root) == 2) && (ct(gbuf) < (3 * (3 * h->maxCt)) / 4)) {
1539  /* collapse tree by one level */
1540  scatterRoot(handle);
1541  nNodesDel += 3;
1542  continue;
1543  }
1544 
1545  if ((rc = scatter(handle, buf, mkey, 3, tmp)) != 0) {
1546  return rc;
1547  }
1548 
1549  /* read child */
1550  if ((cc = search(handle, buf, key, *rec, &mkey, MODE_MATCH)) < 0) {
1551  if ((rc = readDisk(handle, childLT(mkey), &cbuf)) != 0) {
1552  return rc;
1553  }
1554  }
1555  else {
1556  if ((rc = readDisk(handle, childGE(mkey), &cbuf)) != 0) {
1557  return rc;
1558  }
1559  }
1560  }
1561 
1562  if ((cc >= 0) || (mkey != fkey(buf))) {
1563  lastGEvalid = boolean_true;
1564  lastLTvalid = boolean_false;
1565  lastGE = buf->adr;
1566  lastGEkey = mkey - fkey(buf);
1567 
1568  if (cc < 0) {
1569  lastGEkey -= ks(1);
1570  }
1571  }
1572  else {
1573  if (lastGEvalid) {
1574  lastLTvalid = boolean_true;
1575  }
1576  }
1577 
1578  buf = cbuf;
1579  }
1580  }
1581 
1582  return bErrOk;
1583 }
1584 
1587  ion_bpp_handle_t handle,
1588  void *key,
1590 ) {
1591  ion_bpp_err_t rc; /* return code */
1592  ion_bpp_buffer_t *buf; /* buffer */
1593 
1594  ion_bpp_h_node_t *h = handle;
1595 
1596  buf = &h->root;
1597 
1598  while (!leaf(buf)) {
1599  if ((rc = readDisk(handle, childLT(fkey(buf)), &buf)) != 0) {
1600  return rc;
1601  }
1602  }
1603 
1604  if (ct(buf) == 0) {
1605  return bErrKeyNotFound;
1606  }
1607 
1608  memcpy(key, key(fkey(buf)), h->keySize);
1609  *rec = rec(fkey(buf));
1610  h->curBuf = buf;
1611  h->curKey = fkey(buf);
1612  return bErrOk;
1613 }
1614 
1615 /*
1616  * input:
1617  * handle handle returned by b_open
1618  * output:
1619  * key last key in sequential set
1620  * rec record address
1621  * returns:
1622  * bErrOk operation successful
1623  * bErrKeyNotFound key not found
1624 */
1625 
1628  ion_bpp_handle_t handle,
1629  void *key,
1631 ) {
1632  ion_bpp_err_t rc; /* return code */
1633  ion_bpp_buffer_t *buf; /* buffer */
1634 
1635  ion_bpp_h_node_t *h = handle;
1636 
1637  buf = &h->root;
1638 
1639  while (!leaf(buf)) {
1640  if ((rc = readDisk(handle, childGE(lkey(buf)), &buf)) != 0) {
1641  return rc;
1642  }
1643  }
1644 
1645  if (ct(buf) == 0) {
1646  return bErrKeyNotFound;
1647  }
1648 
1649  memcpy(key, key(lkey(buf)), h->keySize);
1650  *rec = rec(lkey(buf));
1651  h->curBuf = buf;
1652  h->curKey = lkey(buf);
1653  return bErrOk;
1654 }
1655 
1658  ion_bpp_handle_t handle,
1659  void *key,
1661 ) {
1662  ion_bpp_err_t rc; /* return code */
1663  ion_bpp_key_t *nkey; /* next key */
1664  ion_bpp_buffer_t *buf; /* buffer */
1665 
1666  ion_bpp_h_node_t *h = handle;
1667 
1668  if ((buf = h->curBuf) == NULL) {
1669  return bErrKeyNotFound;
1670  }
1671 
1672  if (h->curKey == lkey(buf)) {
1673  /* current key is last key in leaf node */
1674  if (next(buf)) {
1675  /* fetch next set */
1676  if ((rc = readDisk(handle, next(buf), &buf)) != 0) {
1677  return rc;
1678  }
1679 
1680  nkey = fkey(buf);
1681  }
1682  else {
1683  /* no more sets */
1684  return bErrKeyNotFound;
1685  }
1686  }
1687  else {
1688  /* bump to next key */
1689  nkey = h->curKey + ks(1);
1690  }
1691 
1692  memcpy(key, key(nkey), h->keySize);
1693  *rec = rec(nkey);
1694  h->curBuf = buf;
1695  h->curKey = nkey;
1696  return bErrOk;
1697 }
1698 
1699 /*
1700  * input:
1701  * handle handle returned by b_open
1702  * output:
1703  * key key found
1704  * rec record address
1705  * returns:
1706  * bErrOk operation successful
1707  * bErrKeyNotFound key not found
1708 */
1711  ion_bpp_handle_t handle,
1712  void *key,
1714 ) {
1715  ion_bpp_err_t rc; /* return code */
1716  ion_bpp_key_t *pkey; /* previous key */
1717  ion_bpp_key_t *fkey; /* first key */
1718  ion_bpp_buffer_t *buf; /* buffer */
1719 
1720  ion_bpp_h_node_t *h = handle;
1721 
1722  if ((buf = h->curBuf) == NULL) {
1723  return bErrKeyNotFound;
1724  }
1725 
1726  fkey = fkey(buf);
1727 
1728  if (h->curKey == fkey) {
1729  /* current key is first key in leaf node */
1730  if (prev(buf)) {
1731  /* fetch previous set */
1732  if ((rc = readDisk(handle, prev(buf), &buf)) != 0) {
1733  return rc;
1734  }
1735 
1736  pkey = fkey(buf) + ks((ct(buf) - 1));
1737  }
1738  else {
1739  /* no more sets */
1740  return bErrKeyNotFound;
1741  }
1742  }
1743  else {
1744  /* bump to previous key */
1745  pkey = h->curKey - ks(1);
1746  }
1747 
1748  memcpy(key, key(pkey), h->keySize);
1749  *rec = rec(pkey);
1750  h->curBuf = buf;
1751  h->curKey = pkey;
1752  return bErrOk;
1753 }
ion_bpp_bool_t dupKeys
Definition: bpp_tree.h:104
ion_bpp_err_t b_close(ion_bpp_handle_t handle)
Definition: bpp_tree.c:1028
unsigned char ion_byte_t
A byte type.
Definition: kv_system.h:232
enum ION_BPP_ERR ion_bpp_err_t
ion_boolean_e ion_bpp_bool_t
Definition: bpp_tree.h:91
ion_bpp_err_t b_insert(ion_bpp_handle_t handle, void *key, ion_bpp_external_address_t rec)
Definition: bpp_tree.c:1155
static ion_bpp_err_t lineError(int lineno, ion_bpp_err_t rc)
Definition: bpp_tree.c:142
static ion_bpp_err_t gather(ion_bpp_handle_t handle, ion_bpp_buffer_t *pbuf, ion_bpp_key_t **pkey, ion_bpp_buffer_t **tmp)
Definition: bpp_tree.c:804
ion_boolean_t ion_fexists(char *name)
Definition: ion_file.c:40
int nDiskReads
Definition: bpp_tree.h:85
#define childGE(k)
Definition: bpp_tree.c:77
int nKeysDel
Definition: bpp_tree.h:84
ion_bpp_address_t childLT
Definition: bpp_tree.c:105
#define ks(ct)
Definition: bpp_tree.c:89
ion_bpp_node_t * p
Definition: bpp_tree.c:115
ion_bpp_address_t prev
Definition: bpp_tree.c:103
ion_file_handle_t fp
Definition: bpp_tree.c:122
int maxHeight
Definition: bpp_tree.h:80
int nNodesDel
Definition: bpp_tree.h:82
ion_bpp_err_t b_find_last_key(ion_bpp_handle_t handle, void *key, ion_bpp_external_address_t *rec)
Definition: bpp_tree.c:1627
#define ION_FILE_END
Definition: ion_file.h:50
static ion_bpp_err_t flush(ion_bpp_handle_t handle, ion_bpp_buffer_t *buf)
Definition: bpp_tree.c:168
ion_bpp_err_t b_get(ion_bpp_handle_t handle, void *key, ion_bpp_external_address_t *rec)
Definition: bpp_tree.c:1062
#define key(k)
Definition: bpp_tree.c:75
ION_BPP_MODE
Definition: bpp_tree.c:409
static ion_bpp_err_t assignBuf(ion_bpp_handle_t handle, ion_bpp_address_t adr, ion_bpp_buffer_t **b)
Definition: bpp_tree.c:264
size_t sectorSize
Definition: bpp_tree.h:105
ion_bpp_buffer_t root
Definition: bpp_tree.c:127
char ion_err_t
The error type used to store error codes.
Definition: kv_system.h:226
static ion_bpp_err_t writeDisk(ion_bpp_buffer_t *buf)
Definition: bpp_tree.c:319
FILE * ion_file_handle_t
Definition: ion_file.h:69
long ion_bpp_address_t
Definition: bpp_tree.h:56
ion_err_t ion_fseek(ion_file_handle_t file, ion_file_offset_t seek_to, int origin)
Definition: ion_file.c:109
#define fkey(b)
Definition: bpp_tree.c:84
ion_bpp_key_t fkey
Definition: bpp_tree.c:107
int nDiskWrites
Definition: bpp_tree.h:86
#define lkey(b)
Definition: bpp_tree.c:85
ion_bpp_address_t adr
Definition: bpp_tree.c:114
char(* ion_bpp_comparison_t)(ion_key_t key1, ion_key_t key2, ion_key_size_t size)
Definition: bpp_tree.h:67
ion_bpp_comparison_t comp
Definition: bpp_tree.h:106
int nKeysIns
Definition: bpp_tree.h:83
unsigned int leaf
Definition: bpp_tree.c:101
ion_file_handle_t ion_fopen(char *name)
Definition: ion_file.c:51
ion_bpp_buffer_t gbuf
Definition: bpp_tree.c:131
#define ION_CC_LT
Definition: bpp_tree.h:60
ion_bpp_err_t b_open(ion_bpp_open_t info, ion_bpp_handle_t *handle)
Definition: bpp_tree.c:887
char ion_bpp_key_t
Definition: bpp_tree.c:91
static ion_bpp_address_t allocAdr(ion_bpp_handle_t handle)
Definition: bpp_tree.c:156
ion_bpp_address_t nextFreeAdr
Definition: bpp_tree.c:136
long ion_bpp_external_address_t
Definition: bpp_tree.h:55
void * ion_bpp_handle_t
Definition: bpp_tree.h:98
#define leaf(b)
Definition: bpp_tree.c:80
static ion_bpp_err_t gatherRoot(ion_bpp_handle_t handle)
Definition: bpp_tree.c:787
static int search(ion_bpp_handle_t handle, ion_bpp_buffer_t *buf, void *key, ion_bpp_external_address_t rec, ion_bpp_key_t **mkey, ion_bpp_mode_e mode)
Definition: bpp_tree.c:412
#define ct(b)
Definition: bpp_tree.c:81
ion_err_t ion_fclose(ion_file_handle_t file)
Definition: ion_file.c:80
ion_bpp_bool_t dupKeys
Definition: bpp_tree.c:124
ion_bpp_err_t b_find_prev_key(ion_bpp_handle_t handle, void *key, ion_bpp_external_address_t *rec)
Definition: bpp_tree.c:1710
unsigned int maxCt
Definition: bpp_tree.c:134
#define ION_CC_EQ
Definition: bpp_tree.h:58
ion_bpp_bool_t valid
Definition: bpp_tree.c:116
ion_bpp_err_t b_update(ion_bpp_handle_t handle, void *key, ion_bpp_external_address_t rec)
Definition: bpp_tree.c:1333
struct ion_bpp_buffer_tag * next
Definition: bpp_tree.c:112
ion_bpp_buffer_t bufList
Definition: bpp_tree.c:128
static ion_bpp_err_t readDisk(ion_bpp_handle_t handle, ion_bpp_address_t adr, ion_bpp_buffer_t **b)
Definition: bpp_tree.c:329
#define error(rc)
Definition: bpp_tree.c:139
ion_bpp_buffer_t * curBuf
Definition: bpp_tree.c:132
struct ion_bpp_buffer_tag * prev
Definition: bpp_tree.c:113
ion_err_t ion_fwrite_at(ion_file_handle_t file, ion_file_offset_t offset, unsigned int num_bytes, ion_byte_t *to_write)
Definition: ion_file.c:177
#define childLT(k)
Definition: bpp_tree.c:74
unsigned int ct
Definition: bpp_tree.c:102
ion_bpp_bool_t modified
Definition: bpp_tree.c:117
int bErrLineNo
Definition: bpp_tree.h:89
#define rec(k)
Definition: bpp_tree.c:76
int ion_key_size_t
The size (length) of a dictionary key in bytes.
Definition: kv_system.h:251
ion_file_offset_t ion_ftell(ion_file_handle_t file)
Definition: ion_file.c:132
struct ion_bpp_buffer_tag ion_bpp_buffer_t
#define ION_CC_GT
Definition: bpp_tree.h:59
ion_bpp_err_t b_find_first_key(ion_bpp_handle_t handle, void *key, ion_bpp_external_address_t *rec)
Definition: bpp_tree.c:1586
ion_err_t ion_fread_at(ion_file_handle_t file, ion_file_offset_t offset, unsigned int num_bytes, ion_byte_t *write_to)
Definition: ion_file.c:237
ion_bpp_err_t b_delete(ion_bpp_handle_t handle, void *key, ion_bpp_external_address_t *rec)
Definition: bpp_tree.c:1441
int nNodesIns
Definition: bpp_tree.h:81
ion_bpp_key_t * curKey
Definition: bpp_tree.c:133
ion_bpp_err_t b_find_first_greater_or_equal(ion_bpp_handle_t handle, void *key, void *mkey, ion_bpp_external_address_t *rec)
Definition: bpp_tree.c:1104
ion_bpp_address_t next
Definition: bpp_tree.c:104
char * iName
Definition: bpp_tree.h:102
static ion_bpp_err_t flushAll(ion_bpp_handle_t handle)
Definition: bpp_tree.c:235
enum ION_BPP_MODE ion_bpp_mode_e
struct ion_bpp_h_node_tag ion_bpp_h_node_t
static ion_bpp_err_t scatterRoot(ion_bpp_handle_t handle)
Definition: bpp_tree.c:541
ion_bpp_comparison_t comp
Definition: bpp_tree.c:126
ion_bpp_err_t b_find_next_key(ion_bpp_handle_t handle, void *key, ion_bpp_external_address_t *rec)
Definition: bpp_tree.c:1657
static ion_bpp_err_t scatter(ion_bpp_handle_t handle, ion_bpp_buffer_t *pbuf, ion_bpp_key_t *pkey, int is, ion_bpp_buffer_t **tmp)
Definition: bpp_tree.c:560