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