gist.cc

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

//      RCOK
/////////////////////////////////////////////////////////////////////////

void
gist::_check_node(
    gist_p&		node,
    const vec_t&	bpv)
{
    int recCnt = node.nrecs();
    AlignedPred x;
    vec_t predv;

    for (int i = 0; i < recCnt; i++) {
	const keyrec_t &tup = node.rec(i);
	predv.set(x.pred, gist_p::max_tup_sz);
	_ext->getKey(node, i, predv);
	if (!_ext->check(bpv, predv, node.level())) {
	    fprintf(stderr, "node %d: pred %d not contained in BP\n",
		node.pid(), i);
	}
    }
}


/////////////////////////////////////////////////////////////////////////
// _check_sub - check subtree for structural consistency
//
// Description:
//
// Preconditions:
// Postconditions:
// Notes:
//
// Return Values:
//      RCOK
/////////////////////////////////////////////////////////////////////////

rc_t
gist::_check_sub(
    shpid_t 		pgno,
    const vec_t&	pred,
    shpid_t		parent,
    int			slot,
    ReachInfo 		reached[])
{
    gist_p page;
    W_DO(_fix_page(page, pgno, LATCH_SH));
    AlignedPred x;
    vec_t predv;

    if (pred.size() != 0) {
	assert(!page.is_root());

	// make sure that the BP contains all other predicates
	_check_node(page, pred);
    }

    if (page.level() > 1) {
	// keep track of nodes reached
	int recCnt = page.nrecs();
	for (int i = 0; i < recCnt; i++) {
	    const keyrec_t &tup = page.rec(i);
	    shpid_t childPtr = tup.child();

	    // check if this is an entry w/ a valid child ptr
	    // (might just be state internal to the node layout)
	    if (childPtr <= 0) continue;

	    if (reached[childPtr].count > 0) {
	        // someone else is pointing to this already
		fprintf(stderr, "additional reference to %d from %d, slot %d\n",
		    childPtr, pgno, i);
	    } else {
	        reached[childPtr].parent = pgno; // that's us
	    }
	    reached[childPtr].count++;

	    // check subtrees recursively
	    predv.set(x.pred, gist_p::max_tup_sz);
	    _ext->getKey(page, i, predv);
	    W_DO(_check_sub(tup.child(), predv, pgno, i, reached));
	}
    }

    _unfix_page(page);
    return RCOK;
}


/////////////////////////////////////////////////////////////////////////
// check - check tree for structural consistency
//
// Description:
//
// Preconditions:
// Postconditions:
// Notes:
//
// Return Values:
//      RCOK
/////////////////////////////////////////////////////////////////////////

rc_t
gist::check()
{
    assert(_isOpen);

    int nodeCnt = _file.size();
    ReachInfo *reached = new ReachInfo[nodeCnt];
	int i;
    for (i = 0; i < nodeCnt; i++) {
	reached[i].count = 0;
	reached[i].parent = 0;
	reached[i].isFree = false;
    }

    reached[rootNo].count = 1;
    W_DO(_check_sub(rootNo, vec_t(), 0, 0, reached));

    // free pages in the file should not be reachable
    shpid_t* freeList = new shpid_t[nodeCnt];
    assert(freeList != NULL);
    int numFree = nodeCnt;
    _file.freelist(freeList, numFree);
    for (i = 0; i < numFree; i++) {
	ReachInfo& info = reached[freeList[i]];
        info.isFree = true;
        if (info.count != 0) {
	    cerr << "free node " << freeList[i] << " referenced "
		 << info.count << " times (orig. parent: " << info.parent
		 << ")" << endl;
	}
    }
    delete [] freeList;

    for (i = 1; i < nodeCnt; i++) {
	ReachInfo& info = reached[i];
	if (info.count != 1 && 
	    !(info.count == 0 && info.isFree)) {

	    // something's fishy
	    cerr << "node " << i << " referenced "
		 << info.count << " times (orig. parent: " << info.parent
		 << ")" << endl;
	}
    }
    delete [] reached;
    return RCOK;
}


/////////////////////////////////////////////////////////////////////////
// _dump_pg - write contents of single page to output stream
//
// Description:
//
// Preconditions:
// Postconditions:
// Notes:
//
// Return Values:
//      RCOK
/////////////////////////////////////////////////////////////////////////

