gist_btree.cc

Libgist is an implementation of the Generalized Search Tree, a template index structure that makes i

// gist_btree.cc
// Copyright (c) 1997, 1998, Regents of the University of California
// $Id: gist_btree.cc,v 1.28 2000/03/15 00:24:09 mashah Exp $

#ifdef __GNUG__
#pragma implementation "gist_btree.h"
#endif

#include <string.h>
#include <stdlib.h>

// VCPORT_B
#ifdef WIN32
#include <iostream>

using namespace std;
#else
#include <iostream.h>
#endif
// VCPORT_E

#include "gist_compat.h"	// for MAXINT/MININT
#include "gist_btree.h"
#include "gist_cursorext.h"	// for gist_cursorext_t::*
#include "gist_support.h"	// for print<>, parse<>, etc.
#include <assert.h>

bt_query_t::~bt_query_t()
{
    if (val1 != NULL) delete (char *)val1;
    if (val2 != NULL) delete (char *)val2;
}

static int
int_cmp(const void *a, const void *b)
{
    // can't simply copy ints, alignment might be wrong
    int x, y;
    (void) memcpy((void *) &x, a, sizeof(x));
    (void) memcpy((void *) &y, b, sizeof(y));
    if (x < y) { 
        return -1;
    } else if (x > y) {
        return 1;
    } else {
        return 0;
    }
    // this doesn't work when a is close to -2^31
    //int res = (*((int *) a) - *((int *) b));
}

static int
double_cmp(const void *a, const void *b)
{
    double x = *((double *) a);
    double y = *((double *) b);
    if (x < y) {
        return -1;
    } else if (x > y) {
        return 1;
    } else {
        return 0;
    }
}

static int
str_cmp(const void *a, const void *b)
{
    return (strcmp((const char *) a, (const char *) b));
}


///////////////////////////////////////////////////////////////////////////////
// gist_btree::gist_btree - constructor
//
// Description:
//
///////////////////////////////////////////////////////////////////////////////

bt_ext_t::bt_ext_t(
    gist_ext_t::gist_ext_ids id,
    const char* name,
    PrintPredFct printPred,
    PrintDataFct printData,
    ParseFct parsePred,
    ParseFct parseData,
    ParseQueryFct parseQuery,
    CmpFct keyCmp,
    CmpFct dataCmp,
    SizeFct keySize,
    SizeFct dataSize,
    NegInftyFct negInftyKey,
    NegInftyFct negInftyData) :
    gist_ext_t(id, name, printPred, printData, parsePred, parseData, parseQuery),
    keyCmp(keyCmp), dataCmp(dataCmp), keySize(keySize),
    dataSize(dataSize), negInftyKey(negInftyKey), negInftyData(negInftyData)
{
};


///////////////////////////////////////////////////////////////////////////////
// gist_btree::insert - insert new entry in sort order
//
// Description:
//	- insert after rightmost slot with item <= (key, data)
// Return Values:
//      RCOK
///////////////////////////////////////////////////////////////////////////////

rc_t
bt_ext_t::insert(
    gist_p& page,
    const vec_t& key,
    const vec_t& dataPtr,
    shpid_t child)
{
    const void* data;
    if (page.is_leaf()) {
        data = dataPtr.ptr(0);
    } else {
        // by convention, our key also contains a data pointer (to
        // make the internal node keys unique); we don't want to use
        // this during _binSearch(), so we 'skip' over it.
	data = (const void *) (((char *) key.ptr(0)) + this->keySize(key.ptr(0)));
    }
    int slot = _binSearch(page, key.ptr(0), data, false);
    W_DO(page.insert(key, dataPtr, slot + 1, child));
    return RCOK;
}


///////////////////////////////////////////////////////////////////////////////
// gist_btree::remove - remove number of slots
//
// Description:
// Return Values:
//      RCOK
///////////////////////////////////////////////////////////////////////////////

rc_t 
bt_ext_t::remove(
    gist_p& page,
    const int slots[],
    int numSlots)
{
    for (int i = numSlots - 1; i >= 0; i--) {
        W_DO(page.remove(slots[i]));
    }
    return RCOK;
}


///////////////////////////////////////////////////////////////////////////////
// gist_btree::updateKey - nothing to do
//
// Description:
//	- B-tree partitions the data space, no BPs to update 
//
// Return Values:
//      RCOK
///////////////////////////////////////////////////////////////////////////////

rc_t
bt_ext_t::updateKey(
    gist_p& page,
    int& slot,
    const vec_t& newKey)
{
    return RCOK;
}


///////////////////////////////////////////////////////////////////////////////
// gist_btree::findMinPen - return insertion subtree of (key, data)
//
// Description:
//	- return slof of rightmost item that is <= (key, data)
//
// Return Values:
//      RCOK
///////////////////////////////////////////////////////////////////////////////

