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