void
gist::_dump_pg(
    ostream&		s,
    gist_p&		page)
{
    int lvl = page.level();
    // dump header
    s << "level: " << lvl << " #slots: " << page.nrecs() << " avail: "
        << (int) page.usable_space() << endl;

    // dump contents
    int recCnt = page.nrecs();
    AlignedPred x;
    vec_t keyv;
    for (int i = 0; i < recCnt; i++) {
        const keyrec_t &tup = page.rec(i);
	s << "[" << i << "] <";
	keyv.set(x.pred, gist_p::max_tup_sz);
	_ext->getKey(page, i, keyv);
	_ext->printPred(s, keyv, lvl);
	s << "> len: " << (int) tup.klen();
	if (lvl == 1) {
	    s << " data: ";
	    _ext->printData(s, vec_t(tup.elem(), tup.elen()));
	    s << " len: " << (int) tup.elen() << endl;
	} else {
	    s << " child: " << tup.child() << endl;
	}
    }
}


/////////////////////////////////////////////////////////////////////////
// _dump_sub - dump entire subtree to output stream
//
// Description:
//
// Preconditions:
// Postconditions:
// Notes:
//
// Return Values:
//      RCOK
/////////////////////////////////////////////////////////////////////////

rc_t
gist::_dump_sub(
    ostream& 		s,
    shpid_t 		pgno)
{
    gist_p page;

    W_DO(_fix_page(page, pgno, LATCH_SH));
    s << "[" << page.pid() << "] ";
    _dump_pg(s, page);
    int recCnt = page.nrecs();
    if (page.level() > 1) {
	for (int i = 0; i < recCnt; i++) {
	    const keyrec_t &tup = page.rec(i);
	    W_DO(_dump_sub(s, tup.child()));
	}
    }
    _unfix_page(page);
    return RCOK;
}


/////////////////////////////////////////////////////////////////////////
// dump - dump tree to output stream
//
// Description:
//
// Preconditions:
// Postconditions:
// Notes:
//
// Return Values:
//      RCOK
/////////////////////////////////////////////////////////////////////////

rc_t
gist::dump(
    ostream&		s,
    shpid_t 		pgno)
{
    if (pgno != 0) {
        gist_p page;
	W_DO(_fix_page(page, pgno, LATCH_SH));
	_dump_pg(s, page);
	_unfix_page(page);
    } else {
        W_DO(_dump_sub(s, rootNo));
    }
    return RCOK;
}


rc_t
gist::dmp(
    shpid_t	pgno)
{
    if (pgno != 0) {
        gist_p page;
	W_DO(_fix_page(page, pgno, LATCH_SH));
	_dump_pg(cout, page);
	_unfix_page(page);
    } else {
        W_DO(_dump_sub(cout, rootNo));
    }
    return(RCOK);
}


/////////////////////////////////////////////////////////////////////////
// _prepare_page - allocate page during bulk loading
//
// Description:
//
// Preconditions:
// Postconditions:
// Notes:
//
// Return Values:
//      RCOK
/////////////////////////////////////////////////////////////////////////

rc_t
gist::_prepare_page(
    gist_p&		page,
    shpid_t		rootPid,
    int			level)
{
    W_DO(_new_page(rootPid, page, level)); // first page on level
    return RCOK;
}


/////////////////////////////////////////////////////////////////////////
// _finalize_page - finalize page after it was bulk-loaded
//
// Description:
// 	- compute the BP, write it out and unfix the page
//
// Preconditions:
// Postconditions:
// Notes:
//
// Return Values:
//      RCOK
/////////////////////////////////////////////////////////////////////////

rc_t
gist::_finalize_page(
    gist_p& 	page,
    ostream&	outStream) // receives BPs of finished pages
{
    // compute the BP - even if we have already computed one, it may
    // have been computed incrementally, so compute a tight one now.
    vec_t dummyPred;
    bool dummy;
    AlignedPred x;
    vec_t bpv(x.pred, gist_p::max_tup_sz);
    _ext->unionBp(page, bpv, false, vec_t(), vec_t(), dummy);

    // write to outStream
    int len = bpv.size();
    outStream.write((char *) &len, sizeof(len));
    outStream.write((char *) bpv.ptr(0), len);
    shpid_t pageno = page.pid();
    outStream.write((char *) &pageno, sizeof(pageno));

    return RCOK;
}


/////////////////////////////////////////////////////////////////////////
// _build_level - bulk-load one level of tree
//
// Description:
//	- obtain items from tupStream() parameter fct
//	- insert items on current page until we exceed the target
//	  fill factor or tupStream() signals a forced page break
//	- then, compute a BP for the page, write it to bpOutStream
//	  and start a new page
//	- 'page' stays pinned when returning
//
// Return Values:
//      RCOK
/////////////////////////////////////////////////////////////////////////

