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; \ 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 (TYPENAME* hashSet, KEYTYPE key, VALUETYPE value) DE_UNUSED_FUNCTION; \ 70 DE_INLINE deBool TYPENAME##_safeInsert (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 (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 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 (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 (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 (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 */ 213