gist.cc

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

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

/*
 * Comments on the various #ifdefs:
 *
 * 1) #ifdef AMDB: If libgist is used as part of amdb, it needs to
 *    keep counters and call back to amdb when breakpoint-worthy
 *    events happen.
 */

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

// VCPORT_B
#ifdef WIN32
#pragma warning(disable:4786) // Templates can cause names to get too long for
							  // debug information. Disables this warning.
#endif
// VCPORT_E

#include <new.h>
#include <math.h>
#include <stdlib.h>

// VCPORT_B
#if (defined WIN32) || (__GNUG__==3)
#include <iostream>
#include <fstream>
using namespace std;
#else
#include <iostream.h>
#include <fstream.h>
#endif
// VCPORT_E

#include <stdio.h>

#include "gist_compat.h"	// for MAXDOUBLE
#include "gist_defs.h"

#include "gist_ext.h"
#include "gist_cursor.h"
#include "gist_cursorext.h"
#include "gist_ustk.h"
#ifdef AMDB
#include "amdb_wkldprofile.h"
//#include "amdb_ext.h"
#endif
#include "gist.h"


// didn't know where else to put these
const double gist_penalty_t::max_penalty = MAXDOUBLE;
gist_ext_t* gist_ext_t::gist_ext_list[gist_ext_t::gist_numext];

// misc
const shpid_t gist::rootNo = ROOTPAGE;


/////////////////////////////////////////////////////////////////////////
// gist - Constructor
//
// Description:
//
/////////////////////////////////////////////////////////////////////////

gist::gist() : _ext(NULL), _isOpen(false), _file()
#ifdef AMDB
    , _breakHandler(NULL), _profile(NULL)
#endif
{
}


/////////////////////////////////////////////////////////////////////////
// ~gist - Destructor
//
// Description:
// 	- close index
//
/////////////////////////////////////////////////////////////////////////

gist::~gist()
{
    close();
}


/////////////////////////////////////////////////////////////////////////
// _new_page - allocate a new page
//
// Description:
//	- format page and add header entry in slot 0
//	- if we pass in a descriptor, no page in the file is
//	  allocated (need this for gist::splitNode())
//
// Return Values:
//      RCOK
/////////////////////////////////////////////////////////////////////////

rc_t
gist::_new_page(
    shpid_t 			root,
    gist_p&			p,
    int2 			level,
    gist_file::page_descr*	descr)
{
    if (descr == NULL) {
	p._descr = _file.allocPage();
    } else {
        p._descr = descr;
    }
    assert(p._descr != NULL);
    p._pp = (page_s *) p._descr->page;

    gistctrl_t hdr;
    hdr.root = root;
    hdr.level = level;
    W_DO(p.format(p._descr->pageNo, &hdr));
    return(RCOK);
}


/////////////////////////////////////////////////////////////////////////
// is_empty - return true if tree is empty
//
// Description:
//
// Return Values:
//      true/false
/////////////////////////////////////////////////////////////////////////

bool 
gist::is_empty()
{
    gist_p page;

    W_DO(_fix_page(page, rootNo, LATCH_SH));
    return(page.nrecs() == 0);
}


/////////////////////////////////////////////////////////////////////////
// open - open index file
//
// Description:
//
// Return Values:
//      RCOK
/////////////////////////////////////////////////////////////////////////

rc_t
gist::open(
    const char*		filename)
{
  W_DO(_file.open(filename, (const gist_ext_t*&)_ext));
    _isOpen = true;
    return(RCOK);
}


/////////////////////////////////////////////////////////////////////////
// close - close index file
//
// Description:
//
// Return Values:
//      RCOK
/////////////////////////////////////////////////////////////////////////

rc_t
gist::close()
{
    if (_isOpen) {
	W_DO(_file.close());
	_isOpen = false;
    }
#ifdef AMDB
    // don't dealloc profile, the caller might still need it
#endif
    return(RCOK);
}


/////////////////////////////////////////////////////////////////////////
// flush - flush index file
//
// Return Values:
//      RCOK
/////////////////////////////////////////////////////////////////////////

rc_t
gist::flush()
{
    W_DO(_file.flush());
    return(RCOK);
}


