3 /*-------------------------------------------------------------------------
4 * drawElements Memory Pool Library
5 * --------------------------------
7 * Copyright 2014 The Android Open Source Project
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
13 * http://www.apache.org/licenses/LICENSE-2.0
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.
23 * \brief Memory pool set class.
24 *//*--------------------------------------------------------------------*/
27 #include "deMemPool.h"
28 #include "dePoolArray.h"
31 #include <string.h> /* memset() */
35 DE_SET_ELEMENTS_PER_SLOT = 4
40 void dePoolSet_selfTest (void);
44 /*--------------------------------------------------------------------*//*!
45 * \brief Declare a template pool set class interface.
46 * \param TYPENAME Type name of the declared set.
47 * \param KEYTYPE Type of the key.
49 * This macro declares the interface for a set. For the implementation of
50 * the set, see DE_IMPLEMENT_POOL_HASH. Usually this macro is put into the
51 * header file and the implementation macro is put in some .c file.
53 * \todo [petri] Detailed description.
55 * The functions for operating the set are:
56 * \todo [petri] Figure out how to comment these in Doxygen-style.
59 * Set* Set_create (deMemPool* pool);
60 * int Set_getNumElements (const Set* array);
61 * deBool Set_exists (const Set* array, Key key);
62 * deBool Set_insert (Set* array, Key key);
63 * void Set_delete (Set* array, Key key);
65 *//*--------------------------------------------------------------------*/
66 #define DE_DECLARE_POOL_SET(TYPENAME, KEYTYPE) \
68 typedef struct TYPENAME##Slot_s TYPENAME##Slot; \
70 struct TYPENAME##Slot_s \
73 TYPENAME##Slot* nextSlot; \
74 KEYTYPE keys[DE_SET_ELEMENTS_PER_SLOT]; \
77 typedef struct TYPENAME##_s \
83 TYPENAME##Slot** slotTable; \
84 TYPENAME##Slot* slotFreeList; \
87 typedef struct TYPENAME##Iter_s \
89 const TYPENAME* hash; \
91 const TYPENAME##Slot* curSlot; \
95 TYPENAME* TYPENAME##_create (deMemPool* pool); \
96 void TYPENAME##_reset (TYPENAME* set); \
97 deBool TYPENAME##_reserve (TYPENAME* set, int capacity); \
98 deBool TYPENAME##_exists (const TYPENAME* set, KEYTYPE key); \
99 deBool TYPENAME##_insert (TYPENAME* set, KEYTYPE key); \
100 void TYPENAME##_delete (TYPENAME* set, KEYTYPE key); \
102 DE_INLINE int TYPENAME##_getNumElements (const TYPENAME* set) DE_UNUSED_FUNCTION; \
103 DE_INLINE void TYPENAME##Iter_init (const TYPENAME* hash, TYPENAME##Iter* iter) DE_UNUSED_FUNCTION; \
104 DE_INLINE deBool TYPENAME##Iter_hasItem (const TYPENAME##Iter* iter) DE_UNUSED_FUNCTION; \
105 DE_INLINE void TYPENAME##Iter_next (TYPENAME##Iter* iter) DE_UNUSED_FUNCTION; \
106 DE_INLINE KEYTYPE TYPENAME##Iter_getKey (const TYPENAME##Iter* iter) DE_UNUSED_FUNCTION; \
107 DE_INLINE deBool TYPENAME##_safeInsert (TYPENAME* set, KEYTYPE key) DE_UNUSED_FUNCTION; \
108 DE_INLINE void TYPENAME##_safeDelete (TYPENAME* set, KEYTYPE key) DE_UNUSED_FUNCTION; \
110 DE_INLINE int TYPENAME##_getNumElements (const TYPENAME* set) \
112 return set->numElements; \
115 DE_INLINE void TYPENAME##Iter_init (const TYPENAME* hash, TYPENAME##Iter* iter) \
118 iter->curSlotIndex = 0; \
119 iter->curSlot = DE_NULL; \
120 iter->curElemIndex = 0; \
121 if (TYPENAME##_getNumElements(hash) > 0) \
123 int slotTableSize = hash->slotTableSize; \
125 while (slotNdx < slotTableSize) \
127 if (hash->slotTable[slotNdx]) \
131 DE_ASSERT(slotNdx < slotTableSize); \
132 iter->curSlotIndex = slotNdx; \
133 iter->curSlot = hash->slotTable[slotNdx]; \
134 DE_ASSERT(iter->curSlot); \
138 DE_INLINE deBool TYPENAME##Iter_hasItem (const TYPENAME##Iter* iter) \
140 return (iter->curSlot != DE_NULL); \
143 DE_INLINE void TYPENAME##Iter_next (TYPENAME##Iter* iter) \
145 DE_ASSERT(TYPENAME##Iter_hasItem(iter)); \
146 if (++iter->curElemIndex == iter->curSlot->numUsed) \
148 iter->curElemIndex = 0; \
149 if (iter->curSlot->nextSlot) \
151 iter->curSlot = iter->curSlot->nextSlot; \
155 const TYPENAME* hash = iter->hash; \
156 int curSlotIndex = iter->curSlotIndex; \
157 int slotTableSize = hash->slotTableSize; \
158 while (++curSlotIndex < slotTableSize) \
160 if (hash->slotTable[curSlotIndex]) \
163 iter->curSlotIndex = curSlotIndex; \
164 if (curSlotIndex < slotTableSize) \
165 iter->curSlot = hash->slotTable[curSlotIndex]; \
167 iter->curSlot = DE_NULL; \
172 DE_INLINE KEYTYPE TYPENAME##Iter_getKey (const TYPENAME##Iter* iter) \
174 DE_ASSERT(TYPENAME##Iter_hasItem(iter)); \
175 return iter->curSlot->keys[iter->curElemIndex]; \
178 DE_INLINE deBool TYPENAME##_safeInsert (TYPENAME* set, KEYTYPE key) \
181 if (TYPENAME##_exists(set, key)) \
183 return TYPENAME##_insert(set, key); \
186 DE_INLINE void TYPENAME##_safeDelete (TYPENAME* set, KEYTYPE key) \
189 if (TYPENAME##_exists(set, key)) \
190 TYPENAME##_delete(set, key); \
193 struct TYPENAME##Dummy_s { int dummy; }
195 /*--------------------------------------------------------------------*//*!
196 * \brief Implement a template pool set class.
197 * \param TYPENAME Type name of the declared set.
198 * \param KEYTYPE Type of the key.
199 * \param HASHFUNC Function used for hashing the key.
200 * \param CMPFUNC Function used for exact matching of the keys.
202 * This macro has implements the set declared with DE_DECLARE_POOL_SET.
203 * Usually this macro should be used from a .c file, since the macro expands
204 * into multiple functions. The TYPENAME and KEYTYPE parameters
205 * must match those of the declare macro.
206 *//*--------------------------------------------------------------------*/
207 #define DE_IMPLEMENT_POOL_SET(TYPENAME, KEYTYPE, HASHFUNC, CMPFUNC) \
209 TYPENAME* TYPENAME##_create (deMemPool* pool) \
211 /* Alloc struct. */ \
212 TYPENAME* set = DE_POOL_NEW(pool, TYPENAME); \
217 memset(set, 0, sizeof(TYPENAME)); \
223 void TYPENAME##_reset (TYPENAME* set) \
226 for (slotNdx = 0; slotNdx < set->slotTableSize; slotNdx++) \
228 TYPENAME##Slot* slot = set->slotTable[slotNdx]; \
231 TYPENAME##Slot* nextSlot = slot->nextSlot; \
232 slot->nextSlot = set->slotFreeList; \
233 set->slotFreeList = slot; \
237 set->slotTable[slotNdx] = DE_NULL; \
239 set->numElements = 0; \
242 TYPENAME##Slot* TYPENAME##_allocSlot (TYPENAME* set) \
244 TYPENAME##Slot* slot; \
245 if (set->slotFreeList) \
247 slot = set->slotFreeList; \
248 set->slotFreeList = set->slotFreeList->nextSlot; \
251 slot = (TYPENAME##Slot*)deMemPool_alloc(set->pool, sizeof(TYPENAME##Slot) * DE_SET_ELEMENTS_PER_SLOT); \
255 slot->nextSlot = DE_NULL; \
262 deBool TYPENAME##_rehash (TYPENAME* set, int newSlotTableSize) \
264 DE_ASSERT(deIsPowerOfTwo32(newSlotTableSize) && newSlotTableSize > 0); \
265 if (newSlotTableSize > set->slotTableSize) \
267 TYPENAME##Slot** oldSlotTable = set->slotTable; \
268 TYPENAME##Slot** newSlotTable = (TYPENAME##Slot**)deMemPool_alloc(set->pool, sizeof(TYPENAME##Slot*) * (size_t)newSlotTableSize); \
269 int oldSlotTableSize = set->slotTableSize; \
275 for (slotNdx = 0; slotNdx < oldSlotTableSize; slotNdx++) \
276 newSlotTable[slotNdx] = oldSlotTable[slotNdx]; \
278 for (slotNdx = oldSlotTableSize; slotNdx < newSlotTableSize; slotNdx++) \
279 newSlotTable[slotNdx] = DE_NULL; \
281 set->slotTableSize = newSlotTableSize; \
282 set->slotTable = newSlotTable; \
284 for (slotNdx = 0; slotNdx < oldSlotTableSize; slotNdx++) \
286 TYPENAME##Slot* slot = oldSlotTable[slotNdx]; \
287 newSlotTable[slotNdx] = DE_NULL; \
291 for (elemNdx = 0; elemNdx < slot->numUsed; elemNdx++) \
293 set->numElements--; \
294 if (!TYPENAME##_insert(set, slot->keys[elemNdx])) \
297 slot = slot->nextSlot; \
305 deBool TYPENAME##_exists (const TYPENAME* set, KEYTYPE key) \
307 if (set->numElements > 0) \
309 int slotNdx = (int)(HASHFUNC(key) & (deUint32)(set->slotTableSize - 1)); \
310 TYPENAME##Slot* slot = set->slotTable[slotNdx]; \
311 DE_ASSERT(deInBounds32(slotNdx, 0, set->slotTableSize)); \
316 for (elemNdx = 0; elemNdx < slot->numUsed; elemNdx++) \
318 if (CMPFUNC(slot->keys[elemNdx], key)) \
321 slot = slot->nextSlot; \
328 deBool TYPENAME##_insert (TYPENAME* set, KEYTYPE key) \
331 TYPENAME##Slot* slot; \
334 DE_ASSERT(!TYPENAME##_exists(set, key)); \
336 if ((set->numElements + 1) >= set->slotTableSize * DE_SET_ELEMENTS_PER_SLOT) \
337 if (!TYPENAME##_rehash(set, deMax32(4, 2*set->slotTableSize))) \
340 slotNdx = (int)(HASHFUNC(key) & (deUint32)(set->slotTableSize - 1)); \
341 DE_ASSERT(slotNdx >= 0 && slotNdx < set->slotTableSize); \
342 slot = set->slotTable[slotNdx]; \
346 slot = TYPENAME##_allocSlot(set); \
347 if (!slot) return DE_FALSE; \
348 set->slotTable[slotNdx] = slot; \
353 if (slot->numUsed == DE_SET_ELEMENTS_PER_SLOT) \
355 if (slot->nextSlot) \
356 slot = slot->nextSlot; \
359 TYPENAME##Slot* nextSlot = TYPENAME##_allocSlot(set); \
360 if (!nextSlot) return DE_FALSE; \
361 slot->nextSlot = nextSlot; \
367 slot->keys[slot->numUsed] = key; \
369 set->numElements++; \
375 void TYPENAME##_delete (TYPENAME* set, KEYTYPE key) \
378 TYPENAME##Slot* slot; \
379 TYPENAME##Slot* prevSlot = DE_NULL; \
381 DE_ASSERT(set->numElements > 0); \
382 slotNdx = (int)(HASHFUNC(key) & (deUint32)(set->slotTableSize - 1)); \
383 DE_ASSERT(slotNdx >= 0 && slotNdx < set->slotTableSize); \
384 slot = set->slotTable[slotNdx]; \
390 DE_ASSERT(slot->numUsed > 0); \
391 for (elemNdx = 0; elemNdx < slot->numUsed; elemNdx++) \
393 if (CMPFUNC(key, slot->keys[elemNdx])) \
395 TYPENAME##Slot* lastSlot = slot; \
396 while (lastSlot->nextSlot) \
398 prevSlot = lastSlot; \
399 lastSlot = lastSlot->nextSlot; \
402 slot->keys[elemNdx] = lastSlot->keys[lastSlot->numUsed-1]; \
403 lastSlot->numUsed--; \
405 if (lastSlot->numUsed == 0) \
408 prevSlot->nextSlot = DE_NULL; \
410 set->slotTable[slotNdx] = DE_NULL; \
412 lastSlot->nextSlot = set->slotFreeList; \
413 set->slotFreeList = lastSlot; \
416 set->numElements--; \
422 slot = slot->nextSlot; \
427 struct TYPENAME##Dummy2_s { int dummy; }
429 /* Copy-to-array templates. */
431 #define DE_DECLARE_POOL_SET_TO_ARRAY(SETTYPENAME, ARRAYTYPENAME) \
432 deBool SETTYPENAME##_copyToArray(const SETTYPENAME* set, ARRAYTYPENAME* array); \
433 struct SETTYPENAME##_##ARRAYTYPENAME##_declare_dummy { int dummy; }
435 #define DE_IMPLEMENT_POOL_SET_TO_ARRAY(SETTYPENAME, ARRAYTYPENAME) \
436 deBool SETTYPENAME##_copyToArray(const SETTYPENAME* set, ARRAYTYPENAME* array) \
438 int numElements = set->numElements; \
442 if (!ARRAYTYPENAME##_setSize(array, numElements)) \
445 for (slotNdx = 0; slotNdx < set->slotTableSize; slotNdx++) \
447 const SETTYPENAME##Slot* slot = set->slotTable[slotNdx]; \
451 for (elemNdx = 0; elemNdx < slot->numUsed; elemNdx++) \
452 ARRAYTYPENAME##_set(array, arrayNdx++, slot->keys[elemNdx]); \
453 slot = slot->nextSlot; \
456 DE_ASSERT(arrayNdx == numElements); \
459 struct SETTYPENAME##_##ARRAYTYPENAME##_implement_dummy { int dummy; }
461 /*--------------------------------------------------------------------*//*!
462 * \brief Declare set-wise operations for a set template.
463 * \param TYPENAME Type name of the declared set.
464 * \param KEYTYPE Type of the key.
466 * This macro declares union and intersection operations for a set.
467 * For implementation see DE_IMPLEMENT_POOL_SET_UNION_INTERSECT.
469 * \todo [petri] Detailed description.
471 * The functions for operating the set are:
472 * \todo [petri] Figure out how to comment these in Doxygen-style.
475 * deBool Set_union (Set* to, const Set* a, const Set* b);
476 * deBool Set_unionInplace (Set* a, const Set* b);
477 * deBool Set_intersect (Set* to, const Set* a, const Set* b);
478 * void Set_intersectInplace (Set* a, const Set* b);
479 * deBool Set_difference (Set* to, const Set* a, const Set* b);
480 * void Set_differenceInplace (Set* a, const Set* b);
482 *//*--------------------------------------------------------------------*/
483 #define DE_DECLARE_POOL_SET_SETWISE_OPERATIONS(TYPENAME) \
484 deBool TYPENAME##_union (TYPENAME* to, const TYPENAME* a, const TYPENAME* b); \
485 deBool TYPENAME##_unionInplace (TYPENAME* a, const TYPENAME* b); \
486 deBool TYPENAME##_intersect (TYPENAME* to, const TYPENAME* a, const TYPENAME* b); \
487 void TYPENAME##_intersectInplace (TYPENAME* a, const TYPENAME* b); \
488 deBool TYPENAME##_difference (TYPENAME* to, const TYPENAME* a, const TYPENAME* b); \
489 void TYPENAME##_differenceInplace (TYPENAME* a, const TYPENAME* b); \
490 struct TYPENAME##SetwiseDeclareDummy_s { int dummy; }
492 #define DE_IMPLEMENT_POOL_SET_SETWISE_OPERATIONS(TYPENAME, KEYTYPE) \
493 deBool TYPENAME##_union (TYPENAME* to, const TYPENAME* a, const TYPENAME* b) \
495 TYPENAME##_reset(to); \
496 if (!TYPENAME##_unionInplace(to, a)) \
498 if (!TYPENAME##_unionInplace(to, b)) \
503 deBool TYPENAME##_unionInplace (TYPENAME* a, const TYPENAME* b) \
505 TYPENAME##Iter iter; \
506 for (TYPENAME##Iter_init(b, &iter); \
507 TYPENAME##Iter_hasItem(&iter); \
508 TYPENAME##Iter_next(&iter)) \
510 KEYTYPE key = TYPENAME##Iter_getKey(&iter); \
511 if (!TYPENAME##_exists(a, key)) \
513 if (!TYPENAME##_insert(a, key)) \
520 deBool TYPENAME##_intersect (TYPENAME* to, const TYPENAME* a, const TYPENAME* b) \
522 TYPENAME##Iter iter; \
523 TYPENAME##_reset(to); \
524 for (TYPENAME##Iter_init(a, &iter); \
525 TYPENAME##Iter_hasItem(&iter); \
526 TYPENAME##Iter_next(&iter)) \
528 KEYTYPE key = TYPENAME##Iter_getKey(&iter); \
529 if (TYPENAME##_exists(b, key)) \
531 if (!TYPENAME##_insert(to, key)) \
538 void TYPENAME##_intersectInplace (TYPENAME* a, const TYPENAME* b) \
541 DE_FATAL("Not implemented."); \
544 deBool TYPENAME##_difference (TYPENAME* to, const TYPENAME* a, const TYPENAME* b) \
546 TYPENAME##Iter iter; \
547 TYPENAME##_reset(to); \
548 for (TYPENAME##Iter_init(a, &iter); \
549 TYPENAME##Iter_hasItem(&iter); \
550 TYPENAME##Iter_next(&iter)) \
552 KEYTYPE key = TYPENAME##Iter_getKey(&iter); \
553 if (!TYPENAME##_exists(b, key)) \
555 if (!TYPENAME##_insert(to, key)) \
562 void TYPENAME##_differenceInplace (TYPENAME* a, const TYPENAME* b) \
564 TYPENAME##Iter iter; \
565 for (TYPENAME##Iter_init(b, &iter); \
566 TYPENAME##Iter_hasItem(&iter); \
567 TYPENAME##Iter_next(&iter)) \
569 KEYTYPE key = TYPENAME##Iter_getKey(&iter); \
570 if (TYPENAME##_exists(a, key)) \
571 TYPENAME##_delete(a, key); \
575 struct TYPENAME##UnionIntersectImplementDummy_s { int dummy; }
577 #endif /* _DEPOOLSET_H */