gistnode.h

此文件包含了在linux下实现tpr-tree索引的源代码

// -*- Mode: C++ -*-
//--------------------------------------------------------------------
//        GiSTnode.h
//        ----------
//
//        GiST - Generalized Search Tree 
//        June 2001 release, Aalborg University
//        
//        This file is a revised version of a part of the original 
//        libGiST release (version  0.9beta1)     
//        Copyright (c) 1996, Regents of the University of California
//

#ifndef GISTNODE_H
#define GISTNODE_H

#include "GiSTentry.h"
#include "GiSTpredicate.h"
#include "GiSTpath.h"
#include "GiSTstore.h"
#include "GiSTlist.h"

class GiST;

// Type of line table element
typedef unsigned short GiSTlte;

//------------------------------------------------
//  Entry pointer, with some handy operators
//

class GiSTentryptr
{
  public:
    GiSTentryptr() { ptr = NULL; }
    operator GiSTentry*  () const { return ptr; }
    operator GiSTentry&  () const { return *ptr; }
    GiSTentry* operator->() const { return ptr; }

    GiSTentryptr& operator = (GiSTentry* ptr)
    {
       this->ptr = ptr;
       return *this;
    }

    GiSTentryptr& operator = (GiSTentryptr& ptr)
    {
       this->ptr = ptr.ptr; return *this;
    }

    GiSTentry* Ptr() const { return ptr; }

  private:
    GiSTentry *ptr;
};

#define GIST_PAGE_HEADER_SIZE sizeof(GiSTheader)

//------------------------------------------------
//  The GiST node class.
//

class GiSTnode : public GiSTobject
{
public:
  GiSTnode();
  GiSTnode(const GiSTnode& node);

  GiSTobjid IsA() const { return GISTNODE_CLASS; }
#ifdef PRINTING_OBJECTS
  virtual void Print(ostream& os) const;
#endif
  // Operations on the entry array
        GiSTentryptr& operator [] (int index);
  const GiSTentryptr& operator [] (int index) const;

  void Expand       (int index);
  int  NumEntries   ()  const { return numEntries; }
  void SetNumEntries(int num) { numEntries = num; }

  // Search methods
  virtual GiSTentry* SearchPtr       (GiSTpage ptr) const;
  virtual GiSTpage   SearchMinPenalty(const GiSTentry& entry) const;
  virtual GiSTpage   SearchNeighbors (GiSTpage ptr) const;
  virtual GiSTlist<GiSTentry*> Search(const GiSTpredicate &query) const;

  // Insertion and deletion
  virtual void Insert      (const GiSTentry &entry);
  virtual void InsertBefore(const GiSTentry &entry, int index);
  virtual void DeleteEntry (int index);
  virtual void DeleteBulk  (int vec[], int veclen);
  virtual void DeleteAll   ();

  // Pack/unpack disk representation
  virtual void Pack  (char *page);
  virtual void Unpack(const char *page);
  
  // Commit - the opportunity to do some final actions before deallocting or writing 
  virtual void Commit () {};  

  // two of the basic GiST methods

  // Union returns the "bounding box" of all entries
  virtual GiSTentry* Union() const = 0;   

  // Splitting
  virtual GiSTnode*  PickSplit();

  // required support methods
  virtual GiSTentry* CreateEntry()   const = 0;
  virtual int        FixedLength()   const { return 0; }

  // NumEntryTypes can be non-zero only if FixedLength() is zero
  virtual int        NumEntryTypes() const { return 0; } 

  // coalescing
  virtual void Coalesce(const GiSTnode &node, const GiSTentry& entry);

  // access to the private members
  GiSTpage Sibling   () const     { return sibling; }
  void     SetSibling(GiSTpage p) { sibling = p; }
  int      IsLeaf    () const     { return level == 0; }
  int      Level     () const     { return level; }
  void     SetLevel  (int l)      { level = l; }

  virtual int IsOverFull (const GiSTstore &store, 
                          int vec[] = NULL, int veclen = 0) const;
  virtual int IsUnderFull(const GiSTstore &store, 
                          int vec[] = NULL, int veclen = 0) const;

  ~GiSTnode();

  virtual int Size(int vec[] = NULL, int veclen = 0) const;

  GiST* Tree   () const  { return tree; }
  void  SetTree(GiST *t) { tree = t; }

  const GiSTpath& Path() const { return path; }
        GiSTpath& Path()       { return path; }

protected:
  // Node header formation functions
  virtual void       HeaderFromString(const char* buf);
  virtual void       HeaderToString  (char* buf) const;  
  virtual int        HeaderSize() const { return 3 * sizeof(int); }
  
  void SetPackedNode (const char* page);
  void Reset();

private:
  GiSTpath      path;
  GiSTentryptr* entries;
  char*         packedNode;
  GiSTpage      sibling;
  int           level;
  int           numEntries, maxEntries;
  GiST*         tree;
};

#endif