Lines Matching full:hash
23 * \brief Memory pool hash class.
45 * \brief Declare a template pool hash class interface.
46 * \param TYPENAME Type name of the declared hash.
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
56 * The functions for operating the hash are:
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);
91 const TYPENAME* hash; \
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); \
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; \
111 DE_INLINE int TYPENAME##_getNumElements (const TYPENAME* hash) \
113 return hash->numElements; \
116 DE_INLINE void TYPENAME##Iter_init (const TYPENAME* hash, TYPENAME##Iter* iter) \
118 iter->hash = hash; \
122 if (TYPENAME##_getNumElements(hash) > 0) \
124 int slotTableSize = hash->slotTableSize; \
128 if (hash->slotTable[slotNdx]) \
134 iter->curSlot = hash->slotTable[slotNdx]; \
156 const TYPENAME* hash = iter->hash; \
158 int slotTableSize = hash->slotTableSize; \
161 if (hash->slotTable[curSlotIndex]) \
166 iter->curSlot = hash->slotTable[curSlotIndex]; \
188 * \brief Implement a template pool hash class.
189 * \param TYPENAME Type name of the declared hash.
195 * This macro has implements the hash declared with DE_DECLARE_POOL_HASH.
205 TYPENAME* hash = DE_POOL_NEW(pool, TYPENAME); \
206 if (!hash) \
209 memset(hash, 0, sizeof(TYPENAME)); \
210 hash->pool = pool; \
212 return hash; \
215 void TYPENAME##_reset (TYPENAME* hash) \
218 for (slotNdx = 0; slotNdx < hash->slotTableSize; slotNdx++) \
220 TYPENAME##Slot* slot = hash->slotTable[slotNdx]; \
224 slot->nextSlot = hash->slotFreeList; \
225 hash->slotFreeList = slot; \
229 hash->slotTable[slotNdx] = DE_NULL; \
231 hash->numElements = 0; \
234 TYPENAME##Slot* TYPENAME##_allocSlot (TYPENAME* hash) \
237 if (hash->slotFreeList) \
239 slot = hash->slotFreeList; \
240 hash->slotFreeList = hash->slotFreeList->nextSlot; \
243 slot = (TYPENAME##Slot*)deMemPool_alloc(hash->pool, sizeof(TYPENAME##Slot) * DE_HASH_ELEMENTS_PER_SLOT); \
254 deBool TYPENAME##_rehash (TYPENAME* hash, int newSlotTableSize) \
257 if (newSlotTableSize > hash->slotTableSize) \
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; \
273 hash->slotTableSize = newSlotTableSize; \
274 hash->slotTable = newSlotTable; \
285 hash->numElements--; \
286 if (!TYPENAME##_insert(hash, slot->keys[elemNdx], slot->values[elemNdx])) \
297 VALUETYPE* TYPENAME##_find (const TYPENAME* hash, KEYTYPE key) \
299 if (hash->numElements > 0) \
301 int slotNdx = HASHFUNC(key) & (hash->slotTableSize - 1); \
302 TYPENAME##Slot* slot = hash->slotTable[slotNdx]; \
303 DE_ASSERT(deInBounds32(slotNdx, 0, hash->slotTableSize)); \
320 deBool TYPENAME##_insert (TYPENAME* hash, KEYTYPE key, VALUETYPE value) \
325 DE_ASSERT(!TYPENAME##_find(hash, key)); \
327 if ((hash->numElements + 1) >= hash->slotTableSize * DE_HASH_ELEMENTS_PER_SLOT) \
328 if (!TYPENAME##_rehash(hash, deMax32(4, 2*hash->slotTableSize))) \
331 slotNdx = HASHFUNC(key) & (hash->slotTableSize - 1); \
332 DE_ASSERT(slotNdx >= 0 && slotNdx < hash->slotTableSize); \
333 slot = hash->slotTable[slotNdx]; \
337 slot = TYPENAME##_allocSlot(hash); \
339 hash->slotTable[slotNdx] = slot; \
350 TYPENAME##Slot* nextSlot = TYPENAME##_allocSlot(hash); \
361 hash->numElements++; \
367 void TYPENAME##_delete (TYPENAME* hash, KEYTYPE key) \
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]; \
403 hash->slotTable[slotNdx] = DE_NULL; \
405 lastSlot->nextSlot = hash->slotFreeList; \
406 hash->slotFreeList = lastSlot; \
409 hash->numElements--; \
428 deBool HASHTYPENAME##_copyToArray(const HASHTYPENAME* hash, KEYARRAYTYPENAME* keyArray, VALUEARRAYTYPENAME* valueArray) \
430 int numElements = hash->numElements; \
438 for (slotNdx = 0; slotNdx < hash->slotTableSize; slotNdx++) \
440 const HASHTYPENAME##Slot* slot = hash->slotTable[slotNdx]; \