void
bt_ext_t::findMinPen(
    const gist_p& page,
    const vec_t& key,
    const vec_t& data,
    int& slot)
{
    slot = _binSearch(page, key.ptr(0), data.ptr(0), false);
    assert(slot != -1);
}


///////////////////////////////////////////////////////////////////////////////
// gist_btree::search - return qualifying slots
//
// Description:
//	- return slof of rightmost item that is <= (key, data)
//
// Return Values:
//      RCOK
///////////////////////////////////////////////////////////////////////////////

void 
bt_ext_t::search(
    gist_p& page,
    const gist_query_t* query,
    int matches[],
    int& numMatches)
{
    const bt_query_t* q = (const bt_query_t *) query;
    int start, end; // start and end slot to scan

    numMatches = 0;
    switch (q->oper) {
    case bt_query_t::bt_nooper:
        start = 0;
	end = page.nrecs() - 1;
	break;
    case bt_query_t::bt_eq:
        start = _binSearch(page, q->val1, NULL, true);
	if (start == -1) {
	    // we're not going to find anything here
	    return;
	}
	// if we're at an internal node and val1 == key[start], there might be 
	// duplicates of val on the child to the left of child[start] (unless
	// we're already at the left boundary)
	if (!page.is_leaf() && start > 0 &&
	    keyCmp(page.rec(start).key(), q->val1) == 0) {

	    start--;
	}

	// The end of the range would be the rightmost slot with the same key,
	// but since _binSearch() can't find that or the position of the next higher
	// key, we pretend our range extends to the end of the page and check the 
	// keys as we go through the slots.
	end = page.nrecs() - 1;
	break;
    case bt_query_t::bt_lt:
    case bt_query_t::bt_le:
        start = 0;
	end = _binSearch(page, q->val1, NULL, true);
	break;
    case bt_query_t::bt_gt:
    case bt_query_t::bt_ge:
        start = _binSearch(page, q->val1, NULL, true);
	if (start == -1) start = 0;
	end = page.nrecs() - 1;
	break;
    case bt_query_t::bt_betw:  // equiv. to >= val1 && <= val2
        start = _binSearch(page, q->val1, NULL, true);
	if (start == -1) start = 0;
        end = _binSearch(page, q->val2, NULL, true);
	break;
    default: // something's wrong
        assert(0);
    };

    bool hit = false;
    bool stop = false; // bt_eq might tell us to stop
    for (int slot = start; slot <= end; slot++) {
        if (page.is_leaf()) {
	    switch (q->oper) {
	    case bt_query_t::bt_nooper:
		hit = true;
		break;
	    case bt_query_t::bt_eq:
	        if (keyCmp(page.rec(slot).key(), q->val1) == 0) {
		    hit = true;
		} else {
		    hit = false;
		    stop = true; // no more equal keys on this page
		}
		break;
	    case bt_query_t::bt_lt:
	        if (slot != end || keyCmp(page.rec(slot).key(), q->val1) < 0) {
		    hit = true;
		}
		break;
	    case bt_query_t::bt_le:
		hit = true;
		break;
	    case bt_query_t::bt_gt:
	        if (slot != start || keyCmp(page.rec(slot).key(), q->val1) > 0) {
		    hit = true;
		}
		break;
	    case bt_query_t::bt_ge:
		// start positioned on rightmost item <= key, we must only return
		// items < key
	        if (slot != start || keyCmp(page.rec(slot).key(), q->val1) >= 0) {
		    hit = true;
		}
		break;
	    case bt_query_t::bt_betw:
	        if (slot != start || keyCmp(page.rec(slot).key(), q->val1) >= 0) {
		    hit = true;
		}
		break;
	    default: // something's fishy
	        assert(0);
	    }

	} else { // internal node
	    switch (q->oper) {
	    case bt_query_t::bt_lt: 
		if (slot == end) {
		    // only goto child if its smallest key < val1; _binSearch()
		    // might have found key == val1)
		    if (keyCmp(page.rec(slot).key(), q->val1) < 0) hit = true;
		} else {
		    hit = true;
		}
		break;
	    case bt_query_t::bt_eq: 
		// stop checking the entries when we hit one that's > val1
	        if (keyCmp(page.rec(slot).key(), q->val1) > 0) {
		    hit = false;
		    stop = true;
		} else {
		    hit = true;
		}
		break;
	    default:
	        hit = true;
	    }
	}
	if (hit) {
	    matches[numMatches] = slot;
	    numMatches++;
	    hit = false;
	}
	if (stop) {
	    break;
	}
    }
}


///////////////////////////////////////////////////////////////////////////////
// gist_btree:getKey - return pointer to key on page
//
// Description:
//
///////////////////////////////////////////////////////////////////////////////

void 
bt_ext_t::getKey(
    const gist_p& page,
    int slot,
    vec_t& key)
{
    const keyrec_t& tup = page.rec(slot);
    key.set(tup.key(), tup.klen());
}