1 #ifndef _DEPOOLHASH_H 2 #define _DEPOOLHASH_H 3 /*------------------------------------------------------------------------- 4 * drawElements Memory Pool Library 5 * -------------------------------- 6 * 7 * Copyright 2014 The Android Open Source Project 8 * 9 * Licensed under the Apache License, Version 2.0 (the "License"); 10 * you may not use this file except in compliance with the License. 11 * You may obtain a copy of the License at 12 * 13 * http://www.apache.org/licenses/LICENSE-2.0 14 * 15 * Unless required by applicable law or agreed to in writing, software 16 * distributed under the License is distributed on an "AS IS" BASIS, 17 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 18 * See the License for the specific language governing permissions and 19 * limitations under the License. 20 * 21 *//*! 22 * \file 23 * \brief Memory pool hash class. 24 *//*--------------------------------------------------------------------*/ 25 26 #include "deDefs.h" 27 #include "deMemPool.h" 28 #include "dePoolArray.h" 29 #include "deInt32.h" 30 31 #include <string.h> /* memset() */ 32 33 enum 34 { 35 DE_HASH_ELEMENTS_PER_SLOT = 4 36 }; 37 38 DE_BEGIN_EXTERN_C 39 40 void dePoolHash_selfTest (void); 41 42 DE_END_EXTERN_C 43 44 /*--------------------------------------------------------------------*//*! 45 * \brief Declare a template pool hash class interface. 46 * \param TYPENAME Type name of the declared hash. 47 * \param KEYTYPE Type of the key. 48 * \param VALUETYPE Type of the value. 49 * 50 * This macro declares the interface for a hash. For the implementation of 51 * the hash, see DE_IMPLEMENT_POOL_HASH. Usually this macro is put into the 52 * header file and the implementation macro is put in some .c file. 53 * 54 * \todo [petri] Detailed description. 55 * 56 * The functions for operating the hash are: 57 * \todo [petri] Figure out how to comment these in Doxygen-style. 58 * 59 * \code 60 * Hash* Hash_create (deMemPool* pool); 61 * int Hash_getNumElements (const Hash* hash); 62 * Value* Hash_find (Hash* hash, Key key); 63 * deBool Hash_insert (Hash* hash, Key key, Value value); 64 * void Hash_delete (Hash* hash, Key key); 65 * \endcode 66 *//*--------------------------------------------------------------------*/ 67 #define DE_DECLARE_POOL_HASH(TYPENAME, KEYTYPE, VALUETYPE) \ 68 \ 69 typedef struct TYPENAME##Slot_s TYPENAME##Slot; \ 70 \ 71 struct TYPENAME##Slot_s \ 72 { \ 73 int numUsed; \ 74 TYPENAME##Slot* nextSlot; \ 75 KEYTYPE keys[DE_HASH_ELEMENTS_PER_SLOT]; \ 76 VALUETYPE values[DE_HASH_ELEMENTS_PER_SLOT]; \ 77 }; \ 78 \ 79 typedef struct TYPENAME##_s \ 80 { \ 81 deMemPool* pool; \ 82 int numElements; \ 83 \ 84 int slotTableSize; \ 85 TYPENAME##Slot** slotTable; \ 86 TYPENAME##Slot* slotFreeList; \ 87 } TYPENAME; \ 88 \ 89 typedef struct TYPENAME##Iter_s \ 90 { \ 91 const TYPENAME* hash; \ 92 int curSlotIndex; \ 93 const TYPENAME##Slot* curSlot; \ 94 int curElemIndex; \ 95 } TYPENAME##Iter; \ 96 \ 97 TYPENAME* TYPENAME##_create (deMemPool* pool); \ 98 void TYPENAME##_reset (TYPENAME* hash); \ 99 deBool TYPENAME##_reserve (TYPENAME* hash, int capacity); \ 100 VALUETYPE* TYPENAME##_find (const TYPENAME* hash, KEYTYPE key); \ 101 deBool TYPENAME##_insert (TYPENAME* hash, KEYTYPE key, VALUETYPE value); \ 102 void TYPENAME##_delete (TYPENAME* hash, KEYTYPE key); \ 103 \ 104 DE_INLINE int TYPENAME##_getNumElements (const TYPENAME* hash) DE_UNUSED_FUNCTION; \ 105 DE_INLINE void TYPENAME##Iter_init (const TYPENAME* hash, TYPENAME##Iter* iter) DE_UNUSED_FUNCTION; \ 106 DE_INLINE deBool TYPENAME##Iter_hasItem (const TYPENAME##Iter* iter) DE_UNUSED_FUNCTION; \ 107 DE_INLINE void TYPENAME##Iter_next (TYPENAME##Iter* iter) DE_UNUSED_FUNCTION; \ 108 DE_INLINE KEYTYPE TYPENAME##Iter_getKey (const TYPENAME##Iter* iter) DE_UNUSED_FUNCTION; \ 109 DE_INLINE VALUETYPE TYPENAME##Iter_getValue (const TYPENAME##Iter* iter) DE_UNUSED_FUNCTION; \ 110 \ 111 DE_INLINE int TYPENAME##_getNumElements (const TYPENAME* hash) \ 112 { \ 113 return hash->numElements; \ 114 } \ 115 \ 116 DE_INLINE void TYPENAME##Iter_init (const TYPENAME* hash, TYPENAME##Iter* iter) \ 117 { \ 118 iter->hash = hash; \ 119 iter->curSlotIndex = 0; \ 120 iter->curSlot = DE_NULL; \ 121 iter->curElemIndex = 0; \ 122 if (TYPENAME##_getNumElements(hash) > 0) \ 123 { \ 124 int slotTableSize = hash->slotTableSize; \ 125 int slotNdx = 0; \ 126 while (slotNdx < slotTableSize) \ 127 { \ 128 if (hash->slotTable[slotNdx]) \ 129 break; \ 130 slotNdx++; \ 131 } \ 132 DE_ASSERT(slotNdx < slotTableSize); \ 133 iter->curSlotIndex = slotNdx; \ 134 iter->curSlot = hash->slotTable[slotNdx]; \ 135 DE_ASSERT(iter->curSlot); \ 136 } \ 137 } \ 138 \ 139 DE_INLINE deBool TYPENAME##Iter_hasItem (const TYPENAME##Iter* iter) \ 140 { \ 141 return (iter->curSlot != DE_NULL); \ 142 } \ 143 \ 144 DE_INLINE void TYPENAME##Iter_next (TYPENAME##Iter* iter) \ 145 { \ 146 DE_ASSERT(TYPENAME##Iter_hasItem(iter)); \ 147 if (++iter->curElemIndex == iter->curSlot->numUsed) \ 148 { \ 149 iter->curElemIndex = 0; \ 150 if (iter->curSlot->nextSlot) \ 151 { \ 152 iter->curSlot = iter->curSlot->nextSlot; \ 153 } \ 154 else \ 155 { \ 156 const TYPENAME* hash = iter->hash; \ 157 int curSlotIndex = iter->curSlotIndex; \ 158 int slotTableSize = hash->slotTableSize; \ 159 while (++curSlotIndex < slotTableSize) \ 160 { \ 161 if (hash->slotTable[curSlotIndex]) \ 162 break; \ 163 } \ 164 iter->curSlotIndex = curSlotIndex; \ 165 if (curSlotIndex < slotTableSize) \ 166 iter->curSlot = hash->slotTable[curSlotIndex]; \ 167 else \ 168 iter->curSlot = DE_NULL; \ 169 } \ 170 } \ 171 } \ 172 \ 173 DE_INLINE KEYTYPE TYPENAME##Iter_getKey (const TYPENAME##Iter* iter) \ 174 { \ 175 DE_ASSERT(TYPENAME##Iter_hasItem(iter)); \ 176 return iter->curSlot->keys[iter->curElemIndex]; \ 177 } \ 178 \ 179 DE_INLINE VALUETYPE TYPENAME##Iter_getValue (const TYPENAME##Iter* iter) \ 180 { \ 181 DE_ASSERT(TYPENAME##Iter_hasItem(iter)); \ 182 return iter->curSlot->values[iter->curElemIndex]; \ 183 } \ 184 \ 185 struct TYPENAME##Dummy_s { int dummy; } 186 187 /*--------------------------------------------------------------------*//*! 188 * \brief Implement a template pool hash class. 189 * \param TYPENAME Type name of the declared hash. 190 * \param KEYTYPE Type of the key. 191 * \param VALUETYPE Type of the value. 192 * \param HASHFUNC Function used for hashing the key. 193 * \param CMPFUNC Function used for exact matching of the keys. 194 * 195 * This macro has implements the hash declared with DE_DECLARE_POOL_HASH. 196 * Usually this macro should be used from a .c file, since the macro expands 197 * into multiple functions. The TYPENAME, KEYTYPE, and VALUETYPE parameters 198 * must match those of the declare macro. 199 *//*--------------------------------------------------------------------*/ 200 #define DE_IMPLEMENT_POOL_HASH(TYPENAME, KEYTYPE, VALUETYPE, HASHFUNC, CMPFUNC) \ 201 \ 202 TYPENAME* TYPENAME##_create (deMemPool* pool) \ 203 { \ 204 /* Alloc struct. */ \ 205 TYPENAME* hash = DE_POOL_NEW(pool, TYPENAME); \ 206 if (!hash) \ 207 return DE_NULL; \ 208 \ 209 memset(hash, 0, sizeof(TYPENAME)); \ 210 hash->pool = pool; \ 211 \ 212 return hash; \ 213 } \ 214 \ 215 void TYPENAME##_reset (TYPENAME* hash) \ 216 { \ 217 int slotNdx; \ 218 for (slotNdx = 0; slotNdx < hash->slotTableSize; slotNdx++) \ 219 { \ 220 TYPENAME##Slot* slot = hash->slotTable[slotNdx]; \ 221 while (slot) \ 222 { \ 223 TYPENAME##Slot* nextSlot = slot->nextSlot; \ 224 slot->nextSlot = hash->slotFreeList; \ 225 hash->slotFreeList = slot; \ 226 slot->numUsed = 0; \ 227 slot = nextSlot; \ 228 } \ 229 hash->slotTable[slotNdx] = DE_NULL; \ 230 } \ 231 hash->numElements = 0; \ 232 } \ 233 \ 234 TYPENAME##Slot* TYPENAME##_allocSlot (TYPENAME* hash) \ 235 { \ 236 TYPENAME##Slot* slot; \ 237 if (hash->slotFreeList) \ 238 { \ 239 slot = hash->slotFreeList; \ 240 hash->slotFreeList = hash->slotFreeList->nextSlot; \ 241 } \ 242 else \ 243 slot = (TYPENAME##Slot*)deMemPool_alloc(hash->pool, sizeof(TYPENAME##Slot) * DE_HASH_ELEMENTS_PER_SLOT); \ 244 \ 245 if (slot) \ 246 { \ 247 slot->nextSlot = DE_NULL; \ 248 slot->numUsed = 0; \ 249 } \ 250 \ 251 return slot; \ 252 } \ 253 \ 254 deBool TYPENAME##_rehash (TYPENAME* hash, int newSlotTableSize) \ 255 { \ 256 DE_ASSERT(deIsPowerOfTwo32(newSlotTableSize) && newSlotTableSize > 0); \ 257 if (newSlotTableSize > hash->slotTableSize) \ 258 { \ 259 TYPENAME##Slot** oldSlotTable = hash->slotTable; \ 260 TYPENAME##Slot** newSlotTable = (TYPENAME##Slot**)deMemPool_alloc(hash->pool, sizeof(TYPENAME##Slot*) * newSlotTableSize); \ 261 int oldSlotTableSize = hash->slotTableSize; \ 262 int slotNdx; \ 263 \ 264 if (!newSlotTable) \ 265 return DE_FALSE; \ 266 \ 267 for (slotNdx = 0; slotNdx < oldSlotTableSize; slotNdx++) \ 268 newSlotTable[slotNdx] = oldSlotTable[slotNdx]; \ 269 \ 270 for (slotNdx = oldSlotTableSize; slotNdx < newSlotTableSize; slotNdx++) \ 271 newSlotTable[slotNdx] = DE_NULL; \ 272 \ 273 hash->slotTableSize = newSlotTableSize; \ 274 hash->slotTable = newSlotTable; \ 275 \ 276 for (slotNdx = 0; slotNdx < oldSlotTableSize; slotNdx++) \ 277 { \ 278 TYPENAME##Slot* slot = oldSlotTable[slotNdx]; \ 279 newSlotTable[slotNdx] = DE_NULL; \ 280 while (slot) \ 281 { \ 282 int elemNdx; \ 283 for (elemNdx = 0; elemNdx < slot->numUsed; elemNdx++) \ 284 { \ 285 hash->numElements--; \ 286 if (!TYPENAME##_insert(hash, slot->keys[elemNdx], slot->values[elemNdx])) \ 287 return DE_FALSE; \ 288 } \ 289 slot = slot->nextSlot; \ 290 } \ 291 } \ 292 } \ 293 \ 294 return DE_TRUE; \ 295 } \ 296 \ 297 VALUETYPE* TYPENAME##_find (const TYPENAME* hash, KEYTYPE key) \ 298 { \ 299 if (hash->numElements > 0) \ 300 { \ 301 int slotNdx = HASHFUNC(key) & (hash->slotTableSize - 1); \ 302 TYPENAME##Slot* slot = hash->slotTable[slotNdx]; \ 303 DE_ASSERT(deInBounds32(slotNdx, 0, hash->slotTableSize)); \ 304 \ 305 while (slot) \ 306 { \ 307 int elemNdx; \ 308 for (elemNdx = 0; elemNdx < slot->numUsed; elemNdx++) \ 309 { \ 310 if (CMPFUNC(slot->keys[elemNdx], key)) \ 311 return &slot->values[elemNdx]; \ 312 } \ 313 slot = slot->nextSlot; \ 314 } \ 315 } \ 316 \ 317 return DE_NULL; \ 318 } \ 319 \ 320 deBool TYPENAME##_insert (TYPENAME* hash, KEYTYPE key, VALUETYPE value) \ 321 { \ 322 int slotNdx; \ 323 TYPENAME##Slot* slot; \ 324 \ 325 DE_ASSERT(!TYPENAME##_find(hash, key)); \ 326 \ 327 if ((hash->numElements + 1) >= hash->slotTableSize * DE_HASH_ELEMENTS_PER_SLOT) \ 328 if (!TYPENAME##_rehash(hash, deMax32(4, 2*hash->slotTableSize))) \ 329 return DE_FALSE; \ 330 \ 331 slotNdx = HASHFUNC(key) & (hash->slotTableSize - 1); \ 332 DE_ASSERT(slotNdx >= 0 && slotNdx < hash->slotTableSize); \ 333 slot = hash->slotTable[slotNdx]; \ 334 \ 335 if (!slot) \ 336 { \ 337 slot = TYPENAME##_allocSlot(hash); \ 338 if (!slot) return DE_FALSE; \ 339 hash->slotTable[slotNdx] = slot; \ 340 } \ 341 \ 342 for (;;) \ 343 { \ 344 if (slot->numUsed == DE_HASH_ELEMENTS_PER_SLOT) \ 345 { \ 346 if (slot->nextSlot) \ 347 slot = slot->nextSlot; \ 348 else \ 349 { \ 350 TYPENAME##Slot* nextSlot = TYPENAME##_allocSlot(hash); \ 351 if (!nextSlot) return DE_FALSE; \ 352 slot->nextSlot = nextSlot; \ 353 slot = nextSlot; \ 354 } \ 355 } \ 356 else \ 357 { \ 358 slot->keys[slot->numUsed] = key; \ 359 slot->values[slot->numUsed] = value; \ 360 slot->numUsed++; \ 361 hash->numElements++; \ 362 return DE_TRUE; \ 363 } \ 364 } \ 365 } \ 366 \ 367 void TYPENAME##_delete (TYPENAME* hash, KEYTYPE key) \ 368 { \ 369 int slotNdx; \ 370 TYPENAME##Slot* slot; \ 371 TYPENAME##Slot* prevSlot = DE_NULL; \ 372 \ 373 DE_ASSERT(hash->numElements > 0); \ 374 slotNdx = HASHFUNC(key) & (hash->slotTableSize - 1); \ 375 DE_ASSERT(slotNdx >= 0 && slotNdx < hash->slotTableSize); \ 376 slot = hash->slotTable[slotNdx]; \ 377 DE_ASSERT(slot); \ 378 \ 379 for (;;) \ 380 { \ 381 int elemNdx; \ 382 DE_ASSERT(slot->numUsed > 0); \ 383 for (elemNdx = 0; elemNdx < slot->numUsed; elemNdx++) \ 384 { \ 385 if (CMPFUNC(slot->keys[elemNdx], key)) \ 386 { \ 387 TYPENAME##Slot* lastSlot = slot; \ 388 while (lastSlot->nextSlot) \ 389 { \ 390 prevSlot = lastSlot; \ 391 lastSlot = lastSlot->nextSlot; \ 392 } \ 393 \ 394 slot->keys[elemNdx] = lastSlot->keys[lastSlot->numUsed-1]; \ 395 slot->values[elemNdx] = lastSlot->values[lastSlot->numUsed-1]; \ 396 lastSlot->numUsed--; \ 397 \ 398 if (lastSlot->numUsed == 0) \ 399 { \ 400 if (prevSlot) \ 401 prevSlot->nextSlot = DE_NULL; \ 402 else \ 403 hash->slotTable[slotNdx] = DE_NULL; \ 404 \ 405 lastSlot->nextSlot = hash->slotFreeList; \ 406 hash->slotFreeList = lastSlot; \ 407 } \ 408 \ 409 hash->numElements--; \ 410 return; \ 411 } \ 412 } \ 413 \ 414 prevSlot = slot; \ 415 slot = slot->nextSlot; \ 416 DE_ASSERT(slot); \ 417 } \ 418 } \ 419 struct TYPENAME##Dummy2_s { int dummy; } 420 421 /* Copy-to-array templates. */ 422 423 #define DE_DECLARE_POOL_HASH_TO_ARRAY(HASHTYPENAME, KEYARRAYTYPENAME, VALUEARRAYTYPENAME) \ 424 deBool HASHTYPENAME##_copyToArray(const HASHTYPENAME* set, KEYARRAYTYPENAME* keyArray, VALUEARRAYTYPENAME* valueArray); \ 425 struct HASHTYPENAME##_##KEYARRAYTYPENAME##_##VALUEARRAYTYPENAME##_declare_dummy { int dummy; } 426 427 #define DE_IMPLEMENT_POOL_HASH_TO_ARRAY(HASHTYPENAME, KEYARRAYTYPENAME, VALUEARRAYTYPENAME) \ 428 deBool HASHTYPENAME##_copyToArray(const HASHTYPENAME* hash, KEYARRAYTYPENAME* keyArray, VALUEARRAYTYPENAME* valueArray) \ 429 { \ 430 int numElements = hash->numElements; \ 431 int arrayNdx = 0; \ 432 int slotNdx; \ 433 \ 434 if ((keyArray && !KEYARRAYTYPENAME##_setSize(keyArray, numElements)) || \ 435 (valueArray && !VALUEARRAYTYPENAME##_setSize(valueArray, numElements))) \ 436 return DE_FALSE; \ 437 \ 438 for (slotNdx = 0; slotNdx < hash->slotTableSize; slotNdx++) \ 439 { \ 440 const HASHTYPENAME##Slot* slot = hash->slotTable[slotNdx]; \ 441 while (slot) \ 442 { \ 443 int elemNdx; \ 444 for (elemNdx = 0; elemNdx < slot->numUsed; elemNdx++) \ 445 { \ 446 if (keyArray) \ 447 KEYARRAYTYPENAME##_set(keyArray, arrayNdx, slot->keys[elemNdx]); \ 448 if (valueArray) \ 449 VALUEARRAYTYPENAME##_set(valueArray, arrayNdx, slot->values[elemNdx]); \ 450 arrayNdx++; \ 451 } \ 452 slot = slot->nextSlot; \ 453 } \ 454 } \ 455 DE_ASSERT(arrayNdx == numElements); \ 456 return DE_TRUE; \ 457 } \ 458 struct HASHTYPENAME##_##KEYARRAYTYPENAME##_##VALUEARRAYTYPENAME##_implement_dummy { int dummy; } 459 460 #endif /* _DEPOOLHASH_H */ 461