Tree-M/GiST/GiST.cpp

// -*- Mode: C++ -*-

//         GiST.cpp
//
// Copyright (c) 1996, Regents of the University of California
// $Header: /usr/local/devel/GiST/libGiST/libGiST/GiST.cpp,v 1.1.1.1 1996/08/06 23:47:20 jmh Exp $

#include <stdio.h>
#include <string.h>

#include "GiST.h"
#include "GiSTpath.h" // for GiSTRootPage

GiST::GiST()
{
        isOpen=0;
        debug=0;
        store=0;
}

void 
GiST::Create(const char *filename)
{
        GiSTpage page;

        if(IsOpen()) return;
        store=CreateStore();
        store->Create(filename);
        if(!store->IsOpen()) return;
        page=store->Allocate();

        GiSTnode *node=NewNode(this);
        node->Path().MakeRoot();
        WriteNode(node);
        delete node;
        isOpen=1;
}

void 
GiST::Open(const char *filename)
{
        if(IsOpen()) return;
        store=CreateStore();
        store->Open(filename);
        if(!store->IsOpen()) return;
        isOpen=1;
}

void 
GiST::Close()
{
        if(IsOpen()) {
                store->Close();
                isOpen=0;
    }
}

void 
GiST::Insert(const GiSTentry &entry)
{
        InsertHelper(entry, 0);
}

void 
GiST::InsertHelper(const GiSTentry &entry, 
                   int level, // level of tree at which to insert
                   int *splitvec) // a vector to trigger Split instead of forced reinsert
{
        GiSTnode *leaf;
        int overflow=0;

        leaf=ChooseSubtree(GiSTRootPage, entry, level);
        leaf->Insert(entry);
        if (leaf->IsOverFull(*store)) {
                if(ForcedReinsert()&&!leaf->Path().IsRoot()&&(!splitvec||!splitvec[level])) {
                        int split[GIST_MAX_LEVELS];

                        // R*-tree-style forced reinsert
                        for(int i=0; i<GIST_MAX_LEVELS; i++) split[i]=0;
                        OverflowTreatment(leaf, entry, split);
                        overflow=1;
                }
                else Split(&leaf, entry);
                if(leaf->IsOverFull(*store)) {
                        // we only should get here if we reinserted, and the node re-filled
                        assert(overflow);
                        leaf->DeleteEntry(entry.Position());
                        Split(&leaf, entry);
                }
        }
        else WriteNode(leaf);
        if(!overflow) AdjustKeys(leaf, NULL);
        delete leaf;
}

void 
GiST::OverflowTreatment(GiSTnode *node, const GiSTentry& entry, int *splitvec)
{
        GiSTlist<GiSTentry*> deleted;

        // 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;
        // Shorten the tree if necessary (This should only be done if root actually changed!)
        path.MakeRoot();
        GiSTnode *root=ReadNode(path);

        if(!root->IsLeaf()&&root->NumEntries()==1) {
                path.MakeChild((*root)[0]->Ptr());
                GiSTnode *child=ReadNode(path);

                store->Deallocate(path.Page());
                child->SetSibling(0);
                child->Path().MakeRoot();
                WriteNode(child);
                delete child;
        }
        delete root;
}

