bpp_tree.c File Reference
#include "bpp_tree.h"

Description

Author
public domain code
Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions are met:
1.Redistributions of source code must retain the above copyright notice,
this list of conditions and the following disclaimer.
2.Redistributions in binary form must reproduce the above copyright notice,
this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.
3.Neither the name of the copyright holder nor the names of its contributors
may be used to endorse or promote products derived from this software without specific prior written permission.
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

Definition in file bpp_tree.c.

Include dependency graph for bpp_tree.c:

Classes

struct  ion_bpp_node_t
 
struct  ion_bpp_buffer_tag
 
struct  ion_bpp_h_node_tag
 

Macros

#define bAdr(p)   *(ion_bpp_address_t *) (p)
 
#define eAdr(p)   *(ion_bpp_external_address_t *) (p)
 
#define childLT(k)   bAdr((char *) k - sizeof(ion_bpp_address_t))
 
#define key(k)   (k)
 
#define rec(k)   eAdr((char *) (k) + h->keySize)
 
#define childGE(k)   bAdr((char *) (k) + h->keySize + sizeof(ion_bpp_external_address_t))
 
#define leaf(b)   b->p->leaf
 
#define ct(b)   b->p->ct
 
#define next(b)   b->p->next
 
#define prev(b)   b->p->prev
 
#define fkey(b)   & b->p->fkey
 
#define lkey(b)   (fkey(b) + ks((ct(b) - 1)))
 
#define p(b)   (char *) (b->p)
 
#define ks(ct)   ((ct) * h->ks)
 
#define error(rc)   lineError(__LINE__, rc)
 

Typedefs

typedef char ion_bpp_key_t
 
typedef struct ion_bpp_buffer_tag ion_bpp_buffer_t
 
typedef struct ion_bpp_h_node_tag ion_bpp_h_node_t
 
typedef enum ION_BPP_MODE ion_bpp_mode_e
 

Enumerations

enum  ION_BPP_MODE { MODE_FIRST, MODE_MATCH, MODE_FGEQ, MODE_LLEQ }
 

Functions

static ion_bpp_err_t lineError (int lineno, ion_bpp_err_t rc)
 
static ion_bpp_address_t allocAdr (ion_bpp_handle_t handle)
 
static ion_bpp_err_t flush (ion_bpp_handle_t handle, ion_bpp_buffer_t *buf)
 
static ion_bpp_err_t flushAll (ion_bpp_handle_t handle)
 
static ion_bpp_err_t assignBuf (ion_bpp_handle_t handle, ion_bpp_address_t adr, ion_bpp_buffer_t **b)
 
static ion_bpp_err_t writeDisk (ion_bpp_buffer_t *buf)
 
static ion_bpp_err_t readDisk (ion_bpp_handle_t handle, ion_bpp_address_t adr, ion_bpp_buffer_t **b)
 
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)
 
static ion_bpp_err_t scatterRoot (ion_bpp_handle_t handle)
 
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)
 
static ion_bpp_err_t gatherRoot (ion_bpp_handle_t handle)
 
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)
 
ion_bpp_err_t b_open (ion_bpp_open_t info, ion_bpp_handle_t *handle)
 
ion_bpp_err_t b_close (ion_bpp_handle_t handle)
 
ion_bpp_err_t b_get (ion_bpp_handle_t handle, void *key, ion_bpp_external_address_t *rec)
 
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)
 
ion_bpp_err_t b_insert (ion_bpp_handle_t handle, void *key, ion_bpp_external_address_t rec)
 
ion_bpp_err_t b_update (ion_bpp_handle_t handle, void *key, ion_bpp_external_address_t rec)
 
ion_bpp_err_t b_delete (ion_bpp_handle_t handle, void *key, ion_bpp_external_address_t *rec)
 
ion_bpp_err_t b_find_first_key (ion_bpp_handle_t handle, void *key, ion_bpp_external_address_t *rec)
 
ion_bpp_err_t b_find_last_key (ion_bpp_handle_t handle, void *key, ion_bpp_external_address_t *rec)
 
