| 1 |
root |
1.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 |
