Tree-M/GiST/GiSTnode.cpp

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

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

#include <string.h>
#include "GiST.h"

const int ALLOC_INCR=32;

extern "C" int 
GiSTintcmp(const void *x, const void *y)
{
        int i=*(int *)x;
        int j=*(int *)y;
        return(i-j);
}

int 
GiSTnode::Size() const
{
        int size=GIST_PAGE_HEADER_SIZE+sizeof(GiSTlte);
        int fixlen=FixedLength();

        if(fixlen) size+=numEntries*(fixlen+sizeof(GiSTpage));
        else for(int i=0; i<numEntries; i++)
                size+=(sizeof(GiSTlte)+sizeof(GiSTpage)+entries[i]->CompressedLength());
        return size;
}

GiSTnode::GiSTnode()
{
        packedNode=NULL;
        sibling=0;
        level=0;
        numEntries=0;
        maxEntries=0;
        entries=NULL;
        tree=NULL;
}

GiSTnode::GiSTnode(const GiSTnode &node)
{
        maxEntries=node.maxEntries;
        numEntries=node.numEntries;
        level=node.level;
        sibling=node.sibling;
        tree=node.tree;
        if (node.packedNode) {
                packedNode=new char[tree->Store()->PageSize()];
                memcpy(packedNode, node.packedNode, tree->Store()->PageSize());
        }
        else packedNode=NULL;
        if(maxEntries) entries=new GiSTentryptr[maxEntries];
        else entries=NULL;
        for(int i=0; i<numEntries; i++) {
                entries[i]=(GiSTentry*) node.entries[i]->Copy();
                ((GiSTentry *)entries[i])->SetNode(this);
        }
        path=node.path;
}

void 
GiSTnode::Expand(int index)
{
        int newMaxEntries=maxEntries+ALLOC_INCR;
        if(newMaxEntries<index+1) newMaxEntries=index+1+ALLOC_INCR;
        GiSTentryptr *newEntries=new GiSTentryptr[newMaxEntries];
        int i;

        for(i=numEntries; i<newMaxEntries; i++) newEntries[i]=NULL;
        for(i=0; i<numEntries; i++) newEntries[i]=entries[i];
        if(entries!=NULL) delete entries;
        entries=newEntries;
        maxEntries=newMaxEntries;
}

GiSTentryptr& 
GiSTnode::operator[](int index)
{
        assert(index>=0);
        if (index>=maxEntries) Expand(index);
        return entries[index];
}

const GiSTentryptr& 
GiSTnode::operator[](int index) const
{
        static GiSTentryptr e;

        assert(index>=0);
        if(index>=maxEntries) return e;
        return entries[index];
}

void 
GiSTnode::InsertBefore(const GiSTentry& entry, int index)
{
        assert(index<=NumEntries());
        GiSTentry *e=(GiSTentry*) entry.Copy();

        e->SetLevel(Level());
        e->SetPosition(index);
        e->SetNode(this);
        // Move everything else over
        for(int i=NumEntries(); i>index; i--) {
                GiSTentry *e=(*this)[i-1];
                e->SetPosition(i);
                (*this)[i]=e;
        }
        // Stick the entry in
        (*this)[index]=e;
        // Bump up the count
        numEntries++;
}

void 
GiSTnode::Insert(const GiSTentry& entry)
{
        // Find out where to insert it
        int i;

        for(i=0; i<NumEntries(); i++) if((*this)[i]->Compare(entry)>0) break;
        // Do the deed
        InsertBefore(entry, i);
}

void 
GiSTnode::DeleteEntry(int index)
{
        int j;

        assert(index<numEntries);
        // free up the memory in the entry to be deleted
        if(entries[index].Ptr()) delete entries[index].Ptr();
        // Remove the entry
        for(j=index; j<numEntries-1; j++) {
                entries[j]=entries[j+1];
                entries[j]->SetPosition(j);
        }
        numEntries--;
}

void
GiSTnode::DeleteBulk(int vec[], int veclen)
{
        int i;

        qsort(vec, veclen, sizeof(int), GiSTintcmp);
        for(i=veclen-1; i>=0; i--) DeleteEntry(vec[i]);
}