/////////////////////////////////////////////////////////////////////////
// create - create new index file
//
// Description:
//	- initializes tree with empty root and flushes file
//
// Return Values:
//      RCOK
/////////////////////////////////////////////////////////////////////////

rc_t
gist::create(
    const char*		filename,
    gist_ext_t*		extension)
{
    _ext = extension;
    W_DO(_file.create(filename, _ext));
    _isOpen = true;

    // create the root page
    gist_p root;
    _new_page(rootNo, root, 1); // this is a leaf
    assert(rootNo == root.pid());
    _unfix_page(root);
    W_DO(_file.flush());
    return(RCOK);
}


/////////////////////////////////////////////////////////////////////////
// create - create index and bulk-load it
//
// Description:
//
// Return Values:
//      RCOK
/////////////////////////////////////////////////////////////////////////

rc_t
gist::create(
    const char*		filename,
    gist_ext_t*		extension,
    TupleStream		s,
    void*		sParam,
    float		fillFactor)
{
    // create the root (must be in page 1)
    W_DO(create(filename, extension));

    // set up temp files for BPs
    char* temp1 = "temp1"; // to be changed later
    char* temp2 = "temp2";
    bool toTemp1 = true; // true: write BPs to temp1



	// VCPORT_B
	// Gotta make sure that the temp files that are written are written in binary
#ifdef WIN32
	ofstream bpOutStream(temp1, ios_base::out | ios_base::binary);
	ofstream tmpfile(temp2, ios_base::out | ios_base::binary);
#else
	ofstream bpOutStream(temp1); // creates empty file
    ofstream tmpfile(temp2); // creates empty file
#endif
	// VCPORT_E

    tmpfile.close();

	// VCPORT_B
	// The state bits for the stream are not reset when file is close on NT
#ifdef WIN32
	tmpfile.clear();
#endif
	// VCPORT_E

	// VCPORT_B
	// Again make sure you read it in binary as well ...
#ifdef WIN32
	ifstream bpInStream(temp2, ios_base::in | ios_base::binary);
#else
	ifstream bpInStream(temp2); // opens empty file
#endif
	// VCPORT_E

    if (fillFactor > 1.0) fillFactor = 1.0; // can't fill page more than once

    // build tree level by level
    int level = 0;
    for (;;) {
        level++;
	TupleStream tupStream;
	void* streamParam;
	if (level == 1) {
	    // read from user-supplied tuple stream
	    tupStream = s;
	    streamParam = sParam;
	} else {
	    tupStream = _readBpFromTemp;
	    streamParam = (void *) &bpInStream;
	}
	int pageCnt;
	gist_p lastPage;
	W_DO(_build_level(tupStream, streamParam, fillFactor, level, rootNo,
	    bpOutStream, NULL, pageCnt, lastPage));

	bpInStream.close();
	bpOutStream.close();
	// VCPORT_B
	// The state bits for the stream are not reset when file is close on NT
#ifdef WIN32
	bpInStream.clear();
	bpOutStream.clear();
#endif
	// VCPORT_E

	if (pageCnt == 1) {
	    // The last level we produced contains only 1 page: this
	    // is the root level. We must copy the last page of this
	    // level to the (fixed-location) root page, adjust the
	    // level in the root page's header and then delete the
	    // last page.
	    gist_p rootPage;
	    W_DO(_fix_page(rootPage, rootNo, LATCH_EX));
	    W_DO(lastPage.copy(rootPage));
	    rootPage.set_level(level);
	    _unfix_page(rootPage);
	    W_DO(_file.freePage(lastPage._descr));
	    lastPage._pp = NULL;

	    // remove temp files
	    if (unlink(temp1) != 0) return(eFILEERROR);
	    if (unlink(temp2) != 0) return(eFILEERROR);

	    flush();
	    return(RCOK);
	}

	// switch BP input and output for the next level
	toTemp1 = (toTemp1 ? false : true);
	if (toTemp1) {
	    // write to temp1, read from temp2

		// VCPORT_B
#ifdef WIN32
		bpOutStream.open(temp1, ios_base::out | ios_base::binary);
		bpInStream.open(temp2, ios_base::in | ios_base::binary);
#else
	    bpOutStream.open(temp1);
	    bpInStream.open(temp2);
#endif
	} else {
#ifdef WIN32
	    bpOutStream.open(temp2, ios_base::out | ios_base::binary);
	    bpInStream.open(temp1, ios_base::in | ios_base::binary);
#else
	    bpOutStream.open(temp2);
	    bpInStream.open(temp1);
#endif
		// VCPORT_E
	}

    }

    // can't get here
    return(RCOK);
}


