include/server/HashTable.h

   1 /*
   2         SuperCollider real time audio synthesis system
   3     Copyright (c) 2002 James McCartney. All rights reserved.
   4         http://www.audiosynth.com
   5
   6     This program is free software; you can redistribute it and/or modify
   7     it under the terms of the GNU General Public License as published by
   8     the Free Software Foundation; either version 2 of the License, or
   9     (at your option) any later version.
  10
  11     This program is distributed in the hope that it will be useful,
  12     but WITHOUT ANY WARRANTY; without even the implied warranty of
  13     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14     GNU General Public License for more details.
  15
  16     You should have received a copy of the GNU General Public License
  17     along with this program; if not, write to the Free Software
  18     Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301  USA
  19 */
  20
  21 #ifndef _HashTable_
  22 #define _HashTable_
  23
  24 #include "SC_Types.h"
  25 #include "SC_BoundsMacros.h"
  26 #include "SC_Str4.h"
  27 #include "Hash.h"
  28 #include <stddef.h>
  29 #include <stdlib.h>
  30 #include <string.h>
  31
  32 template<class T, class Allocator>
  33 class HashTable
  34 {
  35         Allocator *mPool;
  36         int32 mNumItems, mMaxItems, mTableSize, mHashMask;
  37         T** mItems;
  38         bool mCanResize;
  39
  40 public:
  41
  42         HashTable(Allocator *inPool, int32 inMaxItems, bool inCanResize = true)
  43                 : mPool(inPool)
  44         {
  45                 mNumItems = 0;
  46                 mMaxItems = inMaxItems;
  47                 mTableSize = mMaxItems << 1;
  48                 mItems = AllocTable(mTableSize);
  49                 mHashMask = mTableSize - 1;
  50                 mCanResize = inCanResize;
  51         }
  52
  53         ~HashTable() {
  54                 mPool->Free(mItems);
  55         }
  56
  57         int32 TableSize() const { return mTableSize; }
  58         int32 MaxItems() const { return mMaxItems; }
  59         int32 NumItems() const { return mNumItems; }
  60
  61         T** AllocTable(int inTableSize)
  62         {
  63                 size_t size = inTableSize * sizeof(T*);
  64                 T** items = static_cast<T**>(mPool->Alloc(size));
  65                 for (int i=0; i<inTableSize; ++i) {
  66                         items[i] = 0;
  67                 }
  68                 return items;
  69         }
  70
  71         void MakeEmpty()
  72         {
  73                 for (int i=0; i<mTableSize; ++i) {
  74                         mItems[i] = 0;
  75                 }
  76                 mNumItems = 0;
  77         }
  78
  79         void Resize()
  80         {
  81                 int32 newSize = sc_max(mTableSize << 1, 32);
  82                 int32 oldSize = mTableSize;
  83                 T** oldItems = mItems;
  84                 mItems = AllocTable(newSize);
  85                 mTableSize = newSize;
  86                 mMaxItems = mTableSize >> 1;
  87                 mHashMask = mTableSize - 1;
  88                 mNumItems = 0;
  89                 for (int i=0; i<oldSize; ++i) {
  90                         T* item = oldItems[i];
  91                         if (item) Add(item);
  92                 }
  93                 mPool->Free(oldItems);
  94                 //printf("mMaxItems %d   mTableSize %d   newSize %d\n", mMaxItems, mTableSize, newSize);
  95         }
  96
  97         bool Add(T* inItem)
  98         {
  99                 //printf("mNumItems %d\n", mNumItems);
 100                 //printf("mMaxItems %d\n", mMaxItems);
 101                 //printf("mCanResize %d\n", mCanResize);
 102                 if (mNumItems >= mMaxItems) {
 103                         if (!mCanResize) return false;
 104                         Resize();
 105                 }
 106
 107                 //printf("GetHash(inItem) %d\n", GetHash(inItem));
 108                 //printf("GetKey(inItem) %s\n", GetKey(inItem));
 109                 int32 index = IndexFor(GetHash(inItem), (int32*)GetKey(inItem));
 110                 //printf("index %d\n", index);
 111
 112                 T *item = mItems[index];
 113                 if (item) return item == inItem;
 114
 115                 mItems[index] = inItem;
 116                 mNumItems++;
 117                 return true;
 118         }
 119
 120         bool Remove(T* inItem)
 121         {
 122                 int32 index = IndexFor(GetHash(inItem), (int32*)GetKey(inItem));
 123                 if (mItems[index] != inItem) return false;
 124                 mItems[index] = 0;
 125
 126                 FixCollisionsFrom(index);
 127                 mNumItems--;
 128                 return true;
 129         }
 130
 131         bool RemoveKey(int32* inKey)
 132         {
 133                 T* item = Get(inKey);
 134                 if (!item) return false;
 135                 return Remove(item);
 136         }
 137
 138         int32 IndexFor(int32 inHashID, int32* inKey) const
 139         {
 140                 int index = inHashID & mHashMask;
 141                 for(;;) {
 142                         T *item = mItems[index];
 143                         if (!item) return index;
 144             if (GetHash(item) == inHashID && str4eq(inKey, GetKey(item))) return index;
 145                         index = (index + 1) & mHashMask;
 146                 }
 147         }
 148
 149         T* Get(int32* inKey) const
 150         {
 151             return Get(Hash(inKey), inKey);
 152         }
 153
 154         T* Get(int32 inHashID, int32* inKey) const
 155         {
 156         //printf("Get hash %d %s\n", inHashID, inKey);
 157                 int32 index = IndexFor(inHashID, inKey);
 158                 //printf("index %d\n", index);
 159                 return mItems[index];
 160         }
 161
 162         bool Includes(T* inItem) const
 163         {
 164                 return Get(GetHash(inItem), GetKey(inItem)) == inItem;
 165         }
 166
 167         T* AtIndex(int32 inIndex) const
 168         {
 169                 return mItems[inIndex];
 170         }
 171
 172 private:
 173         void FixCollisionsFrom(int32 inIndex)
 174         {
 175                 int oldIndex = inIndex;
 176                 for (;;) {
 177                         oldIndex = (oldIndex + 1) & mHashMask;
 178                         T *oldItem = mItems[oldIndex];
 179                         if (!oldItem) break;
 180                         int newIndex = IndexFor(GetHash(oldItem), (int32*)GetKey(oldItem));
 181                         if (oldIndex != newIndex) {
 182                                 mItems[oldIndex] = mItems[newIndex];
 183                                 mItems[newIndex] = oldItem;
 184                         }
 185                 }
 186         }
 187 };
 188
 189
 190 template<class T, class Allocator>
 191 class IntHashTable
 192 {
 193         Allocator *mPool;
 194         int32 mNumItems, mMaxItems, mTableSize, mHashMask;
 195         T** mItems;
 196         bool mCanResize;
 197
 198 public:
 199
 200         IntHashTable(Allocator *inPool, int32 inMaxItems, bool inCanResize = true)
 201                 : mPool(inPool)
 202         {
 203                 mNumItems = 0;
 204                 mMaxItems = inMaxItems;
 205                 mTableSize = mMaxItems << 1;
 206                 mItems = AllocTable(mTableSize);
 207                 mHashMask = mTableSize - 1;
 208                 mCanResize = inCanResize;
 209         }
 210
 211         ~IntHashTable() {
 212                 mPool->Free(mItems);
 213         }
 214
 215         int32 TableSize() const { return mTableSize; }
 216         int32 MaxItems() const { return mMaxItems; }
 217         int32 NumItems() const { return mNumItems; }
 218
 219         T** AllocTable(int inTableSize)
 220         {
 221                 size_t size = inTableSize * sizeof(T*);
 222                 T** items = static_cast<T**>(mPool->Alloc(size));
 223                 for (int i=0; i<inTableSize; ++i) {
 224                         items[i] = 0;
 225                 }
 226                 return items;
 227         }
 228
 229         void Resize()
 230         {
 231                 int32 newSize = sc_max(mTableSize << 1, 32);
 232                 T** oldItems = mItems;
 233                 mItems = AllocTable(newSize);
 234                 for (int i=0; i<mTableSize; ++i) {
 235                         T* item = oldItems[i];
 236                         if (item) Add(item);
 237                 }
 238                 mTableSize = newSize;
 239                 mMaxItems = mTableSize >> 1;
 240                 mHashMask = mTableSize - 1;
 241                 mPool->Free(oldItems);
 242                 //printf("mMaxItems %d   mTableSize %d   newSize %d\n", mMaxItems, mTableSize, newSize);
 243         }
 244
 245         bool Add(T* inItem)
 246         {
 247                 //printf("mNumItems %d\n", mNumItems);
 248                 //printf("mMaxItems %d\n", mMaxItems);
 249                 //printf("mCanResize %d\n", mCanResize);
 250                 if (mNumItems >= mMaxItems) {
 251                         if (!mCanResize) return false;
 252                         Resize();
 253                 }
 254
 255                 //printf("GetHash(inItem) %d\n", GetHash(inItem));
 256                 //printf("GetKey(inItem) %d\n", GetKey(inItem));
 257                 int32 index = IndexFor(GetHash(inItem), GetKey(inItem));
 258                 //printf("index %d\n", index);
 259
 260                 T *item = mItems[index];
 261                 if (item) return item == inItem;
 262
 263                 mItems[index] = inItem;
 264                 mNumItems++;
 265                 return true;
 266         }
 267
 268         bool Remove(T* inItem)
 269         {
 270                 int32 index = IndexFor(GetHash(inItem), GetKey(inItem));
 271                 //printf("rmv index %d hash %d key %d\n", index, GetHash(inItem), GetKey(inItem));
 272                 if (mItems[index] != inItem) return false;
 273                 mItems[index] = 0;
 274
 275                 FixCollisionsFrom(index);
 276                 mNumItems--;
 277                 return true;
 278         }
 279
 280         bool RemoveKey(int32 inKey)
 281         {
 282                 T* item = Get(inKey);
 283                 if (!item) return false;
 284                 return Remove(item);
 285         }
 286
 287         int32 IndexFor(int32 inHashID, int32 inKey) const
 288         {
 289                 int index = inHashID & mHashMask;
 290                 for(;;) {
 291                         T *item = mItems[index];
 292                         if (!item) return index;
 293             if (GetHash(item) == inHashID && inKey == GetKey(item)) return index;
 294                         index = (index + 1) & mHashMask;
 295                 }
 296         }
 297
 298         T* Get(int32 inKey) const
 299         {
 300                 //printf("Get key %d\n", inKey);
 301             return Get(Hash(inKey), inKey);
 302         }
 303
 304         T* Get(int32 inHashID, int32 inKey) const
 305         {
 306                 int32 index = IndexFor(inHashID, inKey);
 307         //printf("Get index %d  hash %d  key %d\n", index, inHashID, inKey);
 308                 return mItems[index];
 309         }
 310
 311         bool Includes(T* inItem) const
 312         {
 313                 return Get(GetHash(inItem), GetKey(inItem)) == inItem;
 314         }
 315
 316         T* AtIndex(int32 inIndex) const
 317         {
 318                 return mItems[inIndex];
 319         }
 320
 321         void Dump()
 322         {
 323                 for (int i=0; i<mTableSize; ++i) {
 324                         T* item = mItems[i];
 325                         if (item) {
 326                                 printf("%4d %4d %08X %08X\n", i, GetKey(item), GetHash(item), item);
 327                         }
 328                 }
 329         }
 330
 331 private:
 332         void FixCollisionsFrom(int32 inIndex)
 333         {
 334                 //printf("FixCollisionsFrom %d\n", inIndex);
 335                 int oldIndex = inIndex;
 336                 for (;;) {
 337                         oldIndex = (oldIndex + 1) & mHashMask;
 338                         T *oldItem = mItems[oldIndex];
 339                         if (!oldItem) break;
 340                         int newIndex = IndexFor(GetHash(oldItem), GetKey(oldItem));
 341                         if (oldIndex != newIndex) {
 342                                 //printf("swap %d %d\n", oldIndex, newIndex);
 343                                 mItems[oldIndex] = mItems[newIndex];
 344                                 mItems[newIndex] = oldItem;
 345                         }
 346                 }
 347         }
 348 };
 349
 350 struct Malloc
 351 {
 352         void Free(void* ptr) { free(ptr); }
 353         void* Alloc(size_t size) { return malloc(size); }
 354 };
 355
 356 #endif