framework/delibs/depool/dePoolMultiSet.h

   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##DeclareUnused_s { int unused; }
 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##ImplementUnused_s { int unused; }
 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##SetwiseDeclareUnused_s { int unused; }
 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##SetwiseImplementUnused_s { int unused; }
 295
 296 #endif /* _DEPOOLMULTISET_H */