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 * bool MultiSet_exists (const MultiSet* set, Key key); 55 * bool MultiSet_insert (MultiSet* set, Key key); 56 * void MultiSet_delete (MultiSet* set, Key key); 57 * int MultiSet_getKeyCount (const MultiSet* set, Key key); 58 * bool 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 bool 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 bool TYPENAME##_exists(const TYPENAME *set, KEYTYPE key) \ 90 { \ 91 return (TYPENAME##_getKeyCount(set, key) > 0); \ 92 } \ 93 \ 94 DE_INLINE bool 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##DeclareUnused_s \ 108 { \ 109 int unused; \ 110 } 111 112 /*--------------------------------------------------------------------*//*! 113 * \brief Implement a template pool multiset class. 114 * \param TYPENAME Type name of the declared multiset. 115 * \param KEYTYPE Type of the key. 116 * \param HASHFUNC Function used for hashing the key. 117 * \param CMPFUNC Function used for exact matching of the keys. 118 * 119 * This macro has implements the set declared with DE_DECLARE_POOL_MULTISET. 120 * Usually this macro should be used from a .c file, since the macro expands 121 * into multiple functions. The TYPENAME and KEYTYPE parameters 122 * must match those of the declare macro. 123 *//*--------------------------------------------------------------------*/ 124 #define DE_IMPLEMENT_POOL_MULTISET(TYPENAME, KEYTYPE, HASHFUNC, CMPFUNC) \ 125 \ 126 DE_IMPLEMENT_POOL_HASH(TYPENAME##Hash, KEYTYPE, int, HASHFUNC, CMPFUNC); \ 127 \ 128 TYPENAME *TYPENAME##_create(deMemPool *pool) \ 129 { \ 130 /* Alloc struct. */ \ 131 DE_PTR_TYPE(TYPENAME) set = DE_POOL_NEW(pool, TYPENAME); \ 132 if (!set) \ 133 return DE_NULL; \ 134 \ 135 /* Init. */ \ 136 memset(set, 0, sizeof(TYPENAME)); \ 137 set->pool = pool; \ 138 \ 139 set->hash = TYPENAME##Hash_create(pool); \ 140 \ 141 return set; \ 142 } \ 143 \ 144 void TYPENAME##_reset(DE_PTR_TYPE(TYPENAME) set) \ 145 { \ 146 TYPENAME##Hash_reset(set->hash); \ 147 set->numElements = 0; \ 148 } \ 149 \ 150 bool TYPENAME##_setKeyCount(DE_PTR_TYPE(TYPENAME) set, KEYTYPE key, int newCount) \ 151 { \ 152 int *countPtr = TYPENAME##Hash_find(set->hash, key); \ 153 int oldCount = countPtr ? *countPtr : 0; \ 154 \ 155 DE_ASSERT(oldCount > 0 || !countPtr); \ 156 DE_ASSERT(newCount >= 0); \ 157 set->numElements += (newCount - oldCount); \ 158 \ 159 if (newCount == 0 && countPtr) \ 160 TYPENAME##Hash_delete(set->hash, key); \ 161 else if (newCount > 0 && countPtr) \ 162 *countPtr = newCount; \ 163 else if (newCount > 0) \ 164 return TYPENAME##Hash_insert(set->hash, key, newCount); \ 165 return true; \ 166 } \ 167 \ 168 struct TYPENAME##ImplementUnused_s \ 169 { \ 170 int unused; \ 171 } 172 173 /*--------------------------------------------------------------------*//*! 174 * \brief Declare set-wise operations for a multiset template. 175 * \param TYPENAME Type name of the declared set. 176 * \param KEYTYPE Type of the key. 177 * 178 * This macro declares union and intersection operations for a multiset. 179 * For implementation see DE_IMPLEMENT_POOL_MULTISET_UNION_INTERSECT. 180 * 181 * \todo [petri] Detailed description. 182 * 183 * The functions for operating the set are: 184 * \todo [petri] Figure out how to comment these in Doxygen-style. 185 * 186 * \code 187 * bool MultiSet_union (Set* to, const Set* a, const Set* b); 188 * bool MultiSet_unionInplace (Set* a, const Set* b); 189 * bool MultiSet_intersect (Set* to, const Set* a, const Set* b); 190 * void MultiSet_intersectInplace (Set* a, const Set* b); 191 * bool MultiSet_sum (Set* to, const Set* a, const Set* b); 192 * bool MultiSet_sumInplace (Set* a, const Set* b); 193 * bool MultiSet_difference (Set* to, const Set* a, const Set* b); 194 * void MultiSet_differenceInplace (Set* a, const Set* b); 195 * \endcode 196 *//*--------------------------------------------------------------------*/ 197 #define DE_DECLARE_POOL_MULTISET_SETWISE_OPERATIONS(TYPENAME) \ 198 bool TYPENAME##_union(DE_PTR_TYPE(TYPENAME) to, const TYPENAME *a, const TYPENAME *b); \ 199 bool TYPENAME##_unionInplace(DE_PTR_TYPE(TYPENAME) a, const TYPENAME *b); \ 200 bool TYPENAME##_intersect(DE_PTR_TYPE(TYPENAME) to, const TYPENAME *a, const TYPENAME *b); \ 201 void TYPENAME##_intersectInplace(DE_PTR_TYPE(TYPENAME) a, const TYPENAME *b); \ 202 bool TYPENAME##_sum(DE_PTR_TYPE(TYPENAME) to, const TYPENAME *a, const TYPENAME *b); \ 203 bool TYPENAME##_sumInplace(DE_PTR_TYPE(TYPENAME) a, const TYPENAME *b); \ 204 bool TYPENAME##_difference(DE_PTR_TYPE(TYPENAME) to, const TYPENAME *a, const TYPENAME *b); \ 205 void TYPENAME##_differenceInplace(DE_PTR_TYPE(TYPENAME) a, const TYPENAME *b); \ 206 struct TYPENAME##SetwiseDeclareUnused_s \ 207 { \ 208 int unused; \ 209 } 210 211 #define DE_IMPLEMENT_POOL_MULTISET_SETWISE_OPERATIONS(TYPENAME, KEYTYPE) \ 212 bool TYPENAME##_union(DE_PTR_TYPE(TYPENAME) to, const TYPENAME *a, const TYPENAME *b) \ 213 { \ 214 TYPENAME##_reset(to); \ 215 return TYPENAME##_unionInplace(to, a) && TYPENAME##_unionInplace(to, b); \ 216 } \ 217 \ 218 bool TYPENAME##_unionInplace(DE_PTR_TYPE(TYPENAME) a, const TYPENAME *b) \ 219 { \ 220 TYPENAME##HashIter iter; \ 221 for (TYPENAME##HashIter_init(b, &iter); TYPENAME##HashIter_hasItem(&iter); TYPENAME##HashIter_next(&iter)) \ 222 { \ 223 KEYTYPE key = TYPENAME##HashIter_getKey(&iter); \ 224 int bCount = TYPENAME##HashIter_getValue(&iter); \ 225 int aCount = TYPENAME##_getKeyCount(a, key); \ 226 int count = deMax32(aCount, bCount); \ 227 if (bCount && !TYPENAME##_setKeyCount(a, key, aCount + bCount)) \ 228 return false; \ 229 } \ 230 return true; \ 231 } \ 232 \ 233 bool TYPENAME##_intersect(DE_PTR_TYPE(TYPENAME) to, const TYPENAME *a, const TYPENAME *b) \ 234 { \ 235 TYPENAME##HashIter iter; \ 236 TYPENAME##_reset(to); \ 237 for (TYPENAME##HashIter_init(a, &iter); TYPENAME##HashIter_hasItem(&iter); TYPENAME##HashIter_next(&iter)) \ 238 { \ 239 KEYTYPE key = TYPENAME##HashIter_getKey(&iter); \ 240 int aCount = TYPENAME##HashIter_getValue(&iter); \ 241 int bCount = TYPENAME##_getKeyValue(b, key); \ 242 int count = deMin32(aCount, bCount); \ 243 if (count && !TYPENAME##_setKeyCount(to, key, count)) \ 244 return false; \ 245 } \ 246 return true; \ 247 } \ 248 \ 249 void TYPENAME##_intersectInplace(DE_PTR_TYPE(TYPENAME) a, const TYPENAME *b) \ 250 { \ 251 DE_FATAL("Not implemented."); \ 252 } \ 253 \ 254 bool TYPENAME##_sum(DE_PTR_TYPE(TYPENAME) to, const TYPENAME *a, const TYPENAME *b) \ 255 { \ 256 TYPENAME##_reset(to); \ 257 return TYPENAME##_sumInplace(to, a) && TYPENAME##_sumInplace(to, b); \ 258 } \ 259 \ 260 bool TYPENAME##_sumInplace(DE_PTR_TYPE(TYPENAME) a, const TYPENAME *b) \ 261 { \ 262 TYPENAME##HashIter iter; \ 263 for (TYPENAME##HashIter_init(b, &iter); TYPENAME##HashIter_hasItem(&iter); TYPENAME##HashIter_next(&iter)) \ 264 { \ 265 KEYTYPE key = TYPENAME##HashIter_getKey(&iter); \ 266 int aCount = TYPENAME##_getKeyValue(a, key); \ 267 int bCount = TYPENAME##HashIter_getValue(&iter); \ 268 int count = aCount + bCount; \ 269 if (!TYPENAME##_setKeyCount(a, key, count)) \ 270 return false; \ 271 } \ 272 } \ 273 \ 274 bool TYPENAME##_difference(DE_PTR_TYPE(TYPENAME) to, const TYPENAME *a, const TYPENAME *b) \ 275 { \ 276 TYPENAME##HashIter iter; \ 277 TYPENAME##_reset(to); \ 278 for (TYPENAME##HashIter_init(a, &iter); TYPENAME##HashIter_hasItem(&iter); TYPENAME##HashIter_next(&iter)) \ 279 { \ 280 KEYTYPE key = TYPENAME##HashIter_getKey(&iter); \ 281 int aCount = TYPENAME##HashIter_getValue(&iter); \ 282 int bCount = TYPENAME##_getKeyValue(b, key); \ 283 int count = deMax32(0, aCount - bCount); \ 284 if (count && !TYPENAME##_setKeyCount(to, key, count)) \ 285 return false; \ 286 } \ 287 return true; \ 288 } \ 289 \ 290 void TYPENAME##_differenceInplace(DE_PTR_TYPE(TYPENAME) a, const TYPENAME *b) \ 291 { \ 292 DE_FATAL("Not implemented."); \ 293 } \ 294 \ 295 struct TYPENAME##SetwiseImplementUnused_s \ 296 { \ 297 int unused; \ 298 } 299 300 #endif /* _DEPOOLMULTISET_H */ 301