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 *
#	Content
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	}