#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; \
\
TYPENAME* TYPENAME##_create (deMemPool* pool); \
void TYPENAME##_reset (TYPENAME* set); \
deBool TYPENAME##_setKeyCount (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 (TYPENAME* set, KEYTYPE key) \
{ \
int oldCount = TYPENAME##_getKeyCount(set, key); \
return TYPENAME##_setKeyCount(set, key, oldCount + 1); \
} \
\
DE_INLINE void TYPENAME##_delete (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. */ \
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 (TYPENAME* set) \
{ \
TYPENAME##Hash_reset(set->hash); \
set->numElements = 0; \
} \
\
deBool TYPENAME##_setKeyCount (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 (TYPENAME* to, const TYPENAME* a, const TYPENAME* b); \
deBool TYPENAME##_unionInplace (TYPENAME* a, const TYPENAME* b); \
deBool TYPENAME##_intersect (TYPENAME* to, const TYPENAME* a, const TYPENAME* b); \
void TYPENAME##_intersectInplace (TYPENAME* a, const TYPENAME* b); \
deBool TYPENAME##_sum (TYPENAME* to, const TYPENAME* a, const TYPENAME* b); \
deBool TYPENAME##_sumInplace (TYPENAME* a, const TYPENAME* b); \
deBool TYPENAME##_difference (TYPENAME* to, const TYPENAME* a, const TYPENAME* b); \
void TYPENAME##_differenceInplace (TYPENAME* a, const TYPENAME* b); \
struct TYPENAME##SetwiseDeclareDummy_s { int dummy; }
#define DE_IMPLEMENT_POOL_MULTISET_SETWISE_OPERATIONS(TYPENAME, KEYTYPE) \
deBool TYPENAME##_union (TYPENAME* to, const TYPENAME* a, const TYPENAME* b) \
{ \
TYPENAME##_reset(to); \
return TYPENAME##_unionInplace(to, a) && TYPENAME##_unionInplace(to, b); \
} \
\
deBool TYPENAME##_unionInplace (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 (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 (TYPENAME* a, const TYPENAME* b) \
{ \
DE_ASSERT(!"Not implemented."); \
} \
\
deBool TYPENAME##_sum (TYPENAME* to, const TYPENAME* a, const TYPENAME* b) \
{ \
TYPENAME##_reset(to); \
return TYPENAME##_sumInplace(to, a) && TYPENAME##_sumInplace(to, b); \
} \
\
deBool TYPENAME##_sumInplace (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 (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 (TYPENAME* a, const TYPENAME* b) \
{ \
DE_ASSERT(!"Not implemented."); \
} \
\
struct TYPENAME##SetwiseImplementDummy_s { int dummy; }
#endif /* _DEPOOLMULTISET_H */