00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019 #ifndef __CS_UTIL_HASH_H__
00020 #define __CS_UTIL_HASH_H__
00021
00022 #include <csutil/array.h>
00023
00030 uint32 csHashCompute (char const*);
00031
00038 uint32 csHashCompute (char const*, int length);
00039
00040 template <class T>
00041 class csIntegralHashKeyHandler
00042 {
00043 public:
00044 static uint32 ComputeHash (const T& key)
00045 {
00046 return (uint32)key;
00047 }
00048
00049 static bool CompareKeys (const T& key1, const T& key2)
00050 {
00051 return (key1 == key2);
00052 }
00053 };
00054
00059 template <class T, class K = uint32,
00060 class KeyHandler = csIntegralHashKeyHandler<K> >
00061 class csHash
00062 {
00063 protected:
00064 struct Element
00065 {
00066 const K key;
00067 T value;
00068
00069 Element (const K& key0, const T &value0) : key (key0), value (value0) {}
00070 Element (const Element &other) : key (other.key), value (other.value) {}
00071 };
00072 csArray< csArray<Element> > Elements;
00073
00074 int Modulo;
00075
00076 private:
00077 int InitModulo;
00078 int GrowRate;
00079 int MaxSize;
00080 int Size;
00081
00082 void Grow ()
00083 {
00084 static const int Primes[] =
00085 {
00086 53, 97, 193, 389, 769,
00087 1543, 3079, 6151, 12289, 24593,
00088 49157, 98317, 196613, 393241, 786433,
00089 1572869, 3145739, 6291469, 12582917, 25165843,
00090 50331653, 100663319, 201326611, 402653189, 805306457,
00091 1610612741, 0
00092 };
00093
00094 const int *p;
00095 for (p = Primes; *p && *p <= Elements.Length (); p++) ;
00096 Modulo = *p;
00097 CS_ASSERT (Modulo);
00098
00099 int elen = Elements.Length ();
00100 Elements.SetLength (Modulo, csArray<Element> (1, 7));
00101
00102 for (int i = 0; i < elen; i++)
00103 {
00104 csArray<Element>& src = Elements[i];
00105 int slen = src.Length ();
00106 for (int j = slen - 1; j >= 0; j--)
00107 {
00108 const Element& srcElem = src[j];
00109 csArray<Element>& dst =
00110 Elements.Get (KeyHandler::ComputeHash (srcElem.key) % Modulo);
00111 if (&src != &dst)
00112 {
00113 dst.Push (srcElem);
00114 src.DeleteIndex (j);
00115 }
00116 }
00117 }
00118 }
00119
00120 public:
00134 csHash (int size = 257, int grow_rate = 64, int max_size = 20000)
00135 : Elements (size), Modulo (size), InitModulo (size),
00136 GrowRate (grow_rate), MaxSize (max_size), Size (0)
00137 {
00138 Elements.SetLength (size, csArray<Element> (1, 7));
00139 }
00140
00142 csHash (const csHash<T> &o) : Elements (o.Elements),
00143 Modulo (o.Modulo), InitModulo (o.InitModulo),
00144 GrowRate (o.GrowRate), MaxSize (o.MaxSize), Size (o.Size) {}
00145
00147 void Put (const K& key, const T &value)
00148 {
00149 csArray<Element> &values =
00150 Elements[KeyHandler::ComputeHash (key) % Modulo];
00151 values.Push (Element (key, value));
00152 Size++;
00153 if (values.Length () > Elements.Length () / GrowRate
00154 && Elements.Length () < MaxSize) Grow ();
00155 }
00156
00158 csArray<T> GetAll (uint32 key) const
00159 {
00160 const csArray<Element> &values =
00161 Elements[KeyHandler::ComputeHash (key) % Modulo];
00162 csArray<T> ret (values.Length () / 2);
00163 for (int i = values.Length () - 1; i >= 0; i--)
00164 if (KeyHandler::CompareKeys (values[i].key, key))
00165 ret.Push (values[i].value);
00166 return ret;
00167 }
00168
00170 void PutFirst (const K& key, const T &value)
00171 {
00172 csArray<Element> &values =
00173 Elements[KeyHandler::ComputeHash (key) % Modulo];
00174 for (int i = values.Length () - 1; i >= 0; i--)
00175 if (KeyHandler::CompareKeys (values[i].key, key))
00176 {
00177 values[i].value = value;
00178 return;
00179 }
00180
00181 values.Push (Element (key, value));
00182 Size++;
00183 if (values.Length () > Elements.Length () / GrowRate
00184 && Elements.Length () < MaxSize) Grow ();
00185 }
00186
00188 const T& Get (const K& key) const
00189 {
00190 const csArray<Element> &values =
00191 Elements[KeyHandler::ComputeHash (key) % Modulo];
00192 for (int i = values.Length () - 1; i >= 0; i--)
00193 if (KeyHandler::CompareKeys (values[i].key, key))
00194 return values[i].value;
00195
00196 static const T zero (0);
00197 return zero;
00198 }
00199
00201 bool DeleteAll ()
00202 {
00203 bool ret = false;
00204 int elen = Elements.Length ();
00205 Elements.SetLength (Modulo = InitModulo);
00206 for (int i = 0; i < elen; i++)
00207 {
00208 if (Elements[i].Length ()) ret = true;
00209 Elements[i].Empty ();
00210 }
00211 Size = 0;
00212 return ret;
00213 }
00214
00216 bool DeleteAll (const K& key)
00217 {
00218 bool ret = false;
00219 csArray<Element> &values =
00220 Elements[KeyHandler::ComputeHash (key) % Modulo];
00221 for (int i = values.Length () - 1; i >= 0; i--)
00222 if (KeyHandler::CompareKeys (values[i].key, key))
00223 {
00224 values.DeleteIndex (i);
00225 ret = true;
00226 Size--;
00227 }
00228 return ret;
00229 }
00230
00232 bool Delete (const K& key, const T &value)
00233 {
00234 bool ret = false;
00235 csArray<Element> &values =
00236 Elements[KeyHandler::ComputeHash (key) % Modulo];
00237 for (int i = values.Length () - 1; i >= 0; i--)
00238 if (KeyHandler::CompareKeys (values[i].key, key) &&
00239 (values[i].value == value))
00240 {
00241 values.DeleteIndex (i);
00242 ret = true;
00243 Size--;
00244 }
00245 return ret;
00246 }
00247
00249 int GetSize () const
00250 {
00251 return Size;
00252 }
00253
00255 class Iterator
00256 {
00257 private:
00258 const csHash<T, K, KeyHandler>* hash;
00259 const K key;
00260 int bucket, size, element;
00261
00262 void Seek ()
00263 {
00264 while ((element < size) &&
00265 ! KeyHandler::CompareKeys (hash->Elements[bucket][element].key, key))
00266 element++;
00267 }
00268
00269 protected:
00270 Iterator (const csHash<T, K, KeyHandler>* hash0, const K& key0)
00271 : hash (hash0), key (key0),
00272 bucket (KeyHandler::ComputeHash (key) % hash->Modulo),
00273 size (hash->Elements[bucket].Length ()) { Return (); }
00274
00275 friend class csHash<T, K, KeyHandler>;
00276 public:
00277 Iterator (const Iterator &o)
00278 : hash (o.hash), bucket (o.bucket), size (o.size), element (o.element) {}
00279
00281 bool HasNext () const
00282 {
00283 return element < size;
00284 }
00285
00287 const T& Next ()
00288 {
00289 const T &ret = hash->Elements[bucket][element].value;
00290 element++;
00291 Seek ();
00292 return ret;
00293 }
00294
00296 void DeleteNext ()
00297 {
00298 hash->Elements[bucket].DeleteIndex (element);
00299 }
00300
00302 void Return () { element = 0; Seek (); }
00303 };
00304 friend class csHash<T, K, KeyHandler>::Iterator;
00305
00307 class GlobalIterator
00308 {
00309 private:
00310 const csHash<T, K, KeyHandler> *hash;
00311 int bucket, size, element;
00312
00313 void Zero () { bucket = element = 0; }
00314 void Init () { size = hash->Elements[bucket].Length (); }
00315
00316 void FindItem ()
00317 {
00318 if (element >= size)
00319 {
00320 while (++bucket < hash->Elements.Length ())
00321 {
00322 Init ();
00323 if (size != 0)
00324 {
00325 element = 0;
00326 break;
00327 }
00328 }
00329 }
00330 }
00331
00332 protected:
00333 GlobalIterator (const csHash<T, K, KeyHandler> *hash0) : hash (hash0)
00334 {
00335 Zero ();
00336 Init ();
00337 FindItem ();
00338 }
00339
00340 friend class csHash<T, K, KeyHandler>;
00341 public:
00342 GlobalIterator (const Iterator &o) : hash (o.hash), bucket (o.bucket),
00343 size (o.size), element (o.element) {}
00344
00346 bool HasNext () const
00347 {
00348 if (hash->Elements.Length () == 0) return false;
00349 return element < size || bucket < hash->Elements.Length ();
00350 }
00351
00353 const T& Next ()
00354 {
00355 const T &ret = hash->Elements[bucket][element].value;
00356 element++;
00357 FindItem ();
00358 return ret;
00359 }
00360
00362 const T& Next (K &key)
00363 {
00364 key = hash->Elements[bucket][element].key;
00365 return Next ();
00366 }
00367
00369 void DeleteNext ()
00370 {
00371 hash->Elements[bucket].DeleteIndex (element);
00372 }
00373
00375 void Return () { Zero (); Init (); }
00376 };
00377 friend class csHash<T, K, KeyHandler>::GlobalIterator;
00378
00385 Iterator GetIterator (const K& key) const
00386 {
00387 return Iterator (this, key);
00388 }
00389
00395 GlobalIterator GetIterator () const
00396 {
00397 return GlobalIterator (this);
00398 }
00399 };
00400
00401 #endif