1 #ifndef SPARSE_ARRAY_H 2 3 #define SPARSE_ARRAY_H 4 5 #include "PlatformConfigHACD.h" 6 7 using namespace hacd; 8 9 /*! 10 ** 11 ** Copyright (c) 20011 by John W. Ratcliff mailto:jratcliffscarab@gmail.com 12 ** 13 ** 14 ** The MIT license: 15 ** 16 ** Permission is hereby granted, free of charge, to any person obtaining a copy 17 ** of this software and associated documentation files (the "Software"), to deal 18 ** in the Software without restriction, including without limitation the rights 19 ** to use, copy, modify, merge, publish, distribute, sublicense, and/or sell 20 ** copies of the Software, and to permit persons to whom the Software is furnished 21 ** to do so, subject to the following conditions: 22 ** 23 ** The above copyright notice and this permission notice shall be included in all 24 ** copies or substantial portions of the Software. 25 26 ** THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 27 ** IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 28 ** FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 29 ** AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, 30 ** WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN 31 ** CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 32 33 */ 34 35 // This class implements a sparse array. 36 // You must know the maximum number of actual elements you will ever have in your array at creation time. 37 // Meaning it does not support 'growing' the number of active elements. 38 // The size of the array can be any array indexes up to 32 bits. 39 // 40 41 42 template < class Value, size_t hashTableSize = 512 > // *MUST* be a power of 2! 43 class SparseArray : public UANS::UserAllocated 44 { 45 public: SparseArray(HaU32 maxEntries)46 SparseArray(HaU32 maxEntries) 47 { 48 mFreeList = NULL; 49 mHashTableCount = 0; 50 for (size_t i = 0; i < hashTableSize; i++) 51 { 52 mHashTable[i] = NULL; 53 } 54 mMaxEntries = maxEntries; 55 mEntries = HACD_NEW(HashEntry)[maxEntries]; 56 } ~SparseArray(void)57 ~SparseArray(void) 58 { 59 delete []mEntries; 60 } 61 62 Value& operator[] (HaU32 key) 63 { 64 Value *v = find(key); 65 if ( v == NULL ) 66 { 67 Value dummy; 68 insert(key,dummy); 69 v = find(key); 70 HACD_ASSERT(v); 71 } 72 return *v; 73 } 74 75 const Value& operator[](HaU32 key) const 76 { 77 Value *v = find(key); 78 if ( v == NULL ) 79 { 80 Value dummy; 81 insert(key,dummy); 82 v = find(key); 83 HACD_ASSERT(v); 84 } 85 return *v; 86 } 87 88 find(HaU32 key)89 Value* find(HaU32 key) const 90 { 91 Value* ret = NULL; 92 HaU32 hash = getHash(key); 93 HashEntry* h = mHashTable[hash]; 94 while (h) 95 { 96 if (h->mKey == key) 97 { 98 ret = &h->mValue; 99 break; 100 } 101 h = h->mNext; 102 } 103 return ret; 104 } 105 erase(HaU32 key)106 void erase(HaU32 key) 107 { 108 HaU32 hash = getHash(key); 109 HashEntry* h = mHashTable[hash]; 110 HashEntry *prev = NULL; 111 while (h) 112 { 113 if (h->mKey == key) 114 { 115 if ( prev ) 116 { 117 prev->mNext = h->mNext; // if there was a previous, then it's next is our old next 118 } 119 else 120 { 121 mHashTable[hash] = h->mNext; // if there was no previous than the new head of the list is our next. 122 } 123 // add this hash entry to the free list. 124 HashEntry *oldFreeList = mFreeList; 125 mFreeList = h; 126 h->mNext = oldFreeList; 127 break; 128 } 129 prev = h; 130 h = h->mNext; 131 } 132 } 133 insert(HaU32 key,const Value & value)134 void insert(HaU32 key, const Value& value) 135 { 136 if (mHashTableCount < mMaxEntries ) 137 { 138 HashEntry* h; 139 if ( mFreeList ) // if there are previously freed hash entry items 140 { 141 h = mFreeList; 142 mFreeList = h->mNext; 143 h->mNext = NULL; 144 } 145 else 146 { 147 h = &mEntries[mHashTableCount]; 148 mHashTableCount++; 149 HACD_ASSERT( mHashTableCount < mMaxEntries ); 150 } 151 152 h->mKey = key; 153 h->mValue = value; 154 HaU32 hash = getHash(key); 155 if (mHashTable[hash]) 156 { 157 HashEntry* next = mHashTable[hash]; 158 mHashTable[hash] = h; 159 h->mNext = next; 160 } 161 else 162 { 163 mHashTable[hash] = h; 164 } 165 } 166 } 167 private: 168 169 // Thomas Wang's 32 bit mix 170 // http://www.cris.com/~Ttwang/tech/inthash.htm hash(const HaU32 key)171 HACD_INLINE HaU32 hash(const HaU32 key) const 172 { 173 HaU32 k = key; 174 k += ~(k << 15); 175 k ^= (k >> 10); 176 k += (k << 3); 177 k ^= (k >> 6); 178 k += ~(k << 11); 179 k ^= (k >> 16); 180 return (HaU32)k; 181 } 182 getHash(HaU32 key)183 HACD_INLINE HaU32 getHash(HaU32 key) const 184 { 185 HaU32 ret = hash(key); 186 return ret & (hashTableSize - 1); 187 } 188 189 class HashEntry : public UANS::UserAllocated 190 { 191 public: HashEntry(void)192 HashEntry(void) 193 { 194 mNext = NULL; 195 } 196 HashEntry* mNext; 197 HaU32 mKey; 198 Value mValue; 199 }; 200 201 HashEntry* mFreeList; 202 HashEntry* mHashTable[hashTableSize]; 203 unsigned int mHashTableCount; 204 HaU32 mMaxEntries; 205 HashEntry *mEntries; 206 207 }; 208 209 #endif 210