_ch_hash.c

数据类型和算法库LEDA 数据类型和算法库LEDA

/*******************************************************************************
+
+  LEDA  3.0
+
+
+  _ch_hash.c
+
+
+  Copyright (c) 1992  by  Max-Planck-Institut fuer Informatik
+  Im Stadtwald, 6600 Saarbruecken, FRG     
+  All rights reserved.
+ 
*******************************************************************************/


#include <LEDA/impl/ch_hash.h>

//------------------------------------------------------------------------------
//  hashing with chaining
//------------------------------------------------------------------------------


int ch_hash::next_pow(int x) const
{ // return next power of 2
  int result = 1;    
  while ((x>>=1) > 0) result <<= 1;
  return result;
 }

 

ch_hash_item ch_hash::search(GenPtr x, ch_hash_item& pred) const
{ register int n;
  register ch_hash_item p;
  register ch_hash_item q;

  if (int_type())
  { n = int(x) & (table_size-1);  // table_size = power of 2
    p = table[n];
    q = p->succ;
    table[n+1]->k = x;
    while (q->k != x) { p = q; q = q->succ; }
   }
  else
  { n = hash_fct(x) & (table_size-1);
    p = table[n];
    q = p->succ;
    table[n+1]->k = x;
    while (cmp(q->k,x) != 0) { p = q; q = q->succ; }
   }

  pred = p;

  return (q == table[n+1]) ? 0 : q;
}

void ch_hash::change_inf(ch_hash_item p, GenPtr x)
{ clear_inf(p->i);
  p->i = x;
  copy_inf(p->i);
 }

void ch_hash::del(GenPtr x)
{ ch_hash_item p;
  ch_hash_item q = search(x,p);

  if (q==0) return;

  clear_key(q->k);
  clear_inf(q->i);

  p->succ = q->succ;
  delete q;
  count--;
  if (count == low_table) rehash(low_table);
 }

void ch_hash::del_item(ch_hash_item q)
{ register ch_hash_item p = table[hash_fct(q->k) & (table_size-1)];
  while(p->succ != q) p = p->succ;
  clear_key(q->k);
  clear_inf(q->i);
  p->succ = q->succ;
  delete q;
  count--;
  if (count == low_table) rehash(low_table);
 }
  
  

ch_hash_item ch_hash::insert(GenPtr x, GenPtr y)
{ ch_hash_item p;
  ch_hash_item q = search(x,p);

  if (q)
  { clear_inf(q->i);
    q->i = y;
    copy_inf(q->i);
    return q;
   }

   copy_key(x);
   copy_inf(y);

   q = new ch_hash_elem(x,y,p->succ);
   p->succ = q;

   count++;

   if (count == high_table) rehash(high_table);

   return q;

}



ch_hash_item ch_hash::first_item() const
{ register ch_hash_item p = table[0];
  while (p && p->head) p = p->succ;
  return p;
 }

ch_hash_item ch_hash::next_item(ch_hash_item q) const
{ register ch_hash_item p = q->succ;
  while (p && p->head) p = p->succ;
  return p;
 }


void ch_hash::destroy()
{ register ch_hash_item p = first_item();
  while (p)
  { clear_key(p->k);
    clear_inf(p->i);
    p = next_item(p);
  }
  deallocate_list(table[0],table[table_size],sizeof(ch_hash_elem));
  delete table;
}


void ch_hash::init(int T)
{ register int i;
  register ch_hash_item p;

  table_size = T;

  low_table  = (table_size > 1024) ? table_size >> 1 : -1;
  high_table = table_size << 1;

  table = new ch_hash_item[table_size+1];

  p = new ch_hash_elem(0,0);
  p->head = true;
  table[0] = p;

  for (i = 1; i <= table_size ; i++ )
  { p->succ = new ch_hash_elem(0,0);
    p = p->succ;
    p->head = true;
    table[i] = p;
   }

  p->succ = 0;

  count = 0;
}

void ch_hash::rehash(int T)
{ register ch_hash_item p;
  register ch_hash_item q;
  register ch_hash_item r;

  if (T == table_size) return;

  ch_hash_item* old_table      = table;
  int           old_table_size = table_size;
  int           old_count      = count;

  init(T);

  p = old_table[0];

  while (p)
  { r = p->succ;
    if (p->head)
       delete p;
    else
     { q = table[hash_fct(p->k) & (table_size-1)];
       p->succ = q->succ;
       q->succ = p;
      }
    p = r;
  }
  count = old_count;

  delete old_table;
}


ch_hash::ch_hash(const ch_hash& D)
{ ch_hash_item p;
  init(D.table_size);
  forall_items(p,D) 
  { insert(p->k,p->i);
    copy_key(p->k);
    copy_inf(p->i);
   }
}


ch_hash& ch_hash::operator=(const ch_hash& D)
{ ch_hash_item p;
  clear();
  forall_items(p,D) insert(p->k,p->i);
  return *this;
}