gist.cc

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

    // update the BP, if there is one
    if (!page.is_root()) {
	unsigned int oldLen = bpv.len(0);
	_ext->unionBp(page, bpv, true, key, vec_t(), bpChanged);
	assert(bpv.len(0) <= gist_p::max_tup_sz);
	assert(bpChanged || oldLen == bpv.len(0));

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

    } else {
	// the root doesn't have a BP
	bpChanged = false;
    }

    return (RCOK);
}


/////////////////////////////////////////////////////////////////////////
// _apply_update - Update/insert entries on page and update BP
//
// Description:
// 	- If both 'leftBp' and 'rightBp' contain keys with non-zero size, we
// 	  are inserting the BPs resulting from a page split.  In general,
// 	  'leftBp' (having been recomputed to fit its new contents by
// 	  pickSplit()) will be different from that present before the split.
//	- If only 'leftBp' has non-zero size, we are simply applying an
// 	  update caused by a change in a child BP.
//	- We compute the updated BP *before* modifying the page contents,
//	  otherwise the new key(s) would be present on the page and also
//	  passed as arguments 'pred1/-2' into unionBp
//
// Preconditions:
// Postconditions:
// Notes:
//
// Return Values:
//      RCOK
//      eRECWONTFIT
/////////////////////////////////////////////////////////////////////////

rc_t
gist::_apply_update(
    gist_p&		page, // in/out: parent to update
    int& 		leftIdx, // in/out: slot index of entry for orig. child page
    const vec_t&	leftBp, // in: BP of orig. child page
    const vec_t&	rightBp, // in: BP of new child (or NULL if orig. child not split)
    shpid_t 		rightChild, // in: pointer to new child
    vec_t&		bp, // in/out: BP as stored in parent entry
    bool&		bpChanged) // out: true if the BP changed
{
    if (!page.is_root()) {
	unsigned int oldLen = bp.len(0);
	_ext->unionBp(page, bp, true, leftBp, rightBp, bpChanged);
	assert(bp.len(0) <= gist_p::max_tup_sz);
	assert(bpChanged || oldLen == bp.len(0));

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

    } else {
        bpChanged = false;
    }

    // update the entry for the original page
    W_DO(_ext->updateKey(page, leftIdx, leftBp));

#ifdef AMDB
    // call to updateKey() updated a BP
    if (_breakHandler != NULL) {
	// construct bp info
	amdb_breakpoints::BreakInfo info;
	info.event = amdb_breakpoints::bpUpdatedEvent;
	info.param.updNodeParam = page.pid();
	(void) _breakHandler(&info);
    }
#endif

    // insert rightBp, if we have one
    if (rightBp.size() != 0) {
#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

	// insert the entry for the new right sibling
	rc_t status = _ext->insert(page, rightBp, vec_t(), rightChild);
	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
    }

    return(RCOK);
}


/////////////////////////////////////////////////////////////////////////
// _split - split page and update parent
//
// Description:
// 	- Split page, given the split info, and return the new right page
// 	  through rightSib. 
//	- Both page and rightSib remain fixed.
//
// Preconditions:
// Postconditions:
// Notes:
//
// Return Values:
//      RCOK
/////////////////////////////////////////////////////////////////////////

