framework/delibs/depool/dePoolHashSet.h

   1 #ifndef _DEPOOLHASHSET_H
   2 #define _DEPOOLHASHSET_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-set class.
  24  *//*--------------------------------------------------------------------*/
  25
  26 #include "deDefs.h"
  27 #include "dePoolHash.h"
  28 #include "dePoolSet.h"
  29
  30 DE_BEGIN_EXTERN_C
  31
  32 void    dePoolHashSet_selfTest          (void);
  33
  34 DE_END_EXTERN_C
  35
  36 /*--------------------------------------------------------------------*//*!
  37  * \brief Declare a template pool hash-set (hash of sets) class interface.
  38  * \param TYPENAME      Type name of the declared hash-set.
  39  * \param KEYTYPE       Type of the key.
  40  * \param VALUETYPE     Type of the value.
  41  *
  42  * \todo [petri] Description.
  43  *
  44  * The functions for operating the hash are:
  45  * \todo [petri] Figure out how to comment these in Doxygen-style.
  46  *
  47  * \code
  48  * HashSet*    HashSet_create            (deMemPool* pool);
  49  * int         HashSet_getNumElements    (const HashSet* hashSet);
  50  * Set<Value>* HashSet_find              (const HashSet* hashSet, Key key); TODO: better API
  51  * Hash<Set*>* HashSet_getHash           (const HashSet* hashSet); TODO: better API
  52  * deBool      HashSet_insert            (HashSet* hashSet, Key key, Value value);
  53  * void        HashSet_delete            (HashSet* hashSet, Key key, Value value);
  54  * deBool      HashSet_exists            (const HashSet* hashSet, Key key, Value value);
  55  * \endcode
  56 *//*--------------------------------------------------------------------*/
  57 #define DE_DECLARE_POOL_HASH_SET(TYPENAME, KEYTYPE, VALUETYPE)                                                                          \
  58                                                                                                                                                                                                         \
  59 DE_DECLARE_POOL_SET(TYPENAME##Set, VALUETYPE);                                                                                                          \
  60 DE_DECLARE_POOL_HASH(TYPENAME##Hash, KEYTYPE, TYPENAME##Set*);                                                                          \
  61 typedef struct TYPENAME##_s                                                                                                                                                     \
  62 {                                                                                                                                                                                                       \
  63         TYPENAME##Hash* hash;                                                                                                                                                   \
  64 } TYPENAME;      /* NOLINT(TYPENAME) */                                                                                                                                 \
  65                                                                                                                                                                                                         \
  66 DE_INLINE TYPENAME*                     TYPENAME##_create                       (deMemPool* pool);                                                      \
  67 DE_INLINE int                           TYPENAME##_getNumElements       (const TYPENAME* hashSet)                                                                               DE_UNUSED_FUNCTION;     \
  68 DE_INLINE TYPENAME##Hash*       TYPENAME##_getHash                      (const TYPENAME* hashSet)                                                                               DE_UNUSED_FUNCTION;     \
  69 DE_INLINE deBool                        TYPENAME##_insert                       (DE_PTR_TYPE(TYPENAME) hashSet, KEYTYPE key, VALUETYPE value)   DE_UNUSED_FUNCTION;     \
  70 DE_INLINE deBool                        TYPENAME##_safeInsert           (DE_PTR_TYPE(TYPENAME) hashSet, KEYTYPE key, VALUETYPE value)   DE_UNUSED_FUNCTION;     \
  71 DE_INLINE TYPENAME##Set*        TYPENAME##_find                         (const TYPENAME* hashSet, KEYTYPE key)                                                  DE_UNUSED_FUNCTION;     \
  72 DE_INLINE void                          TYPENAME##_delete                       (DE_PTR_TYPE(TYPENAME) hashSet, KEYTYPE key, VALUETYPE value)   DE_UNUSED_FUNCTION;     \
  73 DE_INLINE deBool                        TYPENAME##_exists                       (const TYPENAME* hashSet, KEYTYPE key, VALUETYPE value)                 DE_UNUSED_FUNCTION;     \
  74                                                                                                                                                                                                         \
  75 DE_INLINE TYPENAME* TYPENAME##_create (deMemPool* pool)                                                                                         \
  76 {                                                                                                                                                                                                       \
  77         DE_PTR_TYPE(TYPENAME) hashSet = DE_POOL_NEW(pool, TYPENAME);                                                                    \
  78         if (!hashSet) return DE_NULL;                                                                                                                                   \
  79         if ((hashSet->hash = TYPENAME##Hash_create(pool)) == DE_NULL)                                                                   \
  80                 return DE_NULL;                                                                                                                                                         \
  81         return hashSet;                                                                                                                                                                 \
  82 }                                                                                                                                                                                                       \
  83                                                                                                                                                                                                         \
  84 DE_INLINE int TYPENAME##_getNumElements (const TYPENAME* hashSet)                                                                       \
  85 {                                                                                                                                                                                                       \
  86         return TYPENAME##Hash_getNumElements(hashSet->hash);                                                                                    \
  87 }                                                                                                                                                                                                       \
  88                                                                                                                                                                                                         \
  89 DE_INLINE TYPENAME##Hash* TYPENAME##_getHash (const TYPENAME* hashSet)                                                          \
  90 {                                                                                                                                                                                                       \
  91         return hashSet->hash;                                                                                                                                                   \
  92 }                                                                                                                                                                                                       \
  93                                                                                                                                                                                                         \
  94 DE_INLINE deBool TYPENAME##_insert (DE_PTR_TYPE(TYPENAME) hashSet, KEYTYPE key, VALUETYPE value)        \
  95 {                                                                                                                                                                                                       \
  96         TYPENAME##Set** setPtr  = TYPENAME##Hash_find(hashSet->hash, key);                                                              \
  97         TYPENAME##Set*  set             = setPtr ? *setPtr : DE_NULL;                                                                                   \
  98         if (!set)                                                                                                                                                                               \
  99         {                                                                                                                                                                                               \
 100                 set = TYPENAME##Set_create(hashSet->hash->pool);                                                                                        \
 101                 if (!set) return DE_FALSE;                                                                                                                                      \
 102                 if (!TYPENAME##Set_insert(set, value)) return DE_FALSE;                                                                         \
 103                 return TYPENAME##Hash_insert(hashSet->hash, key, set);                                                                          \
 104         }                                                                                                                                                                                               \
 105         else                                                                                                                                                                                    \
 106         {                                                                                                                                                                                               \
 107                 return TYPENAME##Set_insert(set, value);                                                                                                        \
 108         }                                                                                                                                                                                               \
 109 }                                                                                                                                                                                                       \
 110                                                                                                                                                                                                         \
 111 DE_INLINE deBool TYPENAME##_safeInsert (DE_PTR_TYPE(TYPENAME) hashSet, KEYTYPE key, VALUETYPE value)\
 112 {                                                                                                                                                                                                       \
 113         TYPENAME##Set** setPtr  = TYPENAME##Hash_find(hashSet->hash, key);                                                              \
 114         TYPENAME##Set*  set             = setPtr ? *setPtr : DE_NULL;                                                                                   \
 115         if (!set)                                                                                                                                                                               \
 116         {                                                                                                                                                                                               \
 117                 return TYPENAME##_insert(hashSet, key, value);                                                                                          \
 118         }                                                                                                                                                                                               \
 119         else                                                                                                                                                                                    \
 120         {                                                                                                                                                                                               \
 121                 return TYPENAME##Set_safeInsert(set, value);                                                                                            \
 122         }                                                                                                                                                                                               \
 123 }                                                                                                                                                                                                       \
 124                                                                                                                                                                                                         \
 125 DE_INLINE TYPENAME##Set* TYPENAME##_find (const TYPENAME* hashSet, KEYTYPE key)                                         \
 126 {                                                                                                                                                                                                       \
 127         TYPENAME##Set** setPtr = TYPENAME##Hash_find(hashSet->hash, key);                                                               \
 128         return setPtr ? *setPtr : DE_NULL;                                                                                                                              \
 129 }                                                                                                                                                                                                       \
 130                                                                                                                                                                                                         \
 131 DE_INLINE void TYPENAME##_delete (DE_PTR_TYPE(TYPENAME) hashSet, KEYTYPE key, VALUETYPE value)          \
 132 {                                                                                                                                                                                                       \
 133         TYPENAME##Set** setPtr = TYPENAME##Hash_find(hashSet->hash, key);                                                               \
 134         TYPENAME##Set*  set;                                                                                                                                                    \
 135         DE_ASSERT(setPtr);                                                                                                                                                              \
 136         set = *setPtr;                                                                                                                                                                  \
 137         TYPENAME##Set_delete(set, value);                                                                                                                               \
 138 }                                                                                                                                                                                                       \
 139                                                                                                                                                                                                         \
 140 DE_INLINE deBool TYPENAME##_exists (const TYPENAME* hashSet, KEYTYPE key, VALUETYPE value)                      \
 141 {                                                                                                                                                                                                       \
 142         TYPENAME##Set** setPtr = TYPENAME##Hash_find(hashSet->hash, key);                                                               \
 143         if (setPtr)                                                                                                                                                                             \
 144                 return TYPENAME##Set_exists(*setPtr, value);                                                                                            \
 145         else                                                                                                                                                                                    \
 146                 return DE_FALSE;                                                                                                                                                        \
 147 }                                                                                                                                                                                                       \
 148                                                                                                                                                                                                         \
 149 struct TYPENAME##Dummy_s { int dummy; }
 150
 151 /*--------------------------------------------------------------------*//*!
 152  * \brief Implement a template pool hash-set class.
 153  * \param TYPENAME      Type name of the declared hash.
 154  * \param KEYTYPE       Type of the key.
 155  * \param VALUETYPE     Type of the value.
 156  * \param HASHFUNC      Function used for hashing the key.
 157  * \param CMPFUNC       Function used for exact matching of the keys.
 158  *
 159  * This macro has implements the hash declared with DE_DECLARE_POOL_HASH.
 160  * Usually this macro should be used from a .c file, since the macro expands
 161  * into multiple functions. The TYPENAME, KEYTYPE, and VALUETYPE parameters
 162  * must match those of the declare macro.
 163 *//*--------------------------------------------------------------------*/
 164 #define DE_IMPLEMENT_POOL_HASH_SET(TYPENAME, KEYTYPE, VALUETYPE, KEYHASHFUNC, KEYCMPFUNC, VALUEHASHFUNC, VALUECMPFUNC)  \
 165 DE_IMPLEMENT_POOL_SET(TYPENAME##Set, VALUETYPE, VALUEHASHFUNC, VALUECMPFUNC);                                                                                   \
 166 DE_IMPLEMENT_POOL_HASH(TYPENAME##Hash, KEYTYPE, TYPENAME##Set*, KEYHASHFUNC, KEYCMPFUNC);                                                               \
 167 struct TYPENAME##Dummy2_s { int dummy; }
 168
 169 /* Copy-to-array templates. */
 170
 171 #if 0
 172
 173 #define DE_DECLARE_POOL_HASH_TO_ARRAY(HASHTYPENAME, KEYARRAYTYPENAME, VALUEARRAYTYPENAME)               \
 174         deBool HASHTYPENAME##_copyToArray(const HASHTYPENAME* set, KEYARRAYTYPENAME* keyArray, VALUEARRAYTYPENAME* valueArray); \
 175         struct HASHTYPENAME##_##KEYARRAYTYPENAME##_##VALUEARRAYTYPENAME##_declare_dummy { int dummy; }
 176
 177 #define DE_IMPLEMENT_POOL_HASH_TO_ARRAY(HASHTYPENAME, KEYARRAYTYPENAME, VALUEARRAYTYPENAME)             \
 178 deBool HASHTYPENAME##_copyToArray(const HASHTYPENAME* hash, KEYARRAYTYPENAME* keyArray, VALUEARRAYTYPENAME* valueArray) \
 179 {       \
 180         int numElements = hash->numElements;    \
 181         int arrayNdx    = 0;    \
 182         int slotNdx;    \
 183         \
 184         if ((keyArray && !KEYARRAYTYPENAME##_setSize(keyArray, numElements)) ||                 \
 185                 (valueArray && !VALUEARRAYTYPENAME##_setSize(valueArray, numElements)))         \
 186                 return DE_FALSE;        \
 187         \
 188         for (slotNdx = 0; slotNdx < hash->slotTableSize; slotNdx++) \
 189         { \
 190                 const HASHTYPENAME##Slot* slot = hash->slotTable[slotNdx]; \
 191                 while (slot) \
 192                 { \
 193                         int elemNdx; \
 194                         for (elemNdx = 0; elemNdx < slot->numUsed; elemNdx++) \
 195                         {       \
 196                                 if (keyArray)   \
 197                                         KEYARRAYTYPENAME##_set(keyArray, arrayNdx, slot->keys[elemNdx]); \
 198                                 if (valueArray) \
 199                                         VALUEARRAYTYPENAME##_set(valueArray, arrayNdx, slot->values[elemNdx]);  \
 200                                 arrayNdx++;     \
 201                         } \
 202                         slot = slot->nextSlot; \
 203                 } \
 204         }       \
 205         DE_ASSERT(arrayNdx == numElements);     \
 206         return DE_TRUE; \
 207 }       \
 208 struct HASHTYPENAME##_##KEYARRAYTYPENAME##_##VALUEARRAYTYPENAME##_implement_dummy { int dummy; }
 209
 210 #endif
 211
 212 #endif /* _DEPOOLHASHSET_H */