ion_bpp_err_t b_find_next_key (ion_bpp_handle_t handle, void *key, ion_bpp_external_address_t *rec)
 
ion_bpp_err_t b_find_prev_key (ion_bpp_handle_t handle, void *key, ion_bpp_external_address_t *rec)
 

Macro Definition Documentation

#define bAdr (   p)    *(ion_bpp_address_t *) (p)

Definition at line 70 of file bpp_tree.c.

#define childGE (   k)    bAdr((char *) (k) + h->keySize + sizeof(ion_bpp_external_address_t))

Definition at line 77 of file bpp_tree.c.

#define childLT (   k)    bAdr((char *) k - sizeof(ion_bpp_address_t))

Definition at line 74 of file bpp_tree.c.

#define ct (   b)    b->p->ct

Definition at line 81 of file bpp_tree.c.

#define eAdr (   p)    *(ion_bpp_external_address_t *) (p)

Definition at line 71 of file bpp_tree.c.

#define error (   rc)    lineError(__LINE__, rc)

Definition at line 139 of file bpp_tree.c.

#define fkey (   b)    & b->p->fkey

Definition at line 84 of file bpp_tree.c.

#define key (   k)    (k)

Definition at line 75 of file bpp_tree.c.

#define ks (   ct)    ((ct) * h->ks)

Definition at line 89 of file bpp_tree.c.

#define leaf (   b)    b->p->leaf

Definition at line 80 of file bpp_tree.c.

#define lkey (   b)    (fkey(b) + ks((ct(b) - 1)))

Definition at line 85 of file bpp_tree.c.

#define next (   b)    b->p->next

Definition at line 82 of file bpp_tree.c.

#define p (   b)    (char *) (b->p)

Definition at line 86 of file bpp_tree.c.

#define prev (   b)    b->p->prev

Definition at line 83 of file bpp_tree.c.

#define rec (   k)    eAdr((char *) (k) + h->keySize)

Definition at line 76 of file bpp_tree.c.

Typedef Documentation

typedef char ion_bpp_key_t

Definition at line 91 of file bpp_tree.c.

Enumeration Type Documentation

Enumerator
MODE_FIRST 
MODE_MATCH 
MODE_FGEQ 
MODE_LLEQ 

Definition at line 409 of file bpp_tree.c.

Function Documentation

static ion_bpp_address_t allocAdr ( ion_bpp_handle_t  handle)
static

Definition at line 156 of file bpp_tree.c.

158  {
159  ion_bpp_h_node_t *h = handle;
160  ion_bpp_address_t adr;
161 
162  adr = h->nextFreeAdr;
163  h->nextFreeAdr += h->sectorSize;
164  return adr;
165 }
long ion_bpp_address_t
Definition: bpp_tree.h:56
ion_bpp_address_t nextFreeAdr
Definition: bpp_tree.c:136

Here is the caller graph for this function:

static ion_bpp_err_t assignBuf ( ion_bpp_handle_t  handle,
ion_bpp_address_t  adr,
ion_bpp_buffer_t **  b 
)
static

Definition at line 264 of file bpp_tree.c.

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 }
enum ION_BPP_ERR ion_bpp_err_t
static ion_bpp_err_t flush(ion_bpp_handle_t handle, ion_bpp_buffer_t *buf)
Definition: bpp_tree.c:168
ion_bpp_buffer_t root
Definition: bpp_tree.c:127
ion_bpp_address_t adr
Definition: bpp_tree.c:114
ion_bpp_bool_t valid
Definition: bpp_tree.c:116
struct ion_bpp_buffer_tag * next
Definition: bpp_tree.c:112
ion_bpp_buffer_t bufList
Definition: bpp_tree.c:128
struct ion_bpp_buffer_tag * prev
Definition: bpp_tree.c:113
ion_bpp_bool_t modified
Definition: bpp_tree.c:117

Here is the call graph for this function:

Here is the caller graph for this function:

ion_bpp_err_t b_close ( ion_bpp_handle_t  handle)

