diff options
Diffstat (limited to 'sc4pd/headers/server/HashTable.h')
-rwxr-xr-x | sc4pd/headers/server/HashTable.h | 356 |
1 files changed, 356 insertions, 0 deletions
diff --git a/sc4pd/headers/server/HashTable.h b/sc4pd/headers/server/HashTable.h new file mode 100755 index 0000000..85da92c --- /dev/null +++ b/sc4pd/headers/server/HashTable.h @@ -0,0 +1,356 @@ +/* + SuperCollider real time audio synthesis system + Copyright (c) 2002 James McCartney. All rights reserved. + http://www.audiosynth.com + + This program is free software; you can redistribute it and/or modify + it under the terms of the GNU General Public License as published by + the Free Software Foundation; either version 2 of the License, or + (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software + Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA +*/ + +#ifndef _HashTable_ +#define _HashTable_ + +#include "SC_Types.h" +#include "SC_BoundsMacros.h" +#include "SC_Str4.h" +#include "Hash.h" +#include <stddef.h> +#include <stdlib.h> +#include <string.h> + +template<class T, class Allocator> +class HashTable +{ + Allocator *mPool; + int32 mNumItems, mMaxItems, mTableSize, mHashMask; + T** mItems; + bool mCanResize; + +public: + + HashTable(Allocator *inPool, int32 inMaxItems, bool inCanResize = true) + : mPool(inPool) + { + mNumItems = 0; + mMaxItems = inMaxItems; + mTableSize = mMaxItems << 1; + mItems = AllocTable(mTableSize); + mHashMask = mTableSize - 1; + mCanResize = inCanResize; + } + + ~HashTable() { + mPool->Free(mItems); + } + + int32 TableSize() const { return mTableSize; } + int32 MaxItems() const { return mMaxItems; } + int32 NumItems() const { return mNumItems; } + + T** AllocTable(int inTableSize) + { + size_t size = inTableSize * sizeof(T*); + T** items = static_cast<T**>(mPool->Alloc(size)); + for (int i=0; i<inTableSize; ++i) { + items[i] = 0; + } + return items; + } + + void MakeEmpty() + { + for (int i=0; i<mTableSize; ++i) { + mItems[i] = 0; + } + mNumItems = 0; + } + + void Resize() + { + int32 newSize = sc_max(mTableSize << 1, 32); + int32 oldSize = mTableSize; + T** oldItems = mItems; + mItems = AllocTable(newSize); + mTableSize = newSize; + mMaxItems = mTableSize >> 1; + mHashMask = mTableSize - 1; + mNumItems = 0; + for (int i=0; i<oldSize; ++i) { + T* item = oldItems[i]; + if (item) Add(item); + } + mPool->Free(oldItems); + //printf("mMaxItems %d mTableSize %d newSize %d\n", mMaxItems, mTableSize, newSize); + } + + bool Add(T* inItem) + { + //printf("mNumItems %d\n", mNumItems); + //printf("mMaxItems %d\n", mMaxItems); + //printf("mCanResize %d\n", mCanResize); + if (mNumItems >= mMaxItems) { + if (!mCanResize) return false; + Resize(); + } + + //printf("GetHash(inItem) %d\n", GetHash(inItem)); + //printf("GetKey(inItem) %s\n", GetKey(inItem)); + int32 index = IndexFor(GetHash(inItem), (int32*)GetKey(inItem)); + //printf("index %d\n", index); + + T *item = mItems[index]; + if (item) return item == inItem; + + mItems[index] = inItem; + mNumItems++; + return true; + } + + bool Remove(T* inItem) + { + int32 index = IndexFor(GetHash(inItem), (int32*)GetKey(inItem)); + if (mItems[index] != inItem) return false; + mItems[index] = 0; + + FixCollisionsFrom(index); + mNumItems--; + return true; + } + + bool RemoveKey(int32* inKey) + { + T* item = Get(inKey); + if (!item) return false; + return Remove(item); + } + + int32 IndexFor(int32 inHashID, int32* inKey) const + { + int index = inHashID & mHashMask; + for(;;) { + T *item = mItems[index]; + if (!item) return index; + if (GetHash(item) == inHashID && str4eq(inKey, GetKey(item))) return index; + index = (index + 1) & mHashMask; + } + } + + T* Get(int32* inKey) const + { + return Get(Hash(inKey), inKey); + } + + T* Get(int32 inHashID, int32* inKey) const + { + //printf("Get hash %d %s\n", inHashID, inKey); + int32 index = IndexFor(inHashID, inKey); + //printf("index %d\n", index); + return mItems[index]; + } + + bool Includes(T* inItem) const + { + return Get(GetHash(inItem), GetKey(inItem)) == inItem; + } + + T* AtIndex(int32 inIndex) const + { + return mItems[inIndex]; + } + +private: + void FixCollisionsFrom(int32 inIndex) + { + int oldIndex = inIndex; + for (;;) { + oldIndex = (oldIndex + 1) & mHashMask; + T *oldItem = mItems[oldIndex]; + if (!oldItem) break; + int newIndex = IndexFor(GetHash(oldItem), (int32*)GetKey(oldItem)); + if (oldIndex != newIndex) { + mItems[oldIndex] = mItems[newIndex]; + mItems[newIndex] = oldItem; + } + } + } +}; + + +template<class T, class Allocator> +class IntHashTable +{ + Allocator *mPool; + int32 mNumItems, mMaxItems, mTableSize, mHashMask; + T** mItems; + bool mCanResize; + +public: + + IntHashTable(Allocator *inPool, int32 inMaxItems, bool inCanResize = true) + : mPool(inPool) + { + mNumItems = 0; + mMaxItems = inMaxItems; + mTableSize = mMaxItems << 1; + mItems = AllocTable(mTableSize); + mHashMask = mTableSize - 1; + mCanResize = inCanResize; + } + + ~IntHashTable() { + mPool->Free(mItems); + } + + int32 TableSize() const { return mTableSize; } + int32 MaxItems() const { return mMaxItems; } + int32 NumItems() const { return mNumItems; } + + T** AllocTable(int inTableSize) + { + size_t size = inTableSize * sizeof(T*); + T** items = static_cast<T**>(mPool->Alloc(size)); + for (int i=0; i<inTableSize; ++i) { + items[i] = 0; + } + return items; + } + + void Resize() + { + int32 newSize = sc_max(mTableSize << 1, 32); + T** oldItems = mItems; + mItems = AllocTable(newSize); + for (int i=0; i<mTableSize; ++i) { + T* item = oldItems[i]; + if (item) Add(item); + } + mTableSize = newSize; + mMaxItems = mTableSize >> 1; + mHashMask = mTableSize - 1; + mPool->Free(oldItems); + //printf("mMaxItems %d mTableSize %d newSize %d\n", mMaxItems, mTableSize, newSize); + } + + bool Add(T* inItem) + { + //printf("mNumItems %d\n", mNumItems); + //printf("mMaxItems %d\n", mMaxItems); + //printf("mCanResize %d\n", mCanResize); + if (mNumItems >= mMaxItems) { + if (!mCanResize) return false; + Resize(); + } + + //printf("GetHash(inItem) %d\n", GetHash(inItem)); + //printf("GetKey(inItem) %d\n", GetKey(inItem)); + int32 index = IndexFor(GetHash(inItem), GetKey(inItem)); + //printf("index %d\n", index); + + T *item = mItems[index]; + if (item) return item == inItem; + + mItems[index] = inItem; + mNumItems++; + return true; + } + + bool Remove(T* inItem) + { + int32 index = IndexFor(GetHash(inItem), GetKey(inItem)); + //printf("rmv index %d hash %d key %d\n", index, GetHash(inItem), GetKey(inItem)); + if (mItems[index] != inItem) return false; + mItems[index] = 0; + + FixCollisionsFrom(index); + mNumItems--; + return true; + } + + bool RemoveKey(int32 inKey) + { + T* item = Get(inKey); + if (!item) return false; + return Remove(item); + } + + int32 IndexFor(int32 inHashID, int32 inKey) const + { + int index = inHashID & mHashMask; + for(;;) { + T *item = mItems[index]; + if (!item) return index; + if (GetHash(item) == inHashID && inKey == GetKey(item)) return index; + index = (index + 1) & mHashMask; + } + } + + T* Get(int32 inKey) const + { + //printf("Get key %d\n", inKey); + return Get(Hash(inKey), inKey); + } + + T* Get(int32 inHashID, int32 inKey) const + { + int32 index = IndexFor(inHashID, inKey); + //printf("Get index %d hash %d key %d\n", index, inHashID, inKey); + return mItems[index]; + } + + bool Includes(T* inItem) const + { + return Get(GetHash(inItem), GetKey(inItem)) == inItem; + } + + T* AtIndex(int32 inIndex) const + { + return mItems[inIndex]; + } + + void Dump() + { + for (int i=0; i<mTableSize; ++i) { + T* item = mItems[i]; + if (item) { + printf("%4d %4d %08X %08X\n", i, GetKey(item), GetHash(item), item); + } + } + } + +private: + void FixCollisionsFrom(int32 inIndex) + { + //printf("FixCollisionsFrom %d\n", inIndex); + int oldIndex = inIndex; + for (;;) { + oldIndex = (oldIndex + 1) & mHashMask; + T *oldItem = mItems[oldIndex]; + if (!oldItem) break; + int newIndex = IndexFor(GetHash(oldItem), GetKey(oldItem)); + if (oldIndex != newIndex) { + //printf("swap %d %d\n", oldIndex, newIndex); + mItems[oldIndex] = mItems[newIndex]; + mItems[newIndex] = oldItem; + } + } + } +}; + +struct Malloc +{ + void Free(void* ptr) { free(ptr); } + void* Alloc(size_t size) { return malloc(size); } +}; + +#endif |