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 * deBool HashArray_insert (Hash* hashArray, Key key, Value value); 56 * deBool 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 deBool TYPENAME##_insert (DE_PTR_TYPE(TYPENAME) hashArray, KEYTYPE key, VALUETYPE value); \ 72 deBool TYPENAME##_copyToArray (const TYPENAME* hashArray, DE_PTR_TYPE(KEYARRAYTYPE) keys, DE_PTR_TYPE(VALUEARRAYTYPE) values); \ 73 \ 74 DE_INLINE int TYPENAME##_getNumElements (const TYPENAME* hashArray) DE_UNUSED_FUNCTION; \ 75 DE_INLINE VALUETYPE* TYPENAME##_find (const TYPENAME* hashArray, KEYTYPE key) DE_UNUSED_FUNCTION; \ 76 DE_INLINE void TYPENAME##_reset (DE_PTR_TYPE(TYPENAME) hashArray) DE_UNUSED_FUNCTION; \ 77 \ 78 DE_INLINE int TYPENAME##_getNumElements (const TYPENAME* hashArray) \ 79 { \ 80 return TYPENAME##Array_getNumElements(hashArray->array); \ 81 } \ 82 \ 83 DE_INLINE VALUETYPE* TYPENAME##_find (const TYPENAME* hashArray, KEYTYPE key) \ 84 { \ 85 int* ndxPtr = TYPENAME##Hash_find(hashArray->hash, key); \ 86 if (!ndxPtr) \ 87 return DE_NULL; \ 88 else \ 89 { \ 90 int ndx = *ndxPtr; \ 91 DE_ASSERT(ndx >= 0 && ndx < hashArray->array->numElements); \ 92 { \ 93 int pageNdx = (ndx >> DE_ARRAY_ELEMENTS_PER_PAGE_LOG2); \ 94 int subNdx = ndx & ((1 << DE_ARRAY_ELEMENTS_PER_PAGE_LOG2) - 1); \ 95 return &((VALUETYPE*)hashArray->array->pageTable[pageNdx])[subNdx]; \ 96 } \ 97 } \ 98 } \ 99 \ 100 DE_INLINE void TYPENAME##_reset (DE_PTR_TYPE(TYPENAME) hashArray) \ 101 { \ 102 TYPENAME##Hash_reset(hashArray->hash); \ 103 TYPENAME##Array_reset(hashArray->array); \ 104 } \ 105 \ 106 struct TYPENAME##Dummy_s { int dummy; } 107 108 /*--------------------------------------------------------------------*//*! 109 * \brief Implement a template pool hash-array class. 110 * \param TYPENAME Type name of the declared hash. 111 * \param KEYTYPE Type of the key. 112 * \param VALUETYPE Type of the value. 113 * \param KEYARRAYTYPE Type of the key array. 114 * \param VALUEARRAYTYPE Type of the value array. 115 * \param HASHFUNC Function used for hashing the key. 116 * \param CMPFUNC Function used for exact matching of the keys. 117 * 118 * This macro has implements the hash declared with DE_DECLARE_POOL_HASH. 119 * Usually this macro should be used from a .c file, since the macro expands 120 * into multiple functions. The TYPENAME, KEYTYPE, and VALUETYPE parameters 121 * must match those of the declare macro. 122 *//*--------------------------------------------------------------------*/ 123 #define DE_IMPLEMENT_POOL_HASH_ARRAY(TYPENAME, KEYTYPE, VALUETYPE, KEYARRAYTYPE, VALUEARRAYTYPE, KEYHASHFUNC, KEYCMPFUNC) \ 124 \ 125 DE_IMPLEMENT_POOL_HASH(TYPENAME##Hash, KEYTYPE, int, KEYHASHFUNC, KEYCMPFUNC); \ 126 \ 127 TYPENAME* TYPENAME##_create (deMemPool* pool) \ 128 { \ 129 DE_PTR_TYPE(TYPENAME) hashArray = DE_POOL_NEW(pool, TYPENAME); \ 130 if (!hashArray) return DE_NULL; \ 131 if ((hashArray->hash = TYPENAME##Hash_create(pool)) == DE_NULL) \ 132 return DE_NULL; \ 133 if ((hashArray->array = TYPENAME##Array_create(pool)) == DE_NULL) \ 134 return DE_NULL; \ 135 return hashArray; \ 136 } \ 137 \ 138 deBool TYPENAME##_insert (DE_PTR_TYPE(TYPENAME) hashArray, KEYTYPE key, VALUETYPE value) \ 139 { \ 140 int numElements = TYPENAME##Array_getNumElements(hashArray->array); \ 141 DE_ASSERT(TYPENAME##Hash_getNumElements(hashArray->hash) == numElements); \ 142 DE_ASSERT(!TYPENAME##Hash_find(hashArray->hash, key)); \ 143 if (!TYPENAME##Array_setSize(hashArray->array, numElements+1) || \ 144 !TYPENAME##Hash_insert(hashArray->hash, key, numElements)) \ 145 return DE_FALSE; \ 146 TYPENAME##Array_set(hashArray->array, numElements, value); \ 147 return DE_TRUE; \ 148 } \ 149 \ 150 deBool TYPENAME##_copyToArray (const TYPENAME* hashArray, DE_PTR_TYPE(KEYARRAYTYPE) keys, DE_PTR_TYPE(VALUEARRAYTYPE) values) \ 151 { \ 152 int numElements = TYPENAME##Array_getNumElements(hashArray->array); \ 153 TYPENAME##Hash* hash = hashArray->hash; \ 154 TYPENAME##HashIter iter; \ 155 DE_ASSERT(TYPENAME##Hash_getNumElements(hashArray->hash) == numElements); \ 156 if ((keys && !KEYARRAYTYPE##_setSize(keys, numElements)) || \ 157 (values && !VALUEARRAYTYPE##_setSize(values, numElements))) \ 158 return DE_FALSE; \ 159 for (TYPENAME##HashIter_init(hash, &iter); TYPENAME##HashIter_hasItem(&iter); TYPENAME##HashIter_next(&iter)) \ 160 { \ 161 KEYTYPE key = TYPENAME##HashIter_getKey(&iter); \ 162 int ndx = TYPENAME##HashIter_getValue(&iter); \ 163 if (keys) KEYARRAYTYPE##_set(keys, ndx, key); \ 164 if (values) VALUEARRAYTYPE##_set(values, ndx, TYPENAME##Array_get(hashArray->array, ndx)); \ 165 } \ 166 return DE_TRUE; \ 167 } \ 168 \ 169 struct TYPENAME##Dummy2_s { int dummy; } 170 171 #endif /* _DEPOOLHASHARRAY_H */ 172