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 31 DE_BEGIN_EXTERN_C 32 33 void dePoolMultiSet_selfTest (void); 34 35 DE_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 \ 63 DE_DECLARE_POOL_HASH(TYPENAME##Hash, KEYTYPE, int); \ 64 \ 65 typedef struct TYPENAME##_s \ 66 { \ 67 deMemPool* pool; \ 68 int numElements; \ 69 TYPENAME##Hash* hash; \ 70 } TYPENAME; /* NOLINT(TYPENAME) */ \ 71 \ 72 TYPENAME* TYPENAME##_create (deMemPool* pool); \ 73 void TYPENAME##_reset (DE_PTR_TYPE(TYPENAME) set); \ 74 deBool TYPENAME##_setKeyCount (DE_PTR_TYPE(TYPENAME) set, KEYTYPE key, int newCount); \ 75 \ 76 DE_INLINE int TYPENAME##_getNumElements (const TYPENAME* set) \ 77 { \ 78 return set->numElements; \ 79 } \ 80 \ 81 DE_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 \ 89 DE_INLINE deBool TYPENAME##_exists (const TYPENAME* set, KEYTYPE key) \ 90 { \ 91 return (TYPENAME##_getKeyCount(set, key) > 0); \ 92 } \ 93 \ 94 DE_INLINE deBool TYPENAME##_insert (DE_PTR_TYPE(TYPENAME) set, KEYTYPE key) \ 95 { \ 96 int oldCount = TYPENAME##_getKeyCount(set, key); \ 97 return TYPENAME##_setKeyCount(set, key, oldCount + 1); \ 98 } \ 99 \ 100 DE_INLINE void TYPENAME##_delete (DE_PTR_TYPE(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 \ 107 struct 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 \ 123 DE_IMPLEMENT_POOL_HASH(TYPENAME##Hash, KEYTYPE, int, HASHFUNC, CMPFUNC); \ 124 \ 125 TYPENAME* TYPENAME##_create (deMemPool* pool) \ 126 { \ 127 /* Alloc struct. */ \ 128 DE_PTR_TYPE(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 \ 141 void TYPENAME##_reset (DE_PTR_TYPE(TYPENAME) set) \ 142 { \ 143 TYPENAME##Hash_reset(set->hash); \ 144 set->numElements = 0; \ 145 } \ 146 \ 147 deBool TYPENAME##_setKeyCount (DE_PTR_TYPE(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 \ 165 struct 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 (DE_PTR_TYPE(TYPENAME) to, const TYPENAME* a, const TYPENAME* b); \ 193 deBool TYPENAME##_unionInplace (DE_PTR_TYPE(TYPENAME) a, const TYPENAME* b); \ 194 deBool TYPENAME##_intersect (DE_PTR_TYPE(TYPENAME) to, const TYPENAME* a, const TYPENAME* b); \ 195 void TYPENAME##_intersectInplace (DE_PTR_TYPE(TYPENAME) a, const TYPENAME* b); \ 196 deBool TYPENAME##_sum (DE_PTR_TYPE(TYPENAME) to, const TYPENAME* a, const TYPENAME* b); \ 197 deBool TYPENAME##_sumInplace (DE_PTR_TYPE(TYPENAME) a, const TYPENAME* b); \ 198 deBool TYPENAME##_difference (DE_PTR_TYPE(TYPENAME) to, const TYPENAME* a, const TYPENAME* b); \ 199 void TYPENAME##_differenceInplace (DE_PTR_TYPE(TYPENAME) a, const TYPENAME* b); \ 200 struct TYPENAME##SetwiseDeclareDummy_s { int dummy; } 201 202 #define DE_IMPLEMENT_POOL_MULTISET_SETWISE_OPERATIONS(TYPENAME, KEYTYPE) \ 203 deBool TYPENAME##_union (DE_PTR_TYPE(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 \ 209 deBool TYPENAME##_unionInplace (DE_PTR_TYPE(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 \ 226 deBool TYPENAME##_intersect (DE_PTR_TYPE(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 \ 244 void TYPENAME##_intersectInplace (DE_PTR_TYPE(TYPENAME) a, const TYPENAME* b) \ 245 { \ 246 DE_FATAL("Not implemented."); \ 247 } \ 248 \ 249 deBool TYPENAME##_sum (DE_PTR_TYPE(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 \ 255 deBool TYPENAME##_sumInplace (DE_PTR_TYPE(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 \ 271 deBool TYPENAME##_difference (DE_PTR_TYPE(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 \ 289 void TYPENAME##_differenceInplace (DE_PTR_TYPE(TYPENAME) a, const TYPENAME* b) \ 290 { \ 291 DE_FATAL("Not implemented."); \ 292 } \ 293 \ 294 struct TYPENAME##SetwiseImplementDummy_s { int dummy; } 295 296 #endif /* _DEPOOLMULTISET_H */ 297