gist.cc

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

        // we're finalizing a split of an internal node by inserting
        // the entries for the original and new child in their
        // respective parents
	amdb_breakpoints::BreakInfo info;
	info.event = amdb_breakpoints::relocateChildEvent;
	if (leftGoesRight) {
	    info.param.relocateChildParam.child = childPtr;
	    info.param.relocateChildParam.oldParent = page.pid();
	    info.param.relocateChildParam.newParent = rightSib.pid();
	    (void) _breakHandler(&info);
	}
	if (rightGoesRight) {
	    info.param.relocateChildParam.child = rightChild;
	    info.param.relocateChildParam.oldParent = page.pid();
	    info.param.relocateChildParam.newParent = rightSib.pid();
	    (void) _breakHandler(&info);
	}
    }
#endif

    W_DO(_ext->insert(leftPg, leftPred, vec_t(), childPtr));

    // insert right item (if there is one)
    if (rightPred.size() != 0) {
	gist_p& rightPg = rightGoesRight ? rightSib : page;

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

	W_DO(_ext->insert(rightPg, rightPred, vec_t(), rightChild));

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

    _unfix_page(page);
    _unfix_page(rightSib);

    return RCOK;
}
 

/////////////////////////////////////////////////////////////////////////
// remove - Remove entries matching query
//
// Description:
//
// Preconditions:
// Postconditions:
// Notes:
//
// Return Values:
//      RCOK
/////////////////////////////////////////////////////////////////////////

rc_t
gist::remove(
    const gist_query_t* query)
{

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

    gist_cursor_t cursor;
    gist_p page;
    bool eof = false;
    unsigned int idx;
    shpid_t prevLeaf = 0, leaf; // assumes: 0 is not a valid page no
    AlignedPred x, y;
    char *key = x.pred, *data = y.pred;
    smsize_t klen, dlen;
    int matches[gist_p::max_scnt];
    int numMatches = 0;

    // run a query to find matching items
    W_DO(fetch_init(cursor, query, 0));
    for (;;) {
	klen = gist_p::max_tup_sz;
	dlen = gist_p::max_tup_sz;
        W_DO(_fetch(cursor, key, klen, data, dlen, leaf, idx, eof));
	if (eof || leaf != prevLeaf) {
	    // we're either at the end or switching to a new leaf:
	    // delete the stuff on the last page we visited
	    prevLeaf = leaf;
	    if (page.is_fixed()) {

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

		// do the deletions
		W_DO(_ext->remove(page, matches, numMatches));

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

	        _unfix_page(page);
	    }
	    if (eof) {
		// no more tuples, we're done
		cursor.reset(); // reset cursor to dealloc stack
	        return (RCOK);
	    }
	    W_DO(_fix_page(page, leaf, LATCH_EX));
	    numMatches = 0;
	}
	// accumulate matches which we'll remove when
	// we move on to the next leaf (or finish the query)
	matches[numMatches] = idx;
	numMatches++;
    }
}


/////////////////////////////////////////////////////////////////////////
// fetch_init - Initialize query cursor
//
// Description:
//
// Preconditions:
// Postconditions:
// Notes:
//
// Return Values:
//      RCOK
/////////////////////////////////////////////////////////////////////////

rc_t
gist::fetch_init(
    gist_cursor_t&	cursor,
    const gist_query_t*	query,
    int 		k,
    int			io)
{
    cursor.ext = _ext;

#ifdef AMDB
    // check for breakpoint
    if (_breakHandler != NULL) {
	// construct bp info
	amdb_breakpoints::BreakInfo info;
	info.event = amdb_breakpoints::fetchEvent;
	if (_breakHandler(&info)) return RCOK; // function was cancelled
    }

    if (_profile != NULL) {
        // create new amdb_wkldprofile::Query for the coming query
	_profile->addQuery();
    }
#endif

    // we assume that remnants from prior searches have been erased already
    cursor.query = query;
    cursor.k = (k < 1) ? MAXINT : k;
    cursor.io = (io < 1) ? MAXINT : io;
    cursor.cext = cursor.ext->queryCursor(query);
    cursor.cext->iter_init(cursor, rootNo);

    return RCOK;
}


