1 // Copyright (C) 1999,2000 Bruce Guenter <bruceg@em.ca>

     2 //

     3 // This program is free software; you can redistribute it and/or modify

     4 // it under the terms of the GNU General Public License as published by

     5 // the Free Software Foundation; either version 2 of the License, or

     6 // (at your option) any later version.

     7 //

     8 // This program is distributed in the hope that it will be useful,

     9 // but WITHOUT ANY WARRANTY; without even the implied warranty of

    10 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

    11 // GNU General Public License for more details.

    12 //

    13 // You should have received a copy of the GNU General Public License

    14 // along with this program; if not, write to the Free Software

    15 // Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

    16 

    17 #ifndef HASH_TABLE__H__

    18 #define HASH_TABLE__H__

    19 

    20 #include "mystring/mystring.h"

    21 

    22 struct hash_base

    23 {

    24   const mystring key;

    25   const unsigned hash;

    26   hash_base(const mystring& k, unsigned h)

    27     : key(k), hash(h)

    28     {

    29     }

    30 };

    31 

    32 template<class T>

    33 struct hash_node : public hash_base

    34 {

    35   T data;

    36   hash_node(const mystring& k, unsigned h, T d)

    37     : hash_base(k, h), data(d)

    38     {

    39     }

    40 };

    41 

    42 template<class T>

    43 struct hash_ptr_node : public hash_base

    44 {

    45   T* data;

    46   hash_ptr_node(const mystring& k, unsigned h, T* d)

    47     : hash_base(k, h), data(d)

    48     {

    49     }

    50   ~hash_ptr_node()

    51     {

    52       if(data)

    53 	delete data;

    54     }

    55 };

    56 

    57 static const unsigned hash_prime_list[] = {

    58   53,         97,         193,       389,       769,

    59   1543,       3079,       6151,      12289,     24593,

    60   49157,      98317,      196613,    393241,    786433,

    61   1572869,    3145739,    6291469,   12582917,  25165843,

    62   50331653,   100663319,  201326611, 402653189, 805306457,

    63   1610612741, 3221225473U, 4294967291U

    64 };

    65   

    66 template<class TYPE, class NODE, class HASH>

    67 class hash_table_iterator;

    68 

    69 template<class TYPE, class NODE, class HASH>

    70 class hash_table

    71 {

    72   friend class hash_table_iterator<TYPE,NODE,HASH>;

    73   

    74   TYPE dummy;

    75   HASH hash;

    76   NODE** table;

    77   unsigned prime_index;

    78   unsigned prime;

    79   unsigned oversize;

    80   unsigned _count;

    81 

    82   unsigned rehash(unsigned h) const

    83     {

    84       return (h + 1) % prime;

    85     }

    86   

    87   void alloc()

    88     {

    89       prime = hash_prime_list[prime_index];

    90       oversize = prime*3/4;

    91       table = new NODE*[prime];

    92       for(unsigned i = 0; i < prime; i++)

    93 	table[i] = 0;

    94       _count = 0;

    95     }

    96 

    97   void realloc(unsigned new_index)

    98     {

    99       //unsigned old_prime_index = prime_index;

   100       unsigned old_prime = prime;

   101       NODE** old_table = table;

   102       prime_index = new_index;

   103       alloc();

   104       for(unsigned i = 0; i < old_prime; i++)

   105 	if(old_table[i])

   106 	  base_insert(old_table[i], true);

   107     }

   108 

   109   unsigned lookup(const mystring& key, unsigned hash) const

   110     {

   111       for(unsigned h = hash % prime; table[h]; h = rehash(h))

   112 	if(table[h]->hash == hash && table[h]->key == key)

   113 	  return h;

   114       return prime;

   115     }

   116 

   117   unsigned lookup(const mystring& key) const

   118     {

   119       return lookup(key, hash(key));

   120     }

   121 

   122   bool base_insert(NODE* e, bool unique)

   123     {

   124       unsigned h;

   125       for(h = e->hash % prime; table[h]; h = rehash(h)) {

   126 	if(table[h]->hash == e->hash &&

   127 	   table[h]->key == e->key) {

   128 	  if(unique)

   129 	    return false;

   130 	  else {

   131 	    delete table[h];

   132 	    --_count;

   133 	    break;

   134 	  }

   135 	}

   136       }

   137       table[h] = e;

   138       ++_count;

   139       return true;

   140     }

   141       

   142 public:

   143   typedef hash_table_iterator<TYPE,NODE,HASH> iterator;

   144   

   145   hash_table()

   146     : dummy(0), prime_index(0)

   147     {

   148       alloc();

   149     }

   150   

   151   ~hash_table()

   152     {

   153       if(table) {

   154 	empty();

   155 	delete[] table;

   156       }

   157     }

   158 

   159   void empty()

   160     {

   161       for(unsigned i = 0; i < prime; i++)

   162 	if(table[i]) {

   163 	  delete table[i];

   164 	  table[i] = 0;

   165 	}

   166       _count = 0;

   167     }

   168 

   169   bool exists(const mystring& key) const

   170     {

   171       return lookup(key) >= prime;

   172     }

   173 

   174   const TYPE& operator[](const mystring& key) const

   175     {

   176       unsigned h = lookup(key);

   177       return (h >= prime) ? dummy : table[h]->data;

   178     }

   179       

   180   TYPE& operator[](const mystring& key)

   181     {

   182       unsigned h = lookup(key);

   183       return (h >= prime) ? dummy : table[h]->data;

   184     }

   185       

   186   unsigned count() const 

   187     {

   188       return _count;

   189     }

   190   

   191   bool insert(const mystring& key, TYPE data)

   192     {

   193       NODE* e = new NODE(key, hash(key), data);

   194       if(_count >= oversize)

   195 	realloc(prime_index+1);

   196       return base_insert(e, true);

   197     }

   198   

   199   bool set(const mystring& key, TYPE data)

   200     {

   201       NODE* e = new NODE(key, hash(key), data);

   202       if(_count >= oversize)

   203 	realloc(prime_index+1);

   204       return base_insert(e, false);

   205     }

   206 

   207   bool remove(const mystring& key, bool mustexist = false)

   208     {

   209       unsigned h = lookup(key);

   210       if(h < prime) {

   211 	delete table[h];

   212 	table[h] = 0;

   213 	--_count;

   214 	return true;

   215       }

   216       else

   217 	return !mustexist;

   218     }

   219 };

   220 

   221 // hash table iterator

   222 // usage: for(var.iterator i = var; !i; i++) use(*i);

   223 template<class TYPE, class NODE, class HASH>

   224 class hash_table_iterator

   225 {

   226   hash_table<TYPE,NODE,HASH>& table;

   227   unsigned index;

   228   void next()

   229     {

   230       while(index < table.prime && !table.table[index])

   231 	++index;

   232     }

   233 public:

   234   hash_table_iterator(hash_table<TYPE,NODE,HASH>& t) : table(t), index(0)

   235     {

   236       next();

   237     }

   238   bool operator!() const

   239     {

   240       return index < table.prime;

   241     }

   242   bool at_end() const

   243     {

   244       return index >= table.prime;

   245     }

   246   void operator++() 

   247     {

   248       ++index;

   249       next();

   250     }

   251   TYPE& operator*()

   252     {

   253       return table.table[index]->data;

   254     }

   255   const TYPE& operator*() const

   256     {

   257       return table.table[index]->data;

   258     }

   259 };

   260 

   261 class hash_sample

   262 {

   263 public:

   264   unsigned operator()(const mystring& str) const

   265     {

   266       unsigned h = 0;

   267       for(unsigned i = 0; i < str.length(); i++)

   268 	h = (h << 1) ^ (unsigned)str[i];

   269       return h;

   270     }

   271 };

   272 

   273 #endif