cuckoo_hash.c

A Library of Efficient Data Types and Algorithms,封装了常用的ADT及其相关算法的软件包

#include <cuckoo_hash.h>

void cuckoo_hash::init(int sz)
{
  count      = 0;
  table_size = sz;
  min_size   = (2 * table_size) / 5;
  mean_size  = 5 * (2 * table_size) / 12;
  max_chain  = 4 + (int)(4 * log(table_size) / log(2) + 0.5);
 
  a1[3] = 32 - (int)(log(table_size) / log(2) + 0.5 );
  a2[3] = a1[3];    /* shift */
  
  T1 = new cuckoo_hash_elem[sz];
  
  if (!T1)
    error_handler(1,"cuckoo_hash::init: error while allocating mem for T1");
  
  cuckoo_hash_item x;
  
  int i;
  for(i = 0; i < sz; i++)
  {
    x = &T1[i];
    
    x->key = 0;
    x->inf = 0;
  
    copy_key(x->key);
    copy_inf(x->inf);
  }
  
  
  T2 = new cuckoo_hash_elem[sz];
  
  if (!T2)
    error_handler(1,"cuckoo_hash::init: error while allocating mem for T2");

  for(i = 0; i < sz; i++)
  {
    x = &T2[i];
    
    x->key = 0;
    x->inf = 0;
    
    copy_key(x->key); 
    copy_inf(x->inf);  
  }

  init_hashfunction(a1);
  init_hashfunction(a2);
}



void cuckoo_hash::rehash(int sz)
{
  cuckoo_hash_elem* T1_old = T1;
  cuckoo_hash_elem* T2_old = T2;
  
  int tbl_sz_old = table_size;
  
  init(sz);
  
  int i;
  for (i = 0; i < tbl_sz_old; i++)
  {
    if (T1_old[i].key && !rehash_insert(T1_old[i]))
    { 
      i = -1;
      continue;
    }
    
    if (T2_old[i].key && !rehash_insert(T2_old[i]))
      i = -1;
  }
  
  /* destroy old tables */
  
  for (i = 0; i < tbl_sz_old; i++)
  {
    clear_key(T1_old[i].key);
    clear_inf(T1_old[i].inf);
  }
  
  for (i = 0; i < tbl_sz_old; i++)
  {
    clear_key(T2_old[i].key);
    clear_inf(T2_old[i].inf);    
  }

  delete [] T1_old;
  delete [] T2_old;
}


void cuckoo_hash::destroy()
{
  int i;
  for (i = 0; i < table_size; i++)
  {
    clear_key(T1[i].key);
    clear_inf(T1[i].inf);
  }
  
  for (i = 0; i < table_size; i++)
  {  
    clear_key(T2[i].key);
    clear_inf(T2[i].inf);    
  }
  
  count = 0;
  
  delete [] T1;
  delete [] T2;
}


/* --- public members ------------------------------------------ */


void cuckoo_hash::change_inf(cuckoo_hash_item it, GenPtr x)
{
  clear_inf(it->inf);
  it->inf = x;
  copy_inf(it->inf);
}


cuckoo_hash_item cuckoo_hash::lookup(GenPtr k) const
{
  int key  = hash_fct(k);
  
  ulong hkey;
  
  hash_cuckoo(hkey,a1,key);
  if (T1[hkey].key ==  k)  return &T1[hkey];
    
  hash_cuckoo(hkey,a2,key);
  if (T2[hkey].key ==  k)  return &T2[hkey];
  
  return 0;   
}


cuckoo_hash_item cuckoo_hash::insert(GenPtr k, GenPtr i)
{
  int key  = hash_fct(k);

  /* if element already stored then return it */
   
  ulong hkey;  
  hash_cuckoo(hkey,a2,key);
  if (T2[hkey].key == k) return &T2[hkey];

  hash_cuckoo(hkey,a1,key);
  if (T1[hkey].key == k) return &T1[hkey];  

  /* else insert a new element */
  
  cuckoo_hash_elem x, tmp;
  
  x.key = k;
  x.inf = i;
    
  for(int j = 0; j < max_chain; j++)
  {
    tmp = T1[hkey];
    
    T1[hkey] = x;
    
    copy_key(T1[hkey].key);
    copy_inf(T1[hkey].inf);
      
    if (!tmp.key)
    {
      count++;
      if (table_size < count) rehash(2 * table_size);
      return &T1[hkey];
    }
    
    x = tmp;
    
    hash_cuckoo(hkey,a2,hash_fct(x.key));
    
    tmp = T2[hkey];
        
    T2[hkey] = x;
    
    copy_key(T2[hkey].key);
    copy_inf(T2[hkey].inf);
    
    if (!tmp.key)
    {
      count++;
      if (table_size < count) rehash(2 * table_size);
      return &T2[hkey];
    }
    
    x = tmp;
    hash_cuckoo(hkey,a1,hash_fct(x.key));
  }
 
  /* forced rehash */
  
  if (count < mean_size)
    rehash(table_size);
  else
    rehash(2 * table_size);
  
  insert(x.key,x.inf);
 
  return 0; /* never reached */
}


void cuckoo_hash::del(GenPtr k)
{
  int key  = hash_fct(k);
  
  ulong hkey;
  hash_cuckoo(hkey,a1,key);
  
  cuckoo_hash_item x = &T1[hkey];
  
  if (x->key == k)
  {
    clear_key(x->key);
    clear_inf(x->inf);
    
    x->key = 0; 
    x->inf = 0;
 
    count--;
    
    if (count < min_size) rehash(table_size / 2);
    
    return;
  }
  
  hash_cuckoo(hkey,a2,key);
  
  x = &T2[hkey];
  
  if (x->key == k)
  {
    clear_key(x->key);
    clear_inf(x->inf);
    
    x->key = 0; 
    x->inf = 0;
    
    count--;
   
    if (count < min_size) rehash(table_size / 2);
  }
}


void cuckoo_hash::del_item(cuckoo_hash_item it)
{
  if (it) 
    del(it->key);
}


cuckoo_hash::cuckoo_hash(const cuckoo_hash& D)
{
  init(D.table_size);
  
  int i;
  for (i = 0; i < table_size; i++)
  {
    T1[i] = D.T1[i];
    
    copy_key(T1[i].key);
    copy_inf(T1[i].inf);
    
    if (T1[i].key) count++;

    T2[i] = D.T2[i];
    
    copy_key(T2[i].key);
    copy_inf(T2[i].inf);

    if (T2[i].key) count++;
  }
  
  for (i = 0; i < 3; i++)
  {
    a1[i] = D.a1[i];
    a2[i] = D.a2[i];
  }
}


cuckoo_hash& cuckoo_hash::operator=(const cuckoo_hash& D)
{
  destroy();
  init(D.table_size);
  
  int i;
  for (i = 0; i < table_size; i++)
  {
    T1[i] = D.T1[i];
    
    copy_key(T1[i].key);
    copy_inf(T1[i].inf);
    
    if (T1[i].key) count++;
    
    T2[i] = D.T2[i];
    
    if (T2[i].key) count++;
   
    copy_key(T2[i].key);
    copy_inf(T2[i].inf);
    
  }

  for (i = 0; i < 3; i++)
  {
    a1[i] = D.a1[i];
    a2[i] = D.a2[i];
  }

  return *this;
}