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