Home | History | Annotate | Download | only in depool
      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 
     30 DE_BEGIN_EXTERN_C
     31 
     32 void	dePoolHashSet_selfTest		(void);
     33 
     34 DE_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 																									\
     59 DE_DECLARE_POOL_SET(TYPENAME##Set, VALUETYPE);														\
     60 DE_DECLARE_POOL_HASH(TYPENAME##Hash, KEYTYPE, TYPENAME##Set*);										\
     61 typedef struct TYPENAME##_s																			\
     62 {																									\
     63 	TYPENAME##Hash*	hash;																			\
     64 } TYPENAME;																							\
     65 																									\
     66 DE_INLINE TYPENAME*			TYPENAME##_create			(deMemPool* pool);							\
     67 DE_INLINE int				TYPENAME##_getNumElements	(const TYPENAME* hashSet)								DE_UNUSED_FUNCTION;	\
     68 DE_INLINE TYPENAME##Hash*	TYPENAME##_getHash			(const TYPENAME* hashSet)								DE_UNUSED_FUNCTION;	\
     69 DE_INLINE deBool			TYPENAME##_insert			(TYPENAME* hashSet, KEYTYPE key, VALUETYPE value)		DE_UNUSED_FUNCTION;	\
     70 DE_INLINE deBool			TYPENAME##_safeInsert		(TYPENAME* hashSet, KEYTYPE key, VALUETYPE value)		DE_UNUSED_FUNCTION;	\
     71 DE_INLINE TYPENAME##Set*	TYPENAME##_find				(const TYPENAME* hashSet, KEYTYPE key)					DE_UNUSED_FUNCTION;	\
     72 DE_INLINE void				TYPENAME##_delete			(TYPENAME* hashSet, KEYTYPE key, VALUETYPE value)		DE_UNUSED_FUNCTION;	\
     73 DE_INLINE deBool			TYPENAME##_exists			(const TYPENAME* hashSet, KEYTYPE key, VALUETYPE value)	DE_UNUSED_FUNCTION;	\
     74 																									\
     75 DE_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 																									\
     84 DE_INLINE int TYPENAME##_getNumElements (const TYPENAME* hashSet)									\
     85 {																									\
     86 	return TYPENAME##Hash_getNumElements(hashSet->hash);											\
     87 }																									\
     88 																									\
     89 DE_INLINE TYPENAME##Hash* TYPENAME##_getHash (const TYPENAME* hashSet)								\
     90 {																									\
     91 	return hashSet->hash;																			\
     92 }																									\
     93 																									\
     94 DE_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 																									\
    111 DE_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 																									\
    125 DE_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 																									\
    131 DE_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 																									\
    140 DE_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 																									\
    149 struct 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)	\
    165 DE_IMPLEMENT_POOL_SET(TYPENAME##Set, VALUETYPE, VALUEHASHFUNC, VALUECMPFUNC);											\
    166 DE_IMPLEMENT_POOL_HASH(TYPENAME##Hash, KEYTYPE, TYPENAME##Set*, KEYHASHFUNC, KEYCMPFUNC);								\
    167 struct 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)		\
    178 deBool 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 }	\
    208 struct HASHTYPENAME##_##KEYARRAYTYPENAME##_##VALUEARRAYTYPENAME##_implement_dummy { int dummy; }
    209 
    210 #endif
    211 
    212 #endif /* _DEPOOLHASHSET_H */
    213