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 * deBool Set_exists (const Set* array, Key key); 62 * deBool 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 deBool TYPENAME##_reserve (DE_PTR_TYPE(TYPENAME) set, int capacity); \ 98 deBool TYPENAME##_exists (const TYPENAME* set, KEYTYPE key); \ 99 deBool 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 deBool 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 deBool 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 deBool 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 deBool TYPENAME##_safeInsert (DE_PTR_TYPE(TYPENAME) set, KEYTYPE key) \ 179 { \ 180 DE_ASSERT(set); \ 181 if (TYPENAME##_exists(set, key)) \ 182 return DE_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 { int unused; } 194 195 /*--------------------------------------------------------------------*//*! 196 * \brief Implement a template pool set class. 197 * \param TYPENAME Type name of the declared set. 198 * \param KEYTYPE Type of the key. 199 * \param HASHFUNC Function used for hashing the key. 200 * \param CMPFUNC Function used for exact matching of the keys. 201 * 202 * This macro has implements the set declared with DE_DECLARE_POOL_SET. 203 * Usually this macro should be used from a .c file, since the macro expands 204 * into multiple functions. The TYPENAME and KEYTYPE parameters 205 * must match those of the declare macro. 206 *//*--------------------------------------------------------------------*/ 207 #define DE_IMPLEMENT_POOL_SET(TYPENAME, KEYTYPE, HASHFUNC, CMPFUNC) \ 208 \ 209 DE_PTR_TYPE(TYPENAME) TYPENAME##_create (deMemPool* pool) \ 210 { \ 211 /* Alloc struct. */ \ 212 DE_PTR_TYPE(TYPENAME) set = DE_POOL_NEW(pool, TYPENAME); \ 213 if (!set) \ 214 return DE_NULL; \ 215 \ 216 /* Init array. */ \ 217 memset(set, 0, sizeof(TYPENAME)); \ 218 set->pool = pool; \ 219 \ 220 return set; \ 221 } \ 222 \ 223 void TYPENAME##_reset (DE_PTR_TYPE(TYPENAME) set) \ 224 { \ 225 int slotNdx; \ 226 for (slotNdx = 0; slotNdx < set->slotTableSize; slotNdx++) \ 227 { \ 228 TYPENAME##Slot* slot = set->slotTable[slotNdx]; \ 229 while (slot) \ 230 { \ 231 TYPENAME##Slot* nextSlot = slot->nextSlot; \ 232 slot->nextSlot = set->slotFreeList; \ 233 set->slotFreeList = slot; \ 234 slot->numUsed = 0; \ 235 slot = nextSlot; \ 236 } \ 237 set->slotTable[slotNdx] = DE_NULL; \ 238 } \ 239 set->numElements = 0; \ 240 } \ 241 \ 242 TYPENAME##Slot* TYPENAME##_allocSlot (DE_PTR_TYPE(TYPENAME) set) \ 243 { \ 244 TYPENAME##Slot* slot; \ 245 if (set->slotFreeList) \ 246 { \ 247 slot = set->slotFreeList; \ 248 set->slotFreeList = set->slotFreeList->nextSlot; \ 249 } \ 250 else \ 251 slot = (TYPENAME##Slot*)deMemPool_alloc(set->pool, sizeof(TYPENAME##Slot) * DE_SET_ELEMENTS_PER_SLOT); \ 252 \ 253 if (slot) \ 254 { \ 255 slot->nextSlot = DE_NULL; \ 256 slot->numUsed = 0; \ 257 } \ 258 \ 259 return slot; \ 260 } \ 261 \ 262 deBool TYPENAME##_rehash (DE_PTR_TYPE(TYPENAME) set, int newSlotTableSize) \ 263 { \ 264 DE_ASSERT(deIsPowerOfTwo32(newSlotTableSize) && newSlotTableSize > 0); \ 265 if (newSlotTableSize > set->slotTableSize) \ 266 { \ 267 TYPENAME##Slot** oldSlotTable = set->slotTable; \ 268 TYPENAME##Slot** newSlotTable = (TYPENAME##Slot**)deMemPool_alloc(set->pool, sizeof(TYPENAME##Slot*) * (size_t)newSlotTableSize); \ 269 int oldSlotTableSize = set->slotTableSize; \ 270 int slotNdx; \ 271 \ 272 if (!newSlotTable) \ 273 return DE_FALSE; \ 274 \ 275 for (slotNdx = 0; slotNdx < oldSlotTableSize; slotNdx++) \ 276 newSlotTable[slotNdx] = oldSlotTable[slotNdx]; \ 277 \ 278 for (slotNdx = oldSlotTableSize; slotNdx < newSlotTableSize; slotNdx++) \ 279 newSlotTable[slotNdx] = DE_NULL; \ 280 \ 281 set->slotTableSize = newSlotTableSize; \ 282 set->slotTable = newSlotTable; \ 283 \ 284 for (slotNdx = 0; slotNdx < oldSlotTableSize; slotNdx++) \ 285 { \ 286 TYPENAME##Slot* slot = oldSlotTable[slotNdx]; \ 287 newSlotTable[slotNdx] = DE_NULL; \ 288 while (slot) \ 289 { \ 290 int elemNdx; \ 291 for (elemNdx = 0; elemNdx < slot->numUsed; elemNdx++) \ 292 { \ 293 set->numElements--; \ 294 if (!TYPENAME##_insert(set, slot->keys[elemNdx])) \ 295 return DE_FALSE; \ 296 } \ 297 slot = slot->nextSlot; \ 298 } \ 299 } \ 300 } \ 301 \ 302 return DE_TRUE; \ 303 } \ 304 \ 305 deBool TYPENAME##_exists (const TYPENAME* set, KEYTYPE key) \ 306 { \ 307 if (set->numElements > 0) \ 308 { \ 309 int slotNdx = (int)(HASHFUNC(key) & (deUint32)(set->slotTableSize - 1)); \ 310 TYPENAME##Slot* slot = set->slotTable[slotNdx]; \ 311 DE_ASSERT(deInBounds32(slotNdx, 0, set->slotTableSize)); \ 312 \ 313 while (slot) \ 314 { \ 315 int elemNdx; \ 316 for (elemNdx = 0; elemNdx < slot->numUsed; elemNdx++) \ 317 { \ 318 if (CMPFUNC(slot->keys[elemNdx], key)) \ 319 return DE_TRUE; \ 320 } \ 321 slot = slot->nextSlot; \ 322 } \ 323 } \ 324 \ 325 return DE_FALSE; \ 326 } \ 327 \ 328 deBool TYPENAME##_insert (DE_PTR_TYPE(TYPENAME) set, KEYTYPE key) \ 329 { \ 330 int slotNdx; \ 331 TYPENAME##Slot* slot; \ 332 \ 333 DE_ASSERT(set); \ 334 DE_ASSERT(!TYPENAME##_exists(set, key)); \ 335 \ 336 if ((set->numElements + 1) >= set->slotTableSize * DE_SET_ELEMENTS_PER_SLOT) \ 337 if (!TYPENAME##_rehash(set, deMax32(4, 2*set->slotTableSize))) \ 338 return DE_FALSE; \ 339 \ 340 slotNdx = (int)(HASHFUNC(key) & (deUint32)(set->slotTableSize - 1)); \ 341 DE_ASSERT(slotNdx >= 0 && slotNdx < set->slotTableSize); \ 342 slot = set->slotTable[slotNdx]; \ 343 \ 344 if (!slot) \ 345 { \ 346 slot = TYPENAME##_allocSlot(set); \ 347 if (!slot) return DE_FALSE; \ 348 set->slotTable[slotNdx] = slot; \ 349 } \ 350 \ 351 for (;;) \ 352 { \ 353 if (slot->numUsed == DE_SET_ELEMENTS_PER_SLOT) \ 354 { \ 355 if (slot->nextSlot) \ 356 slot = slot->nextSlot; \ 357 else \ 358 { \ 359 TYPENAME##Slot* nextSlot = TYPENAME##_allocSlot(set); \ 360 if (!nextSlot) return DE_FALSE; \ 361 slot->nextSlot = nextSlot; \ 362 slot = nextSlot; \ 363 } \ 364 } \ 365 else \ 366 { \ 367 slot->keys[slot->numUsed] = key; \ 368 slot->numUsed++; \ 369 set->numElements++; \ 370 return DE_TRUE; \ 371 } \ 372 } \ 373 } \ 374 \ 375 void TYPENAME##_delete (DE_PTR_TYPE(TYPENAME) set, KEYTYPE key) \ 376 { \ 377 int slotNdx; \ 378 TYPENAME##Slot* slot; \ 379 TYPENAME##Slot* prevSlot = DE_NULL; \ 380 \ 381 DE_ASSERT(set->numElements > 0); \ 382 slotNdx = (int)(HASHFUNC(key) & (deUint32)(set->slotTableSize - 1)); \ 383 DE_ASSERT(slotNdx >= 0 && slotNdx < set->slotTableSize); \ 384 slot = set->slotTable[slotNdx]; \ 385 DE_ASSERT(slot); \ 386 \ 387 for (;;) \ 388 { \ 389 int elemNdx; \ 390 DE_ASSERT(slot->numUsed > 0); \ 391 for (elemNdx = 0; elemNdx < slot->numUsed; elemNdx++) \ 392 { \ 393 if (CMPFUNC(key, slot->keys[elemNdx])) \ 394 { \ 395 TYPENAME##Slot* lastSlot = slot; \ 396 while (lastSlot->nextSlot) \ 397 { \ 398 prevSlot = lastSlot; \ 399 lastSlot = lastSlot->nextSlot; \ 400 } \ 401 \ 402 slot->keys[elemNdx] = lastSlot->keys[lastSlot->numUsed-1]; \ 403 lastSlot->numUsed--; \ 404 \ 405 if (lastSlot->numUsed == 0) \ 406 { \ 407 if (prevSlot) \ 408 prevSlot->nextSlot = DE_NULL; \ 409 else \ 410 set->slotTable[slotNdx] = DE_NULL; \ 411 \ 412 lastSlot->nextSlot = set->slotFreeList; \ 413 set->slotFreeList = lastSlot; \ 414 } \ 415 \ 416 set->numElements--; \ 417 return; \ 418 } \ 419 } \ 420 \ 421 prevSlot = slot; \ 422 slot = slot->nextSlot; \ 423 DE_ASSERT(slot); \ 424 } \ 425 } \ 426 \ 427 struct TYPENAME##Unused2_s { int unused; } 428 429 /* Copy-to-array templates. */ 430 431 #define DE_DECLARE_POOL_SET_TO_ARRAY(SETTYPENAME, ARRAYTYPENAME) \ 432 deBool SETTYPENAME##_copyToArray(const SETTYPENAME* set, DE_PTR_TYPE(ARRAYTYPENAME) array); \ 433 struct SETTYPENAME##_##ARRAYTYPENAME##_declare_unused { int unused; } 434 435 #define DE_IMPLEMENT_POOL_SET_TO_ARRAY(SETTYPENAME, ARRAYTYPENAME) \ 436 deBool SETTYPENAME##_copyToArray(const SETTYPENAME* set, DE_PTR_TYPE(ARRAYTYPENAME) array) \ 437 { \ 438 int numElements = set->numElements; \ 439 int arrayNdx = 0; \ 440 int slotNdx; \ 441 \ 442 if (!ARRAYTYPENAME##_setSize(array, numElements)) \ 443 return DE_FALSE; \ 444 \ 445 for (slotNdx = 0; slotNdx < set->slotTableSize; slotNdx++) \ 446 { \ 447 const SETTYPENAME##Slot* slot = set->slotTable[slotNdx]; \ 448 while (slot) \ 449 { \ 450 int elemNdx; \ 451 for (elemNdx = 0; elemNdx < slot->numUsed; elemNdx++) \ 452 ARRAYTYPENAME##_set(array, arrayNdx++, slot->keys[elemNdx]); \ 453 slot = slot->nextSlot; \ 454 } \ 455 } \ 456 DE_ASSERT(arrayNdx == numElements); \ 457 return DE_TRUE; \ 458 } \ 459 struct SETTYPENAME##_##ARRAYTYPENAME##_implement_unused { int unused; } 460 461 /*--------------------------------------------------------------------*//*! 462 * \brief Declare set-wise operations for a set template. 463 * \param TYPENAME Type name of the declared set. 464 * \param KEYTYPE Type of the key. 465 * 466 * This macro declares union and intersection operations for a set. 467 * For implementation see DE_IMPLEMENT_POOL_SET_UNION_INTERSECT. 468 * 469 * \todo [petri] Detailed description. 470 * 471 * The functions for operating the set are: 472 * \todo [petri] Figure out how to comment these in Doxygen-style. 473 * 474 * \code 475 * deBool Set_union (Set* to, const Set* a, const Set* b); 476 * deBool Set_unionInplace (Set* a, const Set* b); 477 * deBool Set_intersect (Set* to, const Set* a, const Set* b); 478 * void Set_intersectInplace (Set* a, const Set* b); 479 * deBool Set_difference (Set* to, const Set* a, const Set* b); 480 * void Set_differenceInplace (Set* a, const Set* b); 481 * \endcode 482 *//*--------------------------------------------------------------------*/ 483 #define DE_DECLARE_POOL_SET_SETWISE_OPERATIONS(TYPENAME) \ 484 deBool TYPENAME##_union (DE_PTR_TYPE(TYPENAME) to, const TYPENAME* a, const TYPENAME* b); \ 485 deBool TYPENAME##_unionInplace (DE_PTR_TYPE(TYPENAME) a, const TYPENAME* b); \ 486 deBool TYPENAME##_intersect (DE_PTR_TYPE(TYPENAME) to, const TYPENAME* a, const TYPENAME* b); \ 487 void TYPENAME##_intersectInplace (DE_PTR_TYPE(TYPENAME) a, const TYPENAME* b); \ 488 deBool TYPENAME##_difference (DE_PTR_TYPE(TYPENAME) to, const TYPENAME* a, const TYPENAME* b); \ 489 void TYPENAME##_differenceInplace (DE_PTR_TYPE(TYPENAME) a, const TYPENAME* b); \ 490 struct TYPENAME##SetwiseDeclareUnused_s { int unused; } 491 492 #define DE_IMPLEMENT_POOL_SET_SETWISE_OPERATIONS(TYPENAME, KEYTYPE) \ 493 deBool TYPENAME##_union (DE_PTR_TYPE(TYPENAME) to, const TYPENAME* a, const TYPENAME* b) \ 494 { \ 495 TYPENAME##_reset(to); \ 496 if (!TYPENAME##_unionInplace(to, a)) \ 497 return DE_FALSE; \ 498 if (!TYPENAME##_unionInplace(to, b)) \ 499 return DE_FALSE; \ 500 return DE_TRUE; \ 501 } \ 502 \ 503 deBool TYPENAME##_unionInplace (DE_PTR_TYPE(TYPENAME) a, const TYPENAME* b) \ 504 { \ 505 TYPENAME##Iter iter; \ 506 for (TYPENAME##Iter_init(b, &iter); \ 507 TYPENAME##Iter_hasItem(&iter); \ 508 TYPENAME##Iter_next(&iter)) \ 509 { \ 510 KEYTYPE key = TYPENAME##Iter_getKey(&iter); \ 511 if (!TYPENAME##_exists(a, key)) \ 512 { \ 513 if (!TYPENAME##_insert(a, key)) \ 514 return DE_FALSE; \ 515 } \ 516 } \ 517 return DE_TRUE; \ 518 } \ 519 \ 520 deBool TYPENAME##_intersect (DE_PTR_TYPE(TYPENAME) to, const TYPENAME* a, const TYPENAME* b) \ 521 { \ 522 TYPENAME##Iter iter; \ 523 TYPENAME##_reset(to); \ 524 for (TYPENAME##Iter_init(a, &iter); \ 525 TYPENAME##Iter_hasItem(&iter); \ 526 TYPENAME##Iter_next(&iter)) \ 527 { \ 528 KEYTYPE key = TYPENAME##Iter_getKey(&iter); \ 529 if (TYPENAME##_exists(b, key)) \ 530 { \ 531 if (!TYPENAME##_insert(to, key)) \ 532 return DE_FALSE; \ 533 } \ 534 } \ 535 return DE_TRUE; \ 536 } \ 537 \ 538 void TYPENAME##_intersectInplace (DE_PTR_TYPE(TYPENAME) a, const TYPENAME* b) \ 539 { \ 540 DE_UNREF(a && b); \ 541 DE_FATAL("Not implemented."); \ 542 } \ 543 \ 544 deBool TYPENAME##_difference (DE_PTR_TYPE(TYPENAME) to, const TYPENAME* a, const TYPENAME* b) \ 545 { \ 546 TYPENAME##Iter iter; \ 547 TYPENAME##_reset(to); \ 548 for (TYPENAME##Iter_init(a, &iter); \ 549 TYPENAME##Iter_hasItem(&iter); \ 550 TYPENAME##Iter_next(&iter)) \ 551 { \ 552 KEYTYPE key = TYPENAME##Iter_getKey(&iter); \ 553 if (!TYPENAME##_exists(b, key)) \ 554 { \ 555 if (!TYPENAME##_insert(to, key)) \ 556 return DE_FALSE; \ 557 } \ 558 } \ 559 return DE_TRUE; \ 560 } \ 561 \ 562 void TYPENAME##_differenceInplace (DE_PTR_TYPE(TYPENAME) a, const TYPENAME* b) \ 563 { \ 564 TYPENAME##Iter iter; \ 565 for (TYPENAME##Iter_init(b, &iter); \ 566 TYPENAME##Iter_hasItem(&iter); \ 567 TYPENAME##Iter_next(&iter)) \ 568 { \ 569 KEYTYPE key = TYPENAME##Iter_getKey(&iter); \ 570 if (TYPENAME##_exists(a, key)) \ 571 TYPENAME##_delete(a, key); \ 572 } \ 573 } \ 574 \ 575 struct TYPENAME##UnionIntersectImplementUnused_s { int unused; } 576 577 #endif /* _DEPOOLSET_H */ 578