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 |
} |