void 
GiSTnode::Pack(char *page) const
{
        // Pack the header
        GiSTheader *h=(GiSTheader *) page;

        h->level=Level();
        h->numEntries=NumEntries();
        h->sibling=Sibling();

        int fixlen=FixedLength();
        GiSTlte *ltable=(GiSTlte *)(page+tree->Store()->PageSize());
        GiSTlte ltptr=GIST_PAGE_HEADER_SIZE;

        for(int i=0; i<numEntries; i++) {
                GiSTcompressedEntry compressedEntry=(*this)[i]->Compress();

                if(fixlen) assert(fixlen==compressedEntry.keyLen);
                // Copy the entry onto the page
                if(compressedEntry.keyLen>0) memcpy(page+ltptr, compressedEntry.key, compressedEntry.keyLen);
                memcpy(page+ltptr+compressedEntry.keyLen, &compressedEntry.ptr, sizeof(GiSTpage));
                // Be tidy
                if(compressedEntry.key) delete compressedEntry.key;
                // Enter a pointer to the entry in the line table
                if(!fixlen) *--ltable=ltptr;
                ltptr+=compressedEntry.keyLen+sizeof(GiSTpage);
        }
        // Store extra line table entry so we know last entry's length
        *--ltable=ltptr;
}

void 
GiSTnode::Unpack(const char *page)
{
        const GiSTheader *h=(const GiSTheader *) page;

        Reset();
        SetLevel(h->level);
        SetSibling(h->sibling);
        if(!packedNode) packedNode=new char[tree->Store()->PageSize()];
        memcpy(packedNode, page, tree->Store()->PageSize());
        Expand(h->numEntries);
        SetNumEntries(h->numEntries);
        for(int i=0; i<h->numEntries; i++) {
                GiSTcompressedEntry tmpentry=Entry(i);
                GiSTentry *e=CreateEntry();

                e->SetLevel(Level());
                e->SetPosition(i);
                e->SetNode(this);
                e->Decompress(tmpentry);
                // be tidy
                if(tmpentry.key) delete tmpentry.key;
                // Append the body with the entry
                entries[i]=e;
        }
}

// SearchMinPenalty returns where a new entry should be inserted.
GiSTpage 
GiSTnode::SearchMinPenalty(const GiSTentry &newEntry) const
{
        GiSTentry *minEntry=NULL;
        GiSTpenalty *minPenalty=NULL;

        for(int i=0; i<numEntries; i++) {
                GiSTentry *e=(*this)[i];
                assert(e->Node()==this);
                GiSTpenalty *penalty=e->Penalty(newEntry);

                if(minEntry==NULL||(*penalty)<(*minPenalty)) {
                        minEntry=e;
                        if(minPenalty) delete minPenalty;
                        minPenalty=penalty;
                }
                else delete penalty;
        }
        delete minPenalty;
        return minEntry->Ptr();
}

void 
GiSTnode::Coalesce(const GiSTnode &source, const GiSTentry& entry) // entry is the entry in the parent node that points to this
{
        // Coalesce by one-by-one insertion
        //   Take each entry from the source node
        //   and insert it into this node.
        for(int i=0; i<source.numEntries; i++) {
                GiSTentry& e=source[i];

                InsertBefore(e, NumEntries());
        }
}

GiSTcompressedEntry 
GiSTnode::Entry(int entryPos) const
{
        // Look up the line table
        GiSTlte keyPhysicalPos, nextKeyPhysicalPos;
        int fixlen=FixedLength();

        if(!fixlen) {
                memcpy(&keyPhysicalPos, packedNode+tree->Store()->PageSize()-(entryPos+1)*sizeof(GiSTlte), sizeof(GiSTlte));
                memcpy(&nextKeyPhysicalPos, packedNode+tree->Store()->PageSize()-(entryPos+2)*sizeof(GiSTlte), sizeof(GiSTlte));
        }
        else {
                keyPhysicalPos=GIST_PAGE_HEADER_SIZE+(sizeof(GiSTpage)+fixlen)*entryPos;
                nextKeyPhysicalPos=keyPhysicalPos+sizeof(GiSTpage)+fixlen;
        }

        // Allocate and set up the return key
        GiSTcompressedEntry entry;

        entry.keyLen=nextKeyPhysicalPos-keyPhysicalPos-sizeof(GiSTpage);
        if(entry.keyLen>0) {
                entry.key=new char[entry.keyLen];
                memcpy(entry.key, packedNode+keyPhysicalPos, entry.keyLen);
        }
        memcpy(&entry.ptr, packedNode+keyPhysicalPos+entry.keyLen, sizeof(GiSTpage));
        return entry;
}

