include/lang/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 "Hash.h"
  27 #include <stddef.h>
  28
  29 template<class T, class Allocator, class KeyType>
  30 class HashTable
  31 {
  32         Allocator *mPool;
  33         int32 mNumItems, mMaxItems, mTableSize, mHashMask;
  34         T** mItems;
  35         bool mCanResize;
  36
  37 public:
  38
  39         HashTable(Allocator *inPool, int32 inMaxItems, bool inCanResize = true)
  40                 : mPool(inPool)
  41         {
  42                 mNumItems = 0;
  43                 mMaxItems = inMaxItems;
  44                 mTableSize = mMaxItems << 1;
  45                 mItems = AllocTable(mTableSize);
  46                 mHashMask = mTableSize - 1;
  47                 mCanResize = inCanResize;
  48         }
  49
  50         ~HashTable() {
  51                 mPool->Free(mItems);
  52         }
  53
  54         int32 TableSize() const { return mTableSize; }
  55         int32 MaxItems() const { return mMaxItems; }
  56         int32 NumItems() const { return mNumItems; }
  57
  58         T** AllocTable(int inTableSize)
  59         {
  60                 size_t size = inTableSize * sizeof(T*);
  61                 T** items = static_cast<T**>(mPool->Alloc(size));
  62                 for (int i=0; i<inTableSize; ++i) {
  63                         items[i] = 0;
  64                 }
  65                 return items;
  66         }
  67
  68         void Resize()
  69         {
  70                 int32 newSize = sc_max(mTableSize << 1, 32);
  71                 T** oldItems = mItems;
  72                 mItems = AllocTable(newSize);
  73                 for (int i=0; i<mTableSize; ++i) {
  74                         T* item = oldItems[i];
  75                         if (item) Add(item);
  76                 }
  77                 mTableSize = newSize;
  78                 mMaxItems = mTableSize >> 1;
  79                 mHashMask = mTableSize - 1;
  80                 mPool->Free(oldItems);
  81                 //printf("mMaxItems %d   mTableSize %d   newSize %d\n", mMaxItems, mTableSize, newSize);
  82         }
  83
  84         bool Add(T* inItem)
  85         {
  86                 //printf("mNumItems %d\n", mNumItems);
  87                 //printf("mMaxItems %d\n", mMaxItems);
  88                 //printf("mCanResize %d\n", mCanResize);
  89                 if (mNumItems >= mMaxItems) {
  90                         if (!mCanResize) return false;
  91                         Resize();
  92                 }
  93
  94                 //printf("GetHash(inItem) %d\n", GetHash(inItem));
  95                 //printf("GetKey(inItem) %s\n", GetKey(inItem));
  96                 int32 index = IndexFor(GetHash(inItem), GetKey(inItem));
  97                 //printf("index %d\n", index);
  98
  99                 T *item = mItems[index];
 100                 if (item) return item == inItem;
 101
 102                 mItems[index] = inItem;
 103                 mNumItems++;
 104                 return true;
 105         }
 106
 107         bool Remove(T* inItem)
 108         {
 109                 int32 index = IndexFor(GetHash(inItem), GetKey(inItem));
 110                 if (mItems[index] != inItem) return false;
 111                 mItems[index] = 0;
 112
 113                 FixCollisionsFrom(index);
 114                 mNumItems--;
 115                 return true;
 116         }
 117
 118         int32 IndexFor(int32 inHashID, KeyType inKey) const
 119         {
 120                 int index = inHashID & mHashMask;
 121                 for(;;) {
 122                         T *item = mItems[index];
 123                         if (!item) return index;
 124                         if (GetHash(item) == inHashID
 125                                 && strcmp(inKey, GetKey(item)) == 0) return index;
 126                         index = (index + 1) & mHashMask;
 127                 }
 128         }
 129
 130         T* Get(KeyType inKey) const
 131         {
 132                 return Get(Hash(inKey), inKey);
 133         }
 134
 135         T* Get(int32 inHashID, KeyType inKey) const
 136         {
 137                 int32 index = IndexFor(inHashID, inKey);
 138                 return mItems[index];
 139         }
 140
 141         bool Includes(T* inItem) const
 142         {
 143                 return Get(GetHash(inItem), GetKey(inItem)) == inItem;
 144         }
 145
 146         T* AtIndex(int32 inIndex) const
 147         {
 148                 return mItems[inIndex];
 149         }
 150
 151 private:
 152         void FixCollisionsFrom(int32 inIndex)
 153         {
 154                 int oldIndex = inIndex;
 155                 for (;;) {
 156                         oldIndex = (oldIndex + 1) & mHashMask;
 157                         T *oldItem = mItems[oldIndex];
 158                         if (!oldItem) break;
 159                         int newIndex = IndexFor(GetHash(oldItem), GetKey(oldItem));
 160                         if (oldIndex != newIndex) {
 161                                 mItems[oldIndex] = mItems[newIndex];
 162                                 mItems[newIndex] = oldItem;
 163                         }
 164                 }
 165         }
 166 };
 167
 168 template<class T, int kMaxItems, class KeyType>
 169 class StaticHashTable
 170 {
 171         int32 mNumItems, mTableSize, mHashMask;
 172         T* mItems[kMaxItems*2];
 173
 174 public:
 175
 176         StaticHashTable()
 177         {
 178                 mNumItems = 0;
 179                 mTableSize = kMaxItems << 1;
 180                 ClearTable();
 181                 mHashMask = mTableSize - 1;
 182         }
 183
 184         ~StaticHashTable() {
 185         }
 186
 187         int32 TableSize() const { return mTableSize; }
 188         int32 MaxItems() const { return kMaxItems; }
 189         int32 NumItems() const { return mNumItems; }
 190
 191         void ClearTable()
 192         {
 193                 for (int i=0; i<mTableSize; ++i) {
 194                         mItems[i] = 0;
 195                 }
 196         }
 197
 198         bool Add(T* inItem)
 199         {
 200                 if (mNumItems >= kMaxItems) return false;
 201
 202                 int32 index = IndexFor(GetHash(inItem), GetKey(inItem));
 203
 204                 T *item = mItems[index];
 205                 if (item) return item == inItem;
 206
 207                 mItems[index] = inItem;
 208                 mNumItems++;
 209                 return true;
 210         }
 211
 212         bool Remove(T* inItem)
 213         {
 214                 int32 index = IndexFor(GetHash(inItem), GetKey(inItem));
 215                 if (mItems[index] != inItem) return false;
 216                 mItems[index] = 0;
 217
 218                 FixCollisionsFrom(index);
 219                 mNumItems--;
 220                 return true;
 221         }
 222
 223         int32 IndexFor(int32 inHashID, KeyType inKey) const
 224         {
 225                 int index = inHashID & mHashMask;
 226                 for(;;) {
 227                         T *item = mItems[index];
 228                         if (!item) return index;
 229                         if (GetHash(item) == inHashID
 230                                 && strcmp(inKey, GetKey(item)) == 0) return index;
 231                         index = (index + 1) & mHashMask;
 232                 }
 233         }
 234
 235         T* Get(KeyType inKey) const
 236         {
 237                 return Get(Hash(inKey), inKey);
 238         }
 239
 240         T* Get(int32 inHashID, KeyType inKey) const
 241         {
 242                 int32 index = IndexFor(inHashID, inKey);
 243                 return mItems[index];
 244         }
 245
 246         bool Includes(T* inItem) const
 247         {
 248                 return Get(GetHash(inItem), GetKey(inItem)) == inItem;
 249         }
 250
 251         T* AtIndex(int32 inIndex) const
 252         {
 253                 return mItems[inIndex];
 254         }
 255
 256 private:
 257         void FixCollisionsFrom(int32 inIndex)
 258         {
 259                 int oldIndex = inIndex;
 260                 for (;;) {
 261                         oldIndex = (oldIndex + 1) & mHashMask;
 262                         T *oldItem = mItems[oldIndex];
 263                         if (!oldItem) break;
 264                         int newIndex = IndexFor(GetHash(oldItem), GetKey(oldItem));
 265                         if (oldIndex != newIndex) {
 266                                 mItems[oldIndex] = mItems[newIndex];
 267                                 mItems[newIndex] = oldItem;
 268                         }
 269                 }
 270         }
 271 };
 272
 273
 274 #endif