Definition at line 1028 of file bpp_tree.c.

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 }
ion_file_handle_t fp
Definition: bpp_tree.c:122
ion_err_t ion_fclose(ion_file_handle_t file)
Definition: ion_file.c:80
static ion_bpp_err_t flushAll(ion_bpp_handle_t handle)
Definition: bpp_tree.c:235

Here is the call graph for this function:

Here is the caller graph for this function:

ion_bpp_err_t b_delete ( ion_bpp_handle_t  handle,
void *  key,
ion_bpp_external_address_t rec 
)

Definition at line 1441 of file bpp_tree.c.

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 }
ion_boolean_e ion_bpp_bool_t
Definition: bpp_tree.h:91
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
#define childGE(k)
Definition: bpp_tree.c:77
int nKeysDel
Definition: bpp_tree.h:84
#define ks(ct)
Definition: bpp_tree.c:89
int nNodesDel
Definition: bpp_tree.h:82
#define key(k)
Definition: bpp_tree.c:75
ion_bpp_buffer_t root
Definition: bpp_tree.c:127
static ion_bpp_err_t writeDisk(ion_bpp_buffer_t *buf)
Definition: bpp_tree.c:319
long ion_bpp_address_t
Definition: bpp_tree.h:56
#define fkey(b)
Definition: bpp_tree.c:84
ion_bpp_address_t adr
Definition: bpp_tree.c:114
ion_bpp_buffer_t gbuf
Definition: bpp_tree.c:131
char ion_bpp_key_t
Definition: bpp_tree.c:91
#define leaf(b)
Definition: bpp_tree.c:80
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
unsigned int maxCt
Definition: bpp_tree.c:134
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 childLT(k)
Definition: bpp_tree.c:74
#define rec(k)
Definition: bpp_tree.c:76
static ion_bpp_err_t scatterRoot(ion_bpp_handle_t handle)
Definition: bpp_tree.c:541
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

Here is the call graph for this function:

Here is the caller graph for this function:

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 at line 1104 of file bpp_tree.c.

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 }
enum ION_BPP_ERR ion_bpp_err_t
#define childGE(k)
Definition: bpp_tree.c:77
#define ks(ct)
Definition: bpp_tree.c:89
#define key(k)
Definition: bpp_tree.c:75
ion_bpp_buffer_t root
Definition: bpp_tree.c:127
#define fkey(b)
Definition: bpp_tree.c:84
char ion_bpp_key_t
Definition: bpp_tree.c:91
#define leaf(b)
Definition: bpp_tree.c:80
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
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
ion_bpp_buffer_t * curBuf
Definition: bpp_tree.c:132
#define childLT(k)
Definition: bpp_tree.c:74
#define rec(k)
Definition: bpp_tree.c:76
ion_bpp_key_t * curKey
Definition: bpp_tree.c:133

Here is the call graph for this function:

Here is the caller graph for this function:

ion_bpp_err_t b_find_first_key ( ion_bpp_handle_t  handle,
void *  key,
ion_bpp_external_address_t rec 
)

Definition at line 1586 of file bpp_tree.c.

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 }
enum ION_BPP_ERR ion_bpp_err_t
#define key(k)
Definition: bpp_tree.c:75
ion_bpp_buffer_t root
Definition: bpp_tree.c:127
#define fkey(b)
Definition: bpp_tree.c:84
#define leaf(b)
Definition: bpp_tree.c:80
#define ct(b)
Definition: bpp_tree.c:81
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
ion_bpp_buffer_t * curBuf
Definition: bpp_tree.c:132
#define childLT(k)
Definition: bpp_tree.c:74
#define rec(k)
Definition: bpp_tree.c:76
ion_bpp_key_t * curKey
Definition: bpp_tree.c:133

Here is the call graph for this function:

Here is the caller graph for this function:

ion_bpp_err_t b_find_last_key ( ion_bpp_handle_t  handle,
void *  key,
ion_bpp_external_address_t rec 
)