GiSTlist<GiSTentry*> 
GiSTnode::Search(const GiSTpredicate &query) const
{
        GiSTlist<GiSTentry*> list;

        for(int i=0; i<numEntries; i++) {
                GiSTentry *e=(*this)[i];

                if(query.Consistent(*e)) list.Append((GiSTentry*)e->Copy());
        }
        return list;
}

GiSTentry* 
GiSTnode::SearchPtr(GiSTpage ptr) const
{
        for(int i=0; i<numEntries; i++) {
                GiSTentry *e=(*this)[i];

                if(e->Ptr()==ptr) return (GiSTentry*) e->Copy();
        }
        return NULL;
}

#ifdef PRINTING_OBJECTS
void 
GiSTnode::Print(ostream& os) const
{
        os << path << " #Entries: " << NumEntries() << ", ";
        os << "Level " << Level();
        if (IsLeaf()) os << "(Leaf)";
        else os << "(Internal)";
        os << ", Sibling: " << Sibling();
        os << ", Size: " << Size() << "/" << tree->Store()->PageSize() << endl;
        for(int i=0; i<numEntries; i++) (*this)[i]->Print(os);
}
#endif

GiSTpage 
GiSTnode::SearchNeighbors(GiSTpage ptr) const
{
        for(int i=0; i<numEntries; i++)
                if((*this)[i]->Ptr()==ptr) {
                        // Is there a right neighbor?
                        if(i!=numEntries-1) return (*this)[i+1]->Ptr();
                        // Is there a left neighbor?
                        if (i!=0) return (*this)[i-1]->Ptr();
                        break;
                }
        return 0;
}

GiSTnode* 
GiSTnode::PickSplit()
{
        // Create the right node.  Make it an exact copy of this one.
        GiSTnode *node=(GiSTnode*) Copy();
        int half=numEntries/2;
        int i;

        // Delete the first N/2 entries from the right node.
        node->numEntries=0;
        for(i=0; i<numEntries-half; i++) {
                node->entries[i]=node->entries[i+half];
                node->entries[i]->SetPosition(i);
                node->numEntries++;
        }
        // Delete the last N/2 entries from the left node.
        numEntries=half;
        // Return the right node.
        return node;
}

void 
GiSTnode::Reset()
{
        if(entries!=NULL) {
                for(int i=0; i<numEntries; i++) delete entries[i].Ptr();
                delete entries;
                entries=NULL;
        }
        if (packedNode) {
                delete packedNode;
                packedNode=NULL;
        }
        numEntries=maxEntries=0;
}

GiSTnode::~GiSTnode()
{
        Reset();
}

int 
GiSTnode::IsUnderFull(const GiSTstore &store) const
{
        return Size()<store.PageSize()/2;
}

