| 1 |
// -*- Mode: C++ -*- |
| 2 |
|
| 3 |
// GiSTnode.h |
| 4 |
// |
| 5 |
// Copyright (c) 1996, Regents of the University of California |
| 6 |
// $Header: /usr/local/devel/GiST/libGiST/libGiST/GiSTnode.h,v 1.1.1.1 1996/08/06 23:47:21 jmh Exp $ |
| 7 |
#ifndef GISTNODE_H |
| 8 |
#define GISTNODE_H |
| 9 |
|
| 10 |
#include "GiSTentry.h" |
| 11 |
#include "GiSTpredicate.h" |
| 12 |
#include "GiSTpath.h" |
| 13 |
#include "GiSTstore.h" |
| 14 |
class GiST; |
| 15 |
|
| 16 |
// Type of line table element |
| 17 |
typedef unsigned short GiSTlte; |
| 18 |
|
| 19 |
// Page header |
| 20 |
struct GiSTheader { |
| 21 |
int level; |
| 22 |
int numEntries; |
| 23 |
GiSTpage parent; |
| 24 |
GiSTpage sibling; |
| 25 |
}; |
| 26 |
|
| 27 |
// Entry pointer, with some handy operators |
| 28 |
class GiSTentryptr { |
| 29 |
public: |
| 30 |
GiSTentryptr() { ptr=NULL; } |
| 31 |
operator GiSTentry* () const { return ptr; } |
| 32 |
operator GiSTentry& () const { return *ptr; } |
| 33 |
GiSTentry* operator->() const { return ptr; } |
| 34 |
GiSTentryptr& operator=(GiSTentry* ptr) { this->ptr=ptr; return *this; } |
| 35 |
GiSTentryptr& operator=(GiSTentryptr& ptr) { this->ptr=ptr.ptr; return *this; } |
| 36 |
GiSTentry* Ptr() const { return ptr; }
|
| 37 |
|
| 38 |
private: |
| 39 |
GiSTentry *ptr; |
| 40 |
}; |
| 41 |
|
| 42 |
#define GIST_PAGE_HEADER_SIZE sizeof(GiSTheader) |
| 43 |
|
| 44 |
// The GiST node class. |
| 45 |
class GiSTnode: public GiSTobject { |
| 46 |
public: |
| 47 |
GiSTnode(); |
| 48 |
GiSTnode(const GiSTnode& node); |
| 49 |
|
| 50 |
GiSTobjid IsA() const { return GISTNODE_CLASS; } |
| 51 |
#ifdef PRINTING_OBJECTS |
| 52 |
virtual void Print(ostream& os) const; |
| 53 |
#endif |
| 54 |
// Operations on the entry array |
| 55 |
GiSTentryptr& operator[](int index); |
| 56 |
const GiSTentryptr& operator[](int index) const; |
| 57 |
|
| 58 |
void Expand(int index); |
| 59 |
int NumEntries() const { return numEntries; } |
| 60 |
void SetNumEntries(int num) { numEntries=num; } |
| 61 |
|
| 62 |
// Search methods |
| 63 |
virtual GiSTentry* SearchPtr(GiSTpage ptr) const; |
| 64 |
virtual GiSTpage SearchMinPenalty(const GiSTentry& entry) const; |
| 65 |
virtual GiSTpage SearchNeighbors(GiSTpage ptr) const; |
| 66 |
virtual GiSTlist<GiSTentry*> Search(const GiSTpredicate &query) const; |
| 67 |
|
| 68 |
// Insertion and deletion |
| 69 |
virtual void Insert(const GiSTentry &entry); |
| 70 |
virtual void InsertBefore(const GiSTentry &entry, int index); |
| 71 |
virtual void DeleteEntry(int index); |
| 72 |
virtual void DeleteBulk(int vec[], int veclen); |
| 73 |
|
| 74 |
// Pack/unpack disk representation |
| 75 |
virtual void Pack(char *page) const; |
| 76 |
virtual void Unpack(const char *page); |
| 77 |
|
| 78 |
// two of the basic GiST methods |
| 79 |
// Returns the Union of all entries |
| 80 |
virtual GiSTentry* Union() const=0; |
| 81 |
// Splitting |
| 82 |
virtual GiSTnode *PickSplit(); |
| 83 |
|
| 84 |
// required support methods |
| 85 |
virtual GiSTentry* CreateEntry() const=0; |
| 86 |
virtual int FixedLength() const { return 0; } |
| 87 |
|
| 88 |
virtual GiSTcompressedEntry Entry(int entryPos) const; |
| 89 |
|
| 90 |
// coalescing |
| 91 |
virtual void Coalesce(const GiSTnode &node, const GiSTentry& entry); |
| 92 |
|
| 93 |
// access to the private members |
| 94 |
GiSTpage Sibling() const { return sibling; } |
| 95 |
void SetSibling(GiSTpage p) { sibling=p; } |
| 96 |
int IsLeaf() const { return level==0; } |
| 97 |
int Level() const { return level; } |
| 98 |
void SetLevel(int l) { level=l; } |
| 99 |
|
| 100 |
virtual int IsOverFull(const GiSTstore &store) const; |
| 101 |
virtual int IsUnderFull(const GiSTstore &store) const; |
| 102 |
|
| 103 |
~GiSTnode(); |
| 104 |
|
| 105 |
virtual int Size() const; |
| 106 |
|
| 107 |
GiST *Tree() const { return tree; } |
| 108 |
void SetTree(GiST *t) { tree=t; } |
| 109 |
|
| 110 |
GiSTpath& Path() { return path; } |
| 111 |
|
| 112 |
private: |
| 113 |
void Reset(); |
| 114 |
GiSTpath path; |
| 115 |
GiSTentryptr *entries; |
| 116 |
char *packedNode; |
| 117 |
GiSTpage sibling; |
| 118 |
int level; |
| 119 |
int numEntries, maxEntries; |
| 120 |
GiST *tree; |
| 121 |
}; |
| 122 |
|
| 123 |
#endif |
