gistnode.cpp

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

//--------------------------------------------------------------------
//        GiSTnode.cpp
//        ------------
//
//        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
//

#include <string.h>

#include "GiST.h"

const int ALLOC_INCR = 32;

extern "C" int
GiSTintcmp(const void *x, const void *y)
{
    int i = *(int *)x;
    int j = *(int *)y;
    return(i-j);
}

//------------------------------------------------
void       
GiSTnode::HeaderFromString(const char* buf)
{
    SetLevel(((int*) buf)[0]);
    SetNumEntries(((int*) buf)[1]);
    SetSibling(((int*) buf)[2]);
}

//------------------------------------------------
void
GiSTnode::HeaderToString  (char* buf) const
{
    ((int*) buf)[0] = Level();
    ((int*) buf)[1] = NumEntries(); 
    ((int*) buf)[2] = Sibling(); 
}

//------------------------------------------------
int
GiSTnode::Size(int vec[], int veclen) const
{
    int size       = HeaderSize();
    int fixlen     = FixedLength();
    int entrytypes = NumEntryTypes();

    if (fixlen)
       if (vec) size += veclen     * (fixlen + sizeof(GiSTpage));
       else     size += numEntries * (fixlen + sizeof(GiSTpage));
    else if (entrytypes)
         {
            size += sizeof(short) * entrytypes;
            if (vec) 
               for (int i = 0; i < veclen; i++)
                  size += (sizeof(GiSTpage) + entries[vec[i]]->CompressedLength());   
            else
               for (int i = 0; i < numEntries; i++)
                  size += (sizeof(GiSTpage) + entries[i]->CompressedLength());   
         }
         else 
         {
            size += sizeof(GiSTlte);
            if (vec) 
               for (int i = 0; i < veclen; i++)
                  size += (sizeof(GiSTlte) + sizeof(GiSTpage) +
	    	                 entries[vec[i]]->CompressedLength());
            else
               for (int i = 0; i < numEntries; i++)
                  size += (sizeof(GiSTlte) + sizeof(GiSTpage) +
	    	                 entries[i]->CompressedLength());
         }
    return size;
}

//------------------------------------------------
GiSTnode::GiSTnode()
{
    packedNode = NULL;
    sibling = 0;
    level = 0;
    numEntries = 0;
    maxEntries = 0;
    entries = NULL;
    tree = NULL;
}

//------------------------------------------------
GiSTnode::GiSTnode(const GiSTnode &node)
{
    maxEntries = node.maxEntries;
    numEntries = node.numEntries;
    level = node.level;
    sibling = node.sibling;
    tree = node.tree;

    if (node.packedNode)
    {
    	 packedNode = new char[tree->Store()->PageSize()];
	    memcpy(packedNode, node.packedNode, tree->Store()->PageSize());
    }
    else
	    packedNode = NULL;

    if (maxEntries)
	    entries = new GiSTentryptr[maxEntries];
    else
	    entries = NULL;
    for (int i=0; i<numEntries; i++)
    {
      entries[i] = (GiSTentry*) node.entries[i]->Copy();
      ((GiSTentry *)entries[i])->SetNode(this);
    }

    path = node.path;
}

//------------------------------------------------
void
GiSTnode::Expand(int index)
{
    int newMaxEntries = maxEntries + ALLOC_INCR;
    if (newMaxEntries < index + 1) newMaxEntries = index + 1 + ALLOC_INCR;
    GiSTentryptr *newEntries = new GiSTentryptr[newMaxEntries];

    int i;

    for (i=numEntries; i<newMaxEntries; i++)	newEntries[i] = NULL;
    for (i=0; i<numEntries; i++) newEntries[i] = entries[i];
    if (entries != NULL) delete entries;
    entries = newEntries;
    maxEntries = newMaxEntries;
}

//------------------------------------------------
GiSTentryptr&
GiSTnode::operator [] (int index)
{
    assert(index >= 0);
    if (index >= maxEntries) Expand(index);
    return entries[index];
}

//------------------------------------------------
const GiSTentryptr&
GiSTnode::operator [] (int index) const
{
    static GiSTentryptr e;

    assert(index >= 0);
    if (index >= maxEntries) return e;
    return entries[index];
}

//------------------------------------------------
void
GiSTnode::InsertBefore(const GiSTentry& entry, int index)
{
    assert(index <= NumEntries());

    GiSTentry *e = (GiSTentry*) entry.Copy();
    e->SetLevel(Level());
    e->SetPosition(index);
    e->SetNode(this);

    // Move everything else over
    for (int i = NumEntries(); i > index; i--)
    {
       GiSTentry *e = (*this)[i-1];
       e->SetPosition(i);
       (*this)[i] = e;
    }
    
    // Stick the entry in
    (*this)[index] = e;
    
    // Bump up the count
    numEntries++;
}

//------------------------------------------------
void
GiSTnode::Insert(const GiSTentry& entry)
{
    // Find out where to insert it
    int i;
/*    for (i=0; i<NumEntries(); i++)
	    if ((*this)[i]->Compare(entry) > 0) break;

    // Do the deed
    InsertBefore(entry, i);
*/
    InsertBefore(entry, NumEntries());
}

