hashtree.c

hashtree算发

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "IntList.h"
#include "HashTree.h"

//////////////////////////////////////////////////////////////////////

// Constructor
TreeNode::TreeNode(bool l, int d, int n)
:con(NULL), len(0), depth(d), brFactor(n)
{
  int i;

  if (!l) {
    // Internal node
    index = NULL;
    child = new (TreeNode*)[n];
  } else {
    // Leaf node

    // Allocate the pointers
    index = new (IntList*)[n];
    child = NULL;
    for (i=0; i<n; i++) index[i]=NULL;

    con = new Content[n];
    for (i=0; i<n; i++)
    {
      con[i].a = 0;
      /***********************************************************
      **		initialization of content		**
      ***********************************************************/
    }
  }
}

// Destructor
TreeNode::~TreeNode()
{
  int i;
  
  if (!isLeaf()) {
    // Internal node
    delete[] child;
  } else {
    // Leaf node
    for (i=0; i<len; i++) delete index[i];
    
    delete[] index;
    delete[] con;
  }
}

// A hash function
int TreeNode::hashFunc(int i)
{
  return i%brFactor;
}

// Given a node, transver to the leaf node
TreeNode* TreeNode::transver(const IntList& i)
{
  TreeNode* curNode = this;
  int d = depth-1;

  
  while (!curNode->isLeaf()) {
    assert(d<i.get_len());
    
    curNode = curNode->child[hashFunc(i[d])];
    d++;
  }

  return curNode;
}

// Insert a node into the hash tree
void TreeNode::insert(const IntList& ss)
{
  TreeNode* leafNode;
  
  // find the leaf node to insert to
  leafNode = transver(ss);
  
  // check if it is full or not
  if (leafNode->len < leafNode->brFactor) {
    // Not full
    leafNode->index[leafNode->len] = new IntList;
    leafNode->index[leafNode->len]->copy(ss);
    leafNode->len++;
  } else {
    // Full
    
    // See if splitting is possible
    if (leafNode->depth<=ss.get_len()) {
      // Splitting
      leafNode->split();
      leafNode->insert(ss);
    } else {
      printf("Resize the leaf node...\n");
      leafNode->resize(leafNode->brFactor*2);
      leafNode->index[leafNode->len] = new IntList;
      leafNode->index[leafNode->len]->copy(ss);
      leafNode->len++;
    }
  }
}

// Split a leaf node
void TreeNode::split()
{
  IntList** reinsert;
  int oldlen, i;

  // Convert the leaf node into an internal node
  // Create children
  child = new (TreeNode*)[brFactor];
  for (i=0; i<brFactor; i++) {
    child[i] = new TreeNode(true,depth+1,brFactor);
  }
  
  // Convert to an internal node
  reinsert = index;
  oldlen = len;
  index = NULL;
  len = 0;

  // Reinsert the indexs
  for (i=0; i<oldlen; i++) {
    insert(*reinsert[i]);
    setCon(*reinsert[i],con[i]);
    delete reinsert[i];
  }
  
  // Release old nodes
  delete[] reinsert;
  delete[] con;
}

// Resize a leaf node
void TreeNode::resize(int newsize)
{
  IntList** temp_ss;
  Content*  temp_con;

  if (!isLeaf()) {
    printf("TreeNode::resize(): Resize of internal node is invalid.\n");
    return;
  }
  
  if (newsize<=brFactor) {
    printf("TreeNode::resize(): Cannot reduce the size of a node.\n");
    return;
  }
  
  // Copy the old node and statistics
  temp_ss = index;
  temp_con = con;

  // Allocate new and larger space
  index = new (IntList*)[newsize];
  memcpy(index,temp_ss,sizeof(IntList*)*brFactor);
  con = new Content[newsize];
  memcpy(con,temp_con,sizeof(Content)*brFactor);
  brFactor = newsize;
  
  // Delete temp data
  delete[] temp_ss;
  delete[] temp_con;
}