/////////////////////////////////////////////////////////////////////////
// _static_fix_page - fix page in buffer pool
//
// Description:
//	- pin page and set descriptor in 'page'
//	- we need this function to be static so we can call 
//	  it from other static member functions (such as _optItemStream)
//
// Return Values:
//      RCOK
/////////////////////////////////////////////////////////////////////////

rc_t
gist::_static_fix_page(
    gist_file&    	file,
    gist_p&		page,
    shpid_t 		pageNo,
    latch_mode_t	mode)
{
    page._descr = file.pinPage(pageNo);
    if (page._descr == NULL) {
        return eOUTOFSPACE;
    }
    page._pp = (page_s *) page._descr->page;
    return RCOK;
}


/////////////////////////////////////////////////////////////////////////
// _static_unfix_page - unfix page in buffer pool
//
// Description:
//	- this is a static member function for the same reasons as
//	  _static_fix_page
/////////////////////////////////////////////////////////////////////////

void
gist::_static_unfix_page(
    gist_file&    	file,
    gist_p&		page)
{
    assert(page._descr->pinCount > 0);
    assert(page._pp != NULL);
    file.unpinPage(page._descr);
    page._pp = NULL;
}


/////////////////////////////////////////////////////////////////////////
// fetch - return next matching tuple
//
// Description:
//
// Preconditions:
// Postconditions:
// Notes:
//
// Return Values:
//      RCOK
/////////////////////////////////////////////////////////////////////////

rc_t
gist::fetch(
    gist_cursor_t&	cursor,
    void*		key,
    smsize_t&		klen,
    void*		el,
    smsize_t&		elen,
    bool&		eof)
{
    shpid_t leaf;
    unsigned int idx;

    rc_t status;
    if (cursor.cext->prio() == true) {
        status = _fetch_nn(cursor, key, klen, el, elen, leaf, idx, eof);
    } else {
        status = _fetch(cursor, key, klen, el, elen, leaf, idx, eof);
    }
#ifdef AMDB
    // maintain profiling information
    if (_profile != NULL) {
	if (!eof) {
	    // record the returned item (its itemno)
	    _profile->addToResultSet(leaf, idx);
	} else {
	    // query is finished: update the per-query and global
	    // traversal statistics
	    _profile->finalizeQuery(rootNo);
	}
    }
#endif

    if (eof) {
        cursor.reset(); // We're done, get rid of state.
    }
    return (status);
}


/////////////////////////////////////////////////////////////////////////
// _copy_rec - copy lstk entry to output variables
//
// Description:
//
// Preconditions:
// Postconditions:
// Notes:
//
// Return Values:
//      RCOK
/////////////////////////////////////////////////////////////////////////

inline rc_t
_copy_rec(
    void* key,
    smsize_t& klen,
    void* data,
    smsize_t& dlen,
    shpid_t& leafNo,
    unsigned int& idx,
    gist_lstk_entry& e)
{
    if (klen < e.val.item.klen || dlen < e.val.item.dlen) {
	// not enough space to copy the items
	delete [] e.val.item.key;
	delete [] e.val.item.data;
	e.typ = gist_lstk_entry::eIllegal;	// !gc
	return(eRECWONTFIT);
    }
    
    //copy key and data ptr
    (void) memcpy(key, e.val.item.key, e.val.item.klen);
    klen = e.val.item.klen;
    (void) memcpy(data, e.val.item.data, e.val.item.dlen);
    dlen = e.val.item.dlen;
    leafNo = e.val.item.page;
    idx = e.val.item.idx;
    delete [] e.val.item.key;
    delete [] e.val.item.data;
    e.typ = gist_lstk_entry::eIllegal;		// !gc
    return(RCOK);
}


/////////////////////////////////////////////////////////////////////////
// _fetch - return next match from lookup stack
//
// Description:
//
// Preconditions:
// Postconditions:
// Notes:
//
// Return Values:
//      RCOK
/////////////////////////////////////////////////////////////////////////

