view release on metacpan or  search on metacpan

GiST/GiST.cpp  view on Meta::CPAN

	// remove the "top" p entries from the node
	deleted=RemoveTop(node);
	WriteNode(node);
	AdjustKeys(node, NULL);
	// note that we've seen this level already
	splitvec[node->Level()]=1;
	// for each of the deleted entries, call InsertHelper at this level
	while (!deleted.IsEmpty()) {
		GiSTentry *tmpentry=deleted.RemoveFront();

		InsertHelper(*tmpentry, node->Level(), splitvec);
		delete tmpentry;
	}
}

GiSTlist<GiSTentry*>
GiST::RemoveTop(GiSTnode *node)
{
	GiSTlist<GiSTentry*> deleted;
	int count=node->NumEntries();
	// default: remove the first ones on the page
	int num_rem=(int)((count+1)*RemoveRatio()+0.5);

	for(int i=num_rem-1; i>=0; i--) {
		deleted.Append((GiSTentry *)(*node)[i].Ptr()->Copy());
		node->DeleteEntry(i);
	}
	return(deleted);
}

void 
GiST::AdjustKeys(GiSTnode *node, GiSTnode **parent)
{
	GiSTnode *P;

	if(node->Path().IsRoot()) return;
	// Read in node's parent
	if(parent==NULL) {
		GiSTpath parent_path=node->Path();

		parent_path.MakeParent();
		P=ReadNode(parent_path);
		parent=&P;
	}
	else P=*parent;

	// Get the old entry pointing to node
	GiSTentry *entry=P->SearchPtr(node->Path().Page());

	assert(entry!=NULL);

	// Get union of node
	GiSTentry *actual=node->Union();

	actual->SetPtr(node->Path().Page());
	if(!entry->IsEqual(*actual)) {
		int pos=entry->Position();

		P->DeleteEntry(pos);
		P->InsertBefore(*actual, pos);
		// A split may be necessary.
		// XXX: should we do Forced Reinsert here too?
		if(P->IsOverFull(*store)) {
			Split(parent, *actual);

			GiSTpage page=node->Path().Page();

			node->Path()=P->Path();
			node->Path().MakeChild(page);
		}
        else {
		    WriteNode(P);
			AdjustKeys(P, NULL);
		}
	}
	if(parent==&P) delete P;
	delete actual;
	delete entry;
}

void 
GiST::Sync()
{
	store->Sync();
}

void 
GiST::Delete(const GiSTpredicate& pred)
{
	GiSTcursor *c=Search(pred);
	int condensed;
	GiSTentry *e;

	do {
		if(c==NULL) return;
		e=c->Next();

		GiSTpath path=c->Path();
		delete c;
		if(e==NULL) return;

		// Read in the node that this belongs to
		GiSTnode *node=ReadNode(path);

		node->DeleteEntry(e->Position());
		WriteNode(node);
		condensed=CondenseTree(node);
		delete node;
		if(condensed) {
			ShortenTree();
			// because the tree changed, we need to search all over again!
			// XXX - this is inefficient!  users may want to avoid condensing.
			c=Search(pred);
		}
	} while(e!=NULL);
}

void
GiST::ShortenTree()
{
	GiSTpath path;