// handle underfull leaf nodes
int
GiST::CondenseTree(GiSTnode *node)
{
        GiSTlist<GiSTentry*> Q;
        int deleted=0;

        // Must be condensing a leaf
        assert(node->IsLeaf());
        while(!node->Path().IsRoot()) {
                GiSTpath parent_path=node->Path();
                parent_path.MakeParent();
                GiSTnode *P=ReadNode(parent_path);
                GiSTentry *En=P->SearchPtr(node->Path().Page());

                assert(En!=NULL);
                // Handle under-full node
                if(node->IsUnderFull(*store)) {
                    if(!IsOrdered()) {
                                TruePredicate truePredicate;
                                GiSTlist<GiSTentry*> list=node->Search(truePredicate);

                                while(!list.IsEmpty()) {
                                        GiSTentry *e=list.RemoveFront();

                                        Q.Append(e);
                                }
                                P->DeleteEntry(En->Position());
                                WriteNode(P);
                                deleted=1;
                                AdjustKeys(P, NULL);
                        }
                        else {
                                // Try to borrow entries, else coalesce with a neighbor
                                // Have to look at left sibling???
                                GiSTpage neighbor_page=P->SearchNeighbors(node->Path().Page());
                                GiSTpath neighbor_path=node->Path();

                                neighbor_path.MakeSibling(neighbor_page);
                                if(neighbor_page!=0) {
                                        GiSTnode *neighbor;

                                        // If neighbor is RIGHT sibling...
                                        if(node->Sibling()==neighbor_page) neighbor=ReadNode(neighbor_path);
                    else {
                                                neighbor=node;
                                                node=ReadNode(neighbor_path);
                                        }

                                        GiSTentry *e=P->SearchPtr(node->Path().Page());

                                        node->Coalesce(*neighbor, *e);
                                        delete e;
                                        // If not overfull, coalesce, kill right node
                                        if(!node->IsOverFull(*store)) {
                                                node->SetSibling(neighbor->Sibling());
                                                WriteNode(node);

                                                // Delete the neighbor from parent
                                                GiSTentry *e=P->SearchPtr(neighbor->Path().Page());

                                                P->DeleteEntry(e->Position());
                                                WriteNode(P);
                                                delete e;
                                                store->Deallocate(neighbor->Path().Page());
                                                deleted=1;
                                        }
                                        // If overfull, split (same as borrowing)
                                        else {
                                                GiSTnode *node2=node->PickSplit();

                                                node2->Path()=neighbor->Path();
                                                node2->SetSibling(neighbor->Sibling());
                                                WriteNode(node);
                                                WriteNode(node2);
                                                AdjustKeys(node2, &P);
                                                delete node2;
                                                deleted=1;
                                        }
                                        delete neighbor;
                                }
                        }
                }
                // Adjust covering predicate
                if(!deleted) AdjustKeys(node, &P);
                parent_path=node->Path();
                parent_path.MakeParent();
                delete node;
                // Propagate deletes
                if(!deleted) break;
                node=P;
        }
        // Re-insert orphaned entries
        while(!Q.IsEmpty()) {
                GiSTentry *e=Q.RemoveFront();

                InsertHelper(*e, e->Level());
                delete e;
        }
        return(deleted);
}

GiSTnode* 
GiST::ChooseSubtree(GiSTpage page, const GiSTentry &entry, int level)
{
        GiSTnode *node;
        GiSTpath path;

        for(;;) {
                path.MakeChild(page);
                node=ReadNode(path);
                if(level==node->Level()||node->IsLeaf()) break;
                page=node->SearchMinPenalty(entry);
                delete node;
        }
        return node;
}

void 
GiST::Split(GiSTnode **node, const GiSTentry& entry)
{
        int went_left=0, new_root=0;

        if((*node)->Path().IsRoot()) {
                new_root=1;
                (*node)->Path().MakeChild(store->Allocate());
        }

        GiSTnode *node2=(*node)->PickSplit();
        node2->Path().MakeSibling(store->Allocate());
        GiSTentry *e=(*node)->SearchPtr(entry.Ptr());

        if(e!=NULL) {
                went_left=1;
                delete e;
        }
        node2->SetSibling((*node)->Sibling());
        (*node)->SetSibling(node2->Path().Page());
        WriteNode(*node);
        WriteNode(node2);

        GiSTentry *e1=(*node)->Union();
        GiSTentry *e2=node2->Union();

        e1->SetPtr((*node)->Path().Page());
        e2->SetPtr(node2->Path().Page());
        // Create new root if root is being split
        if (new_root) {
                GiSTnode *root=NewNode(this);

                root->SetLevel((*node)->Level()+1);
                root->InsertBefore(*e1, 0);
                root->InsertBefore(*e2, 1);
                root->Path().MakeRoot();
                WriteNode(root);
                delete root;
        }
        else {
                // Insert entry for N' in parent
                GiSTpath parent_path=(*node)->Path();
                parent_path.MakeParent();
                GiSTnode *parent=ReadNode(parent_path);
                // Find the entry for N in parent
                GiSTentry *e=parent->SearchPtr((*node)->Path().Page());
                assert(e!=NULL);
                // Insert the new entry right after it
                int pos=e->Position();

                parent->DeleteEntry(pos);
                parent->InsertBefore(*e1, pos);
                parent->InsertBefore(*e2, pos+1);
                delete e;
                if(!parent->IsOverFull(*store)) WriteNode(parent);
                else {
                        Split(&parent, went_left? *e1: *e2);
                        GiSTpage page=(*node)->Path().Page();

                        (*node)->Path()=parent->Path();
                        (*node)->Path().MakeChild(page);
                        page=node2->Path().Page();
                        node2->Path()=(*node)->Path();
                        node2->Path().MakeSibling(page);
                }
                delete parent;
        }
        if(!went_left) {
                delete *node;
                *node=node2;
        }
        else delete node2;
        delete e1;
        delete e2;
}