rc_t
gist::_split(
    shpid_t 		root,
    gist_p&		page, // in/out: page to split
    gist_ustk&		gstack, // records ancestors
    int 		stkIdx, // our pos on stack
    const int 		rightEntries[], // slot indices of entries for the right sibling
    int 		numRight, // how many right entries
    gist_p&		rightSib, // out: new right sibling
    vec_t&		leftBp, // BP for page
    vec_t&		rightBp) // BP for rightSib
{
#ifdef AMDB
    if (_breakHandler != NULL) {
	// construct bp info
	amdb_breakpoints::BreakInfo info;
	info.event = amdb_breakpoints::splitEvent;
	info.node = page.pid();
	(void) _breakHandler(&info);
    }
#endif

    if (gstack.is_root(stkIdx)) {
        // do root split
	gist_p leftChild;

	// both children will be at the level the root is at now
	W_DO(_new_page(root, leftChild, page.level()));
	W_DO(_new_page(root, rightSib, page.level()));

	// copy all entries on root into leftChild
	W_DO(page.copy(leftChild));

	// create a blank root page
	gistctrl_t hdr;
	hdr.root = root;
	hdr.level = page.level() + 1; // added one level
	W_DO(page.format(root, &hdr));

	// split the left child
	W_DO(_split_node(leftChild, rightSib, rightEntries, numRight));

#ifdef AMDB
	if (_breakHandler != NULL) {
	    // construct bp info for root split
	    amdb_breakpoints::BreakInfo info;
	    info.event = amdb_breakpoints::newRootEvent;
	    info.param.newRootParam.leftNode = leftChild.pid();
	    info.param.newRootParam.rightNode = rightSib.pid();
	    info.param.newRootParam.rightChildren = new amdb_breakpoints::ChildVect();
	    _getChildren(rightSib, info.param.newRootParam.rightChildren);
	    (void) _breakHandler(&info);
	}
#endif
	// add the two new entries to the otherwise empty root
	W_DO(_ext->insert(page, leftBp, vec_t(), leftChild.pid()));
	W_DO(_ext->insert(page, rightBp, vec_t(), rightSib.pid()));

	// unfix root and return left child as split page.  we needn't
	// fix the stack, because _update_parent() will not be called
	_unfix_page(page);
	page = leftChild;
    } else {
        // do regular split
	W_DO(_new_page(root, rightSib, page.level()));
	W_DO(_split_node(page, rightSib, rightEntries, numRight));

#ifdef AMDB
	if (_breakHandler != NULL) {
	    // Construct bp info for node split. This structure change
	    // event must be reported at this point rather than after
	    // the parent update (the parent update might hit another
	    // breakpoint and try to display the tree, which requires
	    // the in-core tree structure to be updated).
	    amdb_breakpoints::BreakInfo info;
	    info.event = amdb_breakpoints::newNodeEvent;
	    info.param.newNodeParam.origNode = page.pid();
	    info.param.newNodeParam.rightSib = rightSib.pid();
	    info.param.newNodeParam.rightChildren = new amdb_breakpoints::ChildVect();
	    _getChildren(rightSib, info.param.newNodeParam.rightChildren);
	    (void) _breakHandler(&info);
	}
#endif

	// leave both page and rightSib fixed, the caller might have
	// to insert into one of them

	W_DO(_update_parent(root, gstack, stkIdx+1, leftBp, rightBp,
	    rightSib.pid()));
    }

    return RCOK;
}


/////////////////////////////////////////////////////////////////////////
// _split_node - split single page 
//
// Description:
//
// Preconditions:
// Postconditions:
// Notes:
//
// Return Values:
//      RCOK
/////////////////////////////////////////////////////////////////////////

rc_t
gist::_split_node(
    gist_p&		left, // page to split (remove entries from)
    gist_p&		right, // page to add entries to
    const int 		rightEntries[], // slot indices of entries to be moved right
    int 		numRight) // number of entries to move right
{
    // first, move entries to new right sibling
    AlignedPred x, y;
    char *data = y.pred;
    vec_t keyv;
    vec_t datav;

    // gist::_split() guarantees that this is true (see above).
    assert(!left.is_root());
    assert(!right.is_root());

    // distribute the entries;
    for (int i = 0; i < numRight; i++) {
	int idx = rightEntries[i];
	assert(idx < left.nrecs()); // gist_ext_t::pickSplit says this shouldn't happen

	// item exists on page; copy it (both key and data)
	keyv.set(x.pred, gist_p::max_tup_sz);
	_ext->getKey(left, idx, keyv);
	(void) memcpy(data, left.rec(idx).elem(), left.rec(idx).elen());
	datav.set(data, left.rec(idx).elen());
	W_DO(_ext->insert(right, keyv, datav, left.rec(idx).child()));
    }

    // Clean up the original page: remove the moved entries
    W_DO(_ext->remove(left, rightEntries, numRight));

    return RCOK;
}


/////////////////////////////////////////////////////////////////////////
// intCmp - qsort integer comparison function
//
// Return Values:
/////////////////////////////////////////////////////////////////////////

static int
intCmp(
    const void*		a,
    const void*		b)
{
    return *((int *) a) - *((int *) b);
}


/////////////////////////////////////////////////////////////////////////
// insert - insert a new entry into the tree
//
// Description:
//
// Preconditions:
// Postconditions:
// Notes:
//
// Return Values:
//      RCOK
/////////////////////////////////////////////////////////////////////////

