rt.cpp

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

//------------------------------------------------------------------------
//      RT.cpp
//      ------
//      Implements the tree
//
//      TPR-tree - Index for continuously moving objects
//      July 2001 release, Aalborg University
//

//#define NDEBUG

#include <string.h>
#include <iomanip.h>
#include <memory.h>
#include <fenv.h>
#include <algorithm>

#ifdef UNIX
#include <unistd.h> 
#endif 

#include "rtprofile.h"
#include "rt.h"

using namespace std;

//----------------------------------------------------
//  Global variables
//

RTtimeStamp CT = 0;             // The current time 
RTsettings  Settings;           // Settings accessible to everybody 

//----------------------------------------------------
typedef struct
{
  double  dist;
  int     ix;
} distix;

inline bool operator< (const distix& x, const distix& y)
{
   return x.dist > y.dist;      // that's right
}

//----------------------------------------------------
RT::RT () : 
    GiST(), param(0.0), w (0.0), reft(0.0), lastChange(0.0), 
    autoHorizon(false), wfactor(1.0), numEntries(0) 
#ifdef RT_DEL_LOOKUP
    , levels(0), delLookUp0(NULL)  
#endif
{
}

//----------------------------------------------------
RT::~RT ()
{
}

//----------------------------------------------------
void RT::Create(const char *filename)
{
   GiST::Create(filename);

#ifdef RT_DEL_LOOKUP
   ResetDelLookUp();
#endif

   numEntries       = 0;
   numOp            = 0;
   reft = lastReset = lastChange = CT;

   char  timefn[50];
   FILE* timef;
   strcpy (timefn, filename);
   strcat (timefn, ".tim");
   timef = fopen (timefn, "wb");
   int v = Settings.GetTreeType(); 
   fwrite (&v, sizeof(v), 1, timef);
   fwrite (&lastChange, sizeof(lastChange), 1, timef);
   fwrite (&GiSTfileCnt::DefPageSize, sizeof(GiSTfileCnt::DefPageSize), 1, timef);
   v = Settings.GetDims ();
   fwrite (&v, sizeof(v), 1, timef);
   fwrite (&reft, sizeof(reft), 1, timef);     // Reference time stamp
   fwrite (&param, sizeof(param), 1, timef);   // Horizon length 
   fwrite (&w, sizeof(w), 1, timef);           // Querying window length 
   fwrite (&numEntries, sizeof(numEntries), 1, timef);  // # of entries in the index 

   fclose (timef);
   
   strcpy(file_nm, filename);

   UpdateKeyLength();
   horUpdateInt = MinEntries(true);
}

//----------------------------------------------------
void RT::Open  (const char *filename)
{
   char   timefn[50];
   FILE*  timef;
   int    d;
   RTsettings::TreeType tt;

   strcpy (timefn, filename);
   strcat (timefn, ".tim");
   timef = fopen (timefn, "rb");
   if (timef)
   {
      fread (&tt, sizeof(tt), 1, timef);
      fread (&lastChange, sizeof(lastChange), 1, timef);
      fread (&GiSTfileCnt::DefPageSize, sizeof(GiSTfileCnt::DefPageSize), 1, timef);
      fread (&d, sizeof(d), 1, timef);
      fread (&reft, sizeof(reft), 1, timef);
      fread (&param, sizeof(param), 1, timef);   // Horizon length 
      fread (&w, sizeof(w), 1, timef);           // Querying window length 
      fread (&numEntries, sizeof(numEntries), 1, timef);  // # of entries in the index 

      fclose (timef);       
   }
   else return;
   
   if (!Settings.SetDims (d) || !Settings.SetTreeType (tt)) return;

   lastReset = lastChange;
   numOp     = 0;  
 
   GiST::Open(filename);

   strcpy(file_nm, filename);

   UpdateKeyLength();
   horUpdateInt = MinEntries(true);

#ifdef RT_DEL_LOOKUP
   ResetDelLookUp();
#endif
}

//----------------------------------------------------
void RT::Close ()
{
   if (!IsOpen()) return;
   GiST::Close();

   char        timefn[50];
   FILE*       timef;
   long        pagesize = PageSize();

   strcpy (timefn, file_nm);
   strcat (timefn, ".tim");
   timef = fopen (timefn, "rb+");
   fseek (timef, 4L, SEEK_SET);
   fwrite (&lastChange, sizeof(lastChange), 1, timef);
   fwrite (&pagesize, sizeof(pagesize), 1, timef);
   int d = Settings.GetDims();
   fwrite (&d, sizeof(d), 1, timef);
   fwrite (&reft, sizeof(reft), 1, timef);
   fwrite (&param, sizeof(param), 1, timef);   // Horizon length 
   fwrite (&w, sizeof(w), 1, timef);           // Querying window length 
   fwrite (&numEntries, sizeof(numEntries), 1, timef);  // # of entries in the index 

   fclose (timef);
   lastChange = 0;

#ifdef RT_DEL_LOOKUP
   ResetDelLookUp();
#endif
}

//----------------------------------------------------
void RT::Drop()  
{ 
   if (!IsOpen()) return;
   Close();
   unlink(file_nm);

   char timefn[50];
   strcpy (timefn, file_nm);
   strcat (timefn, ".tim");
   unlink (timefn);
}

//----------------------------------------------------
void RT::UpdateKeyLength()
{ 
   switch(Settings.GetTreeType())
   {
   case RTsettings::tTPRtree:
      leafLength    = 2*Settings.GetDims()*sizeof(RTcoord); 
      nonleafLength = 4*Settings.GetDims()*sizeof(RTcoord);
      break;

   case RTsettings::tRtree:
      leafLength = nonleafLength = 2*Settings.GetDims()*sizeof(RTcoord) + 2*sizeof(RTtimeStamp);
      break;

   default:   // tOpttree
      leafLength = nonleafLength = 2*Settings.GetDims()*sizeof(RTcoord);     
   }
}

//----------------------------------------------------
int RT::FixedKeyLength(bool isLeaf) const
{
   return isLeaf ? leafLength : nonleafLength;
}

//----------------------------------------------------
int RT::MinKeyLength(bool isLeaf) const
{
   return isLeaf ? leafLength : nonleafLength;
}

//----------------------------------------------------
int RT::MaxKeyLength(bool isLeaf) const
{
   return MinKeyLength(isLeaf); 
}

//----------------------------------------------------
int RT::MinEntries (bool isLeaf) const
{
   return (Store()->PageSize() - HeaderSize()) / 
          (MaxKeyLength(isLeaf) + sizeof(GiSTpage));
}

//----------------------------------------------------
int RT::MaxEntries (bool isLeaf) const
{
   return (Store()->PageSize() - HeaderSize()) / 
          (MinKeyLength(isLeaf) + sizeof(GiSTpage));
}

#ifdef RT_DEL_LOOKUP
//----------------------------------------------------
void RT::ResetDelLookUp()
{
   if (delLookUp0)
   {
      delete delLookUp0;
      delete delLookUp;
      numDelLookUp0 = 0;
      numDelLookUp  = 0; 
      levels = 0;
   }     
}

//----------------------------------------------------
void RT::InitDelLookUp(int numEntries)
{
   assert(!delLookUp0);
   
   int avgKeysLeaf     = MaxEntries(true)  / 2;
   int avgKeysInternal = MaxEntries(false) / 2;

   if (avgKeysLeaf     < 2) avgKeysLeaf     = 2;
   if (avgKeysInternal < 2) avgKeysInternal = 2;

   numDelLookUp0 = numEntries;
   numDelLookUp  = numEntries / avgKeysLeaf + 1;
   for (int nnl = numDelLookUp; nnl > 1;)
   {
      nnl = nnl / avgKeysInternal;
      numDelLookUp += nnl; 
   }
   delLookUp0 = new GiSTpage[numDelLookUp0];
   delLookUp  = new GiSTpage[numDelLookUp];
   levels = 0;
}
#endif // RT_DEL_LOOKUP 

//-----------------------------------------------------
void RT::Insert(const GiSTentry& entry)
{
   if (autoHorizon) 
      if (++numOp == horUpdateInt)    // time to adjust the time horizon
      {
         RTperiod     UI = numEntries * (CT - lastReset) / numOp;
         RTperiod  oldUI = param / wfactor;
         UI = (UI + oldUI) / 2;
         w     = UI * (wfactor - TPR_UI_FACTOR);
         param = UI * wfactor; 
         lastReset = CT;
         numOp = 0;
      }
   numEntries++;
   lastChange = CT;

   GiST::Insert(entry); 
}

//-----------------------------------------------------
int RT::Delete(const GiSTpredicate& pred)
{
   int                num;

#ifdef  RT_DEL_LOOKUP
   const RTpredicate& rpred = (const RTpredicate&) pred;
   int         l;
   GiSTentry*  e;
   GiSTpath    path;
   GiSTpage    ptr[GIST_MAX_LEVELS];

// Observer support
   if (observer) observer->Inform(ON_DELETESTART);
//
   // Constructing a path from a root to a leaf
   assert(rpred.Ptr() < numDelLookUp0);
   ptr[0] = delLookUp0[rpred.Ptr()]; 
   if (!ptr[0]) return 0;         // there is no such entry in the index
   assert(ptr[0] < numDelLookUp);
   for (l = 1; l < levels; l++)
   {
      ptr[l] = delLookUp[ptr[l-1]]; 
      assert(ptr[l] && ptr[l] < numDelLookUp);       
   }

   path.MakeRoot();
   for (l -= 2; l >= 0; l--) path.MakeChild(ptr[l]);

   GiSTnode *node = ReadNode(path);
   e = node->SearchPtr(rpred.Ptr());

   assert(e);
   
   num = 1;
   node->DeleteEntry(e->Position());
   CorrectTree (node);
   delete node;
   delete e;

   delLookUp0[rpred.Ptr()] = 0;  // marking that we deleted this entry

// Observer support
   if (observer) observer->Inform(ON_DELETEEND);
//
#else   // !defined(RT_DEL_LOOKUP)

   num = GiST::Delete(pred);  
   if (!num) return 0;  // No such entry 
#endif

   lastChange = CT;
   numEntries -= num; 
   assert(numEntries >= 0);   

   return num;
}

//----------------------------------------------------
GiSTlist<GiSTentry*> RT::RemoveTop(GiSTnode *node)
{
   GiSTlist<GiSTentry*> deleted;
   int i;
   int num_rem = (int)((node->NumEntries() + 1) * RemoveRatio() + 0.5);
   RTentry* entry;

   PROFILE_ACTION_BEGIN(profile_removetop); 

   RTindexArray* out;
   RTindexArray  group1  (node->NumEntries());
   RTindexArray  group2  (node->NumEntries());

   assert (num_rem);
   for (i = 0; i < node->NumEntries(); i++) group2.Add(i);
   OldRemoveTop(node, group1, group2, num_rem);
   out = &group1;

   assert(out->GetNum() == num_rem);

   // out[0] will be reinserted last
   for (i = num_rem - 1; i >=0 ; i--)
   {
      assert((*out)[i] < node->NumEntries());
      entry = (RTentry *) (*node)[(*out)[i]].Ptr()->Copy();
      deleted.Append(entry);
   }
   // out[0] will be reinserted first

   // sort the first num_rem by index number to make removal possible
   sort (out->GetArrayPointer(), out->GetArrayPointer() + out->GetNum());

   for (i = num_rem - 1; i >=0 ; i--)
      node->DeleteEntry((*out)[i]);

   PROFILE_ACTION_END(profile_removetop); 

   return deleted;
}

//----------------------------------------------------
void RT::OldRemoveTop(GiSTnode *node, RTindexArray& out, RTindexArray& remains,