GiSTnode* 
GiST::ReadNode(const GiSTpath& path) const
{
        char *buf=new char[store->PageSize()];
        GiSTnode *node=NewNode((GiST *)this);

        store->Read(path.Page(), buf);
        node->Unpack(buf);

#ifdef PRINTING_OBJECTS
        if(debug) {
                cout << "READ PAGE " << path.Page() << ":\n";
                node->Print(cout);
        }
#endif
        node->Path()=path;
        delete []buf;
        return node;
}

void 
GiST::WriteNode(GiSTnode *node)
{
        char *buf=new char[store->PageSize()];
    
        // make Purify happy
        memset(buf, 0, store->PageSize());
#ifdef PRINTING_OBJECTS
        if(debug) {
                cout << "WRITE PAGE " << node->Path().Page() << ":\n";
                node->Print(cout);
        }
#endif
        node->Pack(buf);
        store->Write(node->Path().Page(), buf);
        delete buf;
}

#ifdef PRINTING_OBJECTS

void 
GiST::DumpNode(ostream& os, GiSTpath path) const
{
        GiSTnode *node=ReadNode(path);

        node->Print(os);
        if(!node->IsLeaf()) {
                TruePredicate truePredicate;
                GiSTlist<GiSTentry*> list=node->Search(truePredicate);

                while (!list.IsEmpty()) {
                        GiSTentry *e=list.RemoveFront();

                        path.MakeChild(e->Ptr());
                        DumpNode(os, path);
                        path.MakeParent();
                        delete e;
                }
        }
        delete node;
}

void 
GiST::Print(ostream& os) const
{
        GiSTpath path;

        path.MakeRoot();
        DumpNode(os, path);
}

#endif

GiSTcursor* 
GiST::Search(const GiSTpredicate &query) const
{
        return new GiSTcursor(*this, query);
}

