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
30DE_BEGIN_EXTERN_C
31
32void	dePoolHashSet_selfTest		(void);
33
34DE_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 * deBool      HashSet_insert            (HashSet* hashSet, Key key, Value value);
53 * void        HashSet_delete            (HashSet* hashSet, Key key, Value value);
54 * deBool      HashSet_exists            (const HashSet* hashSet, Key key, Value value);
55 * \endcode
56*//*--------------------------------------------------------------------*/
57#define DE_DECLARE_POOL_HASH_SET(TYPENAME, KEYTYPE, VALUETYPE)										\
58																									\
59DE_DECLARE_POOL_SET(TYPENAME##Set, VALUETYPE);														\
60DE_DECLARE_POOL_HASH(TYPENAME##Hash, KEYTYPE, TYPENAME##Set*);										\
61typedef struct TYPENAME##_s																			\
62{																									\
63	TYPENAME##Hash*	hash;																			\
64} TYPENAME;																							\
65																									\
66DE_INLINE TYPENAME*			TYPENAME##_create			(deMemPool* pool);							\
67DE_INLINE int				TYPENAME##_getNumElements	(const TYPENAME* hashSet)								DE_UNUSED_FUNCTION;	\
68DE_INLINE TYPENAME##Hash*	TYPENAME##_getHash			(const TYPENAME* hashSet)								DE_UNUSED_FUNCTION;	\
69DE_INLINE deBool			TYPENAME##_insert			(TYPENAME* hashSet, KEYTYPE key, VALUETYPE value)		DE_UNUSED_FUNCTION;	\
70DE_INLINE deBool			TYPENAME##_safeInsert		(TYPENAME* hashSet, KEYTYPE key, VALUETYPE value)		DE_UNUSED_FUNCTION;	\
71DE_INLINE TYPENAME##Set*	TYPENAME##_find				(const TYPENAME* hashSet, KEYTYPE key)					DE_UNUSED_FUNCTION;	\
72DE_INLINE void				TYPENAME##_delete			(TYPENAME* hashSet, KEYTYPE key, VALUETYPE value)		DE_UNUSED_FUNCTION;	\
73DE_INLINE deBool			TYPENAME##_exists			(const TYPENAME* hashSet, KEYTYPE key, VALUETYPE value)	DE_UNUSED_FUNCTION;	\
74																									\
75DE_INLINE TYPENAME* TYPENAME##_create (deMemPool* pool)												\
76{																									\
77	TYPENAME* hashSet = DE_POOL_NEW(pool, TYPENAME);												\
78	if (!hashSet) return DE_NULL;																	\
79	if ((hashSet->hash = TYPENAME##Hash_create(pool)) == DE_NULL)									\
80		return DE_NULL;																				\
81	return hashSet;																					\
82}																									\
83																									\
84DE_INLINE int TYPENAME##_getNumElements (const TYPENAME* hashSet)									\
85{																									\
86	return TYPENAME##Hash_getNumElements(hashSet->hash);											\
87}																									\
88																									\
89DE_INLINE TYPENAME##Hash* TYPENAME##_getHash (const TYPENAME* hashSet)								\
90{																									\
91	return hashSet->hash;																			\
92}																									\
93																									\
94DE_INLINE deBool TYPENAME##_insert (TYPENAME* hashSet, KEYTYPE key, VALUETYPE value)				\
95{																									\
96	TYPENAME##Set**	setPtr	= TYPENAME##Hash_find(hashSet->hash, key);								\
97	TYPENAME##Set*	set		= setPtr ? *setPtr : DE_NULL;											\
98	if (!set)																						\
99	{																								\
100		set = TYPENAME##Set_create(hashSet->hash->pool);											\
101		if (!set) return DE_FALSE;																	\
102		if (!TYPENAME##Set_insert(set, value)) return DE_FALSE;										\
103		return TYPENAME##Hash_insert(hashSet->hash, key, set);										\
104	}																								\
105	else																							\
106	{																								\
107		return TYPENAME##Set_insert(set, value);													\
108	}																								\
109}																									\
110																									\
111DE_INLINE deBool TYPENAME##_safeInsert (TYPENAME* hashSet, KEYTYPE key, VALUETYPE value)			\
112{																									\
113	TYPENAME##Set**	setPtr	= TYPENAME##Hash_find(hashSet->hash, key);								\
114	TYPENAME##Set*	set		= setPtr ? *setPtr : DE_NULL;											\
115	if (!set)																						\
116	{																								\
117		return TYPENAME##_insert(hashSet, key, value);												\
118	}																								\
119	else																							\
120	{																								\
121		return TYPENAME##Set_safeInsert(set, value);												\
122	}																								\
123}																									\
124																									\
125DE_INLINE TYPENAME##Set* TYPENAME##_find (const TYPENAME* hashSet, KEYTYPE key)						\
126{																									\
127	TYPENAME##Set** setPtr = TYPENAME##Hash_find(hashSet->hash, key);								\
128	return setPtr ? *setPtr : DE_NULL;																\
129}																									\
130																									\
131DE_INLINE void TYPENAME##_delete (TYPENAME* hashSet, KEYTYPE key, VALUETYPE value)					\
132{																									\
133	TYPENAME##Set**	setPtr = TYPENAME##Hash_find(hashSet->hash, key);								\
134	TYPENAME##Set*	set;																			\
135	DE_ASSERT(setPtr);																				\
136	set = *setPtr;																					\
137	TYPENAME##Set_delete(set, value);																\
138}																									\
139																									\
140DE_INLINE deBool TYPENAME##_exists (const TYPENAME* hashSet, KEYTYPE key, VALUETYPE value)			\
141{																									\
142	TYPENAME##Set** setPtr = TYPENAME##Hash_find(hashSet->hash, key);								\
143	if (setPtr)																						\
144		return TYPENAME##Set_exists(*setPtr, value);												\
145	else																							\
146		return DE_FALSE;																			\
147}																									\
148																									\
149struct TYPENAME##Dummy_s { int dummy; }
150
151/*--------------------------------------------------------------------*//*!
152 * \brief Implement a template pool hash-set class.
153 * \param TYPENAME	Type name of the declared hash.
154 * \param KEYTYPE	Type of the key.
155 * \param VALUETYPE	Type of the value.
156 * \param HASHFUNC	Function used for hashing the key.
157 * \param CMPFUNC	Function used for exact matching of the keys.
158 *
159 * This macro has implements the hash declared with DE_DECLARE_POOL_HASH.
160 * Usually this macro should be used from a .c file, since the macro expands
161 * into multiple functions. The TYPENAME, KEYTYPE, and VALUETYPE parameters
162 * must match those of the declare macro.
163*//*--------------------------------------------------------------------*/
164#define DE_IMPLEMENT_POOL_HASH_SET(TYPENAME, KEYTYPE, VALUETYPE, KEYHASHFUNC, KEYCMPFUNC, VALUEHASHFUNC, VALUECMPFUNC)	\
165DE_IMPLEMENT_POOL_SET(TYPENAME##Set, VALUETYPE, VALUEHASHFUNC, VALUECMPFUNC);											\
166DE_IMPLEMENT_POOL_HASH(TYPENAME##Hash, KEYTYPE, TYPENAME##Set*, KEYHASHFUNC, KEYCMPFUNC);								\
167struct TYPENAME##Dummy2_s { int dummy; }
168
169/* Copy-to-array templates. */
170
171#if 0
172
173#define DE_DECLARE_POOL_HASH_TO_ARRAY(HASHTYPENAME, KEYARRAYTYPENAME, VALUEARRAYTYPENAME)		\
174	deBool HASHTYPENAME##_copyToArray(const HASHTYPENAME* set, KEYARRAYTYPENAME* keyArray, VALUEARRAYTYPENAME* valueArray);	\
175	struct HASHTYPENAME##_##KEYARRAYTYPENAME##_##VALUEARRAYTYPENAME##_declare_dummy { int dummy; }
176
177#define DE_IMPLEMENT_POOL_HASH_TO_ARRAY(HASHTYPENAME, KEYARRAYTYPENAME, VALUEARRAYTYPENAME)		\
178deBool HASHTYPENAME##_copyToArray(const HASHTYPENAME* hash, KEYARRAYTYPENAME* keyArray, VALUEARRAYTYPENAME* valueArray)	\
179{	\
180	int numElements	= hash->numElements;	\
181	int arrayNdx	= 0;	\
182	int slotNdx;	\
183	\
184	if ((keyArray && !KEYARRAYTYPENAME##_setSize(keyArray, numElements)) ||			\
185		(valueArray && !VALUEARRAYTYPENAME##_setSize(valueArray, numElements)))		\
186		return DE_FALSE;	\
187	\
188	for (slotNdx = 0; slotNdx < hash->slotTableSize; slotNdx++) \
189	{ \
190		const HASHTYPENAME##Slot* slot = hash->slotTable[slotNdx]; \
191		while (slot) \
192		{ \
193			int elemNdx; \
194			for (elemNdx = 0; elemNdx < slot->numUsed; elemNdx++) \
195			{	\
196				if (keyArray)	\
197					KEYARRAYTYPENAME##_set(keyArray, arrayNdx, slot->keys[elemNdx]); \
198				if (valueArray)	\
199					VALUEARRAYTYPENAME##_set(valueArray, arrayNdx, slot->values[elemNdx]);	\
200				arrayNdx++;	\
201			} \
202			slot = slot->nextSlot; \
203		} \
204	}	\
205	DE_ASSERT(arrayNdx == numElements);	\
206	return DE_TRUE;	\
207}	\
208struct HASHTYPENAME##_##KEYARRAYTYPENAME##_##VALUEARRAYTYPENAME##_implement_dummy { int dummy; }
209
210#endif
211
212#endif /* _DEPOOLHASHSET_H */
213