Definition at line 1627 of file bpp_tree.c.

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 }
enum ION_BPP_ERR ion_bpp_err_t
#define childGE(k)
Definition: bpp_tree.c:77
#define key(k)
Definition: bpp_tree.c:75
ion_bpp_buffer_t root
Definition: bpp_tree.c:127
#define lkey(b)
Definition: bpp_tree.c:85
#define leaf(b)
Definition: bpp_tree.c:80
#define ct(b)
Definition: bpp_tree.c:81
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
ion_bpp_buffer_t * curBuf
Definition: bpp_tree.c:132
#define rec(k)
Definition: bpp_tree.c:76
ion_bpp_key_t * curKey
Definition: bpp_tree.c:133

Here is the call graph for this function:

ion_bpp_err_t b_find_next_key ( ion_bpp_handle_t  handle,
void *  key,
ion_bpp_external_address_t rec 
)

Definition at line 1657 of file bpp_tree.c.

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 }
enum ION_BPP_ERR ion_bpp_err_t
#define next(b)
Definition: bpp_tree.c:82
#define ks(ct)
Definition: bpp_tree.c:89
#define key(k)
Definition: bpp_tree.c:75
#define fkey(b)
Definition: bpp_tree.c:84
#define lkey(b)
Definition: bpp_tree.c:85
char ion_bpp_key_t
Definition: bpp_tree.c:91
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
ion_bpp_buffer_t * curBuf
Definition: bpp_tree.c:132
#define rec(k)
Definition: bpp_tree.c:76
ion_bpp_key_t * curKey
Definition: bpp_tree.c:133

Here is the call graph for this function:

Here is the caller graph for this function:

ion_bpp_err_t b_find_prev_key ( ion_bpp_handle_t  handle,
void *  key,
ion_bpp_external_address_t rec 
)

Definition at line 1710 of file bpp_tree.c.

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 }
enum ION_BPP_ERR ion_bpp_err_t
#define ks(ct)
Definition: bpp_tree.c:89
#define key(k)
Definition: bpp_tree.c:75
#define fkey(b)
Definition: bpp_tree.c:84
char ion_bpp_key_t
Definition: bpp_tree.c:91
#define ct(b)
Definition: bpp_tree.c:81
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 prev(b)
Definition: bpp_tree.c:83
ion_bpp_buffer_t * curBuf
Definition: bpp_tree.c:132
#define rec(k)
Definition: bpp_tree.c:76
ion_bpp_key_t * curKey
Definition: bpp_tree.c:133

Here is the call graph for this function:

ion_bpp_err_t b_get ( ion_bpp_handle_t  handle,
void *  key,
ion_bpp_external_address_t rec 
)

Definition at line 1062 of file bpp_tree.c.

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 }
enum ION_BPP_ERR ion_bpp_err_t
#define childGE(k)
Definition: bpp_tree.c:77
#define key(k)
Definition: bpp_tree.c:75
ion_bpp_buffer_t root
Definition: bpp_tree.c:127
char ion_bpp_key_t
Definition: bpp_tree.c:91
#define leaf(b)
Definition: bpp_tree.c:80
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
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
ion_bpp_buffer_t * curBuf
Definition: bpp_tree.c:132
#define childLT(k)
Definition: bpp_tree.c:74
#define rec(k)
Definition: bpp_tree.c:76
ion_bpp_key_t * curKey
Definition: bpp_tree.c:133

Here is the call graph for this function:

Here is the caller graph for this function:

ion_bpp_err_t b_insert ( ion_bpp_handle_t  handle,
void *  key,
ion_bpp_external_address_t  rec 
)

