1 #ifndef _DEPOOLHASH_H
2 #define _DEPOOLHASH_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 class.
24  *//*--------------------------------------------------------------------*/
25 
26 #include "deDefs.h"
27 #include "deMemPool.h"
28 #include "dePoolArray.h"
29 #include "deInt32.h"
30 
31 #include <string.h> /* memset() */
32 
33 enum
34 {
35 	DE_HASH_ELEMENTS_PER_SLOT	= 4
36 };
37 
38 DE_BEGIN_EXTERN_C
39 
40 void	dePoolHash_selfTest		(void);
41 
42 DE_END_EXTERN_C
43 
44 /*--------------------------------------------------------------------*//*!
45  * \brief Declare a template pool hash class interface.
46  * \param TYPENAME	Type name of the declared hash.
47  * \param KEYTYPE	Type of the key.
48  * \param VALUETYPE	Type of the value.
49  *
50  * This macro declares the interface for a hash. For the implementation of
51  * the hash, see DE_IMPLEMENT_POOL_HASH. Usually this macro is put into the
52  * header file and the implementation macro is put in some .c file.
53  *
54  * \todo [petri] Detailed description.
55  *
56  * The functions for operating the hash are:
57  * \todo [petri] Figure out how to comment these in Doxygen-style.
58  *
59  * \code
60  * Hash*    Hash_create            (deMemPool* pool);
61  * int      Hash_getNumElements    (const Hash* hash);
62  * Value*   Hash_find              (Hash* hash, Key key);
63  * deBool   Hash_insert            (Hash* hash, Key key, Value value);
64  * void     Hash_delete            (Hash* hash, Key key);
65  * \endcode
66 *//*--------------------------------------------------------------------*/
67 #define DE_DECLARE_POOL_HASH(TYPENAME, KEYTYPE, VALUETYPE)		\
68 \
69 typedef struct TYPENAME##Slot_s TYPENAME##Slot;    \
70 \
71 struct TYPENAME##Slot_s \
72 {    \
73 	int				numUsed; \
74 	TYPENAME##Slot*	nextSlot; \
75 	KEYTYPE			keys[DE_HASH_ELEMENTS_PER_SLOT]; \
76 	VALUETYPE		values[DE_HASH_ELEMENTS_PER_SLOT]; \
77 }; \
78 \
79 typedef struct TYPENAME##_s    \
80 {    \
81 	deMemPool*			pool;				\
82 	int					numElements;		\
83 \
84 	int					slotTableSize;		\
85 	TYPENAME##Slot**	slotTable;			\
86 	TYPENAME##Slot*		slotFreeList;		\
87 } TYPENAME;    \
88 \
89 typedef struct TYPENAME##Iter_s \
90 {	\
91 	const TYPENAME*			hash;			\
92 	int						curSlotIndex;	\
93 	const TYPENAME##Slot*	curSlot;		\
94 	int						curElemIndex;	\
95 } TYPENAME##Iter;	\
96 \
97 TYPENAME*	TYPENAME##_create	(deMemPool* pool);    \
98 void		TYPENAME##_reset	(TYPENAME* hash);    \
99 deBool		TYPENAME##_reserve	(TYPENAME* hash, int capacity);    \
100 VALUETYPE*	TYPENAME##_find		(const TYPENAME* hash, KEYTYPE key);    \
101 deBool		TYPENAME##_insert	(TYPENAME* hash, KEYTYPE key, VALUETYPE value);    \
102 void		TYPENAME##_delete	(TYPENAME* hash, KEYTYPE key);    \
103 \
104 DE_INLINE int		TYPENAME##_getNumElements	(const TYPENAME* hash)							DE_UNUSED_FUNCTION;	\
105 DE_INLINE void		TYPENAME##Iter_init			(const TYPENAME* hash, TYPENAME##Iter* iter)	DE_UNUSED_FUNCTION;	\
106 DE_INLINE deBool	TYPENAME##Iter_hasItem		(const TYPENAME##Iter* iter)					DE_UNUSED_FUNCTION;	\
107 DE_INLINE void		TYPENAME##Iter_next			(TYPENAME##Iter* iter)							DE_UNUSED_FUNCTION;	\
108 DE_INLINE KEYTYPE	TYPENAME##Iter_getKey		(const TYPENAME##Iter* iter)					DE_UNUSED_FUNCTION;	\
109 DE_INLINE VALUETYPE	TYPENAME##Iter_getValue		(const TYPENAME##Iter* iter)					DE_UNUSED_FUNCTION;	\
110 \
111 DE_INLINE int TYPENAME##_getNumElements (const TYPENAME* hash)    \
112 {    \
113 	return hash->numElements;    \
114 }    \
115 \
116 DE_INLINE void TYPENAME##Iter_init (const TYPENAME* hash, TYPENAME##Iter* iter)    \
117 {	\
118 	iter->hash			= hash;		\
119 	iter->curSlotIndex	= 0;		\
120 	iter->curSlot		= DE_NULL;	\
121 	iter->curElemIndex	= 0;		\
122 	if (TYPENAME##_getNumElements(hash) > 0)		\
123 	{												\
124 		int slotTableSize	= hash->slotTableSize;	\
125 		int slotNdx			= 0;					\
126 		while (slotNdx < slotTableSize)				\
127 		{											\
128 			if (hash->slotTable[slotNdx])			\
129 				break;								\
130 			slotNdx++;								\
131 		}											\
132 		DE_ASSERT(slotNdx < slotTableSize);			\
133 		iter->curSlotIndex = slotNdx;				\
134 		iter->curSlot = hash->slotTable[slotNdx];	\
135 		DE_ASSERT(iter->curSlot);					\
136 	}	\
137 }	\
138 \
139 DE_INLINE deBool TYPENAME##Iter_hasItem (const TYPENAME##Iter* iter)    \
140 {	\
141 	return (iter->curSlot != DE_NULL); \
142 }	\
143 \
144 DE_INLINE void TYPENAME##Iter_next (TYPENAME##Iter* iter)    \
145 {	\
146 	DE_ASSERT(TYPENAME##Iter_hasItem(iter));	\
147 	if (++iter->curElemIndex == iter->curSlot->numUsed)	\
148 	{													\
149 		iter->curElemIndex = 0;							\
150 		if (iter->curSlot->nextSlot)					\
151 		{												\
152 			iter->curSlot = iter->curSlot->nextSlot;	\
153 		}												\
154 		else											\
155 		{												\
156 			const TYPENAME*	hash			= iter->hash;			\
157 			int				curSlotIndex	= iter->curSlotIndex;	\
158 			int				slotTableSize	= hash->slotTableSize;	\
159 			while (++curSlotIndex < slotTableSize)		\
160 			{											\
161 				if (hash->slotTable[curSlotIndex])		\
162 					break;								\
163 			}											\
164 			iter->curSlotIndex = curSlotIndex;			\
165 			if (curSlotIndex < slotTableSize)					\
166 				iter->curSlot = hash->slotTable[curSlotIndex];	\
167 			else												\
168 				iter->curSlot = DE_NULL;						\
169 		}	\
170 	}	\
171 }	\
172 \
173 DE_INLINE KEYTYPE TYPENAME##Iter_getKey	(const TYPENAME##Iter* iter)    \
174 {	\
175 	DE_ASSERT(TYPENAME##Iter_hasItem(iter));	\
176 	return iter->curSlot->keys[iter->curElemIndex];	\
177 }	\
178 \
179 DE_INLINE VALUETYPE	TYPENAME##Iter_getValue	(const TYPENAME##Iter* iter)    \
180 {	\
181 	DE_ASSERT(TYPENAME##Iter_hasItem(iter));	\
182 	return iter->curSlot->values[iter->curElemIndex];	\
183 }	\
184 \
185 struct TYPENAME##Dummy_s { int dummy; }
186 
187 /*--------------------------------------------------------------------*//*!
188  * \brief Implement a template pool hash class.
189  * \param TYPENAME	Type name of the declared hash.
190  * \param KEYTYPE	Type of the key.
191  * \param VALUETYPE	Type of the value.
192  * \param HASHFUNC	Function used for hashing the key.
193  * \param CMPFUNC	Function used for exact matching of the keys.
194  *
195  * This macro has implements the hash declared with DE_DECLARE_POOL_HASH.
196  * Usually this macro should be used from a .c file, since the macro expands
197  * into multiple functions. The TYPENAME, KEYTYPE, and VALUETYPE parameters
198  * must match those of the declare macro.
199 *//*--------------------------------------------------------------------*/
200 #define DE_IMPLEMENT_POOL_HASH(TYPENAME, KEYTYPE, VALUETYPE, HASHFUNC, CMPFUNC)		\
201 \
202 TYPENAME* TYPENAME##_create (deMemPool* pool)    \
203 {   \
204 	/* Alloc struct. */ \
205 	TYPENAME* hash = DE_POOL_NEW(pool, TYPENAME); \
206 	if (!hash) \
207 		return DE_NULL; \
208 \
209 	memset(hash, 0, sizeof(TYPENAME)); \
210 	hash->pool = pool; \
211 \
212 	return hash; \
213 } \
214 \
215 void TYPENAME##_reset (TYPENAME* hash)    \
216 {   \
217 	int slotNdx; \
218 	for (slotNdx = 0; slotNdx < hash->slotTableSize; slotNdx++)	\
219 	{	\
220 		TYPENAME##Slot* slot = hash->slotTable[slotNdx]; \
221 		while (slot) \
222 		{ \
223 			TYPENAME##Slot*	nextSlot = slot->nextSlot;	\
224 			slot->nextSlot = hash->slotFreeList;		\
225 			hash->slotFreeList = slot;	\
226 			slot->numUsed = 0;			\
227 			slot = nextSlot;			\
228 		}	\
229 		hash->slotTable[slotNdx] = DE_NULL; \
230 	}	\
231 	hash->numElements = 0; \
232 }	\
233 \
234 TYPENAME##Slot* TYPENAME##_allocSlot (TYPENAME* hash)    \
235 {   \
236 	TYPENAME##Slot* slot; \
237 	if (hash->slotFreeList) \
238 	{ \
239 		slot = hash->slotFreeList; \
240 		hash->slotFreeList = hash->slotFreeList->nextSlot; \
241 	} \
242 	else \
243 		slot = (TYPENAME##Slot*)deMemPool_alloc(hash->pool, sizeof(TYPENAME##Slot) * DE_HASH_ELEMENTS_PER_SLOT); \
244 \
245 	if (slot) \
246 	{ \
247 		slot->nextSlot = DE_NULL; \
248 		slot->numUsed = 0; \
249 	} \
250 \
251 	return slot; \
252 } \
253 \
254 deBool TYPENAME##_rehash (TYPENAME* hash, int newSlotTableSize)    \
255 {    \
256 	DE_ASSERT(deIsPowerOfTwo32(newSlotTableSize) && newSlotTableSize > 0); \
257 	if (newSlotTableSize > hash->slotTableSize)    \
258 	{ \
259 		TYPENAME##Slot**	oldSlotTable = hash->slotTable; \
260 		TYPENAME##Slot**	newSlotTable = (TYPENAME##Slot**)deMemPool_alloc(hash->pool, sizeof(TYPENAME##Slot*) * (size_t)newSlotTableSize); \
261 		int					oldSlotTableSize = hash->slotTableSize; \
262 		int					slotNdx; \
263 \
264 		if (!newSlotTable) \
265 			return DE_FALSE; \
266 \
267 		for (slotNdx = 0; slotNdx < oldSlotTableSize; slotNdx++) \
268 			newSlotTable[slotNdx] = oldSlotTable[slotNdx]; \
269 \
270 		for (slotNdx = oldSlotTableSize; slotNdx < newSlotTableSize; slotNdx++) \
271 			newSlotTable[slotNdx] = DE_NULL; \
272 \
273 		hash->slotTableSize		= newSlotTableSize; \
274 		hash->slotTable			= newSlotTable; \
275 \
276 		for (slotNdx = 0; slotNdx < oldSlotTableSize; slotNdx++) \
277 		{ \
278 			TYPENAME##Slot* slot = oldSlotTable[slotNdx]; \
279 			newSlotTable[slotNdx] = DE_NULL; \
280 			while (slot) \
281 			{ \
282 				int elemNdx; \
283 				for (elemNdx = 0; elemNdx < slot->numUsed; elemNdx++) \
284 				{ \
285 					hash->numElements--; \
286 					if (!TYPENAME##_insert(hash, slot->keys[elemNdx], slot->values[elemNdx])) \
287 						return DE_FALSE; \
288 				} \
289 				slot = slot->nextSlot; \
290 			} \
291 		} \
292 	} \
293 \
294 	return DE_TRUE;    \
295 }    \
296 \
297 VALUETYPE* TYPENAME##_find (const TYPENAME* hash, KEYTYPE key)    \
298 {    \
299 	if (hash->numElements > 0) \
300 	{	\
301 		int				slotNdx	= (int)(HASHFUNC(key) & (deUint32)(hash->slotTableSize - 1)); \
302 		TYPENAME##Slot*	slot	= hash->slotTable[slotNdx]; \
303 		DE_ASSERT(deInBounds32(slotNdx, 0, hash->slotTableSize)); \
304 	\
305 		while (slot) \
306 		{ \
307 			int elemNdx; \
308 			for (elemNdx = 0; elemNdx < slot->numUsed; elemNdx++) \
309 			{ \
310 				if (CMPFUNC(slot->keys[elemNdx], key)) \
311 					return &slot->values[elemNdx]; \
312 			} \
313 			slot = slot->nextSlot; \
314 		} \
315 	} \
316 \
317 	return DE_NULL; \
318 }    \
319 \
320 deBool TYPENAME##_insert (TYPENAME* hash, KEYTYPE key, VALUETYPE value)    \
321 {    \
322 	int				slotNdx; \
323 	TYPENAME##Slot*	slot; \
324 \
325 	DE_ASSERT(!TYPENAME##_find(hash, key));	\
326 \
327 	if ((hash->numElements + 1) >= hash->slotTableSize * DE_HASH_ELEMENTS_PER_SLOT) \
328 		if (!TYPENAME##_rehash(hash, deMax32(4, 2*hash->slotTableSize))) \
329 			return DE_FALSE; \
330 \
331 	slotNdx	= (int)(HASHFUNC(key) & (deUint32)(hash->slotTableSize - 1)); \
332 	DE_ASSERT(slotNdx >= 0 && slotNdx < hash->slotTableSize); \
333 	slot	= hash->slotTable[slotNdx]; \
334 \
335 	if (!slot) \
336 	{ \
337 		slot = TYPENAME##_allocSlot(hash); \
338 		if (!slot) return DE_FALSE; \
339 		hash->slotTable[slotNdx] = slot; \
340 	} \
341 \
342 	for (;;) \
343 	{ \
344 		if (slot->numUsed == DE_HASH_ELEMENTS_PER_SLOT) \
345 		{ \
346 			if (slot->nextSlot) \
347 				slot = slot->nextSlot; \
348 			else \
349 			{ \
350 				TYPENAME##Slot* nextSlot = TYPENAME##_allocSlot(hash); \
351 				if (!nextSlot) return DE_FALSE; \
352 				slot->nextSlot = nextSlot; \
353 				slot = nextSlot; \
354 			} \
355 		} \
356 		else \
357 		{ \
358 			slot->keys[slot->numUsed]	= key; \
359 			slot->values[slot->numUsed]	= value; \
360 			slot->numUsed++; \
361 			hash->numElements++; \
362 			return DE_TRUE; \
363 		} \
364 	} \
365 } \
366 \
367 void TYPENAME##_delete (TYPENAME* hash, KEYTYPE key)    \
368 {    \
369 	int				slotNdx; \
370 	TYPENAME##Slot*	slot; \
371 	TYPENAME##Slot*	prevSlot = DE_NULL; \
372 \
373 	DE_ASSERT(hash->numElements > 0); \
374 	slotNdx	= (int)(HASHFUNC(key) & (deUint32)(hash->slotTableSize - 1)); \
375 	DE_ASSERT(slotNdx >= 0 && slotNdx < hash->slotTableSize); \
376 	slot	= hash->slotTable[slotNdx]; \
377 	DE_ASSERT(slot); \
378 \
379 	for (;;) \
380 	{ \
381 		int elemNdx; \
382 		DE_ASSERT(slot->numUsed > 0); \
383 		for (elemNdx = 0; elemNdx < slot->numUsed; elemNdx++) \
384 		{ \
385 			if (CMPFUNC(slot->keys[elemNdx], key)) \
386 			{ \
387 				TYPENAME##Slot*	lastSlot = slot; \
388 				while (lastSlot->nextSlot) \
389 				{ \
390 					prevSlot = lastSlot; \
391 					lastSlot = lastSlot->nextSlot; \
392 				} \
393 \
394 				slot->keys[elemNdx]		= lastSlot->keys[lastSlot->numUsed-1]; \
395 				slot->values[elemNdx]	= lastSlot->values[lastSlot->numUsed-1]; \
396 				lastSlot->numUsed--; \
397 \
398 				if (lastSlot->numUsed == 0) \
399 				{ \
400 					if (prevSlot) \
401 						prevSlot->nextSlot = DE_NULL; \
402 					else \
403 						hash->slotTable[slotNdx] = DE_NULL; \
404 \
405 					lastSlot->nextSlot = hash->slotFreeList; \
406 					hash->slotFreeList = lastSlot; \
407 				} \
408 \
409 				hash->numElements--; \
410 				return; \
411 			} \
412 		} \
413 \
414 		prevSlot = slot; \
415 		slot = slot->nextSlot; \
416 		DE_ASSERT(slot); \
417 	} \
418 }    \
419 struct TYPENAME##Dummy2_s { int dummy; }
420 
421 /* Copy-to-array templates. */
422 
423 #define DE_DECLARE_POOL_HASH_TO_ARRAY(HASHTYPENAME, KEYARRAYTYPENAME, VALUEARRAYTYPENAME)		\
424 	deBool HASHTYPENAME##_copyToArray(const HASHTYPENAME* set, KEYARRAYTYPENAME* keyArray, VALUEARRAYTYPENAME* valueArray);	\
425 	struct HASHTYPENAME##_##KEYARRAYTYPENAME##_##VALUEARRAYTYPENAME##_declare_dummy { int dummy; }
426 
427 #define DE_IMPLEMENT_POOL_HASH_TO_ARRAY(HASHTYPENAME, KEYARRAYTYPENAME, VALUEARRAYTYPENAME)		\
428 deBool HASHTYPENAME##_copyToArray(const HASHTYPENAME* hash, KEYARRAYTYPENAME* keyArray, VALUEARRAYTYPENAME* valueArray)	\
429 {	\
430 	int numElements	= hash->numElements;	\
431 	int arrayNdx	= 0;	\
432 	int slotNdx;	\
433 	\
434 	if ((keyArray && !KEYARRAYTYPENAME##_setSize(keyArray, numElements)) ||			\
435 		(valueArray && !VALUEARRAYTYPENAME##_setSize(valueArray, numElements)))		\
436 		return DE_FALSE;	\
437 	\
438 	for (slotNdx = 0; slotNdx < hash->slotTableSize; slotNdx++) \
439 	{ \
440 		const HASHTYPENAME##Slot* slot = hash->slotTable[slotNdx]; \
441 		while (slot) \
442 		{ \
443 			int elemNdx; \
444 			for (elemNdx = 0; elemNdx < slot->numUsed; elemNdx++) \
445 			{	\
446 				if (keyArray)	\
447 					KEYARRAYTYPENAME##_set(keyArray, arrayNdx, slot->keys[elemNdx]); \
448 				if (valueArray)	\
449 					VALUEARRAYTYPENAME##_set(valueArray, arrayNdx, slot->values[elemNdx]);	\
450 				arrayNdx++;	\
451 			} \
452 			slot = slot->nextSlot; \
453 		} \
454 	}	\
455 	DE_ASSERT(arrayNdx == numElements);	\
456 	return DE_TRUE;	\
457 }	\
458 struct HASHTYPENAME##_##KEYARRAYTYPENAME##_##VALUEARRAYTYPENAME##_implement_dummy { int dummy; }
459 
460 #endif /* _DEPOOLHASH_H */
461