rc_t		
gist::_build_level(
    TupleStream&	tupStream,
    void*		streamParam,
    float		fillFactor,
    int			level,
    shpid_t 		rootPid,
    ostream&		bpOutStream,
    BreakNotifyFct	breakNotify,
    int&		pageCnt,
    gist_p&		page) // used as the current page to insert on
{
    AlignedPred x, y;
    int klen, dlen;
    vec_t keyv, datav;
    shpid_t child;

    AlignedPred bpPred;

    // we should keep at least that much free space (make sure it's not uint!)
    int minFreeSpace = (size_t) ((1.0 - fillFactor) * ((float) gist_p::data_sz));
    int itemCnt = 0;

    rc_t status;
    W_DO(_prepare_page(page, rootPid, level)); // first page on level
    pageCnt = 1;
    bool breakPage = false;
    for (;;) {
	status = tupStream(x.pred, klen, y.pred, dlen, child, streamParam);
	if (status != RCOK && status != ePAGEBREAK) {
	    break;
	} 

	if (status == ePAGEBREAK) {
	    // the tuple stream encountered the end-of-page marker
	    breakPage = true;
	    continue; // for
	}

	assert(gist_p::rec_size(klen, dlen) <= gist_p::max_tup_sz);

	// create a new page if the parse routine returned an
	// end-of-page marker or we might exceed the target
	// utilization (we assume that the new record uses up about as
	// much space as its combined key and data sizes, which might
	// not be the case, if we compress records in some way; it
	// seems to be a conservative assumption, because the
	// "compressed" storage shouldn't blow records up).
        if (breakPage ||
	    ((int) page.usable_space() -
	    (int) gist_p::rec_size(klen, dlen) <= minFreeSpace)) {

	    // if this isn't a forced break, the caller might want to
	    // know about it
	    if (!breakPage && breakNotify != NULL) {
	        breakNotify(itemCnt, streamParam);
	    }
	    W_DO(_finalize_page(page, bpOutStream));
	    _unfix_page(page);
	    W_DO(_prepare_page(page, rootPid, level));
	    pageCnt++;
	    breakPage = false;
	    // don't reset BP for new page, we need this BP for union_page() of
	    // the next page
	}

	keyv.set(x.pred, klen);
	datav.set(y.pred, dlen);
	status = _ext->insert(page, keyv, datav, child);
	if (status != RCOK) return status;
	itemCnt++;
    }
    if (status != eEOF) return status;
    if (itemCnt == 0) return eFILEERROR; // can't have empty level
    W_DO(_finalize_page(page, bpOutStream)); // last page
    // don't unfix page, it'll be returned to the caller

    return RCOK;
}


/////////////////////////////////////////////////////////////////////////
// _readBpFromTemp - read BPs from temp file 
//
// Description:
//	- temp file written by _build_level() during build of last level
//
// Return Values:
//      RCOK: BP returned
//	eFILEERROR: something wrong
//	eEOF: no more BPs
/////////////////////////////////////////////////////////////////////////

rc_t		
gist::_readBpFromTemp(
    void* 	key,
    int&	klen,
    void* 	data,
    int&	dlen,
    shpid_t&	child,
    void* 	param)
{
    ifstream* s = (ifstream *) param;

// VCPORT_B
// WIN32 API expects (char *) not (void *)
#ifdef WIN32
	s->read((char *) &klen, sizeof(klen));
#else
    s->read((void *) &klen, sizeof(klen));
#endif
// VCPORT_E

    if (s->eof()) return(eEOF);

// VCPORT_B
// WIN32 API expects (char *) not (void *)
#ifdef WIN32
	s->read((char *) key, klen);
#else
    s->read(key, klen);
#endif
// VCPORT_E

    dlen = 0;

// VCPORT_B
// WIN32 API expects (char *) not (void *)
#ifdef WIN32
	s->read((char *) &child, sizeof(child));
#else
    s->read((void *) &child, sizeof(child));
#endif
// VCPORT_E

    if (!s->eof() && !s->good()) return(eFILEERROR);
    return(RCOK);
}

size_t totalMem = 0;

#if 0
extern void* operator
new(size_t size)
{
    void* p;

    totalMem += size;
    p = malloc(size);
    return p;
}
#endif