Definition at line 1155 of file bpp_tree.c.

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 }
ion_boolean_e ion_bpp_bool_t
Definition: bpp_tree.h:91
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
#define childGE(k)
Definition: bpp_tree.c:77
#define ks(ct)
Definition: bpp_tree.c:89
int maxHeight
Definition: bpp_tree.h:80
#define key(k)
Definition: bpp_tree.c:75
ion_bpp_buffer_t root
Definition: bpp_tree.c:127
static ion_bpp_err_t writeDisk(ion_bpp_buffer_t *buf)
Definition: bpp_tree.c:319
long ion_bpp_address_t
Definition: bpp_tree.h:56
#define fkey(b)
Definition: bpp_tree.c:84
ion_bpp_address_t adr
Definition: bpp_tree.c:114
int nKeysIns
Definition: bpp_tree.h:83
#define ION_CC_LT
Definition: bpp_tree.h:60
char ion_bpp_key_t
Definition: bpp_tree.c:91
#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_bpp_bool_t dupKeys
Definition: bpp_tree.c:124
unsigned int maxCt
Definition: bpp_tree.c:134
#define ION_CC_EQ
Definition: bpp_tree.h:58
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 childLT(k)
Definition: bpp_tree.c:74
#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
#define ION_CC_GT
Definition: bpp_tree.h:59
ion_bpp_comparison_t comp
Definition: bpp_tree.c:126
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

Here is the call graph for this function:

Here is the caller graph for this function:

ion_bpp_err_t b_open ( ion_bpp_open_t  info,
ion_bpp_handle_t handle 
)

Definition at line 887 of file bpp_tree.c.

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 }
ion_bpp_bool_t dupKeys
Definition: bpp_tree.h:104
enum ION_BPP_ERR ion_bpp_err_t
ion_boolean_t ion_fexists(char *name)
Definition: ion_file.c:40
ion_bpp_node_t * p
Definition: bpp_tree.c:115
ion_file_handle_t fp
Definition: bpp_tree.c:122
#define ION_FILE_END
Definition: ion_file.h:50
size_t sectorSize
Definition: bpp_tree.h:105
ion_bpp_buffer_t root
Definition: bpp_tree.c:127
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
ion_bpp_comparison_t comp
Definition: bpp_tree.h:106
ion_file_handle_t ion_fopen(char *name)
Definition: ion_file.c:51
ion_bpp_buffer_t gbuf
Definition: bpp_tree.c:131
char ion_bpp_key_t
Definition: bpp_tree.c:91
ion_bpp_address_t nextFreeAdr
Definition: bpp_tree.c:136
long ion_bpp_external_address_t
Definition: bpp_tree.h:55
#define leaf(b)
Definition: bpp_tree.c:80
ion_bpp_bool_t dupKeys
Definition: bpp_tree.c:124
unsigned int maxCt
Definition: bpp_tree.c:134
ion_bpp_bool_t valid
Definition: bpp_tree.c:116
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_bpp_bool_t modified
Definition: bpp_tree.c:117
#define p(b)
Definition: bpp_tree.c:86
ion_file_offset_t ion_ftell(ion_file_handle_t file)
Definition: ion_file.c:132
ion_bpp_key_t * curKey
Definition: bpp_tree.c:133
char * iName
Definition: bpp_tree.h:102
static ion_bpp_err_t flushAll(ion_bpp_handle_t handle)
Definition: bpp_tree.c:235
ion_bpp_comparison_t comp
Definition: bpp_tree.c:126

Here is the call graph for this function:

Here is the caller graph for this function:

ion_bpp_err_t b_update ( ion_bpp_handle_t  handle,
void *  key,
ion_bpp_external_address_t  rec 
)

Definition at line 1333 of file bpp_tree.c.

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 }
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
#define childGE(k)
Definition: bpp_tree.c:77
int maxHeight
Definition: bpp_tree.h:80
#define key(k)
Definition: bpp_tree.c:75
ion_bpp_buffer_t root
Definition: bpp_tree.c:127
#define fkey(b)
Definition: bpp_tree.c:84
#define ION_CC_LT
Definition: bpp_tree.h:60
char ion_bpp_key_t
Definition: bpp_tree.c:91
#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
unsigned int maxCt
Definition: bpp_tree.c:134
#define ION_CC_EQ
Definition: bpp_tree.h:58
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 childLT(k)
Definition: bpp_tree.c:74
#define rec(k)
Definition: bpp_tree.c:76
#define ION_CC_GT
Definition: bpp_tree.h:59
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