rc_t
gist::insert(
    const void*		key, 
    const int	    	klen,
    const void*		data,
    const int	    	dlen)
{
    vec_t keyv(key, klen);
    vec_t datav(data, dlen);

#ifdef AMDB
    if (_breakHandler != NULL) {
	// construct bp info
	amdb_breakpoints::BreakInfo info;
	info.event = amdb_breakpoints::insertEvent;
	if (_breakHandler(&info)) {
	    printf("cancelled insert\n");
	    return RCOK; // function was cancelled
	}
    }
#endif

    gist_ustk gstack;
    bool wasSplit = false; // true if leaf is split

    W_DO(_locate_leaf(rootNo, gstack, keyv, datav));
    gist_p &leaf = gstack.top()->page;

    // extract BP from parent entry
    AlignedPred w;
    vec_t bpv(w.pred, gist_p::max_tup_sz);
    _extract_bp(gstack, 0, bpv);

    // insert item/update BP
    bool bpChanged = false;
    rc_t status = _insert_leaf(leaf, keyv, datav, bpv, bpChanged);
    if (status && status != eRECWONTFIT) {
        return (status);
    }

    if (status == eRECWONTFIT) {
	// something didn't fit; we must split the page

	// find out how to split
	int rightEntries[gist_p::max_scnt];
	int numRight = gist_p::max_scnt;
	AlignedPred x, y;
	vec_t leftv(x.pred, gist_p::max_tup_sz);
	vec_t rightv(y.pred, gist_p::max_tup_sz);
	bool newGoesRight, dummyBool;
	W_DO(_ext->pickSplit(leaf, rightEntries, numRight, bpv, leftv, rightv,
	    vec_t(keyv, datav), newGoesRight, vec_t(), dummyBool));
	assert(leftv.len(0) <= gist_p::max_tup_sz);
	assert(rightv.len(0) <= gist_p::max_tup_sz);
	assert(numRight <= gist_p::max_scnt);
	// assert(_check_split_info(leaf, rightEntries, numRight));

        // do the split
	gist_p rightSib;
	W_DO(_split(rootNo, leaf, gstack, 0, rightEntries, numRight, rightSib, leftv,
	    rightv));
	wasSplit = true;

	// try again; the bp is already updated due to the split
	gist_p &p = newGoesRight ? rightSib : leaf;
#ifdef AMDB
	if (_breakHandler != NULL) {
	    // construct bp info
	    amdb_breakpoints::BreakInfo info;
	    info.event = amdb_breakpoints::nodeInsertEvent;
	    info.node = p.pid();
	    (void) _breakHandler(&info);
	}
#endif
	W_DO(_ext->insert(p, keyv, datav, 0));

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

	_unfix_page(leaf);
	_unfix_page(rightSib);
    }

    if (bpChanged && !wasSplit) {
        W_DO(_update_parent(rootNo, gstack, 1, bpv, vec_t(), 0));

	_unfix_page(leaf);
    }

    // unfix pages that haven't been unfixed before in calls to
    // _split() and _update_parent()
    while (!gstack.is_empty()) {
        gist_ustk_entry *e = gstack.pop();
	if (e->page.is_fixed()) {
	    _unfix_page(e->page);
	}
    }

    // XXX debug
    assert(_file.allUnpinned());

    return(RCOK);
}


/////////////////////////////////////////////////////////////////////////
// _update_parent - Update internal node and propagate changes
//
// Description:
//
// Preconditions:
// Postconditions:
// Notes:
//
// Return Values:
//      RCOK
/////////////////////////////////////////////////////////////////////////

rc_t
gist::_update_parent(
    shpid_t 		root,
    gist_ustk&		gstack, // records ancestors
    int 		stkIdx, // parent level on stack
    const vec_t&	leftPred, // BP of orig. child page
    const vec_t&	rightPred, // BP of child's new sibling
    shpid_t 		rightChild) // pointer to child's new sibling
{
    gist_p &page = gstack.top(stkIdx)->page;

    // extract BP from parent entry
    AlignedPred w;
    vec_t bpv(w.pred, gist_p::max_tup_sz);
    _extract_bp(gstack, stkIdx, bpv);

    // save the pointer to the original child page
    const shpid_t childPtr = page.rec(gstack.top(stkIdx)->idx).child();

    // apply the updates to the parent page (update bp and left item's
    // pred, insert new item)
    bool bpChanged;
    rc_t status = _apply_update(page, gstack.top(stkIdx)->idx, leftPred, rightPred,
        rightChild, bpv, bpChanged);
    if (status != eRECWONTFIT) {
	// either we're done or there was some error; in any case,
	// we're finished with this node
	if (!status && bpChanged) {
	    W_DO(_update_parent(root, gstack, stkIdx+1, bpv, vec_t(), 0));
	}
	_unfix_page(page);
        return (status);
    }

    // something didnt fit, we have to split the page

    // we don't need the entry for the original child anymore
    W_DO(_ext->remove(page, &(gstack.top(stkIdx)->idx), 1));

    // get split info
    int rightEntries[gist_p::max_scnt];
    int numRight;
    AlignedPred x, y;
    vec_t leftv(x.pred, gist_p::max_tup_sz);
    vec_t rightv(y.pred, gist_p::max_tup_sz);
    bool leftGoesRight;
    bool rightGoesRight;
    W_DO(_ext->pickSplit(page, rightEntries, numRight, bpv, leftv, rightv, leftPred,
        leftGoesRight, rightPred, rightGoesRight));
    assert(leftv.len(0) <= gist_p::max_tup_sz);
    assert(rightv.len(0) <= gist_p::max_tup_sz);
    assert(numRight <= gist_p::max_scnt);
    // assert(_check_split_info(leaf, rightEntries, numRight));

    // do the split
    gist_p rightSib;
    W_DO(_split(root, page, gstack, stkIdx, rightEntries, numRight, rightSib, leftv,
        rightv));

    // insert left item
    gist_p &leftPg = leftGoesRight ? rightSib : page;

#ifdef AMDB
    if (_breakHandler != NULL) {