1 #ifndef _DEPOOLSET_H 2 #define _DEPOOLSET_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 set class. 24 *//*--------------------------------------------------------------------*/ 25 26 #include "deDefs.h" 27 #include "deMemPool.h" 28 #include "dePoolArray.h" 29 #include "deInt32.h" 30 31 #include <string.h> /* memset() */ 32 33 enum 34 { 35 DE_SET_ELEMENTS_PER_SLOT = 4 36 }; 37 38 DE_BEGIN_EXTERN_C 39 40 void dePoolSet_selfTest(void); 41 42 DE_END_EXTERN_C 43 44 /*--------------------------------------------------------------------*//*! 45 * \brief Declare a template pool set class interface. 46 * \param TYPENAME Type name of the declared set. 47 * \param KEYTYPE Type of the key. 48 * 49 * This macro declares the interface for a set. For the implementation of 50 * the set, see DE_IMPLEMENT_POOL_HASH. Usually this macro is put into the 51 * header file and the implementation macro is put in some .c file. 52 * 53 * \todo [petri] Detailed description. 54 * 55 * The functions for operating the set are: 56 * \todo [petri] Figure out how to comment these in Doxygen-style. 57 * 58 * \code 59 * Set* Set_create (deMemPool* pool); 60 * int Set_getNumElements (const Set* array); 61 * bool Set_exists (const Set* array, Key key); 62 * bool Set_insert (Set* array, Key key); 63 * void Set_delete (Set* array, Key key); 64 * \endcode 65 *//*--------------------------------------------------------------------*/ 66 #define DE_DECLARE_POOL_SET(TYPENAME, KEYTYPE) \ 67 \ 68 typedef struct TYPENAME##Slot_s TYPENAME##Slot; \ 69 \ 70 struct TYPENAME##Slot_s \ 71 { \ 72 int numUsed; \ 73 TYPENAME##Slot *nextSlot; \ 74 KEYTYPE keys[DE_SET_ELEMENTS_PER_SLOT]; \ 75 }; \ 76 \ 77 typedef struct TYPENAME##_s \ 78 { \ 79 deMemPool *pool; \ 80 int numElements; \ 81 \ 82 int slotTableSize; \ 83 TYPENAME##Slot **slotTable; \ 84 TYPENAME##Slot *slotFreeList; \ 85 } TYPENAME; /* NOLINT(TYPENAME) */ \ 86 \ 87 typedef struct TYPENAME##Iter_s \ 88 { \ 89 const TYPENAME *hash; \ 90 int curSlotIndex; \ 91 const TYPENAME##Slot *curSlot; \ 92 int curElemIndex; \ 93 } TYPENAME##Iter; \ 94 \ 95 TYPENAME *TYPENAME##_create(deMemPool *pool); \ 96 void TYPENAME##_reset(DE_PTR_TYPE(TYPENAME) set); \ 97 bool TYPENAME##_reserve(DE_PTR_TYPE(TYPENAME) set, int capacity); \ 98 bool TYPENAME##_exists(const TYPENAME *set, KEYTYPE key); \ 99 bool TYPENAME##_insert(DE_PTR_TYPE(TYPENAME) set, KEYTYPE key); \ 100 void TYPENAME##_delete(DE_PTR_TYPE(TYPENAME) set, KEYTYPE key); \ 101 \ 102 DE_INLINE int TYPENAME##_getNumElements(const TYPENAME *set) DE_UNUSED_FUNCTION; \ 103 DE_INLINE void TYPENAME##Iter_init(const TYPENAME *hash, TYPENAME##Iter *iter) DE_UNUSED_FUNCTION; \ 104 DE_INLINE bool TYPENAME##Iter_hasItem(const TYPENAME##Iter *iter) DE_UNUSED_FUNCTION; \ 105 DE_INLINE void TYPENAME##Iter_next(TYPENAME##Iter *iter) DE_UNUSED_FUNCTION; \ 106 DE_INLINE KEYTYPE TYPENAME##Iter_getKey(const TYPENAME##Iter *iter) DE_UNUSED_FUNCTION; \ 107 DE_INLINE bool TYPENAME##_safeInsert(DE_PTR_TYPE(TYPENAME) set, KEYTYPE key) DE_UNUSED_FUNCTION; \ 108 DE_INLINE void TYPENAME##_safeDelete(DE_PTR_TYPE(TYPENAME) set, KEYTYPE key) DE_UNUSED_FUNCTION; \ 109 \ 110 DE_INLINE int TYPENAME##_getNumElements(const TYPENAME *set) \ 111 { \ 112 return set->numElements; \ 113 } \ 114 \ 115 DE_INLINE void TYPENAME##Iter_init(const TYPENAME *hash, TYPENAME##Iter *iter) \ 116 { \ 117 iter->hash = hash; \ 118 iter->curSlotIndex = 0; \ 119 iter->curSlot = DE_NULL; \ 120 iter->curElemIndex = 0; \ 121 if (TYPENAME##_getNumElements(hash) > 0) \ 122 { \ 123 int slotTableSize = hash->slotTableSize; \ 124 int slotNdx = 0; \ 125 while (slotNdx < slotTableSize) \ 126 { \ 127 if (hash->slotTable[slotNdx]) \ 128 break; \ 129 slotNdx++; \ 130 } \ 131 DE_ASSERT(slotNdx < slotTableSize); \ 132 iter->curSlotIndex = slotNdx; \ 133 iter->curSlot = hash->slotTable[slotNdx]; \ 134 DE_ASSERT(iter->curSlot); \ 135 } \ 136 } \ 137 \ 138 DE_INLINE bool TYPENAME##Iter_hasItem(const TYPENAME##Iter *iter) \ 139 { \ 140 return (iter->curSlot != DE_NULL); \ 141 } \ 142 \ 143 DE_INLINE void TYPENAME##Iter_next(TYPENAME##Iter *iter) \ 144 { \ 145 DE_ASSERT(TYPENAME##Iter_hasItem(iter)); \ 146 if (++iter->curElemIndex == iter->curSlot->numUsed) \ 147 { \ 148 iter->curElemIndex = 0; \ 149 if (iter->curSlot->nextSlot) \ 150 { \ 151 iter->curSlot = iter->curSlot->nextSlot; \ 152 } \ 153 else \ 154 { \ 155 const TYPENAME *hash = iter->hash; \ 156 int curSlotIndex = iter->curSlotIndex; \ 157 int slotTableSize = hash->slotTableSize; \ 158 while (++curSlotIndex < slotTableSize) \ 159 { \ 160 if (hash->slotTable[curSlotIndex]) \ 161 break; \ 162 } \ 163 iter->curSlotIndex = curSlotIndex; \ 164 if (curSlotIndex < slotTableSize) \ 165 iter->curSlot = hash->slotTable[curSlotIndex]; \ 166 else \ 167 iter->curSlot = DE_NULL; \ 168 } \ 169 } \ 170 } \ 171 \ 172 DE_INLINE KEYTYPE TYPENAME##Iter_getKey(const TYPENAME##Iter *iter) \ 173 { \ 174 DE_ASSERT(TYPENAME##Iter_hasItem(iter)); \ 175 return iter->curSlot->keys[iter->curElemIndex]; \ 176 } \ 177 \ 178 DE_INLINE bool TYPENAME##_safeInsert(DE_PTR_TYPE(TYPENAME) set, KEYTYPE key) \ 179 { \ 180 DE_ASSERT(set); \ 181 if (TYPENAME##_exists(set, key)) \ 182 return true; \ 183 return TYPENAME##_insert(set, key); \ 184 } \ 185 \ 186 DE_INLINE void TYPENAME##_safeDelete(DE_PTR_TYPE(TYPENAME) set, KEYTYPE key) \ 187 { \ 188 DE_ASSERT(set); \ 189 if (TYPENAME##_exists(set, key)) \ 190 TYPENAME##_delete(set, key); \ 191 } \ 192 \ 193 struct TYPENAME##Unused_s \ 194 { \ 195 int unused; \ 196 } 197 198 /*--------------------------------------------------------------------*//*! 199 * \brief Implement a template pool set class. 200 * \param TYPENAME Type name of the declared set. 201 * \param KEYTYPE Type of the key. 202 * \param HASHFUNC Function used for hashing the key. 203 * \param CMPFUNC Function used for exact matching of the keys. 204 * 205 * This macro has implements the set declared with DE_DECLARE_POOL_SET. 206 * Usually this macro should be used from a .c file, since the macro expands 207 * into multiple functions. The TYPENAME and KEYTYPE parameters 208 * must match those of the declare macro. 209 *//*--------------------------------------------------------------------*/ 210 #define DE_IMPLEMENT_POOL_SET(TYPENAME, KEYTYPE, HASHFUNC, CMPFUNC) \ 211 \ 212 DE_PTR_TYPE(TYPENAME) TYPENAME##_create(deMemPool *pool) \ 213 { \ 214 /* Alloc struct. */ \ 215 DE_PTR_TYPE(TYPENAME) set = DE_POOL_NEW(pool, TYPENAME); \ 216 if (!set) \ 217 return DE_NULL; \ 218 \ 219 /* Init array. */ \ 220 memset(set, 0, sizeof(TYPENAME)); \ 221 set->pool = pool; \ 222 \ 223 return set; \ 224 } \ 225 \ 226 void TYPENAME##_reset(DE_PTR_TYPE(TYPENAME) set) \ 227 { \ 228 int slotNdx; \ 229 for (slotNdx = 0; slotNdx < set->slotTableSize; slotNdx++) \ 230 { \ 231 TYPENAME##Slot *slot = set->slotTable[slotNdx]; \ 232 while (slot) \ 233 { \ 234 TYPENAME##Slot *nextSlot = slot->nextSlot; \ 235 slot->nextSlot = set->slotFreeList; \ 236 set->slotFreeList = slot; \ 237 slot->numUsed = 0; \ 238 slot = nextSlot; \ 239 } \ 240 set->slotTable[slotNdx] = DE_NULL; \ 241 } \ 242 set->numElements = 0; \ 243 } \ 244 \ 245 TYPENAME##Slot *TYPENAME##_allocSlot(DE_PTR_TYPE(TYPENAME) set) \ 246 { \ 247 TYPENAME##Slot *slot; \ 248 if (set->slotFreeList) \ 249 { \ 250 slot = set->slotFreeList; \ 251 set->slotFreeList = set->slotFreeList->nextSlot; \ 252 } \ 253 else \ 254 slot = (TYPENAME##Slot *)deMemPool_alloc(set->pool, sizeof(TYPENAME##Slot) * DE_SET_ELEMENTS_PER_SLOT); \ 255 \ 256 if (slot) \ 257 { \ 258 slot->nextSlot = DE_NULL; \ 259 slot->numUsed = 0; \ 260 } \ 261 \ 262 return slot; \ 263 } \ 264 \ 265 bool TYPENAME##_rehash(DE_PTR_TYPE(TYPENAME) set, int newSlotTableSize) \ 266 { \ 267 DE_ASSERT(deIsPowerOfTwo32(newSlotTableSize) && newSlotTableSize > 0); \ 268 if (newSlotTableSize > set->slotTableSize) \ 269 { \ 270 TYPENAME##Slot **oldSlotTable = set->slotTable; \ 271 TYPENAME##Slot **newSlotTable = \ 272 (TYPENAME##Slot **)deMemPool_alloc(set->pool, sizeof(TYPENAME##Slot *) * (size_t)newSlotTableSize); \ 273 int oldSlotTableSize = set->slotTableSize; \ 274 int slotNdx; \ 275 \ 276 if (!newSlotTable) \ 277 return false; \ 278 \ 279 for (slotNdx = 0; slotNdx < oldSlotTableSize; slotNdx++) \ 280 newSlotTable[slotNdx] = oldSlotTable[slotNdx]; \ 281 \ 282 for (slotNdx = oldSlotTableSize; slotNdx < newSlotTableSize; slotNdx++) \ 283 newSlotTable[slotNdx] = DE_NULL; \ 284 \ 285 set->slotTableSize = newSlotTableSize; \ 286 set->slotTable = newSlotTable; \ 287 \ 288 for (slotNdx = 0; slotNdx < oldSlotTableSize; slotNdx++) \ 289 { \ 290 TYPENAME##Slot *slot = oldSlotTable[slotNdx]; \ 291 newSlotTable[slotNdx] = DE_NULL; \ 292 while (slot) \ 293 { \ 294 int elemNdx; \ 295 for (elemNdx = 0; elemNdx < slot->numUsed; elemNdx++) \ 296 { \ 297 set->numElements--; \ 298 if (!TYPENAME##_insert(set, slot->keys[elemNdx])) \ 299 return false; \ 300 } \ 301 slot = slot->nextSlot; \ 302 } \ 303 } \ 304 } \ 305 \ 306 return true; \ 307 } \ 308 \ 309 bool TYPENAME##_exists(const TYPENAME *set, KEYTYPE key) \ 310 { \ 311 if (set->numElements > 0) \ 312 { \ 313 int slotNdx = (int)(HASHFUNC(key) & (uint32_t)(set->slotTableSize - 1)); \ 314 TYPENAME##Slot *slot = set->slotTable[slotNdx]; \ 315 DE_ASSERT(deInBounds32(slotNdx, 0, set->slotTableSize)); \ 316 \ 317 while (slot) \ 318 { \ 319 int elemNdx; \ 320 for (elemNdx = 0; elemNdx < slot->numUsed; elemNdx++) \ 321 { \ 322 if (CMPFUNC(slot->keys[elemNdx], key)) \ 323 return true; \ 324 } \ 325 slot = slot->nextSlot; \ 326 } \ 327 } \ 328 \ 329 return false; \ 330 } \ 331 \ 332 bool TYPENAME##_insert(DE_PTR_TYPE(TYPENAME) set, KEYTYPE key) \ 333 { \ 334 int slotNdx; \ 335 TYPENAME##Slot *slot; \ 336 \ 337 DE_ASSERT(set); \ 338 DE_ASSERT(!TYPENAME##_exists(set, key)); \ 339 \ 340 if ((set->numElements + 1) >= set->slotTableSize * DE_SET_ELEMENTS_PER_SLOT) \ 341 if (!TYPENAME##_rehash(set, deMax32(4, 2 * set->slotTableSize))) \ 342 return false; \ 343 \ 344 slotNdx = (int)(HASHFUNC(key) & (uint32_t)(set->slotTableSize - 1)); \ 345 DE_ASSERT(slotNdx >= 0 && slotNdx < set->slotTableSize); \ 346 slot = set->slotTable[slotNdx]; \ 347 \ 348 if (!slot) \ 349 { \ 350 slot = TYPENAME##_allocSlot(set); \ 351 if (!slot) \ 352 return false; \ 353 set->slotTable[slotNdx] = slot; \ 354 } \ 355 \ 356 for (;;) \ 357 { \ 358 if (slot->numUsed == DE_SET_ELEMENTS_PER_SLOT) \ 359 { \ 360 if (slot->nextSlot) \ 361 slot = slot->nextSlot; \ 362 else \ 363 { \ 364 TYPENAME##Slot *nextSlot = TYPENAME##_allocSlot(set); \ 365 if (!nextSlot) \ 366 return false; \ 367 slot->nextSlot = nextSlot; \ 368 slot = nextSlot; \ 369 } \ 370 } \ 371 else \ 372 { \ 373 slot->keys[slot->numUsed] = key; \ 374 slot->numUsed++; \ 375 set->numElements++; \ 376 return true; \ 377 } \ 378 } \ 379 } \ 380 \ 381 void TYPENAME##_delete(DE_PTR_TYPE(TYPENAME) set, KEYTYPE key) \ 382 { \ 383 int slotNdx; \ 384 TYPENAME##Slot *slot; \ 385 TYPENAME##Slot *prevSlot = DE_NULL; \ 386 \ 387 DE_ASSERT(set->numElements > 0); \ 388 slotNdx = (int)(HASHFUNC(key) & (uint32_t)(set->slotTableSize - 1)); \ 389 DE_ASSERT(slotNdx >= 0 && slotNdx < set->slotTableSize); \ 390 slot = set->slotTable[slotNdx]; \ 391 DE_ASSERT(slot); \ 392 \ 393 for (;;) \ 394 { \ 395 int elemNdx; \ 396 DE_ASSERT(slot->numUsed > 0); \ 397 for (elemNdx = 0; elemNdx < slot->numUsed; elemNdx++) \ 398 { \ 399 if (CMPFUNC(key, slot->keys[elemNdx])) \ 400 { \ 401 TYPENAME##Slot *lastSlot = slot; \ 402 while (lastSlot->nextSlot) \ 403 { \ 404 prevSlot = lastSlot; \ 405 lastSlot = lastSlot->nextSlot; \ 406 } \ 407 \ 408 slot->keys[elemNdx] = lastSlot->keys[lastSlot->numUsed - 1]; \ 409 lastSlot->numUsed--; \ 410 \ 411 if (lastSlot->numUsed == 0) \ 412 { \ 413 if (prevSlot) \ 414 prevSlot->nextSlot = DE_NULL; \ 415 else \ 416 set->slotTable[slotNdx] = DE_NULL; \ 417 \ 418 lastSlot->nextSlot = set->slotFreeList; \ 419 set->slotFreeList = lastSlot; \ 420 } \ 421 \ 422 set->numElements--; \ 423 return; \ 424 } \ 425 } \ 426 \ 427 prevSlot = slot; \ 428 slot = slot->nextSlot; \ 429 DE_ASSERT(slot); \ 430 } \ 431 } \ 432 \ 433 struct TYPENAME##Unused2_s \ 434 { \ 435 int unused; \ 436 } 437 438 /* Copy-to-array templates. */ 439 440 #define DE_DECLARE_POOL_SET_TO_ARRAY(SETTYPENAME, ARRAYTYPENAME) \ 441 bool SETTYPENAME##_copyToArray(const SETTYPENAME *set, DE_PTR_TYPE(ARRAYTYPENAME) array); \ 442 struct SETTYPENAME##_##ARRAYTYPENAME##_declare_unused \ 443 { \ 444 int unused; \ 445 } 446 447 #define DE_IMPLEMENT_POOL_SET_TO_ARRAY(SETTYPENAME, ARRAYTYPENAME) \ 448 bool SETTYPENAME##_copyToArray(const SETTYPENAME *set, DE_PTR_TYPE(ARRAYTYPENAME) array) \ 449 { \ 450 int numElements = set->numElements; \ 451 int arrayNdx = 0; \ 452 int slotNdx; \ 453 \ 454 if (!ARRAYTYPENAME##_setSize(array, numElements)) \ 455 return false; \ 456 \ 457 for (slotNdx = 0; slotNdx < set->slotTableSize; slotNdx++) \ 458 { \ 459 const SETTYPENAME##Slot *slot = set->slotTable[slotNdx]; \ 460 while (slot) \ 461 { \ 462 int elemNdx; \ 463 for (elemNdx = 0; elemNdx < slot->numUsed; elemNdx++) \ 464 ARRAYTYPENAME##_set(array, arrayNdx++, slot->keys[elemNdx]); \ 465 slot = slot->nextSlot; \ 466 } \ 467 } \ 468 DE_ASSERT(arrayNdx == numElements); \ 469 return true; \ 470 } \ 471 struct SETTYPENAME##_##ARRAYTYPENAME##_implement_unused \ 472 { \ 473 int unused; \ 474 } 475 476 /*--------------------------------------------------------------------*//*! 477 * \brief Declare set-wise operations for a set template. 478 * \param TYPENAME Type name of the declared set. 479 * \param KEYTYPE Type of the key. 480 * 481 * This macro declares union and intersection operations for a set. 482 * For implementation see DE_IMPLEMENT_POOL_SET_UNION_INTERSECT. 483 * 484 * \todo [petri] Detailed description. 485 * 486 * The functions for operating the set are: 487 * \todo [petri] Figure out how to comment these in Doxygen-style. 488 * 489 * \code 490 * bool Set_union (Set* to, const Set* a, const Set* b); 491 * bool Set_unionInplace (Set* a, const Set* b); 492 * bool Set_intersect (Set* to, const Set* a, const Set* b); 493 * void Set_intersectInplace (Set* a, const Set* b); 494 * bool Set_difference (Set* to, const Set* a, const Set* b); 495 * void Set_differenceInplace (Set* a, const Set* b); 496 * \endcode 497 *//*--------------------------------------------------------------------*/ 498 #define DE_DECLARE_POOL_SET_SETWISE_OPERATIONS(TYPENAME) \ 499 bool TYPENAME##_union(DE_PTR_TYPE(TYPENAME) to, const TYPENAME *a, const TYPENAME *b); \ 500 bool TYPENAME##_unionInplace(DE_PTR_TYPE(TYPENAME) a, const TYPENAME *b); \ 501 bool TYPENAME##_intersect(DE_PTR_TYPE(TYPENAME) to, const TYPENAME *a, const TYPENAME *b); \ 502 void TYPENAME##_intersectInplace(DE_PTR_TYPE(TYPENAME) a, const TYPENAME *b); \ 503 bool TYPENAME##_difference(DE_PTR_TYPE(TYPENAME) to, const TYPENAME *a, const TYPENAME *b); \ 504 void TYPENAME##_differenceInplace(DE_PTR_TYPE(TYPENAME) a, const TYPENAME *b); \ 505 struct TYPENAME##SetwiseDeclareUnused_s \ 506 { \ 507 int unused; \ 508 } 509 510 #define DE_IMPLEMENT_POOL_SET_SETWISE_OPERATIONS(TYPENAME, KEYTYPE) \ 511 bool TYPENAME##_union(DE_PTR_TYPE(TYPENAME) to, const TYPENAME *a, const TYPENAME *b) \ 512 { \ 513 TYPENAME##_reset(to); \ 514 if (!TYPENAME##_unionInplace(to, a)) \ 515 return false; \ 516 if (!TYPENAME##_unionInplace(to, b)) \ 517 return false; \ 518 return true; \ 519 } \ 520 \ 521 bool TYPENAME##_unionInplace(DE_PTR_TYPE(TYPENAME) a, const TYPENAME *b) \ 522 { \ 523 TYPENAME##Iter iter; \ 524 for (TYPENAME##Iter_init(b, &iter); TYPENAME##Iter_hasItem(&iter); TYPENAME##Iter_next(&iter)) \ 525 { \ 526 KEYTYPE key = TYPENAME##Iter_getKey(&iter); \ 527 if (!TYPENAME##_exists(a, key)) \ 528 { \ 529 if (!TYPENAME##_insert(a, key)) \ 530 return false; \ 531 } \ 532 } \ 533 return true; \ 534 } \ 535 \ 536 bool TYPENAME##_intersect(DE_PTR_TYPE(TYPENAME) to, const TYPENAME *a, const TYPENAME *b) \ 537 { \ 538 TYPENAME##Iter iter; \ 539 TYPENAME##_reset(to); \ 540 for (TYPENAME##Iter_init(a, &iter); TYPENAME##Iter_hasItem(&iter); TYPENAME##Iter_next(&iter)) \ 541 { \ 542 KEYTYPE key = TYPENAME##Iter_getKey(&iter); \ 543 if (TYPENAME##_exists(b, key)) \ 544 { \ 545 if (!TYPENAME##_insert(to, key)) \ 546 return false; \ 547 } \ 548 } \ 549 return true; \ 550 } \ 551 \ 552 void TYPENAME##_intersectInplace(DE_PTR_TYPE(TYPENAME) a, const TYPENAME *b) \ 553 { \ 554 DE_UNREF(a &&b); \ 555 DE_FATAL("Not implemented."); \ 556 } \ 557 \ 558 bool TYPENAME##_difference(DE_PTR_TYPE(TYPENAME) to, const TYPENAME *a, const TYPENAME *b) \ 559 { \ 560 TYPENAME##Iter iter; \ 561 TYPENAME##_reset(to); \ 562 for (TYPENAME##Iter_init(a, &iter); TYPENAME##Iter_hasItem(&iter); TYPENAME##Iter_next(&iter)) \ 563 { \ 564 KEYTYPE key = TYPENAME##Iter_getKey(&iter); \ 565 if (!TYPENAME##_exists(b, key)) \ 566 { \ 567 if (!TYPENAME##_insert(to, key)) \ 568 return false; \ 569 } \ 570 } \ 571 return true; \ 572 } \ 573 \ 574 void TYPENAME##_differenceInplace(DE_PTR_TYPE(TYPENAME) a, const TYPENAME *b) \ 575 { \ 576 TYPENAME##Iter iter; \ 577 for (TYPENAME##Iter_init(b, &iter); TYPENAME##Iter_hasItem(&iter); TYPENAME##Iter_next(&iter)) \ 578 { \ 579 KEYTYPE key = TYPENAME##Iter_getKey(&iter); \ 580 if (TYPENAME##_exists(a, key)) \ 581 TYPENAME##_delete(a, key); \ 582 } \ 583 } \ 584 \ 585 struct TYPENAME##UnionIntersectImplementUnused_s \ 586 { \ 587 int unused; \ 588 } 589 590 #endif /* _DEPOOLSET_H */ 591