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
33enum
34{
35	DE_HASH_ELEMENTS_PER_SLOT	= 4
36};
37
38DE_BEGIN_EXTERN_C
39
40void	dePoolHash_selfTest		(void);
41
42DE_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\
69typedef struct TYPENAME##Slot_s TYPENAME##Slot;    \
70\
71struct 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\
79typedef struct TYPENAME##_s    \
80{    \
81	deMemPool*			pool;				\
82	int					numElements;		\
83\
84	int					slotTableSize;		\
85	TYPENAME##Slot**	slotTable;			\
86	TYPENAME##Slot*		slotFreeList;		\
87} TYPENAME; /* NOLINT(TYPENAME) */			\
88\
89typedef struct TYPENAME##Iter_s \
90{	\
91	const TYPENAME*			hash;			\
92	int						curSlotIndex;	\
93	const TYPENAME##Slot*	curSlot;		\
94	int						curElemIndex;	\
95} TYPENAME##Iter;	\
96\
97TYPENAME*	TYPENAME##_create	(deMemPool* pool);											\
98void		TYPENAME##_reset	(DE_PTR_TYPE(TYPENAME) hash);								\
99deBool		TYPENAME##_reserve	(DE_PTR_TYPE(TYPENAME) hash, int capacity);					\
100VALUETYPE*	TYPENAME##_find		(const TYPENAME* hash, KEYTYPE key);						\
101deBool		TYPENAME##_insert	(DE_PTR_TYPE(TYPENAME) hash, KEYTYPE key, VALUETYPE value);	\
102void		TYPENAME##_delete	(DE_PTR_TYPE(TYPENAME) hash, KEYTYPE key);					\
103\
104DE_INLINE int		TYPENAME##_getNumElements	(const TYPENAME* hash)							DE_UNUSED_FUNCTION;	\
105DE_INLINE void		TYPENAME##Iter_init			(const TYPENAME* hash, TYPENAME##Iter* iter)	DE_UNUSED_FUNCTION;	\
106DE_INLINE deBool	TYPENAME##Iter_hasItem		(const TYPENAME##Iter* iter)					DE_UNUSED_FUNCTION;	\
107DE_INLINE void		TYPENAME##Iter_next			(TYPENAME##Iter* iter)							DE_UNUSED_FUNCTION;	\
108DE_INLINE KEYTYPE	TYPENAME##Iter_getKey		(const TYPENAME##Iter* iter)					DE_UNUSED_FUNCTION;	\
109DE_INLINE VALUETYPE	TYPENAME##Iter_getValue		(const TYPENAME##Iter* iter)					DE_UNUSED_FUNCTION;	\
110\
111DE_INLINE int TYPENAME##_getNumElements (const TYPENAME* hash)    \
112{    \
113	return hash->numElements;    \
114}    \
115\
116DE_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\
139DE_INLINE deBool TYPENAME##Iter_hasItem (const TYPENAME##Iter* iter)    \
140{	\
141	return (iter->curSlot != DE_NULL); \
142}	\
143\
144DE_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\
173DE_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\
179DE_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\
185struct 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\
202TYPENAME* TYPENAME##_create (deMemPool* pool)    \
203{   \
204	/* Alloc struct. */ \
205	DE_PTR_TYPE(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\
215void TYPENAME##_reset (DE_PTR_TYPE(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\
234TYPENAME##Slot* TYPENAME##_allocSlot (DE_PTR_TYPE(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\
254deBool TYPENAME##_rehash (DE_PTR_TYPE(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\
297VALUETYPE* 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\
320deBool TYPENAME##_insert (DE_PTR_TYPE(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\
367void TYPENAME##_delete (DE_PTR_TYPE(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}    \
419struct 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, DE_PTR_TYPE(KEYARRAYTYPENAME) keyArray, DE_PTR_TYPE(VALUEARRAYTYPENAME) valueArray);	\
425	struct HASHTYPENAME##_##KEYARRAYTYPENAME##_##VALUEARRAYTYPENAME##_declare_dummy { int dummy; }
426
427#define DE_IMPLEMENT_POOL_HASH_TO_ARRAY(HASHTYPENAME, KEYARRAYTYPENAME, VALUEARRAYTYPENAME)		\
428deBool HASHTYPENAME##_copyToArray(const HASHTYPENAME* hash, DE_PTR_TYPE(KEYARRAYTYPENAME) keyArray, DE_PTR_TYPE(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}	\
458struct HASHTYPENAME##_##KEYARRAYTYPENAME##_##VALUEARRAYTYPENAME##_implement_dummy { int dummy; }
459
460#endif /* _DEPOOLHASH_H */
461