Home | History | Annotate | Download | only in depool
      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*) * 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	= HASHFUNC(key) & (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	= HASHFUNC(key) & (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	= HASHFUNC(key) & (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