//------------------------------------------------
void
GiSTnode::DeleteEntry(int index)
{
    int j;

    assert(index < numEntries);

    // free up the memory in the entry to be deleted
    if (entries[index].Ptr())
      delete entries[index].Ptr();

    // Remove the entry
    for (j=index; j<numEntries-1; j++)
    {
       entries[j] = entries[j+1];
       entries[j]->SetPosition(j);
    }

    numEntries--;
}

//------------------------------------------------
void
GiSTnode::DeleteBulk(int vec[], int veclen)
{
  int i;

  qsort(vec, veclen, sizeof(int), GiSTintcmp);
  for (i = veclen - 1; i >= 0; i--)
    DeleteEntry(vec[i]);
}

//------------------------------------------------
void
GiSTnode::DeleteAll()
{
   for (int i = numEntries - 1; i >= 0; i--) DeleteEntry(i);
}

//------------------------------------------------
void
GiSTnode::Pack(char *page)
{
  // Pack the header
  HeaderToString(page);

  int      i, j;
  int      fixlen     = FixedLength();
  int      entrytypes = NumEntryTypes();
  GiSTlte* ltable     = (GiSTlte *) (page + tree->Store()->PageSize());
  GiSTlte  ltptr      = HeaderSize();
 
  if (!fixlen && entrytypes)
  {
     short*  typenums = (short *) (page + ltptr);
   
     ltptr += entrytypes * sizeof (short);   
     for (j = 0; j < entrytypes; j++)
        for (i = 0, typenums[j] = 0; i < numEntries; i++)
	   if ((*this)[i]->Type() == j)
	   {
              (*this)[i]->Compress(page + ltptr);
              ltptr += (*this)[i]->CompressedLength() + sizeof(GiSTpage);
              typenums[j]++;                      
           } 
  }
  else 
     for (i = 0; i < numEntries; i++)
     {
        (*this)[i]->Compress(page+ltptr);

        // Enter a pointer to the entry in the line table
        if (!fixlen) *--ltable = ltptr;

        ltptr += (GiSTlte)((*this)[i]->CompressedLength() + sizeof(GiSTpage));
     }
 
  // Store extra line table entry so we know last entry's length
  if (!fixlen && !entrytypes) *--ltable = ltptr;
}
  
//------------------------------------------------
void 
GiSTnode::SetPackedNode (const char* page)
{
   if (!packedNode) packedNode = new char[tree->Store()->PageSize()];
   memcpy(packedNode, page, tree->Store()->PageSize());
}

//------------------------------------------------
void
GiSTnode::Unpack(const char *page)
{
   GiSTlte keyPhysicalPos, nextKeyPhysicalPos;

   Reset();
   HeaderFromString(page);
//  SetPackedNode(page);

   int i, j, k;
   int fixlen     = FixedLength();
   int entrytypes = NumEntryTypes();   
 
   int tmp = numEntries;
   numEntries = 0;
   Expand(tmp);
   SetNumEntries(tmp);

   if (!fixlen && entrytypes)
   {
      short* typenums = (short *) (page + HeaderSize()); 

      keyPhysicalPos  = (GiSTlte) (HeaderSize() + sizeof(short) * entrytypes);
      for (j = 0, i = 0; j < entrytypes; j++)
	 for (k = 0; k < typenums[j]; k++, i++)
	 {
            GiSTentry *e = CreateEntry();
            e->SetLevel(Level());
            e->SetPosition(i);
            e->SetNode(this);
            e->SetType(j);
          
            nextKeyPhysicalPos = (GiSTlte) (keyPhysicalPos + 
                                            sizeof(GiSTpage) + 
                                            e->CompressedLength());
            e->Decompress(page + keyPhysicalPos, nextKeyPhysicalPos - keyPhysicalPos);
            keyPhysicalPos = nextKeyPhysicalPos;
      
            // Append the body with the entry
            entries[i] = e;
         } 
      assert (i == numEntries);
   }
   else
      for (i=0; i < numEntries; i++)
      {
         if (!fixlen)
         {
            // Look up the line table
            memcpy(&keyPhysicalPos,
                   page+tree->Store()->PageSize()-(i + 1)*sizeof(GiSTlte),
                   sizeof(GiSTlte));

            memcpy(&nextKeyPhysicalPos,
                   page+tree->Store()->PageSize()-(i + 2)*sizeof(GiSTlte),
                   sizeof(GiSTlte));
         }
         else
         {
            keyPhysicalPos     = (GiSTlte) (HeaderSize() +
                                           (sizeof(GiSTpage) + fixlen) * i);
            nextKeyPhysicalPos = (GiSTlte) (keyPhysicalPos+sizeof(GiSTpage)+fixlen);
         }

         GiSTentry *e = CreateEntry();
         e->SetLevel(Level());
         e->SetPosition(i);
         e->SetNode(this);
         e->Decompress(page+keyPhysicalPos, 
                       nextKeyPhysicalPos - keyPhysicalPos);
  
         // Append the body with the entry
         entries[i] = e;
      }
}

