bpp_tree.h File Reference
#include <stdio.h>
#include <stdlib.h>
#include <stdarg.h>
#include <string.h>
#include <stdint.h>
#include "../../key_value/kv_system.h"
#include "./../dictionary.h"
#include "./../../file/ion_file.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.h.

Include dependency graph for bpp_tree.h:
This graph shows which files directly or indirectly include this file:

Classes

struct  ion_bpp_open_t
 

Macros

#define ION_CC_EQ   0
 
#define ION_CC_GT   1
 
#define ION_CC_LT   -1
 

Typedefs

typedef long ion_bpp_external_address_t
 
typedef long ion_bpp_address_t
 
typedef char(* ion_bpp_comparison_t) (ion_key_t key1, ion_key_t key2, ion_key_size_t size)
 
typedef ion_boolean_e ion_bpp_bool_t
 
typedef enum ION_BPP_ERR ion_bpp_err_t
 
typedef void * ion_bpp_handle_t
 

Enumerations

enum  ION_BPP_ERR {
  bErrOk, bErrKeyNotFound, bErrDupKeys, bErrSectorSize,
  bErrFileNotOpen, bErrFileExists, bErrIO, bErrMemory
}
 

Functions

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

Variables

int maxHeight
 
int nNodesIns
 
int nNodesDel
 
int nKeysIns
 
int nKeysDel
 
int nDiskReads
 
int nDiskWrites
 
int bErrLineNo
 

Macro Definition Documentation

#define ION_CC_EQ   0

Definition at line 58 of file bpp_tree.h.

#define ION_CC_GT   1

Definition at line 59 of file bpp_tree.h.

#define ION_CC_LT   -1

Definition at line 60 of file bpp_tree.h.

Typedef Documentation

typedef long ion_bpp_address_t

Definition at line 56 of file bpp_tree.h.

Definition at line 91 of file bpp_tree.h.

typedef char(* ion_bpp_comparison_t) (ion_key_t key1, ion_key_t key2, ion_key_size_t size)

Definition at line 67 of file bpp_tree.h.

typedef enum ION_BPP_ERR ion_bpp_err_t

Definition at line 55 of file bpp_tree.h.

typedef void* ion_bpp_handle_t

Definition at line 98 of file bpp_tree.h.

Enumeration Type Documentation

Enumerator
bErrOk 
bErrKeyNotFound 
bErrDupKeys 
bErrSectorSize 
bErrFileNotOpen 
bErrFileExists 
bErrIO 
bErrMemory 

Definition at line 94 of file bpp_tree.h.

Function Documentation

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_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:

Variable Documentation

int bErrLineNo

Definition at line 89 of file bpp_tree.h.

int maxHeight

Definition at line 80 of file bpp_tree.h.

int nDiskReads

Definition at line 85 of file bpp_tree.h.

int nDiskWrites

Definition at line 86 of file bpp_tree.h.

int nKeysDel

Definition at line 84 of file bpp_tree.h.

int nKeysIns

Definition at line 83 of file bpp_tree.h.

int nNodesDel

Definition at line 82 of file bpp_tree.h.

int nNodesIns

Definition at line 81 of file bpp_tree.h.