GiST::~GiST()
{
        Close();
        delete store;
}
Revision:	1.1
Committed:	Sun May 6 00:45:51 2001 UTC (25 years, 4 months ago) by root
Branch:	MAIN
CVS Tags:	HEAD
Log Message:	* empty log message *
#	User	Rev	Content
1	root	1.1	// -- Mode: C++ --
2
3			// GiST.cpp
4			//
5			// Copyright (c) 1996, Regents of the University of California
6			// $Header: /usr/local/devel/GiST/libGiST/libGiST/GiST.cpp,v 1.1.1.1 1996/08/06 23:47:20 jmh Exp $
7
8			#include <stdio.h>
9			#include <string.h>
10
11			#include "GiST.h"
12			#include "GiSTpath.h" // for GiSTRootPage
13
14			GiST::GiST()
15			{
16			isOpen=0;
17			debug=0;
18			store=0;
19			}
20
21			void
22			GiST::Create(const char *filename)
23			{
24			GiSTpage page;
25
26			if(IsOpen()) return;
27			store=CreateStore();
28			store->Create(filename);
29			if(!store->IsOpen()) return;
30			page=store->Allocate();
31
32			GiSTnode *node=NewNode(this);
33			node->Path().MakeRoot();
34			WriteNode(node);
35			delete node;
36			isOpen=1;
37			}
38
39			void
40			GiST::Open(const char *filename)
41			{
42			if(IsOpen()) return;
43			store=CreateStore();
44			store->Open(filename);
45			if(!store->IsOpen()) return;
46			isOpen=1;
47			}
48
49			void
50			GiST::Close()
51			{
52			if(IsOpen()) {
53			store->Close();
54			isOpen=0;
55			}
56			}
57
58			void
59			GiST::Insert(const GiSTentry &entry)
60			{
61			InsertHelper(entry, 0);
62			}
63
64			void
65			GiST::InsertHelper(const GiSTentry &entry,
66			int level, // level of tree at which to insert
67			int *splitvec) // a vector to trigger Split instead of forced reinsert
68			{
69			GiSTnode *leaf;
70			int overflow=0;
71
72			leaf=ChooseSubtree(GiSTRootPage, entry, level);
73			leaf->Insert(entry);
74			if (leaf->IsOverFull(*store)) {
75			if(ForcedReinsert()&&!leaf->Path().IsRoot()&&(!splitvec\|\|!splitvec[level])) {
76			int split[GIST_MAX_LEVELS];
77
78			// R*-tree-style forced reinsert
79			for(int i=0; i<GIST_MAX_LEVELS; i++) split[i]=0;
80			OverflowTreatment(leaf, entry, split);
81			overflow=1;
82			}
83			else Split(&leaf, entry);
84			if(leaf->IsOverFull(*store)) {
85			// we only should get here if we reinserted, and the node re-filled
86			assert(overflow);
87			leaf->DeleteEntry(entry.Position());
88			Split(&leaf, entry);
89			}
90			}
91			else WriteNode(leaf);
92			if(!overflow) AdjustKeys(leaf, NULL);
93			delete leaf;
94			}
95
96			void
97			GiST::OverflowTreatment(GiSTnode node, const GiSTentry& entry, int splitvec)
98			{
99			GiSTlist<GiSTentry*> deleted;
100
101			// remove the "top" p entries from the node
102			deleted=RemoveTop(node);
103			WriteNode(node);
104			AdjustKeys(node, NULL);
105			// note that we've seen this level already
106			splitvec[node->Level()]=1;
107			// for each of the deleted entries, call InsertHelper at this level
108			while (!deleted.IsEmpty()) {
109			GiSTentry *tmpentry=deleted.RemoveFront();
110
111			InsertHelper(*tmpentry, node->Level(), splitvec);
112			delete tmpentry;
113			}
114			}
115
116			GiSTlist<GiSTentry*>
117			GiST::RemoveTop(GiSTnode *node)
118			{
119			GiSTlist<GiSTentry*> deleted;
120			int count=node->NumEntries();
121			// default: remove the first ones on the page
122			int num_rem=(int)((count+1)*RemoveRatio()+0.5);
123
124			for(int i=num_rem-1; i>=0; i--) {
125			deleted.Append((GiSTentry )(node)[i].Ptr()->Copy());
126			node->DeleteEntry(i);
127			}
128			return(deleted);
129			}
130
131			void
132			GiST::AdjustKeys(GiSTnode node, GiSTnode *parent)
133			{
134			GiSTnode *P;
135
136			if(node->Path().IsRoot()) return;
137			// Read in node's parent
138			if(parent==NULL) {
139			GiSTpath parent_path=node->Path();
140
141			parent_path.MakeParent();
142			P=ReadNode(parent_path);
143			parent=&P;
144			}
145			else P=*parent;
146
147			// Get the old entry pointing to node
148			GiSTentry *entry=P->SearchPtr(node->Path().Page());
149
150			assert(entry!=NULL);
151
152			// Get union of node
153			GiSTentry *actual=node->Union();
154
155			actual->SetPtr(node->Path().Page());
156			if(!entry->IsEqual(*actual)) {
157			int pos=entry->Position();
158
159			P->DeleteEntry(pos);
160			P->InsertBefore(*actual, pos);
161			// A split may be necessary.
162			// XXX: should we do Forced Reinsert here too?
163			if(P->IsOverFull(*store)) {
164			Split(parent, *actual);
165
166			GiSTpage page=node->Path().Page();
167
168			node->Path()=P->Path();
169			node->Path().MakeChild(page);
170			}
171			else {
172			WriteNode(P);
173			AdjustKeys(P, NULL);
174			}
175			}
176			if(parent==&P) delete P;
177			delete actual;
178			delete entry;
179			}
180
181			void
182			GiST::Sync()
183			{
184			store->Sync();
185			}
186
187			void
188			GiST::Delete(const GiSTpredicate& pred)
189			{
190			GiSTcursor *c=Search(pred);
191			int condensed;
192			GiSTentry *e;
193
194			do {
195			if(c==NULL) return;
196			e=c->Next();
197
198			GiSTpath path=c->Path();
199			delete c;
200			if(e==NULL) return;
201
202			// Read in the node that this belongs to
203			GiSTnode *node=ReadNode(path);
204
205			node->DeleteEntry(e->Position());
206			WriteNode(node);
207			condensed=CondenseTree(node);
208			delete node;
209			if(condensed) {
210			ShortenTree();
211			// because the tree changed, we need to search all over again!
212			// XXX - this is inefficient! users may want to avoid condensing.
213			c=Search(pred);
214			}
215			} while(e!=NULL);
216			}
217
218			void
219			GiST::ShortenTree()
220			{
221			GiSTpath path;
222			// Shorten the tree if necessary (This should only be done if root actually changed!)
223			path.MakeRoot();
224			GiSTnode *root=ReadNode(path);
225
226			if(!root->IsLeaf()&&root->NumEntries()==1) {
227			path.MakeChild((*root)[0]->Ptr());
228			GiSTnode *child=ReadNode(path);
229
230			store->Deallocate(path.Page());
231			child->SetSibling(0);
232			child->Path().MakeRoot();
233			WriteNode(child);
234			delete child;
235			}
236			delete root;
237			}
238
239			// handle underfull leaf nodes
240			int
241			GiST::CondenseTree(GiSTnode *node)
242			{
243			GiSTlist<GiSTentry*> Q;
244			int deleted=0;
245
246			// Must be condensing a leaf
247			assert(node->IsLeaf());
248			while(!node->Path().IsRoot()) {
249			GiSTpath parent_path=node->Path();
250			parent_path.MakeParent();
251			GiSTnode *P=ReadNode(parent_path);
252			GiSTentry *En=P->SearchPtr(node->Path().Page());
253
254			assert(En!=NULL);
255			// Handle under-full node
256			if(node->IsUnderFull(*store)) {
257			if(!IsOrdered()) {
258			TruePredicate truePredicate;
259			GiSTlist<GiSTentry*> list=node->Search(truePredicate);
260
261			while(!list.IsEmpty()) {
262			GiSTentry *e=list.RemoveFront();
263
264			Q.Append(e);
265			}
266			P->DeleteEntry(En->Position());
267			WriteNode(P);
268			deleted=1;
269			AdjustKeys(P, NULL);
270			}
271			else {
272			// Try to borrow entries, else coalesce with a neighbor
273			// Have to look at left sibling???
274			GiSTpage neighbor_page=P->SearchNeighbors(node->Path().Page());
275			GiSTpath neighbor_path=node->Path();
276
277			neighbor_path.MakeSibling(neighbor_page);
278			if(neighbor_page!=0) {
279			GiSTnode *neighbor;
280
281			// If neighbor is RIGHT sibling...
282			if(node->Sibling()==neighbor_page) neighbor=ReadNode(neighbor_path);
283			else {
284			neighbor=node;
285			node=ReadNode(neighbor_path);
286			}
287
288			GiSTentry *e=P->SearchPtr(node->Path().Page());
289
290			node->Coalesce(neighbor, e);
291			delete e;
292			// If not overfull, coalesce, kill right node
293			if(!node->IsOverFull(*store)) {
294			node->SetSibling(neighbor->Sibling());
295			WriteNode(node);
296
297			// Delete the neighbor from parent
298			GiSTentry *e=P->SearchPtr(neighbor->Path().Page());
299
300			P->DeleteEntry(e->Position());
301			WriteNode(P);
302			delete e;
303			store->Deallocate(neighbor->Path().Page());
304			deleted=1;
305			}
306			// If overfull, split (same as borrowing)
307			else {
308			GiSTnode *node2=node->PickSplit();
309
310			node2->Path()=neighbor->Path();
311			node2->SetSibling(neighbor->Sibling());
312			WriteNode(node);
313			WriteNode(node2);
314			AdjustKeys(node2, &P);
315			delete node2;
316			deleted=1;
317			}
318			delete neighbor;
319			}
320			}
321			}
322			// Adjust covering predicate
323			if(!deleted) AdjustKeys(node, &P);
324			parent_path=node->Path();
325			parent_path.MakeParent();
326			delete node;
327			// Propagate deletes
328			if(!deleted) break;
329			node=P;
330			}
331			// Re-insert orphaned entries
332			while(!Q.IsEmpty()) {
333			GiSTentry *e=Q.RemoveFront();
334
335			InsertHelper(*e, e->Level());
336			delete e;
337			}
338			return(deleted);
339			}
340
341			GiSTnode*
342			GiST::ChooseSubtree(GiSTpage page, const GiSTentry &entry, int level)
343			{
344			GiSTnode *node;
345			GiSTpath path;
346
347			for(;;) {
348			path.MakeChild(page);
349			node=ReadNode(path);
350			if(level==node->Level()\|\|node->IsLeaf()) break;
351			page=node->SearchMinPenalty(entry);
352			delete node;
353			}
354			return node;
355			}
356
357			void
358			GiST::Split(GiSTnode **node, const GiSTentry& entry)
359			{
360			int went_left=0, new_root=0;
361
362			if((*node)->Path().IsRoot()) {
363			new_root=1;
364			(*node)->Path().MakeChild(store->Allocate());
365			}
366
367			GiSTnode node2=(node)->PickSplit();
368			node2->Path().MakeSibling(store->Allocate());
369			GiSTentry e=(node)->SearchPtr(entry.Ptr());
370
371			if(e!=NULL) {
372			went_left=1;
373			delete e;
374			}
375			node2->SetSibling((*node)->Sibling());
376			(*node)->SetSibling(node2->Path().Page());
377			WriteNode(*node);
378			WriteNode(node2);
379
380			GiSTentry e1=(node)->Union();
381			GiSTentry *e2=node2->Union();
382
383			e1->SetPtr((*node)->Path().Page());
384			e2->SetPtr(node2->Path().Page());
385			// Create new root if root is being split
386			if (new_root) {
387			GiSTnode *root=NewNode(this);
388
389			root->SetLevel((*node)->Level()+1);
390			root->InsertBefore(*e1, 0);
391			root->InsertBefore(*e2, 1);
392			root->Path().MakeRoot();
393			WriteNode(root);
394			delete root;
395			}
396			else {
397			// Insert entry for N' in parent
398			GiSTpath parent_path=(*node)->Path();
399			parent_path.MakeParent();
400			GiSTnode *parent=ReadNode(parent_path);
401			// Find the entry for N in parent
402			GiSTentry e=parent->SearchPtr((node)->Path().Page());
403			assert(e!=NULL);
404			// Insert the new entry right after it
405			int pos=e->Position();
406
407			parent->DeleteEntry(pos);
408			parent->InsertBefore(*e1, pos);
409			parent->InsertBefore(*e2, pos+1);
410			delete e;
411			if(!parent->IsOverFull(*store)) WriteNode(parent);
412			else {
413			Split(&parent, went_left? e1: e2);
414			GiSTpage page=(*node)->Path().Page();
415
416			(*node)->Path()=parent->Path();
417			(*node)->Path().MakeChild(page);
418			page=node2->Path().Page();
419			node2->Path()=(*node)->Path();
420			node2->Path().MakeSibling(page);
421			}
422			delete parent;
423			}
424			if(!went_left) {
425			delete *node;
426			*node=node2;
427			}
428			else delete node2;
429			delete e1;
430			delete e2;
431			}
432
433			GiSTnode*
434			GiST::ReadNode(const GiSTpath& path) const
435			{
436			char *buf=new char[store->PageSize()];
437			GiSTnode node=NewNode((GiST )this);
438
439			store->Read(path.Page(), buf);
440			node->Unpack(buf);
441
442			#ifdef PRINTING_OBJECTS
443			if(debug) {
444			cout << "READ PAGE " << path.Page() << ":\n";
445			node->Print(cout);
446			}
447			#endif
448			node->Path()=path;
449			delete []buf;
450			return node;
451			}
452
453			void
454			GiST::WriteNode(GiSTnode *node)
455			{
456			char *buf=new char[store->PageSize()];
457
458			// make Purify happy
459			memset(buf, 0, store->PageSize());
460			#ifdef PRINTING_OBJECTS
461			if(debug) {
462			cout << "WRITE PAGE " << node->Path().Page() << ":\n";
463			node->Print(cout);
464			}
465			#endif
466			node->Pack(buf);
467			store->Write(node->Path().Page(), buf);
468			delete buf;
469			}
470
471			#ifdef PRINTING_OBJECTS
472
473			void
474			GiST::DumpNode(ostream& os, GiSTpath path) const
475			{
476			GiSTnode *node=ReadNode(path);
477
478			node->Print(os);
479			if(!node->IsLeaf()) {
480			TruePredicate truePredicate;
481			GiSTlist<GiSTentry*> list=node->Search(truePredicate);
482
483			while (!list.IsEmpty()) {
484			GiSTentry *e=list.RemoveFront();
485
486			path.MakeChild(e->Ptr());
487			DumpNode(os, path);
488			path.MakeParent();
489			delete e;
490			}
491			}
492			delete node;
493			}
494
495			void
496			GiST::Print(ostream& os) const
497			{
498			GiSTpath path;
499
500			path.MakeRoot();
501			DumpNode(os, path);
502			}
503
504			#endif
505
506			GiSTcursor*
507			GiST::Search(const GiSTpredicate &query) const
508			{
509			return new GiSTcursor(*this, query);
510			}
511
512			GiST::~GiST()
513			{
514			Close();
515			delete store;
516			}