1 #ifndef _DEPOOLHASHARRAY_H 2 #define _DEPOOLHASHARRAY_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-array class. 24 *//*--------------------------------------------------------------------*/ 25 26 #include "deDefs.h" 27 #include "dePoolHash.h" 28 #include "dePoolArray.h" 29 30 DE_BEGIN_EXTERN_C 31 32 void dePoolHashArray_selfTest(void); 33 34 DE_END_EXTERN_C 35 36 /*--------------------------------------------------------------------*//*! 37 * \brief Declare a template pool hash-array (array with hash) class interface. 38 * \param TYPENAME Type name of the declared hash-array. 39 * \param KEYTYPE Type of the key. 40 * \param VALUETYPE Type of the value. 41 * \param KEYARRAYTYPE Type of the key array. 42 * \param VALUEARRAYTYPE Type of the value array. 43 * 44 * \todo [petri] Description. 45 * 46 * The functions for operating the hash are: 47 * \todo [petri] Figure out how to comment these in Doxygen-style. 48 * 49 * \todo [pyry] HashArray_find() will break if dePoolArray implementation changes. 50 * 51 * \code 52 * HashArray* HashArray_create (deMemPool* pool); 53 * int HashArray_getNumElements (const HashArray* hashArray); 54 * Value* HashArray_find (Hash* hashArray, Key key); 55 * bool HashArray_insert (Hash* hashArray, Key key, Value value); 56 * bool HashArray_copyToArray (Hash* hashArray, KeyArray* keys, ValueArray* values); 57 * \endcode 58 *//*--------------------------------------------------------------------*/ 59 #define DE_DECLARE_POOL_HASH_ARRAY(TYPENAME, KEYTYPE, VALUETYPE, KEYARRAYTYPE, VALUEARRAYTYPE) \ 60 \ 61 DE_DECLARE_POOL_ARRAY(TYPENAME##Array, VALUETYPE); \ 62 DE_DECLARE_POOL_HASH(TYPENAME##Hash, KEYTYPE, int); \ 63 \ 64 typedef struct TYPENAME_s \ 65 { \ 66 TYPENAME##Hash *hash; \ 67 TYPENAME##Array *array; \ 68 } TYPENAME; /* NOLINT(TYPENAME) */ \ 69 \ 70 TYPENAME *TYPENAME##_create(deMemPool *pool); \ 71 bool TYPENAME##_insert(DE_PTR_TYPE(TYPENAME) hashArray, KEYTYPE key, VALUETYPE value); \ 72 bool TYPENAME##_copyToArray(const TYPENAME *hashArray, DE_PTR_TYPE(KEYARRAYTYPE) keys, \ 73 DE_PTR_TYPE(VALUEARRAYTYPE) values); \ 74 \ 75 DE_INLINE int TYPENAME##_getNumElements(const TYPENAME *hashArray) DE_UNUSED_FUNCTION; \ 76 DE_INLINE VALUETYPE *TYPENAME##_find(const TYPENAME *hashArray, KEYTYPE key) DE_UNUSED_FUNCTION; \ 77 DE_INLINE void TYPENAME##_reset(DE_PTR_TYPE(TYPENAME) hashArray) DE_UNUSED_FUNCTION; \ 78 \ 79 DE_INLINE int TYPENAME##_getNumElements(const TYPENAME *hashArray) \ 80 { \ 81 return TYPENAME##Array_getNumElements(hashArray->array); \ 82 } \ 83 \ 84 DE_INLINE VALUETYPE *TYPENAME##_find(const TYPENAME *hashArray, KEYTYPE key) \ 85 { \ 86 int *ndxPtr = TYPENAME##Hash_find(hashArray->hash, key); \ 87 if (!ndxPtr) \ 88 return DE_NULL; \ 89 else \ 90 { \ 91 int ndx = *ndxPtr; \ 92 DE_ASSERT(ndx >= 0 && ndx < hashArray->array->numElements); \ 93 { \ 94 int pageNdx = (ndx >> DE_ARRAY_ELEMENTS_PER_PAGE_LOG2); \ 95 int subNdx = ndx & ((1 << DE_ARRAY_ELEMENTS_PER_PAGE_LOG2) - 1); \ 96 return &((VALUETYPE *)hashArray->array->pageTable[pageNdx])[subNdx]; \ 97 } \ 98 } \ 99 } \ 100 \ 101 DE_INLINE void TYPENAME##_reset(DE_PTR_TYPE(TYPENAME) hashArray) \ 102 { \ 103 TYPENAME##Hash_reset(hashArray->hash); \ 104 TYPENAME##Array_reset(hashArray->array); \ 105 } \ 106 \ 107 struct TYPENAME##Unused_s \ 108 { \ 109 int unused; \ 110 } 111 112 /*--------------------------------------------------------------------*//*! 113 * \brief Implement a template pool hash-array class. 114 * \param TYPENAME Type name of the declared hash. 115 * \param KEYTYPE Type of the key. 116 * \param VALUETYPE Type of the value. 117 * \param KEYARRAYTYPE Type of the key array. 118 * \param VALUEARRAYTYPE Type of the value array. 119 * \param HASHFUNC Function used for hashing the key. 120 * \param CMPFUNC Function used for exact matching of the keys. 121 * 122 * This macro has implements the hash declared with DE_DECLARE_POOL_HASH. 123 * Usually this macro should be used from a .c file, since the macro expands 124 * into multiple functions. The TYPENAME, KEYTYPE, and VALUETYPE parameters 125 * must match those of the declare macro. 126 *//*--------------------------------------------------------------------*/ 127 #define DE_IMPLEMENT_POOL_HASH_ARRAY(TYPENAME, KEYTYPE, VALUETYPE, KEYARRAYTYPE, VALUEARRAYTYPE, KEYHASHFUNC, \ 128 KEYCMPFUNC) \ 129 \ 130 DE_IMPLEMENT_POOL_HASH(TYPENAME##Hash, KEYTYPE, int, KEYHASHFUNC, KEYCMPFUNC); \ 131 \ 132 TYPENAME *TYPENAME##_create(deMemPool *pool) \ 133 { \ 134 DE_PTR_TYPE(TYPENAME) hashArray = DE_POOL_NEW(pool, TYPENAME); \ 135 if (!hashArray) \ 136 return DE_NULL; \ 137 if ((hashArray->hash = TYPENAME##Hash_create(pool)) == DE_NULL) \ 138 return DE_NULL; \ 139 if ((hashArray->array = TYPENAME##Array_create(pool)) == DE_NULL) \ 140 return DE_NULL; \ 141 return hashArray; \ 142 } \ 143 \ 144 bool TYPENAME##_insert(DE_PTR_TYPE(TYPENAME) hashArray, KEYTYPE key, VALUETYPE value) \ 145 { \ 146 int numElements = TYPENAME##Array_getNumElements(hashArray->array); \ 147 DE_ASSERT(TYPENAME##Hash_getNumElements(hashArray->hash) == numElements); \ 148 DE_ASSERT(!TYPENAME##Hash_find(hashArray->hash, key)); \ 149 if (!TYPENAME##Array_setSize(hashArray->array, numElements + 1) || \ 150 !TYPENAME##Hash_insert(hashArray->hash, key, numElements)) \ 151 return false; \ 152 TYPENAME##Array_set(hashArray->array, numElements, value); \ 153 return true; \ 154 } \ 155 \ 156 bool TYPENAME##_copyToArray(const TYPENAME *hashArray, DE_PTR_TYPE(KEYARRAYTYPE) keys, \ 157 DE_PTR_TYPE(VALUEARRAYTYPE) values) \ 158 { \ 159 int numElements = TYPENAME##Array_getNumElements(hashArray->array); \ 160 TYPENAME##Hash *hash = hashArray->hash; \ 161 TYPENAME##HashIter iter; \ 162 DE_ASSERT(TYPENAME##Hash_getNumElements(hashArray->hash) == numElements); \ 163 if ((keys && !KEYARRAYTYPE##_setSize(keys, numElements)) || \ 164 (values && !VALUEARRAYTYPE##_setSize(values, numElements))) \ 165 return false; \ 166 for (TYPENAME##HashIter_init(hash, &iter); TYPENAME##HashIter_hasItem(&iter); TYPENAME##HashIter_next(&iter)) \ 167 { \ 168 KEYTYPE key = TYPENAME##HashIter_getKey(&iter); \ 169 int ndx = TYPENAME##HashIter_getValue(&iter); \ 170 if (keys) \ 171 KEYARRAYTYPE##_set(keys, ndx, key); \ 172 if (values) \ 173 VALUEARRAYTYPE##_set(values, ndx, TYPENAME##Array_get(hashArray->array, ndx)); \ 174 } \ 175 return true; \ 176 } \ 177 \ 178 struct TYPENAME##Unused2_s \ 179 { \ 180 int unused; \ 181 } 182 183 #endif /* _DEPOOLHASHARRAY_H */ 184