// Remove node
void TreeNode::remove(const IntList& ss, int& no_ss)
{
  TreeNode* leafNode;
  int i;
  
  // Transver to leaf node
  leafNode = transver(ss);

  // Search the node to be deleted
  for (i=0; i<leafNode->len; i++) {
    if (ss==*leafNode->index[i]) {
      if (i==leafNode->len-1) {
        // Last node
        leafNode->len--;
      } else {
        // Not last node
        leafNode->index[i]->copy(*leafNode->index[leafNode->len-1]);
        leafNode->con[i] = leafNode->con[leafNode->len-1];
        leafNode->len--;
      }
      
      no_ss--;  // Update the count of no of nodes
      return;  
    }
  }
  
  printf("TreeNode::remove(): Subspace not found\n");
}


// Show the content of a node
void TreeNode::show() const
{
  int i;

  if (isLeaf()) {
    // Leaf
    if (len>0) {
      //printf("%d:",depth);

      //printf("{");
      for (i=0; i<len; i++) {
        index[i]->show();
        if (con!=NULL)
      /***********************************************************
      **		print out the	 content		**
      ***********************************************************/
          printf("%d\n", con[i].a);
        //if (i!=len-1) printf(", ");
      }
      //printf("}\n");
    }
  } else {
    // Internal
    //printf("Internal node\n");
    for (i=0; i<brFactor; i++) {
      child[i]->show();
    }
  }
}

// Convert subtree to array
void TreeNode::convert2array(IntList*& ia, int& idx_ss) const
{
  int i;

  if (isLeaf()) {
    // Leaf
    for (i=0; i<len; i++) {
      ia[idx_ss].copy(*index[i]);
      idx_ss++;
    }
  } else {
    // Internal
    for (i=0; i<brFactor; i++) {
      child[i]->convert2array(ia,idx_ss);
    }
  }
}                                      
                                      
// Set the statistics of a node
void TreeNode::setCon(const IntList& ss, const Content& es)
{
  TreeNode* leafNode;
  int i;

  // Transver to leaf node
  leafNode = transver(ss);
  
  // Find the node in leaf node
  for (i=0; i<leafNode->len; i++) {
    if (ss==*leafNode->index[i]) {
      // Copy the statistics
      memcpy(&leafNode->con[i],&es,sizeof(Content));
    }
  }
}


//////////////////////////////////////////////////////////////////////

// Constructor
HashTree::HashTree(int n, int d)
:brFactor(n), dim(d), no_ss(0)
{
  root = new TreeNode(true,1,brFactor);
}

// Destructor
HashTree::~HashTree()
{
  delete root;
}

// Insert a new node
void HashTree::insert(const IntList& ss) 
{ 
  assert(ss.get_len()==dim);  

  root->insert(ss);  // insert it to tree
  no_ss++;           // update counter
}

// Remove a node
void HashTree::remove(const IntList& ss) 
{ 
  root->remove(ss, no_ss); 
}

// Check whether a node already exists in a node
bool HashTree::exist(const IntList& il) const
{
  TreeNode* leafNode;
  int i;
  
  // Transver to leaf node
  leafNode = root->transver(il);
  
  // Test if it is stored in leaf node
  for (i=0; i<leafNode->len; i++) {
    if (il==*leafNode->index[i]) return true;
  }
  
  return false;
}
  
// Put all nodes in the hash tree to an array
void HashTree::convert2array(IntList*& ia, int& idx_ss) const
{
  // index stating the first unused element of ia = 0
  idx_ss = 0;  

  // Allocate memory for the array
  ia = new IntList[no_ss];
  
  // Involve recursive member function
  root->convert2array(ia,idx_ss);
  
  // Warning: user of this function is responsible for releasing
  //          the memory allocated for ia
}

// Lock the tree
void HashTree::locktree()
{
  printf("Warning: HashTree::locktree() is called which is obsolete.\n");

}

// Set the statistics of a node
void HashTree::setCon(const IntList& ss, const Content& es)
{
  root->setCon(ss,es);

}

// Find the stored statistics from hash tree
Content HashTree::findStat(const IntList& ss) const
{
  TreeNode* leafNode;
  int i;

  // Transver to leaf node
  leafNode = root->transver(ss);

  // Find the index in the leaf node
  for (i=0; i<leafNode->len; i++) {
    if (ss==*leafNode->index[i]) {
      // Return the stat
      return leafNode->con[i];
    }
  }
  
  printf("HashTree::findStat(): Warning: Cannot find the required index\n");

      /***********************************************************
      **	set the return when data not find		**
      ***********************************************************/
  Content es = {-1};
  return es;  
}


//////////////////////////////////////////////////////////////////////