From d0ae3caca5828675335d3b19ab5dd987e7369b23 Mon Sep 17 00:00:00 2001 From: Tim Blechmann Date: Wed, 14 Jul 2004 16:21:44 +0000 Subject: This commit was generated by cvs2svn to compensate for changes in r1857, which included commits to RCS files with non-trunk default branches. svn path=/trunk/externals/tb/; revision=1858 --- sc4pd/headers/server/HashTable.h | 356 +++++++++++++++++++++++++++++++++++++++ 1 file changed, 356 insertions(+) create mode 100755 sc4pd/headers/server/HashTable.h (limited to 'sc4pd/headers/server/HashTable.h') 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 +#include +#include + +template +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(mPool->Alloc(size)); + for (int i=0; i> 1; + mHashMask = mTableSize - 1; + mNumItems = 0; + for (int i=0; iFree(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 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(mPool->Alloc(size)); + for (int i=0; i> 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 Date: Thu, 19 Jun 2008 13:50:58 +0000 Subject: removed the svn:executable bit for code, patches and text svn path=/trunk/externals/tb/; revision=10048 --- sc4pd/headers/server/HashTable.h | 0 1 file changed, 0 insertions(+), 0 deletions(-) mode change 100755 => 100644 sc4pd/headers/server/HashTable.h (limited to 'sc4pd/headers/server/HashTable.h') diff --git a/sc4pd/headers/server/HashTable.h b/sc4pd/headers/server/HashTable.h old mode 100755 new mode 100644 -- cgit v1.2.1