framework/delibs/depool/dePoolHash.h

   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; /* 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 deBool          TYPENAME##_reserve      (DE_PTR_TYPE(TYPENAME) hash, int capacity);                                     \
 100 VALUETYPE*      TYPENAME##_find         (const TYPENAME* hash, KEYTYPE key);                                            \
 101 deBool          TYPENAME##_insert       (DE_PTR_TYPE(TYPENAME) hash, KEYTYPE key, VALUETYPE value);     \
 102 void            TYPENAME##_delete       (DE_PTR_TYPE(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         DE_PTR_TYPE(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 (DE_PTR_TYPE(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 (DE_PTR_TYPE(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 (DE_PTR_TYPE(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*) * (size_t)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 = (int)(HASHFUNC(key) & (deUint32)(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 (DE_PTR_TYPE(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 = (int)(HASHFUNC(key) & (deUint32)(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 (DE_PTR_TYPE(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 = (int)(HASHFUNC(key) & (deUint32)(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, DE_PTR_TYPE(KEYARRAYTYPENAME) keyArray, DE_PTR_TYPE(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, DE_PTR_TYPE(KEYARRAYTYPENAME) keyArray, DE_PTR_TYPE(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 */