rc_t
gist::_fetch(
    gist_cursor_t&	cursor,
    void*		key,
    smsize_t&		klen,
    void*		data,
    smsize_t&		dlen,
    shpid_t&		leafNo,
    unsigned int&	idx,
    bool&		eof)
{
    AlignedPred x;
    char *k = x.pred; // for 8-byte alignment
    eof = false;
    gist_stack_cursorext_t* cext = (gist_stack_cursorext_t*) cursor.cext;

    int numMatches;
    int matches[gist_p::max_scnt];
    gist_lstk_entry e;
    while (cext->iter_fetch(cursor, &e) != eEOF) {
        if (e.typ == gist_lstk_entry::eItem) {
	    W_DO(_copy_rec(key, klen, data, dlen, leafNo, idx, e));
            return (RCOK);
        }

        // fix the page, process it, then unfix it
	gist_p page;
	W_DO(_fix_page(page, e.val.node.page, LATCH_SH));
	cursor.ext->search(page, cursor.query, matches, numMatches);

	// we needn't push more leaf items on the stack than our retrieval
	// limit would allow us to return (don't try to apply this
	// optimization to priority queues - at this point, we haven't
	// prioritized the items).
	if (page.is_leaf() && numMatches > cursor.k) {
	    numMatches = cursor.k;
	}

	cext->iter_update(cursor, page, numMatches, matches);

#ifdef AMDB
	// break event
	if (_breakHandler != NULL) {
	    // construct bp info
	    amdb_breakpoints::BreakInfo info;
	    info.event = amdb_breakpoints::traversalEvent;
	    info.node = e.val.node.page;
	    (void) _breakHandler(&info);
	}

        // maintain profiling information
	if (_profile != NULL) {
	    _profile->traversePage(page.pid(), page.is_leaf(),
		e.val.node.parent);
	    // count retrievals, now that we're done with the page
	    if (page.is_leaf()) {
	        _profile->countRetrievals(page.pid(), numMatches, matches);
	    }
	}
#endif

	_unfix_page(page);
    }
    e.typ = gist_lstk_entry::eIllegal;		// !gc

    eof = true;
    return(RCOK);
}


/////////////////////////////////////////////////////////////////////////
// _fetch - return next match from lookup stack (nearest neighbor)
//
// Description:
// 	- To keep parents around, we park parent entries on the queue
//	  without ever GCing them.
//
// Preconditions:
// Postconditions:
// Notes:
//
// Return Values:
//      RCOK
/////////////////////////////////////////////////////////////////////////

rc_t
gist::_fetch_nn(
    gist_cursor_t&	cursor,
    void*		key,
    smsize_t&		klen,
    void*		data,
    smsize_t&		dlen,
    shpid_t&		leafNo,
    unsigned int&	idx,
    bool&		eof)
{
    eof = false;
    gist_queue_cursorext_t* cext = (gist_queue_cursorext_t*) cursor.cext;

    int numMatches;
    int matches[gist_p::max_scnt];
    gist_prioq_entry e;
    while (cext->iter_fetch(cursor, &e) != eEOF) {
        if (e.typ == gist_lstk_entry::eItem) {
	    W_DO(_copy_rec(key, klen, data, dlen, leafNo, idx, e));
#ifdef AMDB
            if (_profile != NULL) {
		// count 1 retrieved item
	        _profile->countRetrievals(leafNo, 1, (int *) &idx);
	    }
#endif
            return (RCOK);
        }

        // fix the page, process it, then unfix it
	gist_p page;
	W_DO(_fix_page(page, e.val.node.page, LATCH_SH));
	cursor.ext->search(page, cursor.query, matches, numMatches);

	// insert the entries into priority queue
	cext->iter_update(cursor, page, numMatches, matches);

#ifdef AMDB
	// break event
	if (_breakHandler != NULL) {
	    // construct bp info
	    amdb_breakpoints::BreakInfo info;
	    info.event = amdb_breakpoints::traversalEvent;
	    info.node = e.val.node.page;
	    (void) _breakHandler(&info);
	}

        // maintain profiling information
	if (_profile != NULL) {
	    _profile->traversePage(page.pid(), page.is_leaf(), e.val.node.parent);
	}
#endif

	_unfix_page(page);
    }
    e.typ = gist_lstk_entry::eIllegal;		// !gc

    eof = true;
    return(RCOK);
}


/////////////////////////////////////////////////////////////////////////
// _check_node - check node for structural consistency
//
// Description:
//
// Preconditions:
// Postconditions:
// Notes:
//
// Return Values: