tvindexinsert.c

TV-tree的c实现源码

                         stats.IncrementStat(LEAFWRITECOUNT);
                      stats.IncrementStat(SPLITLEAFCOUNT);
                 }
              else
                 {
                   // reinsert

                   n->SetReInsert(e1, reinsertd, thishandle, ip.reinsert_percent, ip.page_size, ip.min_fill_percent, ip.unfold_dim );
                   insertreturn.Onebound(((Leaf_TVNode *)n)->MinBound(gfeat, ip.unfold_dim));
                   stats.IncrementStat(LEAFWRITECOUNT);
                   stats.IncrementStat(REINSERTCOUNT);
                 }
           }
        else
           {
	      // Leaf TVNode not full, just insert the data
              insertreturn.irt = newele;
              stats.IncrementStat(LEAFWRITECOUNT);
	      thishandle.write();
           }
     }
  return insertreturn;
}

// Given that root is splitted, create the new root
// rootbound : point to the calculated new boundary of current root (if exists)
//             (if new root formed from split, the bound would have be stored in rir)
void TVTree::NewRoot(RecurInsertReturn& rir, int rootlevel, ReInsertClass& reinsertd, TVRectangle* rootbound)
{
   // Set up branch for current root 
   TVBranch bin;

   if (rootbound)
      bin = TVBranch(*rootbound, root);
   else
      bin = TVBranch(rir.bound[0], root);

   Internal_TVNode *newroot = new Internal_TVNode(rootlevel, CONSERVE_MAX_BRANCH_FACTOR);

   // Put in the first branch 
   newroot->Put(bin, ip.page_size);
   bin.WriteChild();

   // Attempt to put in the rest of the bound
   int curbranch = 0;
   for (; (curbranch < rir.newcount) && (newroot->Put(rir.branch[curbranch],ip.page_size)); curbranch++)
	;
   if (rir.newcount - curbranch) 
      {
	  TVNodehandle nullhandle;
	  RecurInsertReturn rfc; 
          SplitReturn splitre = newroot->Split(rir.branch[curbranch], nullhandle, ip.page_size, ip.min_fill_percent, ip.unfold_dim);
	  rfc.FromSplit(splitre);
	  root = newroot;

	  for (int i = 0; i < splitre.parts; i++)
              stats.IncrementStat(WRITECOUNT);
          stats.IncrementStat(SPLITNODECOUNT);

	  NewRoot(rfc, rootlevel + 1, reinsertd);
	  for (int j = curbranch + 1; j < rir.newcount; j++)
	       InsertTVBranch1(rir.branch[j], reinsertd);
       } 
   else
     root = newroot;
}

// Inserting a leaf element from the root
TVTree& TVTree::InsertElement1(Leaf_Element& e1, ReInsertClass& reinsertd, VCOM_TYPE (*gfeat)(int, char*))
{
   TVNodehandle nullhandle;
   if (root)
      {
	 // Non-empty tree

         if (root->TVNodeType() == INTERNAL_NODE)
            {

	      // There is children from the root

              int rootlevel = root->GetLevel();
              RecurInsertReturn returnfromchild = RecurInsertElement(root, e1, nullhandle, reinsertd,   gfeat);

              // discount the reading of the root (assume root is in memory)
              stats.AddIntStat(READCOUNT, -1);

              switch (returnfromchild.irt) {
                case newbranch : // Calculate boundary for current root
				 {
				 TVRectangle rootbound;

				 if (root->TVNodeType() == INTERNAL_NODE)
				    rootbound = ((Internal_TVNode *)root)->MinBound(ip.unfold_dim);
				 else
				    rootbound = ((Leaf_TVNode *)root)->MinBound(gfeat, ip.unfold_dim);
	                         NewRoot(returnfromchild, rootlevel + 1, reinsertd, &rootbound);
				 }
				 break;
                case fromsplit : NewRoot(returnfromchild, rootlevel + 1, reinsertd);
				 break;
		default :
			   break;
		 }
            }
         else
            {
	      // Put element in root. check if split necessary
              if (root->Put(e1, ip.page_size) == NODE_FULL)
                {
                  // split root

                  RecurInsertReturn returnfromchild;
                  SplitReturn splitre = root->Split(e1, nullhandle, gfeat, ip.page_size, ip.min_fill_percent, ip.unfold_dim);
		  returnfromchild.FromSplit(splitre);
		  for (int i = 0; i < splitre.parts; i++)
                      stats.IncrementStat(LEAFWRITECOUNT);
                  stats.IncrementStat(SPLITLEAFCOUNT);

		  NewRoot(returnfromchild, 1, reinsertd);
                }
            }
      }
   else
      {
         // create new root
         Leaf_TVNode *lnode = new Leaf_TVNode(CONSERVE_MAX_ELEMENT_FACTOR);
         root = lnode;
         root->Put(e1, ip.page_size);
      }

   return *this;
}


// The main insertion routine
TVTree& TVTree::InsertElement(Leaf_Element& e1, VCOM_TYPE (*gfeat)(int, char*))
{

   // Setting up the reinsert stacks
   int begin_height = GetHeight();
   ReInsertClass reinsertd(begin_height);      

   e1.GetTVector(ip.unfold_dim, gfeat);

   // Traverse and insert
   InsertElement1(e1, reinsertd, gfeat);

   while (reinsertd.NonEmpty())
	{
	   for (int i = begin_height - 1; i > 0; i--)
	       {
		 while (reinsertd.NonEmpty(i))
		    {
		     TVBranch b;
		     b = reinsertd.Top_branch(i);
		     InsertTVBranch1(b, reinsertd);
		     reinsertd.Pop_branch(i);
		    }
	       }
	   while (reinsertd.NonEmpty(0))
	     {
		// Reinserting the stuff removed during the traversal

		Leaf_Element le;
		le = reinsertd.Top_element(0);
		InsertElement1(le, reinsertd, gfeat);
		reinsertd.Pop_element(0);
	     }
        }

   return *this;

}


TVTree& TVTree::Insert(char *e, int size, VCOM_TYPE (*gfeat)(int, char*))
{
   Leaf_Element ele(e, size);
   return InsertElement(ele, gfeat); 
}


// Recursion during insertion of branch
// n : points to the current node on the traversal
// b : elements to be reinserted
// level : the level where insertion is to be done at
// reinsertd : reinsert class, storing stuff to be reinserted
RecurInsertReturn TVTree::RecurInsertTVBranch(TVNode *n, TVBranch &b, int level, const TVNodehandle& thishandle, ReInsertClass& reinsertd)
{
  RecurInsertReturn insertreturn, returnfromchild;
  TVBranch newb;


  if (n->GetLevel() > level)
     {
	int needwrite = FALSE;
        stats.IncrementStat(READCOUNT);

        // continue recursion

        // Pick a branch
        int branchpicked = ((Internal_TVNode *)n)->PickTVBranch(b.GetBound(), ip.pickbranch_compare_count, ip.unfold_dim);
        TVBranch bin = *((n->Fetch(branchpicked)).u.b);
        n->Remove(branchpicked, ip.min_fill_percent);

        // Recursive call
        returnfromchild = RecurInsertTVBranch(bin.FetchChild(), b, level, bin.GetHandle(), reinsertd);


        switch (returnfromchild.irt){
          case newele    : assert(0);
                           break;
          case newbound  : // New bound at the child, see if update necessary    
			   {
			   int curbound = 0;
			   for (; (curbound < returnfromchild.newcount) && (bin.GetBound().Contain(returnfromchild.bound[curbound])); curbound++)
			       ;
                           if (curbound < returnfromchild.newcount)
                              {
			         for (; (curbound < returnfromchild.newcount); curbound++)
                                      bin.UpdateBound(returnfromchild.bound[curbound], ip.unfold_dim);
                                 insertreturn.Onebound(bin.GetBound());
                                 stats.IncrementStat(WRITECOUNT);
				 needwrite = TRUE;
                               }
                           }
                           break;
	  case fromsplit : // Adjust the old branch first
			   {
			   bin.SetBound(returnfromchild.bound[0]);
			   needwrite = TRUE;
			   }
	  case newbranch : // Try to insert the new branches into the node
			   {
			   int curbranch = 0;
			   for (; (curbranch < returnfromchild.newcount) && (n->Put(returnfromchild.branch[curbranch],ip.page_size)); curbranch++)
				 ;

			   if (returnfromchild.newcount - curbranch) 
                              {
				// There are branch to be inserted, put it in the stack and insert later
				for (; (curbranch < returnfromchild.newcount); curbranch++)
				   reinsertd.Add(returnfromchild.branch[curbranch], n->GetLevel());
			        stats.IncrementStat(REINSERTCOUNT);
                              }
			   else
			      {
				 // All extra branches are reinserted, pass the new bound info up
				 if (returnfromchild.irt = fromsplit)
				    insertreturn.Nbound(returnfromchild.bound, returnfromchild.newcount + 1); // the bounding region for the (original) node need to be stored too
				 else
				    insertreturn.Nbound(returnfromchild.branch, returnfromchild.newcount);
			      }
			     needwrite = TRUE;
                           }
                           break;
          case nochange  : 
                           break;
              }

	// Put the selected branch back in, check if split necessary
        if (n->Put(bin, ip.page_size) == NODE_FULL)
           {
             // splitting necessary
            SplitReturn splitre = n->Split(bin, thishandle, ip.page_size, ip.min_fill_percent, ip.unfold_dim);
            insertreturn.FromSplit(splitre);
	    for (int i = 0; i < splitre.parts; i++)
                 stats.IncrementStat(WRITECOUNT);
            stats.IncrementStat(SPLITNODECOUNT);
           }
	else
	   {
	     if (needwrite)
		thishandle.write();

	   }
     }
  else
     {
	// Reached the desired level of insertion
        stats.IncrementStat(READCOUNT);
        if (n->Put(b, ip.page_size) == NODE_FULL)
           {
              SplitReturn splitre = n->Split(b, thishandle, ip.page_size, ip.min_fill_percent, ip.unfold_dim);
              insertreturn.FromSplit(splitre);
	      for (int i = 0; i < splitre.parts; i++)
                   stats.IncrementStat(LEAFWRITECOUNT);
              stats.IncrementStat(SPLITLEAFCOUNT);
           }
        else
           {
              insertreturn.Onebound(b.GetBound());
	      thishandle.write();
           }
     }
  return insertreturn;
}

// Inserting a branch from the root
TVTree& TVTree::InsertTVBranch1(TVBranch &b, ReInsertClass &reinsertd)
{
   assert((root) && (root->TVNodeType() == INTERNAL_NODE));

   TVNodehandle nullhandle;

cout << "InsertTVBranch1 called\n";

   int reslevel;
   int rootlevel = root->GetLevel();
   if (b.FetchChild()->TVNodeType() == LEAF_NODE)
    reslevel = 1;
   else
    reslevel = b.FetchChild()->GetLevel() + 1;
   RecurInsertReturn returnfromchild = RecurInsertTVBranch(root, b, reslevel, nullhandle, reinsertd);
   stats.AddIntStat(READCOUNT, -1); // discount read from root
      switch (returnfromchild.irt) {
	case newbranch : // Calculate boundary for current root
			 {
			 TVRectangle rootbound;

			 rootbound = ((Internal_TVNode *)root)->MinBound(ip.unfold_dim);
			 NewRoot(returnfromchild, rootlevel + 1, reinsertd, &rootbound);
			 }
			 break;
	case fromsplit : NewRoot(returnfromchild, rootlevel + 1, reinsertd);
			 break;
	default :
		   break;
      }

   return *this;
}

// Main procedure for insert branch (note that there is no reinsertion implemented as yet)
TVTree& TVTree::InsertTVBranch(TVBranch &b)
{
   int begin_height = GetHeight();
   ReInsertClass reinsertd(begin_height);
//   ReInsertClass reinsertd(1);  // for reinsert leaf

   InsertTVBranch1(b, reinsertd);
   while (reinsertd.NonEmpty())
      {
	   for (int i = 1; i < begin_height; i++)
	       {
		 while (reinsertd.NonEmpty(i))
		    {
		     TVBranch b;
		     b = reinsertd.Top_branch(i);
		     InsertTVBranch1(b, reinsertd);
		     reinsertd.Pop_branch(i);
		    }
	       }
      }
   return *this;
}