bt_utils.c File Reference

#include <sys/param.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "../include/db.h"
#include "btree.h"

Include dependency graph for bt_utils.c:

Go to the source code of this file.

Functions
int	__bt_cmp (BTREE *t, const DBT *k1, EPG *e)
int	__bt_defcmp (DBT *a, DBT *b) const
size_t	__bt_defpfx (DBT *a, DBT *b) const
int	__bt_ret (BTREE *t, EPG *e, DBT *key, DBT *rkey, DBT *data, DBT *rdata, int copy)

Function Documentation

__bt_cmp()

int __bt_cmp	(	BTREE *	t,
		const DBT *	k1,
		EPG *	e
	)

Definition at line 153 of file bt_utils.c.

{
    BINTERNAL *bi;
    BLEAF *bl;
    DBT k2;
    PAGE *h;
    void *bigkey;
 
    /*
     * The left-most key on internal pages, at any level of the tree, is
     * guaranteed by the following code to be less than any user key.
     * This saves us from having to update the leftmost key on an internal
     * page when the user inserts a new key in the tree smaller than
     * anything we've yet seen.
     */
    h = e->page;
    if (e->index == 0 && h->prevpg == P_INVALID && !(h->flags & P_BLEAF))
        return (1);
 
    bigkey = NULL;
    if (h->flags & P_BLEAF) {
        bl = GETBLEAF(h, e->index);
        if (bl->flags & P_BIGKEY)
            bigkey = bl->bytes;
        else {
            k2.data = bl->bytes;
            k2.size = bl->ksize;
        }
    } else {
        bi = GETBINTERNAL(h, e->index);
        if (bi->flags & P_BIGKEY)
            bigkey = bi->bytes;
        else {
            k2.data = bi->bytes;
            k2.size = bi->ksize;
        }
    }
 
    if (bigkey) {
        if (__ovfl_get(t, bigkey,
            &k2.size, &t->bt_rdata.data, &t->bt_rdata.size))
            return (RET_ERROR);
        k2.data = t->bt_rdata.data;
    }
    return ((*t->bt_cmp)(k1, &k2));
}

References __ovfl_get(), _btree::bt_rdata, _binternal::bytes, _bleaf::bytes, DBT::data, _page::flags, _binternal::flags, _bleaf::flags, GETBINTERNAL, GETBLEAF, _epg::index, _binternal::ksize, _bleaf::ksize, NULL, P_BIGKEY, P_BLEAF, P_INVALID, _epg::page, _page::prevpg, RET_ERROR, and DBT::size.

Referenced by __bt_bdelete(), __bt_curdel(), __bt_first(), __bt_search(), __bt_snext(), __bt_sprev(), and bt_fast().

__bt_defcmp()

int __bt_defcmp	(	DBT *	a,
		DBT *	b
	)		const

Definition at line 216 of file bt_utils.c.

{
    register size_t len;
    register u_char *p1, *p2;
 
    /*
     * XXX
     * If a size_t doesn't fit in an int, this routine can lose.
     * What we need is a integral type which is guaranteed to be
     * larger than a size_t, and there is no such thing.
     */
    len = MIN(a->size, b->size);
    for (p1 = a->data, p2 = b->data; len--; ++p1, ++p2)
        if (*p1 != *p2)
            return ((int)*p1 - (int)*p2);
    return ((int)a->size - (int)b->size);
}

References a, b, len(), and MIN.

Referenced by __bt_open().

__bt_defpfx()

size_t __bt_defpfx	(	DBT *	a,
		DBT *	b
	)		const

Definition at line 246 of file bt_utils.c.

{
    register u_char *p1, *p2;
    register size_t cnt, len;
 
    cnt = 1;
    len = MIN(a->size, b->size);
    for (p1 = a->data, p2 = b->data; len--; ++p1, ++p2, ++cnt)
        if (*p1 != *p2)
            return (cnt);
 
    /* a->size must be <= b->size, or they wouldn't be in this order. */
    return (a->size < b->size ? a->size + 1 : a->size);
}

References a, b, len(), and MIN.

Referenced by __bt_open().

__bt_ret()

int __bt_ret	(	BTREE *	t,
		EPG *	e,
		DBT *	key,
		DBT *	rkey,
		DBT *	data,
		DBT *	rdata,
		int	copy
	)

Definition at line 67 of file bt_utils.c.

{
    BLEAF *bl;
    void *p;
 
    bl = GETBLEAF(e->page, e->index);
 
    /*
     * We must copy big keys/data to make them contiguous.  Otherwise,
     * leave the page pinned and don't copy unless the user specified
     * concurrent access.
     */
    if (key == NULL)
        goto dataonly;
 
    if (bl->flags & P_BIGKEY) {
        if (__ovfl_get(t, bl->bytes,
            &key->size, &rkey->data, &rkey->size))
            return (RET_ERROR);
        key->data = rkey->data;
    } else if (copy || F_ISSET(t, B_DB_LOCK)) {
        if (bl->ksize > rkey->size) {
            p = (void *)(rkey->data == NULL ?
                malloc(bl->ksize) : realloc(rkey->data, bl->ksize));
            if (p == NULL)
                return (RET_ERROR);
            rkey->data = p;
            rkey->size = bl->ksize;
        }
        memmove(rkey->data, bl->bytes, bl->ksize);
        key->size = bl->ksize;
        key->data = rkey->data;
    } else {
        key->size = bl->ksize;
        key->data = bl->bytes;
    }
 
dataonly:
    if (data == NULL)
        return (RET_SUCCESS);
 
    if (bl->flags & P_BIGDATA) {
        if (__ovfl_get(t, bl->bytes + bl->ksize,
            &data->size, &rdata->data, &rdata->size))
            return (RET_ERROR);
        data->data = rdata->data;
    } else if (copy || F_ISSET(t, B_DB_LOCK)) {
        /* Use +1 in case the first record retrieved is 0 length. */
        if (bl->dsize + 1 > rdata->size) {
            p = (void *)(rdata->data == NULL ?
                malloc(bl->dsize + 1) :
                realloc(rdata->data, bl->dsize + 1));
            if (p == NULL)
                return (RET_ERROR);
            rdata->data = p;
            rdata->size = bl->dsize + 1;
        }
        memmove(rdata->data, bl->bytes + bl->ksize, bl->dsize);
        data->size = bl->dsize;
        data->data = rdata->data;
    } else {
        data->size = bl->dsize;
        data->data = bl->bytes + bl->ksize;
    }
 
    return (RET_SUCCESS);
}

References __ovfl_get(), B_DB_LOCK, _bleaf::bytes, copy(), DBT::data, _bleaf::dsize, F_ISSET, _bleaf::flags, GETBLEAF, _epg::index, _bleaf::ksize, malloc(), NULL, P_BIGDATA, P_BIGKEY, _epg::page, realloc, RET_ERROR, RET_SUCCESS, and DBT::size.

Referenced by __bt_curdel(), __bt_get(), and __bt_seq().