Here is the call graph for this function:

Here is the caller graph for this function:

static ion_bpp_err_t flush ( ion_bpp_handle_t  handle,
ion_bpp_buffer_t buf 
)
static

Definition at line 168 of file bpp_tree.c.

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 }
unsigned char ion_byte_t
A byte type.
Definition: kv_system.h:232
ion_bpp_address_t childLT
Definition: bpp_tree.c:105
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
char ion_err_t
The error type used to store error codes.
Definition: kv_system.h:226
ion_bpp_key_t fkey
Definition: bpp_tree.c:107
int nDiskWrites
Definition: bpp_tree.h:86
ion_bpp_address_t adr
Definition: bpp_tree.c:114
unsigned int leaf
Definition: bpp_tree.c:101
#define error(rc)
Definition: bpp_tree.c:139
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
unsigned int ct
Definition: bpp_tree.c:102
ion_bpp_bool_t modified
Definition: bpp_tree.c:117
#define p(b)
Definition: bpp_tree.c:86
ion_bpp_address_t next
Definition: bpp_tree.c:104

Here is the call graph for this function:

Here is the caller graph for this function:

static ion_bpp_err_t flushAll ( ion_bpp_handle_t  handle)
static

Definition at line 235 of file bpp_tree.c.

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 }
enum ION_BPP_ERR ion_bpp_err_t
static ion_bpp_err_t flush(ion_bpp_handle_t handle, ion_bpp_buffer_t *buf)
Definition: bpp_tree.c:168
ion_bpp_buffer_t root
Definition: bpp_tree.c:127
struct ion_bpp_buffer_tag * next
Definition: bpp_tree.c:112
ion_bpp_buffer_t bufList
Definition: bpp_tree.c:128
ion_bpp_bool_t modified
Definition: bpp_tree.c:117

Here is the call graph for this function:

Here is the caller graph for this function:

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 
)
static

Definition at line 804 of file bpp_tree.c.

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 }
enum ION_BPP_ERR ion_bpp_err_t
#define childGE(k)
Definition: bpp_tree.c:77
#define ks(ct)
Definition: bpp_tree.c:89
#define fkey(b)
Definition: bpp_tree.c:84
#define lkey(b)
Definition: bpp_tree.c:85
ion_bpp_buffer_t gbuf
Definition: bpp_tree.c:131
char ion_bpp_key_t
Definition: bpp_tree.c:91
#define leaf(b)
Definition: bpp_tree.c:80
#define ct(b)
Definition: bpp_tree.c:81
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 childLT(k)
Definition: bpp_tree.c:74

Here is the call graph for this function:

Here is the caller graph for this function:

static ion_bpp_err_t gatherRoot ( ion_bpp_handle_t  handle)
static

Definition at line 787 of file bpp_tree.c.

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 }
ion_bpp_node_t * p
Definition: bpp_tree.c:115
ion_bpp_buffer_t root
Definition: bpp_tree.c:127
ion_bpp_buffer_t gbuf
Definition: bpp_tree.c:131
#define leaf(b)
Definition: bpp_tree.c:80
#define ct(b)
Definition: bpp_tree.c:81
#define p(b)
Definition: bpp_tree.c:86

Here is the caller graph for this function:

static ion_bpp_err_t lineError ( int  lineno,
ion_bpp_err_t  rc 
)
static

Definition at line 142 of file bpp_tree.c.

145  {
146  if ((rc == bErrIO) || (rc == bErrMemory)) {
147  if (!bErrLineNo) {
148  bErrLineNo = lineno;
149  }
150  }
151 
152  return rc;
153 }
int bErrLineNo
Definition: bpp_tree.h:89
static ion_bpp_err_t readDisk ( ion_bpp_handle_t  handle,
ion_bpp_address_t  adr,
ion_bpp_buffer_t **  b 
)
static

