aboutsummaryrefslogtreecommitdiff
path: root/sc4pd/headers/server/HashTable.h
diff options
context:
space:
mode:
Diffstat (limited to 'sc4pd/headers/server/HashTable.h')
-rw-r--r--sc4pd/headers/server/HashTable.h356
1 files changed, 356 insertions, 0 deletions
diff --git a/sc4pd/headers/server/HashTable.h b/sc4pd/headers/server/HashTable.h
new file mode 100644
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
generated by cgit v1.2.1 (git 2.18.0) at 2024-05-04 13:53:07 +0000