home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / ledar34.zip / leda-r-3_4_tar / LEDA-3.4 / src / dict / _ch_hash.c < prev    next >
C/C++ Source or Header  |  1996-09-03  |  7KB  |  347 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA 3.4
  4. +
  5. +  _ch_hash.c
  6. +
  7. +  This file is part of the LEDA research version (LEDA-R) that can be 
  8. +  used free of charge in academic research and teaching. Any commercial
  9. +  use of this software requires a license which is distributed by the
  10. +  LEDA Software GmbH, Postfach 151101, 66041 Saarbruecken, FRG
  11. +  (fax +49 681 31104).
  12. +
  13. +  Copyright (c) 1991-1996  by  Max-Planck-Institut fuer Informatik
  14. +  Im Stadtwald, 66123 Saarbruecken, Germany     
  15. +  All rights reserved.
  16. + 
  17. *******************************************************************************/
  18. #include <LEDA/impl/ch_hash.h>
  19.  
  20. //------------------------------------------------------------------------------
  21. //
  22. //  hashing with chaining and table doubling
  23. //
  24. //  S. Naeher (1994)
  25. //
  26. //  last modfied Dec. 1995:  - missing iteration functions
  27. //                           - bugs in destroy,lookup,rehash
  28. //------------------------------------------------------------------------------
  29.  
  30.  
  31. #define NULLKEY  GenPtr(this)
  32.  
  33.  
  34. int ch_hash::next_pow(int x) const
  35. { // return next power of 2
  36.   int result = 1;    
  37.   while ((x>>=1) > 0) result <<= 1;
  38.   return result;
  39.  }
  40.  
  41. // Iteration
  42.  
  43. ch_hash_item ch_hash::next_item(ch_hash_item q) const
  44. { q = q->succ;
  45.   if (q == &STOP)
  46.   { ch_hash_item stop = table + table_size;
  47.     for(;;)
  48.     { (*(ch_hash_item*)&iterator)++;
  49.       if (iterator == stop) break;
  50.       if (iterator->k != NULLKEY) break;
  51.       if (iterator->succ != &STOP) break;
  52.      }
  53.  
  54.     if (iterator < stop)
  55.       q = (iterator->k != NULLKEY) ? iterator : iterator->succ; 
  56.     else
  57.       q = nil;
  58.    }
  59.   return q;
  60.  }
  61.  
  62. ch_hash_item ch_hash::first_item() const 
  63. { *(ch_hash_item*)&iterator = table;
  64.   ch_hash_item q = table;
  65.   if (q->k == NULLKEY) q = next_item(q); 
  66.   return q;
  67.  }
  68.  
  69.  
  70. ch_hash_item ch_hash::lookup(GenPtr x) const
  71. { ch_hash_item q = table;
  72.  
  73.   ((GenPtr&)STOP.k) = x;
  74.  
  75.   if (int_type())
  76.   { q += (LEDA_ACCESS(int,x) & table_size_1);  // table_size = power of 2
  77.     while (q->k != x) q = q->succ;
  78.    }
  79.   else
  80.   { q += (hash_fct(x) & table_size_1);
  81.     while (q->k == NULLKEY || cmp(q->k,x)) q = q->succ;
  82.    }
  83.  
  84.   return (q == &STOP) ? nil : q;
  85. }
  86.  
  87.  
  88. void ch_hash::change_inf(ch_hash_item p, GenPtr x)
  89. { clear_inf(p->i);
  90.   p->i = x;
  91.   copy_inf(p->i);
  92.  }
  93.  
  94. void ch_hash::del(GenPtr x)
  95. { 
  96.   ch_hash_item p = table + (hash_fct(x) & table_size_1);
  97.  
  98.   if (p->k != NULLKEY && cmp(p->k,x) == 0)
  99.   { clear_key(p->k);
  100.     clear_inf(p->i);
  101.     p->k = NULLKEY;
  102.     count--;
  103.     if (count == low_table) rehash(low_table);
  104.     return;
  105.   }
  106.  
  107.   STOP.k = x;
  108.  
  109.   if (int_type())
  110.      while (LEDA_ACCESS(int,p->succ->k) != LEDA_ACCESS(int,x)) p = p->succ;
  111.   else
  112.      while (p->k == NULLKEY || cmp(p->succ->k,x)) p = p->succ;
  113.  
  114.   ch_hash_item q = p->succ;
  115.  
  116.   if (q==&STOP) return;
  117.  
  118.   clear_key(q->k);
  119.   clear_inf(q->i);
  120.  
  121.   p->succ = q->succ;
  122.   delete q;
  123.   count--;
  124.   if (count == low_table) rehash(low_table);
  125.  }
  126.  
  127.  
  128. void ch_hash::del_item(ch_hash_item q)
  129. { ch_hash_item p = table + (hash_fct(q->k) & table_size_1);
  130.   clear_key(q->k);
  131.   clear_inf(q->i);
  132.   if (p==q) 
  133.      p->k = NULLKEY;
  134.   else
  135.     { while(p->succ != q) p = p->succ;
  136.       p->succ = q->succ;
  137.       delete q;
  138.      }
  139.   count--;
  140.   if (count == low_table) rehash(low_table);
  141.  }
  142.   
  143.   
  144.   
  145.  
  146. ch_hash_item ch_hash::insert(GenPtr x, GenPtr y)
  147. { 
  148.   ch_hash_item p = table + (hash_fct(x) & table_size_1);
  149.   //ch_hash_item p = table + (LEDA_ACCESS(int,x) & table_size_1);
  150.   ch_hash_item q = p;
  151.  
  152.   STOP.k = x;
  153.  
  154.   if (int_type())
  155.      while (p->k != x) p = p->succ;
  156.   else
  157.      while (p->k == NULLKEY || cmp(p->k,x)) p = p->succ;
  158.  
  159.   if (p != &STOP)
  160.   { clear_inf(p->i);
  161.     p->i = y;
  162.     copy_inf(p->i);
  163.     return p;
  164.    }
  165.  
  166.   count++;
  167.   copy_key(x);
  168.   copy_inf(y);
  169.  
  170.   if (q->k == NULLKEY) 
  171.     { q->k = x;
  172.       q->i = y;
  173.      }
  174.   else
  175.     { q->succ = new ch_hash_elem(x,y,q->succ);
  176.       q = q->succ;
  177.      }
  178.  
  179.   if (count == high_table) rehash(high_table);
  180.  
  181.   return q;
  182. }
  183.  
  184.  
  185.  
  186. void ch_hash::destroy()
  187. { 
  188.   for(int i=0; i < table_size; i++) 
  189.   { ch_hash_item p = table+i;
  190.     if (p->k != NULLKEY)
  191.     { clear_key(p->k);
  192.       clear_inf(p->i);
  193.      }
  194.     p = p->succ;
  195.     while (p != &STOP)
  196.     { clear_key(p->k);
  197.       clear_inf(p->i);
  198.       ch_hash_item q = p;
  199.       p = p->succ;
  200.       delete q;
  201.     }
  202.   }
  203.  
  204.   //delete[] table;
  205.   free((char*)table);
  206. }
  207.  
  208.  
  209. void ch_hash::init(int T)
  210. { 
  211.   ch_hash_item p;
  212.   ch_hash_item stop;
  213.  
  214.   table_size = T;
  215.   table_size_1 = T-1;
  216.  
  217.   low_table  = (T > 1024) ? T/2 : -1;
  218.   high_table = 2*T;
  219.  
  220.   //table = new ch_hash_elem[table_size];
  221.   table = (ch_hash_elem*)malloc(table_size*sizeof(ch_hash_elem));
  222.  
  223.   stop = table + table_size;
  224.   for(p=table; p<stop; p++) 
  225.   { p->succ = &STOP;
  226.     p->k = NULLKEY;
  227.   }
  228.  
  229.   count = 0;
  230. }
  231.  
  232. void ch_hash::gen_rehash(int T)
  233. { 
  234.   ch_hash_item old_table = table;
  235.   int old_table_size = table_size;
  236.   int old_count = count;
  237.  
  238.   init(T);
  239.  
  240.   for (int i=0; i<old_table_size; i++)
  241.   { ch_hash_item p = old_table[i].succ;
  242.     while(p != &STOP)
  243.     { ch_hash_item r = p->succ;
  244.       ch_hash_item q = table + (hash_fct(p->k) & table_size_1);
  245.       p->succ = q->succ;
  246.       q->succ = p;
  247.       p = r;
  248.     }
  249.    }
  250.  
  251.   ch_hash_item stop = old_table+old_table_size;
  252.  
  253.   for (ch_hash_item p=old_table; p<stop; p++)
  254.     if (p->k != NULLKEY) 
  255.     { ch_hash_item q = table + (hash_fct(p->k) & table_size_1);
  256.       if (q->k == NULLKEY)
  257.         { q->k = p->k;
  258.           q->i = p->i;
  259.          }
  260.       else
  261.          q->succ = new ch_hash_elem(p->k,p->i,q->succ);
  262.     }
  263.    
  264.   count = old_count;
  265.  
  266.   //delete[] old_table;
  267.   free((char*)old_table);
  268. }
  269.  
  270.  
  271.  
  272. void ch_hash::int_rehash(int T)
  273. { 
  274.   ch_hash_item old_table = table;
  275.  
  276.   int old_table_size = table_size;
  277.   int old_count = count;
  278.  
  279.   init(T);
  280.  
  281.   for (int i=0; i<old_table_size; i++)
  282.   { ch_hash_item p = old_table[i].succ;
  283.     while(p != &STOP)
  284.     { ch_hash_item r = p->succ;
  285.       ch_hash_item q = table + (LEDA_ACCESS(int,p->k) & table_size_1);
  286.       p->succ = q->succ;
  287.       q->succ = p;
  288.       p = r;
  289.      }
  290.    }
  291.  
  292.   ch_hash_item stop = old_table+old_table_size;
  293.   for (ch_hash_item p=old_table; p<stop; p++)
  294.     if (p->k != NULLKEY) 
  295.     { ch_hash_item q = table + (LEDA_ACCESS(int,p->k) & table_size_1);
  296.       if (q->k == NULLKEY)
  297.         { q->k = p->k;
  298.           q->i = p->i;
  299.          }
  300.       else
  301.          q->succ = new ch_hash_elem(p->k,p->i,q->succ);
  302.     }
  303.    
  304.   count = old_count;
  305.  
  306.   //delete[] old_table;
  307.   free((char*)old_table);
  308. }
  309.  
  310.  
  311. void ch_hash::rehash(int T)
  312. { if ( int_type() ) 
  313.      int_rehash(T); 
  314.   else 
  315.      gen_rehash(T); 
  316.  }
  317.  
  318.  
  319. ch_hash::ch_hash(const ch_hash& D)
  320. { ch_hash_item p;
  321.   init(D.table_size);
  322.   for (int i=0; i<table_size; i++)
  323.   { p = D.table[i].succ;
  324.     while(p != &(D.STOP))
  325.     { insert(p->k,p->i);
  326.       D.copy_key(p->k);
  327.       D.copy_inf(p->i);
  328.       p = p->succ;
  329.     }
  330.   }
  331. }
  332.  
  333.  
  334. ch_hash& ch_hash::operator=(const ch_hash& D)
  335. { ch_hash_item p;
  336.   clear();
  337.   for (int i=0; i<D.table_size; i++)
  338.   { p = D.table[i].succ;
  339.     while(p != &(D.STOP))
  340.     { insert(p->k,p->i);
  341.       p = p->succ;
  342.      }
  343.    }
  344.   return *this;
  345. }
  346.  
  347.