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
30DE_BEGIN_EXTERN_C
31
32void	dePoolHashArray_selfTest		(void);
33
34DE_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																									\
61DE_DECLARE_POOL_ARRAY(TYPENAME##Array, VALUETYPE);													\
62DE_DECLARE_POOL_HASH(TYPENAME##Hash, KEYTYPE, int);													\
63																									\
64typedef struct TYPENAME_s																			\
65{																									\
66	TYPENAME##Hash*		hash;																		\
67	TYPENAME##Array*	array;																		\
68} TYPENAME;																							\
69																									\
70TYPENAME*		TYPENAME##_create		(deMemPool* pool);											\
71deBool			TYPENAME##_insert		(TYPENAME* hashArray, KEYTYPE key, VALUETYPE value);		\
72deBool			TYPENAME##_copyToArray	(const TYPENAME* hashArray, KEYARRAYTYPE* keys, VALUEARRAYTYPE* values);	\
73																									\
74DE_INLINE int			TYPENAME##_getNumElements	(const TYPENAME* hashArray)					DE_UNUSED_FUNCTION;	\
75DE_INLINE VALUETYPE*	TYPENAME##_find				(const TYPENAME* hashArray, KEYTYPE key)	DE_UNUSED_FUNCTION;	\
76DE_INLINE void			TYPENAME##_reset			(TYPENAME* hashArray)						DE_UNUSED_FUNCTION;	\
77																									\
78DE_INLINE int TYPENAME##_getNumElements (const TYPENAME* hashArray)									\
79{																									\
80	return TYPENAME##Array_getNumElements(hashArray->array);										\
81}																									\
82																									\
83DE_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																									\
100DE_INLINE void TYPENAME##_reset (TYPENAME* hashArray)												\
101{																									\
102	TYPENAME##Hash_reset(hashArray->hash);															\
103	TYPENAME##Array_reset(hashArray->array);														\
104}																									\
105																									\
106struct 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																									\
125DE_IMPLEMENT_POOL_HASH(TYPENAME##Hash, KEYTYPE, int, KEYHASHFUNC, KEYCMPFUNC);						\
126																									\
127TYPENAME* TYPENAME##_create (deMemPool* pool)														\
128{																									\
129	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																									\
138deBool TYPENAME##_insert (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																									\
150deBool TYPENAME##_copyToArray (const TYPENAME* hashArray, KEYARRAYTYPE* keys, 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																									\
169struct TYPENAME##Dummy2_s { int dummy; }
170
171#endif /* _DEPOOLHASHARRAY_H */
172