dePoolMultiSet.h revision 3c827367444ee418f129b2c238299f49d3264554
1#ifndef _DEPOOLMULTISET_H 2#define _DEPOOLMULTISET_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 multiset class. 24 *//*--------------------------------------------------------------------*/ 25 26#include "deDefs.h" 27#include "deMemPool.h" 28#include "dePoolHash.h" 29#include "deInt32.h" 30 31DE_BEGIN_EXTERN_C 32 33void dePoolMultiSet_selfTest (void); 34 35DE_END_EXTERN_C 36 37/*--------------------------------------------------------------------*//*! 38 * \brief Declare a template pool multiset class interface. 39 * \param TYPENAME Type name of the declared multiset. 40 * \param KEYTYPE Type of the key. 41 * 42 * This macro declares the interface for a multiset. For the implementation 43 * of the multiset, see DE_IMPLEMENT_POOL_MULTISET. Usually this macro is put 44 * into the header file and the implementation macro is put in some .c file. 45 * 46 * \todo [petri] Detailed description. 47 * 48 * The functions for operating the multiset are: 49 * \todo [petri] Figure out how to comment these in Doxygen-style. 50 * 51 * \code 52 * MultiSet* MultiSet_create (deMemPool* pool); 53 * int MultiSet_getNumElements (const MultiSet* set); 54 * deBool MultiSet_exists (const MultiSet* set, Key key); 55 * deBool MultiSet_insert (MultiSet* set, Key key); 56 * void MultiSet_delete (MultiSet* set, Key key); 57 * int MultiSet_getKeyCount (const MultiSet* set, Key key); 58 * deBool MultiSet_setKeyCount (MultiSet* set, Key key, int count); 59 * \endcode 60*//*--------------------------------------------------------------------*/ 61#define DE_DECLARE_POOL_MULTISET(TYPENAME, KEYTYPE) \ 62\ 63DE_DECLARE_POOL_HASH(TYPENAME##Hash, KEYTYPE, int); \ 64\ 65typedef struct TYPENAME##_s \ 66{ \ 67 deMemPool* pool; \ 68 int numElements; \ 69 TYPENAME##Hash* hash; \ 70} TYPENAME; \ 71\ 72TYPENAME* TYPENAME##_create (deMemPool* pool); \ 73void TYPENAME##_reset (TYPENAME* set); \ 74deBool TYPENAME##_setKeyCount (TYPENAME* set, KEYTYPE key, int newCount); \ 75\ 76DE_INLINE int TYPENAME##_getNumElements (const TYPENAME* set) \ 77{ \ 78 return set->numElements; \ 79} \ 80\ 81DE_INLINE int TYPENAME##_getKeyCount (const TYPENAME* set, KEYTYPE key) \ 82{ \ 83 int* countPtr = TYPENAME##Hash_find(set->hash, key); \ 84 int count = countPtr ? *countPtr : 0; \ 85 DE_ASSERT(count > 0 || !countPtr); \ 86 return count; \ 87} \ 88\ 89DE_INLINE deBool TYPENAME##_exists (const TYPENAME* set, KEYTYPE key) \ 90{ \ 91 return (TYPENAME##_getKeyCount(set, key) > 0); \ 92} \ 93\ 94DE_INLINE deBool TYPENAME##_insert (TYPENAME* set, KEYTYPE key) \ 95{ \ 96 int oldCount = TYPENAME##_getKeyCount(set, key); \ 97 return TYPENAME##_setKeyCount(set, key, oldCount + 1); \ 98} \ 99\ 100DE_INLINE void TYPENAME##_delete (TYPENAME* set, KEYTYPE key) \ 101{ \ 102 int oldCount = TYPENAME##_getKeyCount(set, key); \ 103 DE_ASSERT(oldCount > 0); \ 104 TYPENAME##_setKeyCount(set, key, oldCount - 1); \ 105} \ 106\ 107struct TYPENAME##DeclareDummy_s { int dummy; } 108 109/*--------------------------------------------------------------------*//*! 110 * \brief Implement a template pool multiset class. 111 * \param TYPENAME Type name of the declared multiset. 112 * \param KEYTYPE Type of the key. 113 * \param HASHFUNC Function used for hashing the key. 114 * \param CMPFUNC Function used for exact matching of the keys. 115 * 116 * This macro has implements the set declared with DE_DECLARE_POOL_MULTISET. 117 * Usually this macro should be used from a .c file, since the macro expands 118 * into multiple functions. The TYPENAME and KEYTYPE parameters 119 * must match those of the declare macro. 120*//*--------------------------------------------------------------------*/ 121#define DE_IMPLEMENT_POOL_MULTISET(TYPENAME, KEYTYPE, HASHFUNC, CMPFUNC) \ 122\ 123DE_IMPLEMENT_POOL_HASH(TYPENAME##Hash, KEYTYPE, int, HASHFUNC, CMPFUNC); \ 124\ 125TYPENAME* TYPENAME##_create (deMemPool* pool) \ 126{ \ 127 /* Alloc struct. */ \ 128 TYPENAME* set = DE_POOL_NEW(pool, TYPENAME); \ 129 if (!set) \ 130 return DE_NULL; \ 131\ 132 /* Init. */ \ 133 memset(set, 0, sizeof(TYPENAME)); \ 134 set->pool = pool; \ 135\ 136 set->hash = TYPENAME##Hash_create(pool); \ 137\ 138 return set; \ 139} \ 140\ 141void TYPENAME##_reset (TYPENAME* set) \ 142{ \ 143 TYPENAME##Hash_reset(set->hash); \ 144 set->numElements = 0; \ 145} \ 146\ 147deBool TYPENAME##_setKeyCount (TYPENAME* set, KEYTYPE key, int newCount) \ 148{ \ 149 int* countPtr = TYPENAME##Hash_find(set->hash, key); \ 150 int oldCount = countPtr ? *countPtr : 0; \ 151\ 152 DE_ASSERT(oldCount > 0 || !countPtr); \ 153 DE_ASSERT(newCount >= 0); \ 154 set->numElements += (newCount - oldCount); \ 155\ 156 if (newCount == 0 && countPtr) \ 157 TYPENAME##Hash_delete(set->hash, key); \ 158 else if (newCount > 0 && countPtr) \ 159 *countPtr = newCount; \ 160 else if (newCount > 0) \ 161 return TYPENAME##Hash_insert(set->hash, key, newCount); \ 162 return DE_TRUE; \ 163} \ 164\ 165struct TYPENAME##ImplementDummy_s { int dummy; } 166 167/*--------------------------------------------------------------------*//*! 168 * \brief Declare set-wise operations for a multiset template. 169 * \param TYPENAME Type name of the declared set. 170 * \param KEYTYPE Type of the key. 171 * 172 * This macro declares union and intersection operations for a multiset. 173 * For implementation see DE_IMPLEMENT_POOL_MULTISET_UNION_INTERSECT. 174 * 175 * \todo [petri] Detailed description. 176 * 177 * The functions for operating the set are: 178 * \todo [petri] Figure out how to comment these in Doxygen-style. 179 * 180 * \code 181 * deBool MultiSet_union (Set* to, const Set* a, const Set* b); 182 * deBool MultiSet_unionInplace (Set* a, const Set* b); 183 * deBool MultiSet_intersect (Set* to, const Set* a, const Set* b); 184 * void MultiSet_intersectInplace (Set* a, const Set* b); 185 * deBool MultiSet_sum (Set* to, const Set* a, const Set* b); 186 * deBool MultiSet_sumInplace (Set* a, const Set* b); 187 * deBool MultiSet_difference (Set* to, const Set* a, const Set* b); 188 * void MultiSet_differenceInplace (Set* a, const Set* b); 189 * \endcode 190*//*--------------------------------------------------------------------*/ 191#define DE_DECLARE_POOL_MULTISET_SETWISE_OPERATIONS(TYPENAME) \ 192 deBool TYPENAME##_union (TYPENAME* to, const TYPENAME* a, const TYPENAME* b); \ 193 deBool TYPENAME##_unionInplace (TYPENAME* a, const TYPENAME* b); \ 194 deBool TYPENAME##_intersect (TYPENAME* to, const TYPENAME* a, const TYPENAME* b); \ 195 void TYPENAME##_intersectInplace (TYPENAME* a, const TYPENAME* b); \ 196 deBool TYPENAME##_sum (TYPENAME* to, const TYPENAME* a, const TYPENAME* b); \ 197 deBool TYPENAME##_sumInplace (TYPENAME* a, const TYPENAME* b); \ 198 deBool TYPENAME##_difference (TYPENAME* to, const TYPENAME* a, const TYPENAME* b); \ 199 void TYPENAME##_differenceInplace (TYPENAME* a, const TYPENAME* b); \ 200 struct TYPENAME##SetwiseDeclareDummy_s { int dummy; } 201 202#define DE_IMPLEMENT_POOL_MULTISET_SETWISE_OPERATIONS(TYPENAME, KEYTYPE) \ 203deBool TYPENAME##_union (TYPENAME* to, const TYPENAME* a, const TYPENAME* b) \ 204{ \ 205 TYPENAME##_reset(to); \ 206 return TYPENAME##_unionInplace(to, a) && TYPENAME##_unionInplace(to, b); \ 207} \ 208\ 209deBool TYPENAME##_unionInplace (TYPENAME* a, const TYPENAME* b) \ 210{ \ 211 TYPENAME##HashIter iter; \ 212 for (TYPENAME##HashIter_init(b, &iter); \ 213 TYPENAME##HashIter_hasItem(&iter); \ 214 TYPENAME##HashIter_next(&iter)) \ 215 { \ 216 KEYTYPE key = TYPENAME##HashIter_getKey(&iter); \ 217 int bCount = TYPENAME##HashIter_getValue(&iter); \ 218 int aCount = TYPENAME##_getKeyCount(a, key); \ 219 int count = deMax32(aCount, bCount); \ 220 if (bCount && !TYPENAME##_setKeyCount(a, key, aCount + bCount)) \ 221 return DE_FALSE; \ 222 } \ 223 return DE_TRUE; \ 224} \ 225\ 226deBool TYPENAME##_intersect (TYPENAME* to, const TYPENAME* a, const TYPENAME* b) \ 227{ \ 228 TYPENAME##HashIter iter; \ 229 TYPENAME##_reset(to); \ 230 for (TYPENAME##HashIter_init(a, &iter); \ 231 TYPENAME##HashIter_hasItem(&iter); \ 232 TYPENAME##HashIter_next(&iter)) \ 233 { \ 234 KEYTYPE key = TYPENAME##HashIter_getKey(&iter); \ 235 int aCount = TYPENAME##HashIter_getValue(&iter); \ 236 int bCount = TYPENAME##_getKeyValue(b, key); \ 237 int count = deMin32(aCount, bCount); \ 238 if (count && !TYPENAME##_setKeyCount(to, key, count)) \ 239 return DE_FALSE; \ 240 } \ 241 return DE_TRUE; \ 242} \ 243\ 244void TYPENAME##_intersectInplace (TYPENAME* a, const TYPENAME* b) \ 245{ \ 246 DE_ASSERT(!"Not implemented."); \ 247} \ 248\ 249deBool TYPENAME##_sum (TYPENAME* to, const TYPENAME* a, const TYPENAME* b) \ 250{ \ 251 TYPENAME##_reset(to); \ 252 return TYPENAME##_sumInplace(to, a) && TYPENAME##_sumInplace(to, b); \ 253} \ 254\ 255deBool TYPENAME##_sumInplace (TYPENAME* a, const TYPENAME* b) \ 256{ \ 257 TYPENAME##HashIter iter; \ 258 for (TYPENAME##HashIter_init(b, &iter); \ 259 TYPENAME##HashIter_hasItem(&iter); \ 260 TYPENAME##HashIter_next(&iter)) \ 261 { \ 262 KEYTYPE key = TYPENAME##HashIter_getKey(&iter); \ 263 int aCount = TYPENAME##_getKeyValue(a, key); \ 264 int bCount = TYPENAME##HashIter_getValue(&iter); \ 265 int count = aCount + bCount; \ 266 if (!TYPENAME##_setKeyCount(a, key, count)) \ 267 return DE_FALSE; \ 268 } \ 269} \ 270\ 271deBool TYPENAME##_difference (TYPENAME* to, const TYPENAME* a, const TYPENAME* b) \ 272{ \ 273 TYPENAME##HashIter iter; \ 274 TYPENAME##_reset(to); \ 275 for (TYPENAME##HashIter_init(a, &iter); \ 276 TYPENAME##HashIter_hasItem(&iter); \ 277 TYPENAME##HashIter_next(&iter)) \ 278 { \ 279 KEYTYPE key = TYPENAME##HashIter_getKey(&iter); \ 280 int aCount = TYPENAME##HashIter_getValue(&iter); \ 281 int bCount = TYPENAME##_getKeyValue(b, key); \ 282 int count = deMax32(0, aCount - bCount); \ 283 if (count && !TYPENAME##_setKeyCount(to, key, count)) \ 284 return DE_FALSE; \ 285 } \ 286 return DE_TRUE; \ 287} \ 288\ 289void TYPENAME##_differenceInplace (TYPENAME* a, const TYPENAME* b) \ 290{ \ 291 DE_ASSERT(!"Not implemented."); \ 292} \ 293\ 294struct TYPENAME##SetwiseImplementDummy_s { int dummy; } 295 296#endif /* _DEPOOLMULTISET_H */ 297