| #ifndef _DEPOOLMULTISET_H |
| #define _DEPOOLMULTISET_H |
| /*------------------------------------------------------------------------- |
| * drawElements Memory Pool Library |
| * -------------------------------- |
| * |
| * Copyright 2014 The Android Open Source Project |
| * |
| * Licensed under the Apache License, Version 2.0 (the "License"); |
| * you may not use this file except in compliance with the License. |
| * You may obtain a copy of the License at |
| * |
| * http://www.apache.org/licenses/LICENSE-2.0 |
| * |
| * Unless required by applicable law or agreed to in writing, software |
| * distributed under the License is distributed on an "AS IS" BASIS, |
| * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| * See the License for the specific language governing permissions and |
| * limitations under the License. |
| * |
| *//*! |
| * \file |
| * \brief Memory pool multiset class. |
| *//*--------------------------------------------------------------------*/ |
| |
| #include "deDefs.h" |
| #include "deMemPool.h" |
| #include "dePoolHash.h" |
| #include "deInt32.h" |
| |
| DE_BEGIN_EXTERN_C |
| |
| void dePoolMultiSet_selfTest (void); |
| |
| DE_END_EXTERN_C |
| |
| /*--------------------------------------------------------------------*//*! |
| * \brief Declare a template pool multiset class interface. |
| * \param TYPENAME Type name of the declared multiset. |
| * \param KEYTYPE Type of the key. |
| * |
| * This macro declares the interface for a multiset. For the implementation |
| * of the multiset, see DE_IMPLEMENT_POOL_MULTISET. Usually this macro is put |
| * into the header file and the implementation macro is put in some .c file. |
| * |
| * \todo [petri] Detailed description. |
| * |
| * The functions for operating the multiset are: |
| * \todo [petri] Figure out how to comment these in Doxygen-style. |
| * |
| * \code |
| * MultiSet* MultiSet_create (deMemPool* pool); |
| * int MultiSet_getNumElements (const MultiSet* set); |
| * deBool MultiSet_exists (const MultiSet* set, Key key); |
| * deBool MultiSet_insert (MultiSet* set, Key key); |
| * void MultiSet_delete (MultiSet* set, Key key); |
| * int MultiSet_getKeyCount (const MultiSet* set, Key key); |
| * deBool MultiSet_setKeyCount (MultiSet* set, Key key, int count); |
| * \endcode |
| *//*--------------------------------------------------------------------*/ |
| #define DE_DECLARE_POOL_MULTISET(TYPENAME, KEYTYPE) \ |
| \ |
| DE_DECLARE_POOL_HASH(TYPENAME##Hash, KEYTYPE, int); \ |
| \ |
| typedef struct TYPENAME##_s \ |
| { \ |
| deMemPool* pool; \ |
| int numElements; \ |
| TYPENAME##Hash* hash; \ |
| } TYPENAME; /* NOLINT(TYPENAME) */ \ |
| \ |
| TYPENAME* TYPENAME##_create (deMemPool* pool); \ |
| void TYPENAME##_reset (DE_PTR_TYPE(TYPENAME) set); \ |
| deBool TYPENAME##_setKeyCount (DE_PTR_TYPE(TYPENAME) set, KEYTYPE key, int newCount); \ |
| \ |
| DE_INLINE int TYPENAME##_getNumElements (const TYPENAME* set) \ |
| { \ |
| return set->numElements; \ |
| } \ |
| \ |
| DE_INLINE int TYPENAME##_getKeyCount (const TYPENAME* set, KEYTYPE key) \ |
| { \ |
| int* countPtr = TYPENAME##Hash_find(set->hash, key); \ |
| int count = countPtr ? *countPtr : 0; \ |
| DE_ASSERT(count > 0 || !countPtr); \ |
| return count; \ |
| } \ |
| \ |
| DE_INLINE deBool TYPENAME##_exists (const TYPENAME* set, KEYTYPE key) \ |
| { \ |
| return (TYPENAME##_getKeyCount(set, key) > 0); \ |
| } \ |
| \ |
| DE_INLINE deBool TYPENAME##_insert (DE_PTR_TYPE(TYPENAME) set, KEYTYPE key) \ |
| { \ |
| int oldCount = TYPENAME##_getKeyCount(set, key); \ |
| return TYPENAME##_setKeyCount(set, key, oldCount + 1); \ |
| } \ |
| \ |
| DE_INLINE void TYPENAME##_delete (DE_PTR_TYPE(TYPENAME) set, KEYTYPE key) \ |
| { \ |
| int oldCount = TYPENAME##_getKeyCount(set, key); \ |
| DE_ASSERT(oldCount > 0); \ |
| TYPENAME##_setKeyCount(set, key, oldCount - 1); \ |
| } \ |
| \ |
| struct TYPENAME##DeclareDummy_s { int dummy; } |
| |
| /*--------------------------------------------------------------------*//*! |
| * \brief Implement a template pool multiset class. |
| * \param TYPENAME Type name of the declared multiset. |
| * \param KEYTYPE Type of the key. |
| * \param HASHFUNC Function used for hashing the key. |
| * \param CMPFUNC Function used for exact matching of the keys. |
| * |
| * This macro has implements the set declared with DE_DECLARE_POOL_MULTISET. |
| * Usually this macro should be used from a .c file, since the macro expands |
| * into multiple functions. The TYPENAME and KEYTYPE parameters |
| * must match those of the declare macro. |
| *//*--------------------------------------------------------------------*/ |
| #define DE_IMPLEMENT_POOL_MULTISET(TYPENAME, KEYTYPE, HASHFUNC, CMPFUNC) \ |
| \ |
| DE_IMPLEMENT_POOL_HASH(TYPENAME##Hash, KEYTYPE, int, HASHFUNC, CMPFUNC); \ |
| \ |
| TYPENAME* TYPENAME##_create (deMemPool* pool) \ |
| { \ |
| /* Alloc struct. */ \ |
| DE_PTR_TYPE(TYPENAME) set = DE_POOL_NEW(pool, TYPENAME); \ |
| if (!set) \ |
| return DE_NULL; \ |
| \ |
| /* Init. */ \ |
| memset(set, 0, sizeof(TYPENAME)); \ |
| set->pool = pool; \ |
| \ |
| set->hash = TYPENAME##Hash_create(pool); \ |
| \ |
| return set; \ |
| } \ |
| \ |
| void TYPENAME##_reset (DE_PTR_TYPE(TYPENAME) set) \ |
| { \ |
| TYPENAME##Hash_reset(set->hash); \ |
| set->numElements = 0; \ |
| } \ |
| \ |
| deBool TYPENAME##_setKeyCount (DE_PTR_TYPE(TYPENAME) set, KEYTYPE key, int newCount) \ |
| { \ |
| int* countPtr = TYPENAME##Hash_find(set->hash, key); \ |
| int oldCount = countPtr ? *countPtr : 0; \ |
| \ |
| DE_ASSERT(oldCount > 0 || !countPtr); \ |
| DE_ASSERT(newCount >= 0); \ |
| set->numElements += (newCount - oldCount); \ |
| \ |
| if (newCount == 0 && countPtr) \ |
| TYPENAME##Hash_delete(set->hash, key); \ |
| else if (newCount > 0 && countPtr) \ |
| *countPtr = newCount; \ |
| else if (newCount > 0) \ |
| return TYPENAME##Hash_insert(set->hash, key, newCount); \ |
| return DE_TRUE; \ |
| } \ |
| \ |
| struct TYPENAME##ImplementDummy_s { int dummy; } |
| |
| /*--------------------------------------------------------------------*//*! |
| * \brief Declare set-wise operations for a multiset template. |
| * \param TYPENAME Type name of the declared set. |
| * \param KEYTYPE Type of the key. |
| * |
| * This macro declares union and intersection operations for a multiset. |
| * For implementation see DE_IMPLEMENT_POOL_MULTISET_UNION_INTERSECT. |
| * |
| * \todo [petri] Detailed description. |
| * |
| * The functions for operating the set are: |
| * \todo [petri] Figure out how to comment these in Doxygen-style. |
| * |
| * \code |
| * deBool MultiSet_union (Set* to, const Set* a, const Set* b); |
| * deBool MultiSet_unionInplace (Set* a, const Set* b); |
| * deBool MultiSet_intersect (Set* to, const Set* a, const Set* b); |
| * void MultiSet_intersectInplace (Set* a, const Set* b); |
| * deBool MultiSet_sum (Set* to, const Set* a, const Set* b); |
| * deBool MultiSet_sumInplace (Set* a, const Set* b); |
| * deBool MultiSet_difference (Set* to, const Set* a, const Set* b); |
| * void MultiSet_differenceInplace (Set* a, const Set* b); |
| * \endcode |
| *//*--------------------------------------------------------------------*/ |
| #define DE_DECLARE_POOL_MULTISET_SETWISE_OPERATIONS(TYPENAME) \ |
| deBool TYPENAME##_union (DE_PTR_TYPE(TYPENAME) to, const TYPENAME* a, const TYPENAME* b); \ |
| deBool TYPENAME##_unionInplace (DE_PTR_TYPE(TYPENAME) a, const TYPENAME* b); \ |
| deBool TYPENAME##_intersect (DE_PTR_TYPE(TYPENAME) to, const TYPENAME* a, const TYPENAME* b); \ |
| void TYPENAME##_intersectInplace (DE_PTR_TYPE(TYPENAME) a, const TYPENAME* b); \ |
| deBool TYPENAME##_sum (DE_PTR_TYPE(TYPENAME) to, const TYPENAME* a, const TYPENAME* b); \ |
| deBool TYPENAME##_sumInplace (DE_PTR_TYPE(TYPENAME) a, const TYPENAME* b); \ |
| deBool TYPENAME##_difference (DE_PTR_TYPE(TYPENAME) to, const TYPENAME* a, const TYPENAME* b); \ |
| void TYPENAME##_differenceInplace (DE_PTR_TYPE(TYPENAME) a, const TYPENAME* b); \ |
| struct TYPENAME##SetwiseDeclareDummy_s { int dummy; } |
| |
| #define DE_IMPLEMENT_POOL_MULTISET_SETWISE_OPERATIONS(TYPENAME, KEYTYPE) \ |
| deBool TYPENAME##_union (DE_PTR_TYPE(TYPENAME) to, const TYPENAME* a, const TYPENAME* b) \ |
| { \ |
| TYPENAME##_reset(to); \ |
| return TYPENAME##_unionInplace(to, a) && TYPENAME##_unionInplace(to, b); \ |
| } \ |
| \ |
| deBool TYPENAME##_unionInplace (DE_PTR_TYPE(TYPENAME) a, const TYPENAME* b) \ |
| { \ |
| TYPENAME##HashIter iter; \ |
| for (TYPENAME##HashIter_init(b, &iter); \ |
| TYPENAME##HashIter_hasItem(&iter); \ |
| TYPENAME##HashIter_next(&iter)) \ |
| { \ |
| KEYTYPE key = TYPENAME##HashIter_getKey(&iter); \ |
| int bCount = TYPENAME##HashIter_getValue(&iter); \ |
| int aCount = TYPENAME##_getKeyCount(a, key); \ |
| int count = deMax32(aCount, bCount); \ |
| if (bCount && !TYPENAME##_setKeyCount(a, key, aCount + bCount)) \ |
| return DE_FALSE; \ |
| } \ |
| return DE_TRUE; \ |
| } \ |
| \ |
| deBool TYPENAME##_intersect (DE_PTR_TYPE(TYPENAME) to, const TYPENAME* a, const TYPENAME* b) \ |
| { \ |
| TYPENAME##HashIter iter; \ |
| TYPENAME##_reset(to); \ |
| for (TYPENAME##HashIter_init(a, &iter); \ |
| TYPENAME##HashIter_hasItem(&iter); \ |
| TYPENAME##HashIter_next(&iter)) \ |
| { \ |
| KEYTYPE key = TYPENAME##HashIter_getKey(&iter); \ |
| int aCount = TYPENAME##HashIter_getValue(&iter); \ |
| int bCount = TYPENAME##_getKeyValue(b, key); \ |
| int count = deMin32(aCount, bCount); \ |
| if (count && !TYPENAME##_setKeyCount(to, key, count)) \ |
| return DE_FALSE; \ |
| } \ |
| return DE_TRUE; \ |
| } \ |
| \ |
| void TYPENAME##_intersectInplace (DE_PTR_TYPE(TYPENAME) a, const TYPENAME* b) \ |
| { \ |
| DE_FATAL("Not implemented."); \ |
| } \ |
| \ |
| deBool TYPENAME##_sum (DE_PTR_TYPE(TYPENAME) to, const TYPENAME* a, const TYPENAME* b) \ |
| { \ |
| TYPENAME##_reset(to); \ |
| return TYPENAME##_sumInplace(to, a) && TYPENAME##_sumInplace(to, b); \ |
| } \ |
| \ |
| deBool TYPENAME##_sumInplace (DE_PTR_TYPE(TYPENAME) a, const TYPENAME* b) \ |
| { \ |
| TYPENAME##HashIter iter; \ |
| for (TYPENAME##HashIter_init(b, &iter); \ |
| TYPENAME##HashIter_hasItem(&iter); \ |
| TYPENAME##HashIter_next(&iter)) \ |
| { \ |
| KEYTYPE key = TYPENAME##HashIter_getKey(&iter); \ |
| int aCount = TYPENAME##_getKeyValue(a, key); \ |
| int bCount = TYPENAME##HashIter_getValue(&iter); \ |
| int count = aCount + bCount; \ |
| if (!TYPENAME##_setKeyCount(a, key, count)) \ |
| return DE_FALSE; \ |
| } \ |
| } \ |
| \ |
| deBool TYPENAME##_difference (DE_PTR_TYPE(TYPENAME) to, const TYPENAME* a, const TYPENAME* b) \ |
| { \ |
| TYPENAME##HashIter iter; \ |
| TYPENAME##_reset(to); \ |
| for (TYPENAME##HashIter_init(a, &iter); \ |
| TYPENAME##HashIter_hasItem(&iter); \ |
| TYPENAME##HashIter_next(&iter)) \ |
| { \ |
| KEYTYPE key = TYPENAME##HashIter_getKey(&iter); \ |
| int aCount = TYPENAME##HashIter_getValue(&iter); \ |
| int bCount = TYPENAME##_getKeyValue(b, key); \ |
| int count = deMax32(0, aCount - bCount); \ |
| if (count && !TYPENAME##_setKeyCount(to, key, count)) \ |
| return DE_FALSE; \ |
| } \ |
| return DE_TRUE; \ |
| } \ |
| \ |
| void TYPENAME##_differenceInplace (DE_PTR_TYPE(TYPENAME) a, const TYPENAME* b) \ |
| { \ |
| DE_FATAL("Not implemented."); \ |
| } \ |
| \ |
| struct TYPENAME##SetwiseImplementDummy_s { int dummy; } |
| |
| #endif /* _DEPOOLMULTISET_H */ |
