1 #ifndef _DEPOOLHASHARRAY_H
2 #define _DEPOOLHASHARRAY_H
3 /*-------------------------------------------------------------------------
4 * drawElements Memory Pool Library
5 * --------------------------------
7 * Copyright 2014 The Android Open Source Project
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
13 * http://www.apache.org/licenses/LICENSE-2.0
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.
23 * \brief Memory pool hash-array class.
24 *//*--------------------------------------------------------------------*/
27 #include "dePoolHash.h"
28 #include "dePoolArray.h"
32 void dePoolHashArray_selfTest (void);
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.
44 * \todo [petri] Description.
46 * The functions for operating the hash are:
47 * \todo [petri] Figure out how to comment these in Doxygen-style.
49 * \todo [pyry] HashArray_find() will break if dePoolArray implementation changes.
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);
58 *//*--------------------------------------------------------------------*/
59 #define DE_DECLARE_POOL_HASH_ARRAY(TYPENAME, KEYTYPE, VALUETYPE, KEYARRAYTYPE, VALUEARRAYTYPE) \
61 DE_DECLARE_POOL_ARRAY(TYPENAME##Array, VALUETYPE); \
62 DE_DECLARE_POOL_HASH(TYPENAME##Hash, KEYTYPE, int); \
64 typedef struct TYPENAME_s \
66 TYPENAME##Hash* hash; \
67 TYPENAME##Array* array; \
68 } TYPENAME; /* NOLINT(TYPENAME) */ \
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); \
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; \
78 DE_INLINE int TYPENAME##_getNumElements (const TYPENAME* hashArray) \
80 return TYPENAME##Array_getNumElements(hashArray->array); \
83 DE_INLINE VALUETYPE* TYPENAME##_find (const TYPENAME* hashArray, KEYTYPE key) \
85 int* ndxPtr = TYPENAME##Hash_find(hashArray->hash, key); \
91 DE_ASSERT(ndx >= 0 && ndx < hashArray->array->numElements); \
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]; \
100 DE_INLINE void TYPENAME##_reset (DE_PTR_TYPE(TYPENAME) hashArray) \
102 TYPENAME##Hash_reset(hashArray->hash); \
103 TYPENAME##Array_reset(hashArray->array); \
106 struct TYPENAME##Dummy_s { int dummy; }
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.
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) \
125 DE_IMPLEMENT_POOL_HASH(TYPENAME##Hash, KEYTYPE, int, KEYHASHFUNC, KEYCMPFUNC); \
127 TYPENAME* TYPENAME##_create (deMemPool* pool) \
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) \
133 if ((hashArray->array = TYPENAME##Array_create(pool)) == DE_NULL) \
138 deBool TYPENAME##_insert (DE_PTR_TYPE(TYPENAME) hashArray, KEYTYPE key, VALUETYPE value) \
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)) \
146 TYPENAME##Array_set(hashArray->array, numElements, value); \
150 deBool TYPENAME##_copyToArray (const TYPENAME* hashArray, DE_PTR_TYPE(KEYARRAYTYPE) keys, DE_PTR_TYPE(VALUEARRAYTYPE) values) \
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))) \
159 for (TYPENAME##HashIter_init(hash, &iter); TYPENAME##HashIter_hasItem(&iter); TYPENAME##HashIter_next(&iter)) \
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)); \
169 struct TYPENAME##Dummy2_s { int dummy; }
171 #endif /* _DEPOOLHASHARRAY_H */