int 
GiSTnode::IsOverFull(const GiSTstore &store) const
{
        return Size()>store.PageSize();
}
Revision:	1.1
Committed:	Sun May 6 00:45:52 2001 UTC (23 years, 1 month ago) by root
Branch:	MAIN
CVS Tags:	HEAD
Log Message:	* empty log message *
#	User	Rev	Content
1	root	1.1	// -- Mode: C++ --
2
3			// GiSTnode.cpp
4			//
5			// Copyright (c) 1996, Regents of the University of California
6			// $Header: /usr/local/devel/GiST/libGiST/libGiST/GiSTnode.cpp,v 1.1.1.1 1996/08/06 23:47:21 jmh Exp $
7
8			#include <string.h>
9			#include "GiST.h"
10
11			const int ALLOC_INCR=32;
12
13			extern "C" int
14			GiSTintcmp(const void x, const void y)
15			{
16			int i=(int )x;
17			int j=(int )y;
18			return(i-j);
19			}
20
21			int
22			GiSTnode::Size() const
23			{
24			int size=GIST_PAGE_HEADER_SIZE+sizeof(GiSTlte);
25			int fixlen=FixedLength();
26
27			if(fixlen) size+=numEntries*(fixlen+sizeof(GiSTpage));
28			else for(int i=0; i<numEntries; i++)
29			size+=(sizeof(GiSTlte)+sizeof(GiSTpage)+entries[i]->CompressedLength());
30			return size;
31			}
32
33			GiSTnode::GiSTnode()
34			{
35			packedNode=NULL;
36			sibling=0;
37			level=0;
38			numEntries=0;
39			maxEntries=0;
40			entries=NULL;
41			tree=NULL;
42			}
43
44			GiSTnode::GiSTnode(const GiSTnode &node)
45			{
46			maxEntries=node.maxEntries;
47			numEntries=node.numEntries;
48			level=node.level;
49			sibling=node.sibling;
50			tree=node.tree;
51			if (node.packedNode) {
52			packedNode=new char[tree->Store()->PageSize()];
53			memcpy(packedNode, node.packedNode, tree->Store()->PageSize());
54			}
55			else packedNode=NULL;
56			if(maxEntries) entries=new GiSTentryptr[maxEntries];
57			else entries=NULL;
58			for(int i=0; i<numEntries; i++) {
59			entries[i]=(GiSTentry*) node.entries[i]->Copy();
60			((GiSTentry *)entries[i])->SetNode(this);
61			}
62			path=node.path;
63			}
64
65			void
66			GiSTnode::Expand(int index)
67			{
68			int newMaxEntries=maxEntries+ALLOC_INCR;
69			if(newMaxEntries<index+1) newMaxEntries=index+1+ALLOC_INCR;
70			GiSTentryptr *newEntries=new GiSTentryptr[newMaxEntries];
71			int i;
72
73			for(i=numEntries; i<newMaxEntries; i++) newEntries[i]=NULL;
74			for(i=0; i<numEntries; i++) newEntries[i]=entries[i];
75			if(entries!=NULL) delete entries;
76			entries=newEntries;
77			maxEntries=newMaxEntries;
78			}
79
80			GiSTentryptr&
81			GiSTnode::operator[](int index)
82			{
83			assert(index>=0);
84			if (index>=maxEntries) Expand(index);
85			return entries[index];
86			}
87
88			const GiSTentryptr&
89			GiSTnode::operator[](int index) const
90			{
91			static GiSTentryptr e;
92
93			assert(index>=0);
94			if(index>=maxEntries) return e;
95			return entries[index];
96			}
97
98			void
99			GiSTnode::InsertBefore(const GiSTentry& entry, int index)
100			{
101			assert(index<=NumEntries());
102			GiSTentry e=(GiSTentry) entry.Copy();
103
104			e->SetLevel(Level());
105			e->SetPosition(index);
106			e->SetNode(this);
107			// Move everything else over
108			for(int i=NumEntries(); i>index; i--) {
109			GiSTentry e=(this)[i-1];
110			e->SetPosition(i);
111			(*this)[i]=e;
112			}
113			// Stick the entry in
114			(*this)[index]=e;
115			// Bump up the count
116			numEntries++;
117			}
118
119			void
120			GiSTnode::Insert(const GiSTentry& entry)
121			{
122			// Find out where to insert it
123			int i;
124
125			for(i=0; i<NumEntries(); i++) if((*this)[i]->Compare(entry)>0) break;
126			// Do the deed
127			InsertBefore(entry, i);
128			}
129
130			void
131			GiSTnode::DeleteEntry(int index)
132			{
133			int j;
134
135			assert(index<numEntries);
136			// free up the memory in the entry to be deleted
137			if(entries[index].Ptr()) delete entries[index].Ptr();
138			// Remove the entry
139			for(j=index; j<numEntries-1; j++) {
140			entries[j]=entries[j+1];
141			entries[j]->SetPosition(j);
142			}
143			numEntries--;
144			}
145
146			void
147			GiSTnode::DeleteBulk(int vec[], int veclen)
148			{
149			int i;
150
151			qsort(vec, veclen, sizeof(int), GiSTintcmp);
152			for(i=veclen-1; i>=0; i--) DeleteEntry(vec[i]);
153			}
154
155			void
156			GiSTnode::Pack(char *page) const
157			{
158			// Pack the header
159			GiSTheader h=(GiSTheader ) page;
160
161			h->level=Level();
162			h->numEntries=NumEntries();
163			h->sibling=Sibling();
164
165			int fixlen=FixedLength();
166			GiSTlte ltable=(GiSTlte )(page+tree->Store()->PageSize());
167			GiSTlte ltptr=GIST_PAGE_HEADER_SIZE;
168
169			for(int i=0; i<numEntries; i++) {
170			GiSTcompressedEntry compressedEntry=(*this)[i]->Compress();
171
172			if(fixlen) assert(fixlen==compressedEntry.keyLen);
173			// Copy the entry onto the page
174			if(compressedEntry.keyLen>0) memcpy(page+ltptr, compressedEntry.key, compressedEntry.keyLen);
175			memcpy(page+ltptr+compressedEntry.keyLen, &compressedEntry.ptr, sizeof(GiSTpage));
176			// Be tidy
177			if(compressedEntry.key) delete compressedEntry.key;
178			// Enter a pointer to the entry in the line table
179			if(!fixlen) *--ltable=ltptr;
180			ltptr+=compressedEntry.keyLen+sizeof(GiSTpage);
181			}
182			// Store extra line table entry so we know last entry's length
183			*--ltable=ltptr;
184			}
185
186			void
187			GiSTnode::Unpack(const char *page)
188			{
189			const GiSTheader h=(const GiSTheader ) page;
190
191			Reset();
192			SetLevel(h->level);
193			SetSibling(h->sibling);
194			if(!packedNode) packedNode=new char[tree->Store()->PageSize()];
195			memcpy(packedNode, page, tree->Store()->PageSize());
196			Expand(h->numEntries);
197			SetNumEntries(h->numEntries);
198			for(int i=0; i<h->numEntries; i++) {
199			GiSTcompressedEntry tmpentry=Entry(i);
200			GiSTentry *e=CreateEntry();
201
202			e->SetLevel(Level());
203			e->SetPosition(i);
204			e->SetNode(this);
205			e->Decompress(tmpentry);
206			// be tidy
207			if(tmpentry.key) delete tmpentry.key;
208			// Append the body with the entry
209			entries[i]=e;
210			}
211			}
212
213			// SearchMinPenalty returns where a new entry should be inserted.
214			GiSTpage
215			GiSTnode::SearchMinPenalty(const GiSTentry &newEntry) const
216			{
217			GiSTentry *minEntry=NULL;
218			GiSTpenalty *minPenalty=NULL;
219
220			for(int i=0; i<numEntries; i++) {
221			GiSTentry e=(this)[i];
222			assert(e->Node()==this);
223			GiSTpenalty *penalty=e->Penalty(newEntry);
224
225			if(minEntry==NULL\|\|(penalty)<(minPenalty)) {
226			minEntry=e;
227			if(minPenalty) delete minPenalty;
228			minPenalty=penalty;
229			}
230			else delete penalty;
231			}
232			delete minPenalty;
233			return minEntry->Ptr();
234			}
235
236			void
237			GiSTnode::Coalesce(const GiSTnode &source, const GiSTentry& entry) // entry is the entry in the parent node that points to this
238			{
239			// Coalesce by one-by-one insertion
240			// Take each entry from the source node
241			// and insert it into this node.
242			for(int i=0; i<source.numEntries; i++) {
243			GiSTentry& e=source[i];
244
245			InsertBefore(e, NumEntries());
246			}
247			}
248
249			GiSTcompressedEntry
250			GiSTnode::Entry(int entryPos) const
251			{
252			// Look up the line table
253			GiSTlte keyPhysicalPos, nextKeyPhysicalPos;
254			int fixlen=FixedLength();
255
256			if(!fixlen) {
257			memcpy(&keyPhysicalPos, packedNode+tree->Store()->PageSize()-(entryPos+1)*sizeof(GiSTlte), sizeof(GiSTlte));
258			memcpy(&nextKeyPhysicalPos, packedNode+tree->Store()->PageSize()-(entryPos+2)*sizeof(GiSTlte), sizeof(GiSTlte));
259			}
260			else {
261			keyPhysicalPos=GIST_PAGE_HEADER_SIZE+(sizeof(GiSTpage)+fixlen)*entryPos;
262			nextKeyPhysicalPos=keyPhysicalPos+sizeof(GiSTpage)+fixlen;
263			}
264
265			// Allocate and set up the return key
266			GiSTcompressedEntry entry;
267
268			entry.keyLen=nextKeyPhysicalPos-keyPhysicalPos-sizeof(GiSTpage);
269			if(entry.keyLen>0) {
270			entry.key=new char[entry.keyLen];
271			memcpy(entry.key, packedNode+keyPhysicalPos, entry.keyLen);
272			}
273			memcpy(&entry.ptr, packedNode+keyPhysicalPos+entry.keyLen, sizeof(GiSTpage));
274			return entry;
275			}
276
277			GiSTlist<GiSTentry*>
278			GiSTnode::Search(const GiSTpredicate &query) const
279			{
280			GiSTlist<GiSTentry*> list;
281
282			for(int i=0; i<numEntries; i++) {
283			GiSTentry e=(this)[i];
284
285			if(query.Consistent(e)) list.Append((GiSTentry)e->Copy());
286			}
287			return list;
288			}
289
290			GiSTentry*
291			GiSTnode::SearchPtr(GiSTpage ptr) const
292			{
293			for(int i=0; i<numEntries; i++) {
294			GiSTentry e=(this)[i];
295
296			if(e->Ptr()==ptr) return (GiSTentry*) e->Copy();
297			}
298			return NULL;
299			}
300
301			#ifdef PRINTING_OBJECTS
302			void
303			GiSTnode::Print(ostream& os) const
304			{
305			os << path << " #Entries: " << NumEntries() << ", ";
306			os << "Level " << Level();
307			if (IsLeaf()) os << "(Leaf)";
308			else os << "(Internal)";
309			os << ", Sibling: " << Sibling();
310			os << ", Size: " << Size() << "/" << tree->Store()->PageSize() << endl;
311			for(int i=0; i<numEntries; i++) (*this)[i]->Print(os);
312			}
313			#endif
314
315			GiSTpage
316			GiSTnode::SearchNeighbors(GiSTpage ptr) const
317			{
318			for(int i=0; i<numEntries; i++)
319			if((*this)[i]->Ptr()==ptr) {
320			// Is there a right neighbor?
321			if(i!=numEntries-1) return (*this)[i+1]->Ptr();
322			// Is there a left neighbor?
323			if (i!=0) return (*this)[i-1]->Ptr();
324			break;
325			}
326			return 0;
327			}
328
329			GiSTnode*
330			GiSTnode::PickSplit()
331			{
332			// Create the right node. Make it an exact copy of this one.
333			GiSTnode node=(GiSTnode) Copy();
334			int half=numEntries/2;
335			int i;
336
337			// Delete the first N/2 entries from the right node.
338			node->numEntries=0;
339			for(i=0; i<numEntries-half; i++) {
340			node->entries[i]=node->entries[i+half];
341			node->entries[i]->SetPosition(i);
342			node->numEntries++;
343			}
344			// Delete the last N/2 entries from the left node.
345			numEntries=half;
346			// Return the right node.
347			return node;
348			}
349
350			void
351			GiSTnode::Reset()
352			{
353			if(entries!=NULL) {
354			for(int i=0; i<numEntries; i++) delete entries[i].Ptr();
355			delete entries;
356			entries=NULL;
357			}
358			if (packedNode) {
359			delete packedNode;
360			packedNode=NULL;
361			}
362			numEntries=maxEntries=0;
363			}
364
365			GiSTnode::~GiSTnode()
366			{
367			Reset();
368			}
369
370			int
371			GiSTnode::IsUnderFull(const GiSTstore &store) const
372			{
373			return Size()<store.PageSize()/2;
374			}
375
376			int
377			GiSTnode::IsOverFull(const GiSTstore &store) const
378			{
379			return Size()>store.PageSize();
380			}