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 * bool HashSet_insert (HashSet* hashSet, Key key, Value value); 53 * void HashSet_delete (HashSet* hashSet, Key key, Value value); 54 * bool 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 bool TYPENAME##_insert(DE_PTR_TYPE(TYPENAME) hashSet, KEYTYPE key, VALUETYPE value) DE_UNUSED_FUNCTION; \ 70 DE_INLINE bool TYPENAME##_safeInsert(DE_PTR_TYPE(TYPENAME) hashSet, KEYTYPE key, VALUETYPE value) \ 71 DE_UNUSED_FUNCTION; \ 72 DE_INLINE TYPENAME##Set *TYPENAME##_find(const TYPENAME *hashSet, KEYTYPE key) DE_UNUSED_FUNCTION; \ 73 DE_INLINE void TYPENAME##_delete(DE_PTR_TYPE(TYPENAME) hashSet, KEYTYPE key, VALUETYPE value) DE_UNUSED_FUNCTION; \ 74 DE_INLINE bool TYPENAME##_exists(const TYPENAME *hashSet, KEYTYPE key, VALUETYPE value) DE_UNUSED_FUNCTION; \ 75 \ 76 DE_INLINE TYPENAME *TYPENAME##_create(deMemPool *pool) \ 77 { \ 78 DE_PTR_TYPE(TYPENAME) hashSet = DE_POOL_NEW(pool, TYPENAME); \ 79 if (!hashSet) \ 80 return DE_NULL; \ 81 if ((hashSet->hash = TYPENAME##Hash_create(pool)) == DE_NULL) \ 82 return DE_NULL; \ 83 return hashSet; \ 84 } \ 85 \ 86 DE_INLINE int TYPENAME##_getNumElements(const TYPENAME *hashSet) \ 87 { \ 88 return TYPENAME##Hash_getNumElements(hashSet->hash); \ 89 } \ 90 \ 91 DE_INLINE TYPENAME##Hash *TYPENAME##_getHash(const TYPENAME *hashSet) \ 92 { \ 93 return hashSet->hash; \ 94 } \ 95 \ 96 DE_INLINE bool TYPENAME##_insert(DE_PTR_TYPE(TYPENAME) hashSet, KEYTYPE key, VALUETYPE value) \ 97 { \ 98 TYPENAME##Set **setPtr = TYPENAME##Hash_find(hashSet->hash, key); \ 99 TYPENAME##Set *set = setPtr ? *setPtr : DE_NULL; \ 100 if (!set) \ 101 { \ 102 set = TYPENAME##Set_create(hashSet->hash->pool); \ 103 if (!set) \ 104 return false; \ 105 if (!TYPENAME##Set_insert(set, value)) \ 106 return false; \ 107 return TYPENAME##Hash_insert(hashSet->hash, key, set); \ 108 } \ 109 else \ 110 { \ 111 return TYPENAME##Set_insert(set, value); \ 112 } \ 113 } \ 114 \ 115 DE_INLINE bool TYPENAME##_safeInsert(DE_PTR_TYPE(TYPENAME) hashSet, KEYTYPE key, VALUETYPE value) \ 116 { \ 117 TYPENAME##Set **setPtr = TYPENAME##Hash_find(hashSet->hash, key); \ 118 TYPENAME##Set *set = setPtr ? *setPtr : DE_NULL; \ 119 if (!set) \ 120 { \ 121 return TYPENAME##_insert(hashSet, key, value); \ 122 } \ 123 else \ 124 { \ 125 return TYPENAME##Set_safeInsert(set, value); \ 126 } \ 127 } \ 128 \ 129 DE_INLINE TYPENAME##Set *TYPENAME##_find(const TYPENAME *hashSet, KEYTYPE key) \ 130 { \ 131 TYPENAME##Set **setPtr = TYPENAME##Hash_find(hashSet->hash, key); \ 132 return setPtr ? *setPtr : DE_NULL; \ 133 } \ 134 \ 135 DE_INLINE void TYPENAME##_delete(DE_PTR_TYPE(TYPENAME) hashSet, KEYTYPE key, VALUETYPE value) \ 136 { \ 137 TYPENAME##Set **setPtr = TYPENAME##Hash_find(hashSet->hash, key); \ 138 TYPENAME##Set *set; \ 139 DE_ASSERT(setPtr); \ 140 set = *setPtr; \ 141 TYPENAME##Set_delete(set, value); \ 142 } \ 143 \ 144 DE_INLINE bool TYPENAME##_exists(const TYPENAME *hashSet, KEYTYPE key, VALUETYPE value) \ 145 { \ 146 TYPENAME##Set **setPtr = TYPENAME##Hash_find(hashSet->hash, key); \ 147 if (setPtr) \ 148 return TYPENAME##Set_exists(*setPtr, value); \ 149 else \ 150 return false; \ 151 } \ 152 \ 153 struct TYPENAME##Unused_s \ 154 { \ 155 int unused; \ 156 } 157 158 /*--------------------------------------------------------------------*//*! 159 * \brief Implement a template pool hash-set class. 160 * \param TYPENAME Type name of the declared hash. 161 * \param KEYTYPE Type of the key. 162 * \param VALUETYPE Type of the value. 163 * \param HASHFUNC Function used for hashing the key. 164 * \param CMPFUNC Function used for exact matching of the keys. 165 * 166 * This macro has implements the hash declared with DE_DECLARE_POOL_HASH. 167 * Usually this macro should be used from a .c file, since the macro expands 168 * into multiple functions. The TYPENAME, KEYTYPE, and VALUETYPE parameters 169 * must match those of the declare macro. 170 *//*--------------------------------------------------------------------*/ 171 #define DE_IMPLEMENT_POOL_HASH_SET(TYPENAME, KEYTYPE, VALUETYPE, KEYHASHFUNC, KEYCMPFUNC, VALUEHASHFUNC, VALUECMPFUNC) \ 172 DE_IMPLEMENT_POOL_SET(TYPENAME##Set, VALUETYPE, VALUEHASHFUNC, VALUECMPFUNC); \ 173 DE_IMPLEMENT_POOL_HASH(TYPENAME##Hash, KEYTYPE, TYPENAME##Set *, KEYHASHFUNC, KEYCMPFUNC); \ 174 struct TYPENAME##Unused2_s \ 175 { \ 176 int unused; \ 177 } 178 179 /* Copy-to-array templates. */ 180 181 #if 0 182 183 #define DE_DECLARE_POOL_HASH_TO_ARRAY(HASHTYPENAME, KEYARRAYTYPENAME, VALUEARRAYTYPENAME) \ 184 bool HASHTYPENAME##_copyToArray(const HASHTYPENAME *set, KEYARRAYTYPENAME *keyArray, \ 185 VALUEARRAYTYPENAME *valueArray); \ 186 struct HASHTYPENAME##_##KEYARRAYTYPENAME##_##VALUEARRAYTYPENAME##_declare_unused \ 187 { \ 188 int unused; \ 189 } 190 191 #define DE_IMPLEMENT_POOL_HASH_TO_ARRAY(HASHTYPENAME, KEYARRAYTYPENAME, VALUEARRAYTYPENAME) \ 192 bool HASHTYPENAME##_copyToArray(const HASHTYPENAME *hash, KEYARRAYTYPENAME *keyArray, \ 193 VALUEARRAYTYPENAME *valueArray) \ 194 { \ 195 int numElements = hash->numElements; \ 196 int arrayNdx = 0; \ 197 int slotNdx; \ 198 \ 199 if ((keyArray && !KEYARRAYTYPENAME##_setSize(keyArray, numElements)) || \ 200 (valueArray && !VALUEARRAYTYPENAME##_setSize(valueArray, numElements))) \ 201 return false; \ 202 \ 203 for (slotNdx = 0; slotNdx < hash->slotTableSize; slotNdx++) \ 204 { \ 205 const HASHTYPENAME##Slot *slot = hash->slotTable[slotNdx]; \ 206 while (slot) \ 207 { \ 208 int elemNdx; \ 209 for (elemNdx = 0; elemNdx < slot->numUsed; elemNdx++) \ 210 { \ 211 if (keyArray) \ 212 KEYARRAYTYPENAME##_set(keyArray, arrayNdx, slot->keys[elemNdx]); \ 213 if (valueArray) \ 214 VALUEARRAYTYPENAME##_set(valueArray, arrayNdx, slot->values[elemNdx]); \ 215 arrayNdx++; \ 216 } \ 217 slot = slot->nextSlot; \ 218 } \ 219 } \ 220 DE_ASSERT(arrayNdx == numElements); \ 221 return true; \ 222 } \ 223 struct HASHTYPENAME##_##KEYARRAYTYPENAME##_##VALUEARRAYTYPENAME##_implement_unused \ 224 { \ 225 int unused; \ 226 } 227 228 #endif 229 230 #endif /* _DEPOOLHASHSET_H */ 231