//------------------------------------------------
// SearchMinPenalty returns where a new entry should be inserted.
GiSTpage
GiSTnode::SearchMinPenalty(const GiSTentry &newEntry) const
{
    GiSTentry *minEntry = NULL;
    GiSTpenalty *minPenalty = NULL;

    for (int i=0; i<numEntries; i++)
    {
       GiSTentry *e = (*this)[i];
       assert(e->Node() == this);
       GiSTpenalty *penalty = e->Penalty(newEntry);
       if (minEntry == NULL || (*penalty) < (*minPenalty))
       {
           minEntry = e;
           if (minPenalty) delete minPenalty;
           minPenalty = penalty;
       }
       else delete penalty;
    }
    delete minPenalty;
    return minEntry->Ptr();
}

//------------------------------------------------
void
GiSTnode::Coalesce(const GiSTnode &source,
		             const GiSTentry& entry) // entry is the entry in the
                                           // parent node that points to this
{
    // Coalesce by one-by-one insertion
    //   Take each entry from the source node
    //   and insert it into this node.
    for (int i=0; i<source.numEntries; i++)
    {
    	 GiSTentry& e = source[i];
    	 InsertBefore(e, NumEntries());
    }
}

//------------------------------------------------
GiSTlist<GiSTentry*>
GiSTnode::Search(const GiSTpredicate &query) const
{
    GiSTlist<GiSTentry*> list;
    int qual = 0;

    for (int i=0; i<numEntries; i++)
    {
       GiSTentry *e = (*this)[i];
       if (query.Consistent(*e))
       {
           list.Append((GiSTentry*)e->Copy());
           qual++;
       } 
    }

    if (Tree()->Observer()) Tree()->Observer()->Inform(ON_SEARCHNODE, qual, NumEntries(), Level());

    return list;
}

//------------------------------------------------
GiSTentry*
GiSTnode::SearchPtr(GiSTpage ptr) const
{
    for (int i=0; i<numEntries; i++)
    {
       GiSTentry *e = (*this)[i];
       if (e->Ptr() == ptr)
           return (GiSTentry*) e->Copy();
    }
    return NULL;
}

#ifdef PRINTING_OBJECTS
//------------------------------------------------
void
GiSTnode::Print(ostream& os) const
{
  os << path << " #Entries: " << NumEntries() << ", ";

  os << "Level " << Level();
  if (IsLeaf())
    os << "(Leaf)";
  else
    os << "(Internal)";

  os << ", Sibling: " << Sibling();
  os << ", Size: " << Size() << "/" << tree->Store()->PageSize() << endl;

  for (int i = 0; i<numEntries; i++)
      (*this)[i]->Print(os);
}
#endif

//------------------------------------------------
GiSTpage
GiSTnode::SearchNeighbors(GiSTpage ptr) const
{
    for (int i=0; i<numEntries; i++)
       if ((*this)[i]->Ptr() == ptr) {
           // Is there a right neighbor?
           if (i != numEntries-1) return (*this)[i+1]->Ptr();
           // Is there a left neighbor?
           if (i != 0) return (*this)[i-1]->Ptr();
           break;
       }
    return 0;
}

//------------------------------------------------
GiSTnode*
GiSTnode::PickSplit()
{
    // Create the right node.  Make it an exact copy of this one.
    GiSTnode *node = (GiSTnode*) Copy();
    int half = numEntries/2;

    // Delete the first N/2 entries from the right node.
    int i;
    node->numEntries = 0;
    for (i=0; i<numEntries-half; i++)
    {
       node->entries[i] = node->entries[i+half];
       node->entries[i]->SetPosition(i);
       node->numEntries++;
    }

    // Delete the last N/2 entries from the left node.
    numEntries = half;

    // Return the right node.
    return node;
}

//------------------------------------------------
void
GiSTnode::Reset()
{
   if (entries != NULL)
   {
       for (int i=0; i<numEntries; i++)
	       delete entries[i].Ptr();
	    delete entries;
	    entries = NULL;
   }
   if (packedNode)
   {
	   delete packedNode;
	   packedNode = NULL;
   }
   numEntries = maxEntries = 0;
}

//------------------------------------------------
GiSTnode::~GiSTnode()
{
    Reset();
}

//------------------------------------------------
int
GiSTnode::IsUnderFull(const GiSTstore &store, int vec[], int veclen) const
{
    if (FixedLength())
       return Size(vec, veclen) - HeaderSize() <
              (int) ((store.PageSize() - HeaderSize()) *
                     tree->m() + 0.5);
    else
       return Size(vec, veclen) < (int)(store.PageSize() * tree->m() + 0.5);
}

//------------------------------------------------
int
GiSTnode::IsOverFull(const GiSTstore &store, int vec[], int veclen) const
{
    return Size(vec, veclen) > store.PageSize();
}