00001 #ifndef _GHashTbl_H_
00002 #define _GHashTbl_H_
00003
00004 #include <ctype.h>
00005 #include "GArray.h"
00006 #include "GString.h"
00007
00008 template<typename CHAR>
00009 uint LgiHash(CHAR *v, int l, bool Case)
00010 {
00011 uint32 h = 0;
00012
00013 if (Case)
00014 {
00015
00016 if (l > 0)
00017 {
00018 while (l--)
00019 {
00020 h = (h << 5) - h + *v++;
00021 }
00022 }
00023 else
00024 {
00025 for (; *v; v ++)
00026 {
00027 h = (h << 5) - h + *v;
00028 }
00029 }
00030 }
00031 else
00032 {
00033
00034 CHAR c;
00035 if (l > 0)
00036 {
00037 while (l--)
00038 {
00039 c = tolower(*v);
00040 v++;
00041 h = (h << 5) - h + c;
00042 }
00043 }
00044 else
00045 {
00046 for (; *v; v++)
00047 {
00048 c = tolower(*v);
00049 h = (h << 5) - h + c;
00050 }
00051 }
00052 }
00053
00054 return h;
00055 }
00056
00057 #define HASH_TABLE_SHRINK_THRESHOLD 15
00058 #define HASH_TABLE_GROW_THRESHOLD 50
00059
00061 template<typename Key, typename Value>
00062 class GHashTbl
00063 {
00064 Key NullKey;
00065 Value NullValue;
00066
00067 template<typename T>
00068 struct KeyPool
00069 {
00070 int Size;
00071 int Used;
00072 char *Mem;
00073
00074 KeyPool()
00075 {
00076 Size = 64 << 10;
00077 Used = 0;
00078 Mem = new char[Size];
00079 }
00080
00081 ~KeyPool()
00082 {
00083 DeleteArray(Mem);
00084 }
00085
00086 int New(int i)
00087 {
00088 return i;
00089 }
00090
00091 void *New(void *i)
00092 {
00093 return i;
00094 }
00095
00096 char *New(char *s)
00097 {
00098 int Len = strlen(s) + 1;
00099 if (Used < Size - Len)
00100 {
00101 char *p = Mem + Used;
00102 strcpy(p, s);
00103 Used += Len;
00104 return p;
00105 }
00106 return 0;
00107 }
00108
00109 char *New(const char *s)
00110 {
00111 int Len = strlen(s) + 1;
00112 if (Used < Size - Len)
00113 {
00114 char *p = Mem + Used;
00115 strcpy(p, s);
00116 Used += Len;
00117 return p;
00118 }
00119 return 0;
00120 }
00121
00122 char16 *New(char16 *s)
00123 {
00124 int Len = StrlenW(s) + sizeof(char16);
00125 if (Used < Size - Len)
00126 {
00127 char16 *p = (char16*) (Mem + Used);
00128 StrcpyW(p, s);
00129 Used += Len;
00130 return p;
00131 }
00132 return 0;
00133 }
00134 };
00135
00136 struct Entry
00137 {
00138 Key k;
00139 Value v;
00140 };
00141
00142 int Size;
00143 int Cur;
00144 int Used;
00145 bool Case;
00146 Entry *Table;
00147 int SizeBackup;
00148
00149 bool Pool;
00150
00151 typedef GArray<KeyPool<Key>*> KeyPoolArr;
00152 KeyPoolArr Pools;
00153
00154 int Percent()
00155 {
00156 return Used * 100 / Size;
00157 }
00158
00159 bool GetEntry(Key k, int &Index, bool Debug = false)
00160 {
00161 if (k != NullKey && Table)
00162 {
00163 uint32 h = Hash(k);
00164
00165 for (int i=0; i<Size; i++)
00166 {
00167 Index = (h + i) % Size;
00168 LgiAssert(Index >= 0);
00169
00170 if (Table[Index].k == NullKey)
00171 return false;
00172
00173 if (CmpKey(Table[Index].k, k))
00174 return true;
00175 }
00176 }
00177
00178 return false;
00179 }
00180
00181 bool Between(int Val, int Min, int Max)
00182 {
00183 if (Min <= Max)
00184 {
00185
00186 return Val >= Min AND Val <= Max;
00187 }
00188 else
00189 {
00190
00191 return Val <= Max OR Val >= Min;
00192 }
00193 }
00194
00195
00196
00197
00198 uint Hash(char *s) { return LgiHash<uchar>((uchar*)s, 0, Case); }
00199 char *CopyKey(char *a) { return NewStr(a); }
00200 int SizeKey(char *a) { return strlen(a) + 1; }
00201 void FreeKey(char *&a) { DeleteArray(a); }
00202 bool CmpKey(char *a, char *b)
00203 {
00204 if (Case)
00205 return strcmp(a, b) == 0;
00206 else
00207 #ifdef WIN32
00208 return stricmp(a, b) == 0;
00209 #else
00210 return strcasecmp(a, b) == 0;
00211 #endif
00212 }
00213
00214
00215 uint Hash(const char *s) { return LgiHash<uchar>((uchar*)s, 0, Case); }
00216 char *CopyKey(const char *a) { return NewStr(a); }
00217 int SizeKey(const char *a) { return strlen(a) + 1; }
00218 void FreeKey(const char *&a) { DeleteArray((char*&)a); }
00219 bool CmpKey(const char *a, const char *b)
00220 {
00221 if (Case)
00222 return strcmp(a, b) == 0;
00223 else
00224 #ifdef WIN32
00225 return stricmp(a, b) == 0;
00226 #else
00227 return strcasecmp(a, b) == 0;
00228 #endif
00229 }
00230
00231
00232 uint Hash(char16 *s) { return LgiHash<char16>(s, 0, Case); }
00233 char16 *CopyKey(char16 *a) { return NewStrW(a); }
00234 int SizeKey(char16 *a) { return StrlenW(a) + 1; }
00235 void FreeKey(char16 *&a) { DeleteArray(a); }
00236 bool CmpKey(char16 *a, char16 *b)
00237 {
00238 if (Case)
00239 return StrcmpW(a, b) == 0;
00240 else
00241 return StricmpW(a, b) == 0;
00242 }
00243
00244
00245 uint Hash(int s) { return s; }
00246 int CopyKey(int a) { return a; }
00247 int SizeKey(int a) { return sizeof(a); }
00248 void FreeKey(int &a) { memcpy(&a, &NullKey, sizeof(a)); }
00249 bool CmpKey(int a, int b)
00250 {
00251 return a == b;
00252 }
00253
00254
00255 uint Hash(int64 s) { return s; }
00256 int CopyKey(int64 a) { return a; }
00257 int SizeKey(int64 a) { return sizeof(a); }
00258 void FreeKey(int64 &a) { memcpy(&a, &NullKey, sizeof(a)); }
00259 bool CmpKey(int64 a, int64 b)
00260 {
00261 return a == b;
00262 }
00263
00264
00265 uint Hash(void *s) { return ((uint)s)/31; }
00266 void *CopyKey(void *a) { return a; }
00267 int SizeKey(void *a) { return sizeof(a); }
00268 void FreeKey(void *&a) { memcpy(&a, &NullKey, sizeof(a)); }
00269 bool CmpKey(void *a, void *b)
00270 {
00271 return a == b;
00272 }
00273
00274 void InitializeTable(Entry *e, int len)
00275 {
00276 if (!e || len < 1) return;
00277 while (len--)
00278 {
00279 e->k = NullKey;
00280 e->v = NullValue;
00281 e++;
00282 }
00283 }
00284
00285 public:
00287 GHashTbl
00288 (
00290 int size = 0,
00292 bool is_case = true,
00294 Key nullkey = 0,
00296 Value nullvalue = (Value)0
00297 )
00298 {
00299 NullKey = nullkey;
00300 NullValue = nullvalue;
00301 Used = 0;
00302 Cur = -1;
00303 Case = is_case;
00304 Pool = false;
00305 SizeBackup = Size = size ? max(size, 16) : 512;
00306 LgiAssert(Size < 10000);
00307
00308 if (Table = new Entry[Size])
00309 {
00310 InitializeTable(Table, Size);
00311 }
00312 }
00313
00315 virtual ~GHashTbl()
00316 {
00317 Empty();
00318 DeleteArray(Table);
00319 }
00320
00322 GHashTbl<Key, Value> &operator =(GHashTbl<Key, Value> &c)
00323 {
00324 if (IsOk() && c.IsOk())
00325 {
00326 Empty();
00327
00328 NullKey = c.NullKey;
00329 NullValue = c.NullValue;
00330 Case = c.Case;
00331 Pool = c.Pool;
00332
00333 int Added = 0;
00334 for (int i=0; i<c.Size; i++)
00335 {
00336 if (c.Table[i].k != c.NullKey)
00337 {
00338 Added += Add(c.Table[i].k, c.Table[i].v) ? 1 : 0;
00339 LgiAssert(Added <= c.Used);
00340 }
00341 }
00342 }
00343 return *this;
00344 }
00345
00347 int64 GetSize()
00348 {
00349 return IsOk() ? Size : 0;
00350 }
00351
00353 bool SetSize(int64 s)
00354 {
00355 bool Status = false;
00356
00357 if (!IsOk())
00358 return false;
00359
00360 int OldSize = Size;
00361 int NewSize = max((int)s, Used * 10 / 7);
00362 if (NewSize != Size)
00363 {
00364 Entry *OldTable = Table;
00365
00366 Used = 0;
00367
00368 SizeBackup = Size = NewSize;
00369
00370 Table = new Entry[Size];
00371 if (Table)
00372 {
00373 KeyPoolArr OldPools;
00374 OldPools = Pools;
00375 Pools.Length(0);
00376
00377 int i;
00378 InitializeTable(Table, Size);
00379 for (i=0; i<OldSize; i++)
00380 {
00381 if (OldTable[i].k != NullKey)
00382 {
00383 if (!Add(OldTable[i].k, OldTable[i].v))
00384 {
00385 LgiAssert(0);
00386 }
00387 if (!Pool)
00388 FreeKey(OldTable[i].k);
00389 }
00390 }
00391
00392 OldPools.DeleteObjects();
00393 Status = true;
00394 }
00395 else
00396 {
00397 LgiAssert(Table);
00398 Table = OldTable;
00399 SizeBackup = Size = OldSize;
00400 return false;
00401 }
00402
00403 DeleteArray(OldTable);
00404 }
00405
00406 return Status;
00407 }
00408
00410 bool GetStringPool()
00411 {
00412 return IsOk() ? Pool : false;
00413 }
00414
00420 void SetStringPool(bool b)
00421 {
00422 if (IsOk())
00423 Pool = b;
00424 }
00425
00427 bool IsCase()
00428 {
00429 return IsOk() ? Case : false;
00430 }
00431
00433 void IsCase(bool c)
00434 {
00435 if (IsOk())
00436 Case = c;
00437 }
00438
00440 bool IsOk()
00441 {
00442 bool Status = this != 0 &&
00443 Table != 0;
00444 if (!Status)
00445 {
00446 LgiStackTrace("%s:%i - this=%p Table=%p Used=%i Size=%i\n", _FL, this, Table, Used, Size);
00447 }
00448 LgiAssert(Status);
00449 return Status;
00450 }
00451
00453 int Length()
00454 {
00455 return IsOk() ? Used : 0;
00456 }
00457
00459 bool Add
00460 (
00462 Key k,
00464 Value v
00465 )
00466 {
00467 if (IsOk() &&
00468 k != NullKey &&
00469 v != NullValue)
00470 {
00471 uint32 h = Hash(k);
00472
00473 int Index = -1;
00474 for (int i=0; i<Size; i++)
00475 {
00476 int idx = (h + i) % Size;
00477 if
00478 (
00479 Table[idx].k == NullKey
00480 ||
00481 CmpKey(Table[idx].k, k)
00482 )
00483 {
00484 Index = idx;
00485 break;
00486 }
00487 }
00488
00489 if (Index >= 0)
00490 {
00491 if (Table[Index].k == NullKey)
00492 {
00493 if (Pool)
00494 {
00495 KeyPool<Key> *p = 0;
00496 if (Pools.Length() == 0)
00497 {
00498 Pools[0] = p = new KeyPool<Key>;
00499 }
00500 else
00501 {
00502 p = Pools[Pools.Length()-1];
00503 }
00504
00505 if (!(Table[Index].k = p->New(k)))
00506 {
00507 Pools.Add(p = new KeyPool<Key>);
00508 Table[Index].k = p->New(k);
00509 }
00510 }
00511 else
00512 {
00513 Table[Index].k = CopyKey(k);
00514 }
00515 Used++;
00516 }
00517 Table[Index].v = v;
00518
00519 if (Percent() > HASH_TABLE_GROW_THRESHOLD)
00520 {
00521 SetSize(Size << 1);
00522 }
00523 return true;
00524 }
00525 }
00526
00527 return false;
00528 }
00529
00531 bool Delete
00532 (
00534 Key k
00535 )
00536 {
00537 int Index = -1;
00538 if (GetEntry(k, Index))
00539 {
00540
00541 if (Pool)
00542 {
00543
00544 Table[Index].k = NullKey;
00545 }
00546 else
00547 {
00548 FreeKey(Table[Index].k);
00549 }
00550 Table[Index].v = NullValue;
00551 Used--;
00552
00553
00554 int Hole = Index;
00555 for (int i = (Index + 1) % Size; i != Index; i = (i + 1) % Size)
00556 {
00557 if (Table[i].k != NullKey)
00558 {
00559 uint32 Hsh = Hash(Table[i].k);
00560 uint32 HashIndex = Hsh % Size;
00561
00562 if (HashIndex != i AND Between(Hole, HashIndex, i))
00563 {
00564
00565 if (Table[Hole].k != NullKey)
00566 {
00567 LgiAssert(0);
00568 }
00569 memmove(Table + Hole, Table + i, sizeof(Table[i]));
00570 InitializeTable(Table + i, 1);
00571 Hole = i;
00572 }
00573 }
00574 else
00575 {
00576
00577 break;
00578 }
00579 }
00580
00581
00582 if (Percent() < HASH_TABLE_SHRINK_THRESHOLD)
00583 {
00584 SetSize(Size >> 1);
00585 }
00586
00587 return true;
00588 }
00589 else
00590 {
00591 GetEntry(k, Index, true);
00592 }
00593
00594 return false;
00595 }
00596
00598 Value Find(Key k)
00599 {
00600 int Index = -1;
00601 if (IsOk() && GetEntry(k, Index))
00602 {
00603 return Table[Index].v;
00604 }
00605
00606 return NullValue;
00607 }
00608
00610 Value First(Key *k = 0)
00611 {
00612 Cur = 0;
00613 if (IsOk())
00614 {
00615 while (Cur < Size)
00616 {
00617 if (Table[Cur].k != NullKey)
00618 {
00619 if (k)
00620 {
00621 *k = Table[Cur].k;
00622 }
00623 return Table[Cur].v;
00624 }
00625 else Cur++;
00626 }
00627 }
00628
00629 return NullValue;
00630 }
00631
00633 Value Current(Key *k = 0)
00634 {
00635 if (Cur >= 0 &&
00636 Cur < Size &&
00637 Table &&
00638 Table[Cur].k != NullKey)
00639 {
00640 if (k)
00641 {
00642 *k = Table[Cur].k;
00643 }
00644 return Table[Cur].v;
00645 }
00646
00647 return NullValue;
00648 }
00649
00651 Value Next(Key *k = 0)
00652 {
00653 if (IsOk() && Cur >= 0)
00654 {
00655 while (++Cur < Size)
00656 {
00657 if (Table[Cur].k != NullKey)
00658 {
00659 if (k)
00660 {
00661 *k = Table[Cur].k;
00662 }
00663 return Table[Cur].v;
00664 }
00665 }
00666 }
00667
00668 return NullValue;
00669 }
00670
00672 void Empty()
00673 {
00674 if (!IsOk())
00675 return;
00676
00677 if (Pool)
00678 {
00679 Pools.DeleteObjects();
00680
00681 for (int i=0; i<Size; i++)
00682 {
00683 Table[i].k = NullKey;
00684 Table[i].v = NullValue;
00685 }
00686 }
00687 else
00688 {
00689 for (int i=0; i<Size; i++)
00690 {
00691 if (Table[i].k != NullKey)
00692 {
00693 FreeKey(Table[i].k);
00694 LgiAssert(Table[i].k == NullKey);
00695 }
00696 Table[i].v = NullValue;
00697 }
00698 }
00699
00700 Used = 0;
00701 SetSize(512);
00702 }
00703
00705 int64 Sizeof()
00706 {
00707 int64 Sz = sizeof(*this);
00708 char s[64];
00709
00710 Sz += Sz * sizeof(Entry);
00711
00712
00713
00714
00715 int Keys = 0;
00716 int64 KeySize = 0;
00717 if (Pool)
00718 {
00719 for (int i=0; i<Pools.Length(); i++)
00720 {
00721 KeyPool<Key> *p = Pools[i];
00722 KeySize += sizeof(*p) + p->Size;
00723 }
00724 }
00725 else
00726 {
00727 for (int i=0; i<Size; i++)
00728 {
00729 if (Table[i].k != NullKey)
00730 {
00731 Keys++;
00732 KeySize += SizeKey(Table[i].k);
00733 }
00734 }
00735 }
00736
00737
00738
00739
00740 return Sz + KeySize;
00741 }
00742
00744 void DeleteObjects()
00745 {
00746 for (int i=0; i<Size; i++)
00747 {
00748 if (Table[i].k != NullKey)
00749 FreeKey(Table[i].k);
00750
00751 if (Table[i].v != NullValue)
00752 DeleteObj(Table[i].v);
00753 }
00754
00755 Used = 0;
00756 }
00757
00759 void DeleteArrays()
00760 {
00761 for (int i=0; i<Size; i++)
00762 {
00763 if (Table[i].k != NullKey)
00764 FreeKey(Table[i].k);
00765
00766 if (Table[i].v != NullValue)
00767 DeleteArray(Table[i].v);
00768 }
00769
00770 Used = 0;
00771 }
00772 };
00773
00774 class LgiClass GHashTable : public GHashTbl<char*, void*>
00775 {
00776 public:
00777 GHashTable(int Size = 0, bool Case = true)
00778 : GHashTbl<char*, void*>(Size, Case)
00779 {
00780 }
00781
00782 bool Add(char *k, void *v = (void*)1)
00783 {
00784 return GHashTbl<char*, void*>::Add(k, v);
00785 }
00786
00787 };
00788
00789 #endif