Definition at line 329 of file bpp_tree.c.

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 }
unsigned char ion_byte_t
A byte type.
Definition: kv_system.h:232
enum ION_BPP_ERR ion_bpp_err_t
int nDiskReads
Definition: bpp_tree.h:85
ion_bpp_address_t childLT
Definition: bpp_tree.c:105
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
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
char ion_err_t
The error type used to store error codes.
Definition: kv_system.h:226
ion_bpp_key_t fkey
Definition: bpp_tree.c:107
ion_bpp_address_t adr
Definition: bpp_tree.c:114
unsigned int leaf
Definition: bpp_tree.c:101
ion_bpp_bool_t valid
Definition: bpp_tree.c:116
#define error(rc)
Definition: bpp_tree.c:139
unsigned int ct
Definition: bpp_tree.c:102
ion_bpp_bool_t modified
Definition: bpp_tree.c:117
#define p(b)
Definition: bpp_tree.c:86
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_address_t next
Definition: bpp_tree.c:104

Here is the call graph for this function:

Here is the caller graph for this function:

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 
)
static

Definition at line 560 of file bpp_tree.c.

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 }
enum ION_BPP_ERR ion_bpp_err_t
#define childGE(k)
Definition: bpp_tree.c:77
#define next(b)
Definition: bpp_tree.c:82
#define ks(ct)
Definition: bpp_tree.c:89
int nNodesDel
Definition: bpp_tree.h:82
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
static ion_bpp_err_t writeDisk(ion_bpp_buffer_t *buf)
Definition: bpp_tree.c:319
#define fkey(b)
Definition: bpp_tree.c:84
ion_bpp_address_t adr
Definition: bpp_tree.c:114
ion_bpp_buffer_t gbuf
Definition: bpp_tree.c:131
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
#define leaf(b)
Definition: bpp_tree.c:80
#define ct(b)
Definition: bpp_tree.c:81
unsigned int maxCt
Definition: bpp_tree.c:134
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 prev(b)
Definition: bpp_tree.c:83
#define childLT(k)
Definition: bpp_tree.c:74
int nNodesIns
Definition: bpp_tree.h:81

Here is the call graph for this function:

Here is the caller graph for this function:

static ion_bpp_err_t scatterRoot ( ion_bpp_handle_t  handle)
static

Definition at line 541 of file bpp_tree.c.

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 }
#define ks(ct)
Definition: bpp_tree.c:89
ion_bpp_buffer_t root
Definition: bpp_tree.c:127
#define fkey(b)
Definition: bpp_tree.c:84
ion_bpp_buffer_t gbuf
Definition: bpp_tree.c:131
#define leaf(b)
Definition: bpp_tree.c:80
#define ct(b)
Definition: bpp_tree.c:81
#define childLT(k)
Definition: bpp_tree.c:74

Here is the caller graph for this function:

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 
)
static

Definition at line 412 of file bpp_tree.c.

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 }
ion_boolean_e ion_bpp_bool_t
Definition: bpp_tree.h:91
#define ks(ct)
Definition: bpp_tree.c:89
#define key(k)
Definition: bpp_tree.c:75
#define fkey(b)
Definition: bpp_tree.c:84
#define ION_CC_LT
Definition: bpp_tree.h:60
#define ct(b)
Definition: bpp_tree.c:81
ion_bpp_bool_t dupKeys
Definition: bpp_tree.c:124
#define ION_CC_EQ
Definition: bpp_tree.h:58
#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
#define ION_CC_GT
Definition: bpp_tree.h:59
ion_bpp_comparison_t comp
Definition: bpp_tree.c:126

Here is the caller graph for this function:

static ion_bpp_err_t writeDisk ( ion_bpp_buffer_t buf)
static

Definition at line 319 of file bpp_tree.c.

321  {
322  /* write buf to disk */
323  buf->valid = boolean_true;
324  buf->modified = boolean_true;
325  return bErrOk;
326 }
ion_bpp_bool_t valid
Definition: bpp_tree.c:116
ion_bpp_bool_t modified
Definition: bpp_tree.c:117

Here is the caller graph for this function: