gist_amdb.cc

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

    int i;
    for (i = 0; i < recCnt; i++) {
	if (next >= numPredInfo) {
	    // predInfo is too small
	    _unfix_page(page);
	    return(eARRAYSIZE);
	}
        predInfo[next].node = subtreeRoot;
        predInfo[next].parent = parent;
        predInfo[next].level = page.level();
        predInfo[next].slot = i;
        predInfo[next].color = 0;
	next++;
    }

    // traverse children
    if (levels > 1 && page.level() > 1) {
	for (i = 0; i < recCnt; i++) {
	    const keyrec_t &tup = page.rec(i);
	    W_DO(_getPredInfo(tup.child(), subtreeRoot, levels-1, predInfo,
	        next, numPredInfo));
	}
    }
    _unfix_page(page);
    return(RCOK);
}


///////////////////////////////////////////////////////////////////////////////
// gist::displayPreds - display predicates in Java canvas
//
// Description:
//	- construct a gist_predcursor_t out of predInfo and call 
//	  amdb_ext_t::displayPreds()
//
// Return Values:
//      RCOK
///////////////////////////////////////////////////////////////////////////////

rc_t
gist::displayPreds(
    JNIEnv*		env, // in
    jint		width, // in
    jint		height, // in
    jobject 		graphicsContext, // in: java.awt.Graphics
    jobject		colors[], // in: array of java.awt.Color objects
    DisplayPredInfo	predInfo[], // in
    int			numPredInfo) // in
{
    // construct predcursor
    gist_disppredcursor_t pcursor(this);
    int i;
    for (i = 0; i < numPredInfo; i++) {
        pcursor.add(predInfo[i].node, predInfo[i].slot, predInfo[i].level,
            predInfo[i].color);
    }

    // call amdb_ext_t
    amdb_ext_t* amdbExt = amdb_ext_t::amdb_ext_list[_ext->myId];
    assert(amdbExt != NULL);
    assert(amdbExt->displayPreds != NULL);
    W_DO(amdbExt->displayPreds(env, width, height, graphicsContext,
        colors, pcursor));
    return(RCOK);
}


/////////////////////////////////////////////////////////////////////////
// display - call amdb extension to display page contents
//
// Description:
//
// Preconditions:
// Postconditions:
// Notes:
//
// Return Values:
//      RCOK
/////////////////////////////////////////////////////////////////////////

rc_t 		
gist::display(
    shpid_t	pgno,
    JNIEnv*	env,
    jint*	highlights,
    jint	numHighlights,
    jobject	graphics,
    jobject	normalColor,
    jobject	highlightColor,
    jint	width,
    jint	height)
{
    gist_p page;
    W_DO(_fix_page(page, pgno, LATCH_SH));

    // dispatch through amdb_ext_t
    amdb_ext_t* amdbExt = amdb_ext_t::amdb_ext_list[_ext->myId];
    amdbExt->display(page, env, highlights, numHighlights, graphics, normalColor,
        highlightColor, width, height);

    _unfix_page(page);
    return RCOK;
}


/////////////////////////////////////////////////////////////////////////
// getChildren - return child pointers of internal node
//
// Description:
//
// Preconditions:
// Postconditions:
// Notes:
//
// Return Values:
//      RCOK
/////////////////////////////////////////////////////////////////////////

rc_t
gist::getChildren(
    shpid_t 	pageno,
    int& 	level,
    Vector* 	children) // vector<shpid_t> *
{
    gist_p page;
    W_DO(_fix_page(page, pageno, LATCH_SH));
    _getChildren(page, children);
    level = page.level();
    _unfix_page(page);
    return RCOK;
}


/////////////////////////////////////////////////////////////////////////
// _getChildren - return child pointers of internal node
//
// Description:
//
// Preconditions:
// Postconditions:
// Notes:
//
// Return Values:
//      RCOK
/////////////////////////////////////////////////////////////////////////

void
gist::_getChildren(
    const gist_p& page,
    Vector* /* vector<shpid_t> */ children)
{
    if (page.is_leaf()) return; // doesnt have children

    int cnt = page.nrecs();
    for (int i = 0; i < cnt; i++) {
        const keyrec_t& tup = page.rec(i);
	children->push_back((void *) tup.child());
    }
}


/////////////////////////////////////////////////////////////////////////
// pickSplit - compute split info for given node
//
// Description:
//	- call extension to compute split info
//
// Return Values:
//      RCOK
/////////////////////////////////////////////////////////////////////////

rc_t		
gist::pickSplit(
    shpid_t	pageno,
    int*	splitEntries, // entry #s, starting at 0
    int&	numSplit, // # of items that go right
    vec_t&	leftBp, // computed BP of left node
    vec_t&	rightBp) // computed BP of right node
{
    gist_p page;
    W_DO(_fix_page(page, pageno, LATCH_SH));

    // get BP from parent
    AlignedPred w;
    vec_t bpv(w.pred, gist_p::max_tup_sz);
    getBp(pageno, bpv);

    // find out which entries go right
    numSplit = gist_p::max_scnt;
    bool dummyBool1, dummyBool2;
    W_DO(_ext->pickSplit(page, splitEntries, numSplit, bpv, leftBp, rightBp,
	vec_t(), dummyBool1, vec_t(), dummyBool2));
    assert(numSplit <= gist_p::max_scnt);

    _unfix_page(page);
    return RCOK;
}


/////////////////////////////////////////////////////////////////////////
// gist::unionBp - wrapper for gist_ext_t::unionBp()
//
// Description:
/////////////////////////////////////////////////////////////////////////

rc_t
gist::unionBp(
    shpid_t 		pageno, // in
    vec_t& 		bp, // in/out
    bool 		bpIsValid, // in
    const vec_t& 	pred1, // in
    const vec_t& 	pred2, // in
    bool& 		bpChanged) // out
{
    gist_p page;
    W_DO(_fix_page(page, pageno, LATCH_SH));
    _ext->unionBp(page, bp, bpIsValid, pred1, pred2, bpChanged);
    _unfix_page(page);
    return(RCOK);
}


/////////////////////////////////////////////////////////////////////////
// gist::getBp - make copy of BP
//
// Description:
//	- currently, simply calls unionBp()
//
// Return Values:
//      RCOK
/////////////////////////////////////////////////////////////////////////

rc_t
gist::getBp(
    shpid_t	pageno,
    vec_t&	bp)
{
    gist_p page;
    W_DO(_fix_page(page, pageno, LATCH_SH));
    vec_t dummyPred;
    bool dummyBool;
    _ext->unionBp(page, bp, false, dummyPred, dummyPred, dummyBool);
    _unfix_page(page);
    return(RCOK);
}


/////////////////////////////////////////////////////////////////////////
// gist::splitNode - split node into (private) left and right page
//
// Description:
//	- leftPg and rightPg point to buffers that are in static memory
//	  instead of under gist_file's control, so the caller doesn't 
//	  need to unfix or free any pages
//
// Return Values:
//      RCOK
/////////////////////////////////////////////////////////////////////////

rc_t
gist::splitNode(
    shpid_t 	node,
    gist_p&	leftPg,
    gist_p&	rightPg,
    const int	rightEntries[],
    int		numRight)
{
    gist_p page;
    W_DO(_fix_page(page, node, LATCH_SH));

    // create leftPg and rightPg, make them point to local mem
    // (we don't want to allocate a page that the caller then 
    // needs to free later on)
    static union {
        double d;
	char buf[SM_PAGESIZE];
    } leftBuf, rightBuf;
    static gist_file::page_descr leftDescr, rightDescr;
    leftDescr.page = leftBuf.buf;
    rightDescr.page = rightBuf.buf;
    (void) _new_page(rootNo, leftPg, page.level(), &leftDescr);
    (void) _new_page(rootNo, rightPg, page.level(), &rightDescr);

    // make copy of node, _split_node() expects leftPg to contain items
    page.copy(leftPg);

    W_DO(_split_node(leftPg, rightPg, rightEntries, numRight));

    _unfix_page(page);
    return(RCOK);
}


///////////////////////////////////////////////////////////////////////////////
// gist::locateTargetLeaf - find target leaf of key insertion
//
// Description:
//	- presently, simply calls _locate_leaf() for top-down traversal
//	- unfixes the pages on the stack
//
// Return Values:
//      RCOK
///////////////////////////////////////////////////////////////////////////////

rc_t
gist::locateTargetLeaf(
    const vec_t& key, // in: key to find leaf for
    shpid_t& leaf) // out: target leaf
{
    gist_ustk stack;
    vec_t noData;
    W_DO(_locate_leaf(rootNo, stack, key, noData));
    leaf = stack.top()->page.pid();

    // unfix pages
    while (!stack.is_empty()) {
        gist_ustk_entry *e = stack.pop();
        if (e->page.is_fixed()) {
            _unfix_page(e->page);
        }
    }

    return(RCOK);
}


/////////////////////////////////////////////////////////////////////////
// gist::writeLoadfile - write leaf level out as load file
//
// Description:
//	- does a top-down traversal of tree, writing out leaf
//	  data items as they are encountered (does a left-to-right
//	  scan of the entries within each node)
//
// Return Values:
//      RCOK
/////////////////////////////////////////////////////////////////////////

rc_t
gist::writeLoadfile(
    ostream&	s)
{
    return(RCOK);

#if 0
    amdb_clustering::Clustering::iterator cinfo;
    int prevClusterNo = amdb_clustering::invalidNo;
    for (cinfo = clustering->begin(); cinfo != clustering->end(); cinfo++) {
	// skip non-retrieved items (with clusterno == invalidNo == -1):
	// they precede all retrieved items in optClustering
        if (cinfo->clusterNo == amdb_clustering::invalidNo) {
	    continue;
	}

	if (prevClusterNo != amdb_clustering::invalidNo &&
	    prevClusterNo != cinfo->clusterNo) {

	    // we crossed a cluster boundary, write a blank line to indicate this
	    s << endl;
	}
	prevClusterNo = cinfo->clusterNo;

	// fetch next item from its leaf page
	const amdb_treemap::RecInfo *info =
	    profile->itemMap.itemInfo(cinfo->itemNo);

	gist_p page;
	W_DO(_fix_page(page, info->loc.treeLoc.page, LATCH_SH));

	// extract and write key and data in ASCII
	AlignedPred x;
	vec_t pred(x.pred, gist_p::max_tup_sz);
	ext->getKey(page, info->loc.treeLoc.slot, pred);
	s << "\"";
	ext->printPred(s, pred, 1);
	const keyrec_t& rec = page.rec(info->loc.treeLoc.slot);
	vec_t data(rec.elem(), rec.elen());
	s << "\" \"";
	ext->printData(s, data);
	s << "\"" << endl;

	_unfix_page(page);
    }
#endif

    return(RCOK);
}


///////////////////////////////////////////////////////////////////////////////
// gist::_OptTreeBuildState::clear - 
//
// Description:
//
///////////////////////////////////////////////////////////////////////////////

void
gist::_OptTreeBuildState::clear()
{
    delete optClustering;
    optClustering = NULL;
    if (deallocMap) {
	delete tupMap;
	tupMap = NULL;
    }
}