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 * bool 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; /* NOLINT(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(DE_PTR_TYPE(TYPENAME) hash); \ 99 bool TYPENAME##_reserve(DE_PTR_TYPE(TYPENAME) hash, int capacity); \ 100 VALUETYPE *TYPENAME##_find(const TYPENAME *hash, KEYTYPE key); \ 101 bool TYPENAME##_insert(DE_PTR_TYPE(TYPENAME) hash, KEYTYPE key, VALUETYPE value); \ 102 void TYPENAME##_delete(DE_PTR_TYPE(TYPENAME) hash, KEYTYPE key); \ 103 \ 104 static inline int TYPENAME##_getNumElements(const TYPENAME *hash) DE_UNUSED_FUNCTION; \ 105 static inline void TYPENAME##Iter_init(const TYPENAME *hash, TYPENAME##Iter *iter) DE_UNUSED_FUNCTION; \ 106 static inline bool TYPENAME##Iter_hasItem(const TYPENAME##Iter *iter) DE_UNUSED_FUNCTION; \ 107 static inline void TYPENAME##Iter_next(TYPENAME##Iter *iter) DE_UNUSED_FUNCTION; \ 108 static inline KEYTYPE TYPENAME##Iter_getKey(const TYPENAME##Iter *iter) DE_UNUSED_FUNCTION; \ 109 static inline VALUETYPE TYPENAME##Iter_getValue(const TYPENAME##Iter *iter) DE_UNUSED_FUNCTION; \ 110 \ 111 static inline int TYPENAME##_getNumElements(const TYPENAME *hash) \ 112 { \ 113 return hash->numElements; \ 114 } \ 115 \ 116 static inline void TYPENAME##Iter_init(const TYPENAME *hash, TYPENAME##Iter *iter) \ 117 { \ 118 iter->hash = hash; \ 119 iter->curSlotIndex = 0; \ 120 iter->curSlot = 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 static inline bool TYPENAME##Iter_hasItem(const TYPENAME##Iter *iter) \ 140 { \ 141 return (iter->curSlot != NULL); \ 142 } \ 143 \ 144 static 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 = NULL; \ 169 } \ 170 } \ 171 } \ 172 \ 173 static 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 static 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##Unused_s \ 186 { \ 187 int unused; \ 188 } 189 190 /*--------------------------------------------------------------------*//*! 191 * \brief Implement a template pool hash class. 192 * \param TYPENAME Type name of the declared hash. 193 * \param KEYTYPE Type of the key. 194 * \param VALUETYPE Type of the value. 195 * \param HASHFUNC Function used for hashing the key. 196 * \param CMPFUNC Function used for exact matching of the keys. 197 * 198 * This macro has implements the hash declared with DE_DECLARE_POOL_HASH. 199 * Usually this macro should be used from a .c file, since the macro expands 200 * into multiple functions. The TYPENAME, KEYTYPE, and VALUETYPE parameters 201 * must match those of the declare macro. 202 *//*--------------------------------------------------------------------*/ 203 #define DE_IMPLEMENT_POOL_HASH(TYPENAME, KEYTYPE, VALUETYPE, HASHFUNC, CMPFUNC) \ 204 \ 205 TYPENAME *TYPENAME##_create(deMemPool *pool) \ 206 { \ 207 /* Alloc struct. */ \ 208 DE_PTR_TYPE(TYPENAME) hash = DE_POOL_NEW(pool, TYPENAME); \ 209 if (!hash) \ 210 return NULL; \ 211 \ 212 memset(hash, 0, sizeof(TYPENAME)); \ 213 hash->pool = pool; \ 214 \ 215 return hash; \ 216 } \ 217 \ 218 void TYPENAME##_reset(DE_PTR_TYPE(TYPENAME) hash) \ 219 { \ 220 int slotNdx; \ 221 for (slotNdx = 0; slotNdx < hash->slotTableSize; slotNdx++) \ 222 { \ 223 TYPENAME##Slot *slot = hash->slotTable[slotNdx]; \ 224 while (slot) \ 225 { \ 226 TYPENAME##Slot *nextSlot = slot->nextSlot; \ 227 slot->nextSlot = hash->slotFreeList; \ 228 hash->slotFreeList = slot; \ 229 slot->numUsed = 0; \ 230 slot = nextSlot; \ 231 } \ 232 hash->slotTable[slotNdx] = NULL; \ 233 } \ 234 hash->numElements = 0; \ 235 } \ 236 \ 237 TYPENAME##Slot *TYPENAME##_allocSlot(DE_PTR_TYPE(TYPENAME) hash) \ 238 { \ 239 TYPENAME##Slot *slot; \ 240 if (hash->slotFreeList) \ 241 { \ 242 slot = hash->slotFreeList; \ 243 hash->slotFreeList = hash->slotFreeList->nextSlot; \ 244 } \ 245 else \ 246 slot = (TYPENAME##Slot *)deMemPool_alloc(hash->pool, sizeof(TYPENAME##Slot) * DE_HASH_ELEMENTS_PER_SLOT); \ 247 \ 248 if (slot) \ 249 { \ 250 slot->nextSlot = NULL; \ 251 slot->numUsed = 0; \ 252 } \ 253 \ 254 return slot; \ 255 } \ 256 \ 257 bool TYPENAME##_rehash(DE_PTR_TYPE(TYPENAME) hash, int newSlotTableSize) \ 258 { \ 259 DE_ASSERT(deIsPowerOfTwo32(newSlotTableSize) && newSlotTableSize > 0); \ 260 if (newSlotTableSize > hash->slotTableSize) \ 261 { \ 262 TYPENAME##Slot **oldSlotTable = hash->slotTable; \ 263 TYPENAME##Slot **newSlotTable = \ 264 (TYPENAME##Slot **)deMemPool_alloc(hash->pool, sizeof(TYPENAME##Slot *) * (size_t)newSlotTableSize); \ 265 int oldSlotTableSize = hash->slotTableSize; \ 266 int slotNdx; \ 267 \ 268 if (!newSlotTable) \ 269 return false; \ 270 \ 271 for (slotNdx = 0; slotNdx < oldSlotTableSize; slotNdx++) \ 272 newSlotTable[slotNdx] = oldSlotTable[slotNdx]; \ 273 \ 274 for (slotNdx = oldSlotTableSize; slotNdx < newSlotTableSize; slotNdx++) \ 275 newSlotTable[slotNdx] = NULL; \ 276 \ 277 hash->slotTableSize = newSlotTableSize; \ 278 hash->slotTable = newSlotTable; \ 279 \ 280 for (slotNdx = 0; slotNdx < oldSlotTableSize; slotNdx++) \ 281 { \ 282 TYPENAME##Slot *slot = oldSlotTable[slotNdx]; \ 283 newSlotTable[slotNdx] = NULL; \ 284 while (slot) \ 285 { \ 286 int elemNdx; \ 287 for (elemNdx = 0; elemNdx < slot->numUsed; elemNdx++) \ 288 { \ 289 hash->numElements--; \ 290 if (!TYPENAME##_insert(hash, slot->keys[elemNdx], slot->values[elemNdx])) \ 291 return false; \ 292 } \ 293 slot = slot->nextSlot; \ 294 } \ 295 } \ 296 } \ 297 \ 298 return true; \ 299 } \ 300 \ 301 VALUETYPE *TYPENAME##_find(const TYPENAME *hash, KEYTYPE key) \ 302 { \ 303 if (hash->numElements > 0) \ 304 { \ 305 int slotNdx = (int)(HASHFUNC(key) & (uint32_t)(hash->slotTableSize - 1)); \ 306 TYPENAME##Slot *slot = hash->slotTable[slotNdx]; \ 307 DE_ASSERT(deInBounds32(slotNdx, 0, hash->slotTableSize)); \ 308 \ 309 while (slot) \ 310 { \ 311 int elemNdx; \ 312 for (elemNdx = 0; elemNdx < slot->numUsed; elemNdx++) \ 313 { \ 314 if (CMPFUNC(slot->keys[elemNdx], key)) \ 315 return &slot->values[elemNdx]; \ 316 } \ 317 slot = slot->nextSlot; \ 318 } \ 319 } \ 320 \ 321 return NULL; \ 322 } \ 323 \ 324 bool TYPENAME##_insert(DE_PTR_TYPE(TYPENAME) hash, KEYTYPE key, VALUETYPE value) \ 325 { \ 326 int slotNdx; \ 327 TYPENAME##Slot *slot; \ 328 \ 329 DE_ASSERT(!TYPENAME##_find(hash, key)); \ 330 \ 331 if ((hash->numElements + 1) >= hash->slotTableSize * DE_HASH_ELEMENTS_PER_SLOT) \ 332 if (!TYPENAME##_rehash(hash, deMax32(4, 2 * hash->slotTableSize))) \ 333 return false; \ 334 \ 335 slotNdx = (int)(HASHFUNC(key) & (uint32_t)(hash->slotTableSize - 1)); \ 336 DE_ASSERT(slotNdx >= 0 && slotNdx < hash->slotTableSize); \ 337 slot = hash->slotTable[slotNdx]; \ 338 \ 339 if (!slot) \ 340 { \ 341 slot = TYPENAME##_allocSlot(hash); \ 342 if (!slot) \ 343 return false; \ 344 hash->slotTable[slotNdx] = slot; \ 345 } \ 346 \ 347 for (;;) \ 348 { \ 349 if (slot->numUsed == DE_HASH_ELEMENTS_PER_SLOT) \ 350 { \ 351 if (slot->nextSlot) \ 352 slot = slot->nextSlot; \ 353 else \ 354 { \ 355 TYPENAME##Slot *nextSlot = TYPENAME##_allocSlot(hash); \ 356 if (!nextSlot) \ 357 return false; \ 358 slot->nextSlot = nextSlot; \ 359 slot = nextSlot; \ 360 } \ 361 } \ 362 else \ 363 { \ 364 slot->keys[slot->numUsed] = key; \ 365 slot->values[slot->numUsed] = value; \ 366 slot->numUsed++; \ 367 hash->numElements++; \ 368 return true; \ 369 } \ 370 } \ 371 } \ 372 \ 373 void TYPENAME##_delete(DE_PTR_TYPE(TYPENAME) hash, KEYTYPE key) \ 374 { \ 375 int slotNdx; \ 376 TYPENAME##Slot *slot; \ 377 TYPENAME##Slot *prevSlot = NULL; \ 378 \ 379 DE_ASSERT(hash->numElements > 0); \ 380 slotNdx = (int)(HASHFUNC(key) & (uint32_t)(hash->slotTableSize - 1)); \ 381 DE_ASSERT(slotNdx >= 0 && slotNdx < hash->slotTableSize); \ 382 slot = hash->slotTable[slotNdx]; \ 383 DE_ASSERT(slot); \ 384 \ 385 for (;;) \ 386 { \ 387 int elemNdx; \ 388 DE_ASSERT(slot->numUsed > 0); \ 389 for (elemNdx = 0; elemNdx < slot->numUsed; elemNdx++) \ 390 { \ 391 if (CMPFUNC(slot->keys[elemNdx], key)) \ 392 { \ 393 TYPENAME##Slot *lastSlot = slot; \ 394 while (lastSlot->nextSlot) \ 395 { \ 396 prevSlot = lastSlot; \ 397 lastSlot = lastSlot->nextSlot; \ 398 } \ 399 \ 400 slot->keys[elemNdx] = lastSlot->keys[lastSlot->numUsed - 1]; \ 401 slot->values[elemNdx] = lastSlot->values[lastSlot->numUsed - 1]; \ 402 lastSlot->numUsed--; \ 403 \ 404 if (lastSlot->numUsed == 0) \ 405 { \ 406 if (prevSlot) \ 407 prevSlot->nextSlot = NULL; \ 408 else \ 409 hash->slotTable[slotNdx] = NULL; \ 410 \ 411 lastSlot->nextSlot = hash->slotFreeList; \ 412 hash->slotFreeList = lastSlot; \ 413 } \ 414 \ 415 hash->numElements--; \ 416 return; \ 417 } \ 418 } \ 419 \ 420 prevSlot = slot; \ 421 slot = slot->nextSlot; \ 422 DE_ASSERT(slot); \ 423 } \ 424 } \ 425 struct TYPENAME##Unused2_s \ 426 { \ 427 int unused; \ 428 } 429 430 /* Copy-to-array templates. */ 431 432 #define DE_DECLARE_POOL_HASH_TO_ARRAY(HASHTYPENAME, KEYARRAYTYPENAME, VALUEARRAYTYPENAME) \ 433 bool HASHTYPENAME##_copyToArray(const HASHTYPENAME *set, DE_PTR_TYPE(KEYARRAYTYPENAME) keyArray, \ 434 DE_PTR_TYPE(VALUEARRAYTYPENAME) valueArray); \ 435 struct HASHTYPENAME##_##KEYARRAYTYPENAME##_##VALUEARRAYTYPENAME##_declare_unused \ 436 { \ 437 int unused; \ 438 } 439 440 #define DE_IMPLEMENT_POOL_HASH_TO_ARRAY(HASHTYPENAME, KEYARRAYTYPENAME, VALUEARRAYTYPENAME) \ 441 bool HASHTYPENAME##_copyToArray(const HASHTYPENAME *hash, DE_PTR_TYPE(KEYARRAYTYPENAME) keyArray, \ 442 DE_PTR_TYPE(VALUEARRAYTYPENAME) valueArray) \ 443 { \ 444 int numElements = hash->numElements; \ 445 int arrayNdx = 0; \ 446 int slotNdx; \ 447 \ 448 if ((keyArray && !KEYARRAYTYPENAME##_setSize(keyArray, numElements)) || \ 449 (valueArray && !VALUEARRAYTYPENAME##_setSize(valueArray, numElements))) \ 450 return false; \ 451 \ 452 for (slotNdx = 0; slotNdx < hash->slotTableSize; slotNdx++) \ 453 { \ 454 const HASHTYPENAME##Slot *slot = hash->slotTable[slotNdx]; \ 455 while (slot) \ 456 { \ 457 int elemNdx; \ 458 for (elemNdx = 0; elemNdx < slot->numUsed; elemNdx++) \ 459 { \ 460 if (keyArray) \ 461 KEYARRAYTYPENAME##_set(keyArray, arrayNdx, slot->keys[elemNdx]); \ 462 if (valueArray) \ 463 VALUEARRAYTYPENAME##_set(valueArray, arrayNdx, slot->values[elemNdx]); \ 464 arrayNdx++; \ 465 } \ 466 slot = slot->nextSlot; \ 467 } \ 468 } \ 469 DE_ASSERT(arrayNdx == numElements); \ 470 return true; \ 471 } \ 472 struct HASHTYPENAME##_##KEYARRAYTYPENAME##_##VALUEARRAYTYPENAME##_implement_unused \ 473 { \ 474 int unused; \ 475 } 476 477 #endif /* _DEPOOLHASH_H */ 478