framework/delibs/depool/dePoolSet.h

   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##Dummy_s { int dummy; }
 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##Dummy2_s { int dummy; }
 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_dummy { int dummy; }
 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_dummy { int dummy; }
 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##SetwiseDeclareDummy_s { int dummy; }
 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##UnionIntersectImplementDummy_s { int dummy; }
 576
 577 #endif /* _DEPOOLSET_H */