/////////////////////////////////////////////////////////////////////////
// _locate_leaf - descend to leaf along minimum-penalty path
//
// Description:
//	- record path on 'stack'
//
// Return Values:
//      RCOK
/////////////////////////////////////////////////////////////////////////

rc_t
gist::_locate_leaf(
    shpid_t 		root, // root of index
    gist_ustk&		gstack, // out: path to leaf
    const vec_t&	key, // key to insert
    const vec_t&	data) // data to insert
{
    shpid_t currPid = root;
    gist_p page;
    int index;

    for (;;) {

	W_DO(_fix_page(page, currPid, LATCH_EX));

#ifdef AMDB
	if (_breakHandler != NULL) {
	    // construct bp info
	    amdb_breakpoints::BreakInfo info;
	    info.event = (page.is_leaf() ? amdb_breakpoints::locateLeafEvent :
		amdb_breakpoints::traversalEvent);
	    info.node = currPid;
	    (void) _breakHandler(&info);
	}
#endif

	if (!page.is_leaf()) {
	    _ext->findMinPen(page, key, data, index);
	    gstack.push(page, index);
	} else {
	    // we found a leaf
	    gstack.push(page, 0);
	    return (RCOK); // leave the leaf latched
	}

	// follow child pointer
	currPid = page.rec(index).child();
	// no page.unfix(); we leave the pages fixed for now
    }
}


/////////////////////////////////////////////////////////////////////////
// _extract_bp - extract BP from parent page of stack entry
//
// Description:
//	- BP is in parent entry of node given by 'stkIdx'
//	- call ext->getKey() to extract the key, but make a copy
//	  if getKey() hasn't done so (BP extracted for modification)
//	- if the node has no parent (is the root), we set
//	  bp.len(0) to 0
//
// Return Values:
//      RCOK
/////////////////////////////////////////////////////////////////////////

void
gist::_extract_bp(
    gist_ustk&	gstack,
    int		stkIdx,
    vec_t&	bp)
{
    if (gstack.is_root(stkIdx)) {
        bp.set(bp.ptr(0), 0);
	return;
    }
    void* bpdata = bp.ptr(0);
    gist_ustk_entry *e = gstack.top(stkIdx + 1);
    _ext->getKey(e->page, e->idx, bp);
    if (bp.ptr(0) != bpdata) {
        // getKey() changed bp to point to the page, 
	// we need to make a copy now
	(void) memcpy(bpdata, bp.ptr(0), bp.len(0));
	bp.set(bpdata, bp.len(0));
    }
}


/////////////////////////////////////////////////////////////////////////
// _insert_leaf - Insert key/data pair on leaf and update BP
//
// Description:
//	- notify amdb of insertion
//
// Preconditions:
// Postconditions:
// Notes:
//
// Return Values:
//      RCOK
//      eRECWONTFIT
/////////////////////////////////////////////////////////////////////////

rc_t
gist::_insert_leaf(
    gist_p&		page, // leaf to insert on
    const vec_t&	key, // key of new entry
    const vec_t&	data, // data of new entry
    vec_t&		bpv, // BP as stored in parent entry
    bool&		bpChanged) // out: true if the BP changed
{
    int cnt = page.nrecs();

    // insert new item 

#ifdef AMDB
    if (_breakHandler != NULL) {
	// construct bp info
	amdb_breakpoints::BreakInfo info;
	info.event = amdb_breakpoints::nodeInsertEvent;
	info.node = page.pid();
	(void) _breakHandler(&info);
    }
#endif

    rc_t status = _ext->insert(page, key, data, 0);
    if (status != RCOK) {
        return (status);
    }

#ifdef AMDB
    if (_breakHandler != NULL) {
	// construct bp info
	amdb_breakpoints::BreakInfo info;
	info.event = amdb_breakpoints::itemInsertedEvent;
	info.param.updNodeParam = page.pid();
	(void) _breakHandler(&info);
    }
#endif