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

Copyright

Copyright 2017 The University of British Columbia, IonDB Project Contributors (see AUTHORS.md)

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)

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.

typedef ion_boolean_e ion_bpp_bool_t

Definition at line 79 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

typedef long ion_bpp_external_address_t

Definition at line 55 of file bpp_tree.h.

typedef void* ion_bpp_handle_t

Definition at line 86 of file bpp_tree.h.

Enumeration Type Documentation

enum ION_BPP_ERR

Enumerator
bErrOk
bErrKeyNotFound
bErrDupKeys
bErrSectorSize
bErrFileNotOpen
bErrFileExists
bErrIO
bErrMemory

Definition at line 82 of file bpp_tree.h.

                         {
    bErrOk, bErrKeyNotFound, bErrDupKeys, bErrSectorSize, bErrFileNotOpen, bErrFileExists, bErrIO, bErrMemory
} ion_bpp_err_t;

Function Documentation

ion_bpp_err_t b_close

(

ion_bpp_handle_t

handle

)

Definition at line 1040 of file bpp_tree.c.

  {
    ion_bpp_h_node_t *h = handle;

    if (h == NULL) {
        return bErrOk;
    }

    /* flush idx */
#if defined(ARDUINO)

    if (h->fp.file) {
#else

    if (h->fp) {
#endif
        flushAll(handle);
        ion_fclose(h->fp);
    }

    if (h->malloc2) {
        free(h->malloc2);
    }

    if (h->malloc1) {
        free(h->malloc1);
    }

    free(h);
    return bErrOk;
}

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 1453 of file bpp_tree.c.

  {
    int                 rc;     /* return code */
    ion_bpp_key_t       *mkey;          /* match key */
    int                 len;    /* length to shift */
    int                 cc;     /* condition code */
    ion_bpp_buffer_t    *buf;               /* buffer */
    ion_bpp_buffer_t    *tmp[4];
    unsigned int        keyOff;
    ion_bpp_bool_t      lastGEvalid;        /* true if GE branch taken */
    ion_bpp_bool_t      lastLTvalid;        /* true if LT branch taken after GE branch */
    ion_bpp_address_t   lastGE;         /* last childGE traversed */
    unsigned int        lastGEkey;  /* last childGE key traversed */
    ion_bpp_buffer_t    *root;
    ion_bpp_buffer_t    *gbuf;

    ion_bpp_h_node_t *h = handle;

    root        = &h->root;
    gbuf        = &h->gbuf;
    lastGEvalid = boolean_false;
    lastLTvalid = boolean_false;

    buf         = root;

    while (1) {
        if (leaf(buf)) {
            /* set mkey to point to deletion point */
            if (search(handle, buf, key, *rec, &mkey, MODE_MATCH) == 0) {
                *rec = rec(mkey);
            }
            else {
                return bErrKeyNotFound;
            }

            /* shift items GT key to left */
            keyOff  = mkey - fkey(buf);
            len     = ks(ct(buf) - 1) - keyOff;

            if (len) {
                memmove(mkey, mkey + ks(1), len);
            }

            ct(buf)--;

            if ((rc = writeDisk(buf)) != 0) {
                return rc;
            }

            /* if deleted key is first key, then fixup lastGE key */
            if (!keyOff && lastLTvalid) {
                ion_bpp_buffer_t    *tbuf;
                ion_bpp_key_t       *tkey;

                if ((rc = readDisk(handle, lastGE, &tbuf)) != 0) {
                    return rc;
                }

                tkey        = fkey(tbuf) + lastGEkey;
                memcpy(key(tkey), mkey, h->keySize);
                rec(tkey)   = rec(mkey);

                if ((rc = writeDisk(tbuf)) != 0) {
                    return rc;
                }
            }

            nKeysDel++;
            break;
        }
        else {
            /* internal node, descend to child */
            ion_bpp_buffer_t *cbuf; /* child buf */

            /* read child */
            if ((cc = search(handle, buf, key, *rec, &mkey, MODE_MATCH)) < 0) {
                if ((rc = readDisk(handle, childLT(mkey), &cbuf)) != 0) {
                    return rc;
                }
            }
            else {
                if ((rc = readDisk(handle, childGE(mkey), &cbuf)) != 0) {
                    return rc;
                }
            }

            /* check for room to delete */
            if (ct(cbuf) == h->maxCt / 2) {
                /* gather 3 bufs and scatter */
                if ((rc = gather(handle, buf, &mkey, tmp)) != 0) {
                    return rc;
                }

                /* if last 3 bufs in root, and count is low enough... */
                if ((buf == root) && (ct(root) == 2) && (ct(gbuf) < (3 * (3 * h->maxCt)) / 4)) {
                    /* collapse tree by one level */
                    scatterRoot(handle);
                    nNodesDel += 3;
                    continue;
                }

                if ((rc = scatter(handle, buf, mkey, 3, tmp)) != 0) {
                    return rc;
                }

                /* read child */
                if ((cc = search(handle, buf, key, *rec, &mkey, MODE_MATCH)) < 0) {
                    if ((rc = readDisk(handle, childLT(mkey), &cbuf)) != 0) {
                        return rc;
                    }
                }
                else {
                    if ((rc = readDisk(handle, childGE(mkey), &cbuf)) != 0) {
                        return rc;
                    }
                }
            }

            if ((cc >= 0) || (mkey != fkey(buf))) {
                lastGEvalid = boolean_true;
                lastLTvalid = boolean_false;
                lastGE      = buf->adr;
                lastGEkey   = mkey - fkey(buf);

                if (cc < 0) {
                    lastGEkey -= ks(1);
                }
            }
            else {
                if (lastGEvalid) {
                    lastLTvalid = boolean_true;
                }
            }

            buf = cbuf;
        }
    }

    return bErrOk;
}

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 1116 of file bpp_tree.c.

  {
    ion_bpp_key_t       *lgeqkey;           /* matched key */
    ion_bpp_buffer_t    *buf;               /* buffer */
    ion_bpp_err_t       rc;         /* return code */
    int                 cc;

    ion_bpp_h_node_t *h = handle;

    buf = &h->root;

    /* find key, and return address */
    while (1) {
        if (leaf(buf)) {
            if ((cc = search(handle, buf, key, 0, &lgeqkey, MODE_LLEQ)) > 0) {
                if ((lgeqkey - fkey(buf)) / (h->ks) == (ct(buf))) {
                    return bErrKeyNotFound;
                }

                lgeqkey += ks(1);
            }

            h->curBuf   = buf;
            h->curKey   = lgeqkey;
            memcpy(mkey, key(lgeqkey), h->keySize);
            *rec        = rec(lgeqkey);

            return bErrOk;
        }
        else {
            cc = search(handle, buf, key, 0, &lgeqkey, MODE_LLEQ);

            if (cc < 0) {
                if ((rc = readDisk(handle, childLT(lgeqkey), &buf)) != 0) {
                    return rc;
                }
            }
            else {
                if ((rc = readDisk(handle, childGE(lgeqkey), &buf)) != 0) {
                    return rc;
                }
            }
        }
    }
}

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 1598 of file bpp_tree.c.

  {
    ion_bpp_err_t       rc;         /* return code */
    ion_bpp_buffer_t    *buf;               /* buffer */

    ion_bpp_h_node_t *h = handle;

    buf = &h->root;

    while (!leaf(buf)) {
        if ((rc = readDisk(handle, childLT(fkey(buf)), &buf)) != 0) {
            return rc;
        }
    }

    if (ct(buf) == 0) {
        return bErrKeyNotFound;
    }

    memcpy(key, key(fkey(buf)), h->keySize);
    *rec        = rec(fkey(buf));
    h->curBuf   = buf;
    h->curKey   = fkey(buf);
    return bErrOk;
}

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 1639 of file bpp_tree.c.

  {
    ion_bpp_err_t       rc;         /* return code */
    ion_bpp_buffer_t    *buf;               /* buffer */

    ion_bpp_h_node_t *h = handle;

    buf = &h->root;

    while (!leaf(buf)) {
        if ((rc = readDisk(handle, childGE(lkey(buf)), &buf)) != 0) {
            return rc;
        }
    }

    if (ct(buf) == 0) {
        return bErrKeyNotFound;
    }

    memcpy(key, key(lkey(buf)), h->keySize);
    *rec        = rec(lkey(buf));
    h->curBuf   = buf;
    h->curKey   = lkey(buf);
    return bErrOk;
}

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 1669 of file bpp_tree.c.

  {
    ion_bpp_err_t       rc;         /* return code */
    ion_bpp_key_t       *nkey;          /* next key */
    ion_bpp_buffer_t    *buf;               /* buffer */

    ion_bpp_h_node_t *h = handle;

    if ((buf = h->curBuf) == NULL) {
        return bErrKeyNotFound;
    }

    if (h->curKey == lkey(buf)) {
        /* current key is last key in leaf node */
        if (next(buf)) {
            /* fetch next set */
            if ((rc = readDisk(handle, next(buf), &buf)) != 0) {
                return rc;
            }

            nkey = fkey(buf);
        }
        else {
            /* no more sets */
            return bErrKeyNotFound;
        }
    }
    else {
        /* bump to next key */
        nkey = h->curKey + ks(1);
    }

    memcpy(key, key(nkey), h->keySize);
    *rec        = rec(nkey);
    h->curBuf   = buf;
    h->curKey   = nkey;
    return bErrOk;
}

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 1074 of file bpp_tree.c.

  {
    ion_bpp_key_t       *mkey;          /* matched key */
    ion_bpp_buffer_t    *buf;               /* buffer */
    ion_bpp_err_t       rc;         /* return code */

    ion_bpp_h_node_t *h = handle;

    buf = &h->root;

    /* find key, and return address */
    while (1) {
        if (leaf(buf)) {
            if (search(handle, buf, key, 0, &mkey, MODE_FIRST) == 0) {
                *rec        = rec(mkey);
                h->curBuf   = buf;
                h->curKey   = mkey;
                return bErrOk;
            }
            else {
                return bErrKeyNotFound;
            }
        }
        else {
            if (search(handle, buf, key, 0, &mkey, MODE_MATCH) < 0) {
                if ((rc = readDisk(handle, childLT(mkey), &buf)) != 0) {
                    return rc;
                }
            }
            else {
                if ((rc = readDisk(handle, childGE(mkey), &buf)) != 0) {
                    return rc;
                }
            }
        }
    }
}

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 1167 of file bpp_tree.c.

  {
    int                 rc;     /* return code */
    ion_bpp_key_t       *mkey;          /* match key */
    int                 len;    /* length to shift */
    int                 cc;     /* condition code */
    ion_bpp_buffer_t    *buf, *root;
    ion_bpp_buffer_t    *tmp[4];
    unsigned int        keyOff;
    ion_bpp_bool_t      lastGEvalid;        /* true if GE branch taken */
    ion_bpp_bool_t      lastLTvalid;        /* true if LT branch taken after GE branch */
    ion_bpp_address_t   lastGE;         /* last childGE traversed */
    unsigned int        lastGEkey;  /* last childGE key traversed */
    int                 height; /* height of tree */

    ion_bpp_h_node_t *h = handle;

    root        = &h->root;
    lastGEvalid = boolean_false;
    lastLTvalid = boolean_false;

    /* check for full root */
    if (ct(root) == 3 * h->maxCt) {
        /* gather root and scatter to 4 bufs */
        /* this increases b-tree height by 1 */
        if ((rc = gatherRoot(handle)) != 0) {
            return rc;
        }

        if ((rc = scatter(handle, root, fkey(root), 0, tmp)) != 0) {
            return rc;
        }
    }

    buf     = root;
    height  = 0;

    while (1) {
        if (leaf(buf)) {
            /* in leaf, and there' room guaranteed */

            if (height > maxHeight) {
                maxHeight = height;
            }

            /* set mkey to point to insertion point */
            switch (search(handle, buf, key, rec, &mkey, MODE_MATCH)) {
                case ION_CC_LT: /* key < mkey */

                    if (!h->dupKeys && (0 != ct(buf)) && (h->comp(key, mkey, (ion_key_size_t) (h->keySize)) == ION_CC_EQ)) {
                        return bErrDupKeys;
                    }

                    break;

                case ION_CC_EQ: /* key = mkey */
                    return bErrDupKeys;
                    break;

                case ION_CC_GT: /* key > mkey */

                    if (!h->dupKeys && (h->comp(key, mkey, (ion_key_size_t) (h->keySize)) == ION_CC_EQ)) {
                        return bErrDupKeys;
                    }

                    mkey += ks(1);
                    break;
            }

            /* shift items GE key to right */
            keyOff  = mkey - fkey(buf);
            len     = ks(ct(buf)) - keyOff;

            if (len) {
                memmove(mkey + ks(1), mkey, len);
            }

            /* insert new key */
            memcpy(key(mkey), key, h->keySize);
            rec(mkey)       = rec;
            childGE(mkey)   = 0;
            ct(buf)++;

            if ((rc = writeDisk(buf)) != 0) {
                return rc;
            }

            /* if new key is first key, then fixup lastGE key */
            if (!keyOff && lastLTvalid) {
                ion_bpp_buffer_t    *tbuf;
                ion_bpp_key_t       *tkey;

                if ((rc = readDisk(handle, lastGE, &tbuf)) != 0) {
                    return rc;
                }

                /* tkey = fkey(tbuf) + lastGEkey; */
                tkey        = fkey(tbuf);
                memcpy(key(tkey), key, h->keySize);
                rec(tkey)   = rec;

                if ((rc = writeDisk(tbuf)) != 0) {
                    return rc;
                }
            }

            nKeysIns++;
            break;
        }
        else {
            /* internal node, descend to child */
            ion_bpp_buffer_t *cbuf; /* child buf */

            height++;

            /* read child */
            if ((cc = search(handle, buf, key, rec, &mkey, MODE_MATCH)) < 0) {
                if ((rc = readDisk(handle, childLT(mkey), &cbuf)) != 0) {
                    return rc;
                }
            }
            else {
                if ((rc = readDisk(handle, childGE(mkey), &cbuf)) != 0) {
                    return rc;
                }
            }

            /* check for room in child */
            if (ct(cbuf) == h->maxCt) {
                /* gather 3 bufs and scatter */
                if ((rc = gather(handle, buf, &mkey, tmp)) != 0) {
                    return rc;
                }

                if ((rc = scatter(handle, buf, mkey, 3, tmp)) != 0) {
                    return rc;
                }

                /* read child */
                if ((cc = search(handle, buf, key, rec, &mkey, MODE_MATCH)) < 0) {
                    if ((rc = readDisk(handle, childLT(mkey), &cbuf)) != 0) {
                        return rc;
                    }
                }
                else {
                    if ((rc = readDisk(handle, childGE(mkey), &cbuf)) != 0) {
                        return rc;
                    }
                }
            }

            if ((cc >= 0) || (mkey != fkey(buf))) {
                lastGEvalid = boolean_true;
                lastLTvalid = boolean_false;
                lastGE      = buf->adr;
                lastGEkey   = mkey - fkey(buf);

                if (cc < 0) {
                    lastGEkey -= ks(1);
                }
            }
            else {
                if (lastGEvalid) {
                    lastLTvalid = boolean_true;
                }
            }

            buf = cbuf;
        }
    }

    return bErrOk;
}

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 899 of file bpp_tree.c.

  {
    ion_bpp_h_node_t    *h;
    ion_bpp_err_t       rc;         /* return code */
    int                 bufCt;  /* number of tmp buffers */
    ion_bpp_buffer_t    *buf;               /* buffer */
    int                 maxCt;  /* maximum number of keys in a node */
    ion_bpp_buffer_t    *root;
    int                 i;
    ion_bpp_node_t      *p;

    if ((info.sectorSize < sizeof(ion_bpp_h_node_t)) || (0 != info.sectorSize % 4)) {
        return bErrSectorSize;
    }

    /* determine sizes and offsets */
    /* leaf/n, prev, next, [childLT,key,rec]... childGE */
    /* ensure that there are at least 3 children/parent for gather/scatter */
    maxCt   = info.sectorSize - (sizeof(ion_bpp_node_t) - sizeof(ion_bpp_key_t));
    maxCt   /= sizeof(ion_bpp_address_t) + info.keySize + sizeof(ion_bpp_external_address_t);

    if (maxCt < 6) {
        return bErrSectorSize;
    }

    /* copy parms to ion_bpp_h_node_t */
    if ((h = calloc(1, sizeof(ion_bpp_h_node_t))) == NULL) {
        return error(bErrMemory);
    }

    h->keySize      = info.keySize;
    h->dupKeys      = info.dupKeys;
    h->sectorSize   = info.sectorSize;
    h->comp         = info.comp;

    /* childLT, key, rec */
    h->ks           = sizeof(ion_bpp_address_t) + h->keySize + sizeof(ion_bpp_external_address_t);
    h->maxCt        = maxCt;

    /* Allocate buflist.
     * During insert/delete, need simultaneous access to 7 buffers:
     *  - 4 adjacent child bufs
     *  - 1 parent buf
     *  - 1 next sequential link
     *  - 1 lastGE
    */
    bufCt           = 7;

    if ((h->malloc1 = calloc(bufCt, sizeof(ion_bpp_buffer_t))) == NULL) {
        return error(bErrMemory);
    }

    buf = h->malloc1;

    /*
     * Allocate bufs.
     * We need space for the following:
     *  - bufCt buffers, of size sectorSize
     *  - 1 buffer for root, of size 3*sectorSize
     *  - 1 buffer for gbuf, size 3*sectorsize + 2 extra keys
     *  to allow for LT pointers in last 2 nodes when gathering 3 full nodes
    */
    if ((h->malloc2 = malloc((bufCt + 6) * h->sectorSize + 2 * h->ks)) == NULL) {
        return error(bErrMemory);
    }

    for (i = 0; i < (bufCt + 6) * h->sectorSize + 2 * h->ks; i++) {
        ((char *) h->malloc2)[i] = 0;
    }

    p               = h->malloc2;

    /* initialize buflist */
    h->bufList.next = buf;
    h->bufList.prev = buf + (bufCt - 1);

    for (i = 0; i < bufCt; i++) {
        buf->next       = buf + 1;
        buf->prev       = buf - 1;
        buf->modified   = boolean_false;
        buf->valid      = boolean_false;
        buf->p          = p;
        p               = (ion_bpp_node_t *) ((char *) p + h->sectorSize);
        buf++;
    }

    h->bufList.next->prev   = &h->bufList;
    h->bufList.prev->next   = &h->bufList;

    /* initialize root */
    root                    = &h->root;
    root->p                 = p;
    p                       = (ion_bpp_node_t *) ((char *) p + 3 * h->sectorSize);
    h->gbuf.p               = p;/* done last to include extra 2 keys */

    h->curBuf               = NULL;
    h->curKey               = NULL;

    /* initialize root */
    if (ion_fexists(info.iName)) {
        /* open an existing database */
        h->fp = ion_fopen(info.iName);

        if ((rc = readDisk(h, 0, &root)) != 0) {
            return rc;
        }

        if (ion_fseek(h->fp, 0, ION_FILE_END)) {
            return error(bErrIO);
        }

        if ((h->nextFreeAdr = ion_ftell(h->fp)) == -1) {
            return error(bErrIO);
        }
    }

#if defined(ARDUINO)
    else if (NULL != (h->fp = ion_fopen(info.iName)).file) {
#else
    else if (NULL != (h->fp = ion_fopen(info.iName))) {
#endif
        /* initialize root */
        memset(root->p, 0, 3 * h->sectorSize);
        leaf(root)      = 1;
        h->nextFreeAdr  = 3 * h->sectorSize;
        root->modified  = 1;
        flushAll(h);
    }
    else {
        /* something's wrong */
        free(h);
        return bErrFileNotOpen;
    }

    *handle = h;
    return bErrOk;
}

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 1345 of file bpp_tree.c.

  {
    int                 rc;     /* return code */
    ion_bpp_key_t       *mkey;  /* match key */
    int                 cc;     /* condition code */
    ion_bpp_buffer_t    *buf, *root;
    ion_bpp_buffer_t    *tmp[4];
    int                 height; /* height of tree */

    ion_bpp_h_node_t *h = handle;

    root = &h->root;

    /* check for full root */
    if (ct(root) == 3 * h->maxCt) {
        /* gather root and scatter to 4 bufs */
        /* this increases b-tree height by 1 */
        if ((rc = gatherRoot(handle)) != 0) {
            return rc;
        }

        if ((rc = scatter(handle, root, fkey(root), 0, tmp)) != 0) {
            return rc;
        }
    }

    buf     = root;
    height  = 0;

    while (1) {
        if (leaf(buf)) {
            /* in leaf, and there' room guaranteed */

            if (height > maxHeight) {
                maxHeight = height;
            }

            /* set mkey to point to update point */
            switch (search(handle, buf, key, rec, &mkey, MODE_MATCH)) {
                case ION_CC_LT: /* key < mkey */
                    return bErrKeyNotFound;
                    break;

                case ION_CC_EQ: /* key = mkey */
                    break;

                case ION_CC_GT: /* key > mkey */
                    return bErrKeyNotFound;
                    break;
            }

            /* update key */
            rec(mkey) = rec;
            break;
        }
        else {
            /* internal node, descend to child */
            ion_bpp_buffer_t *cbuf; /* child buf */

            height++;

            /* read child */
            if ((cc = search(handle, buf, key, rec, &mkey, MODE_MATCH)) < 0) {
                if ((rc = readDisk(handle, childLT(mkey), &cbuf)) != 0) {
                    return rc;
                }
            }
            else {
                if ((rc = readDisk(handle, childGE(mkey), &cbuf)) != 0) {
                    return rc;
                }
            }

            /* check for room in child */
            if (ct(cbuf) == h->maxCt) {
                /* gather 3 bufs and scatter */
                if ((rc = gather(handle, buf, &mkey, tmp)) != 0) {
                    return rc;
                }

                if ((rc = scatter(handle, buf, mkey, 3, tmp)) != 0) {
                    return rc;
                }

                /* read child */
                if ((cc = search(handle, buf, key, rec, &mkey, MODE_MATCH)) < 0) {
                    if ((rc = readDisk(handle, childLT(mkey), &cbuf)) != 0) {
                        return rc;
                    }
                }
                else {
                    if ((rc = readDisk(handle, childGE(mkey), &cbuf)) != 0) {
                        return rc;
                    }
                }
            }

            buf = cbuf;
        }
    }

    return bErrOk;
}

Here is the call graph for this function:

Here is the caller graph for this function: