xref: /aosp_15_r20/external/deqp/framework/delibs/depool/dePoolMultiSet.h (revision 35238bce31c2a825756842865a792f8cf7f89930)

#ifndef _DEPOOLMULTISET_H
#define _DEPOOLMULTISET_H
/*-------------------------------------------------------------------------
 * drawElements Memory Pool Library
 * --------------------------------
 *
 * Copyright 2014 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 *
 *//*!
 * \file
 * \brief Memory pool multiset class.
 *//*--------------------------------------------------------------------*/

#include "deDefs.h"
#include "deMemPool.h"
#include "dePoolHash.h"
#include "deInt32.h"

DE_BEGIN_EXTERN_C

void dePoolMultiSet_selfTest(void);

DE_END_EXTERN_C

/*--------------------------------------------------------------------*//*!
 * \brief Declare a template pool multiset class interface.
 * \param TYPENAME    Type name of the declared multiset.
 * \param KEYTYPE    Type of the key.
 *
 * This macro declares the interface for a multiset. For the implementation
 * of the multiset, see DE_IMPLEMENT_POOL_MULTISET. Usually this macro is put
 * into the header file and the implementation macro is put in some .c file.
 *
 * \todo [petri] Detailed description.
 *
 * The functions for operating the multiset are:
 * \todo [petri] Figure out how to comment these in Doxygen-style.
 *
 * \code
 * MultiSet* MultiSet_create            (deMemPool* pool);
 * int       MultiSet_getNumElements    (const MultiSet* set);
 * bool    MultiSet_exists            (const MultiSet* set, Key key);
 * bool    MultiSet_insert            (MultiSet* set, Key key);
 * void      MultiSet_delete            (MultiSet* set, Key key);
 * int       MultiSet_getKeyCount       (const MultiSet* set, Key key);
 * bool    MultiSet_setKeyCount       (MultiSet* set, Key key, int count);
 * \endcode
*//*--------------------------------------------------------------------*/
#define DE_DECLARE_POOL_MULTISET(TYPENAME, KEYTYPE)                                    \
                                                                                       \
    DE_DECLARE_POOL_HASH(TYPENAME##Hash, KEYTYPE, int);                                \
                                                                                       \
    typedef struct TYPENAME##_s                                                        \
    {                                                                                  \
        deMemPool *pool;                                                               \
        int numElements;                                                               \
        TYPENAME##Hash *hash;                                                          \
    } TYPENAME; /* NOLINT(TYPENAME) */                                                 \
                                                                                       \
    TYPENAME *TYPENAME##_create(deMemPool *pool);                                      \
    void TYPENAME##_reset(DE_PTR_TYPE(TYPENAME) set);                                  \
    bool TYPENAME##_setKeyCount(DE_PTR_TYPE(TYPENAME) set, KEYTYPE key, int newCount); \
                                                                                       \
    DE_INLINE int TYPENAME##_getNumElements(const TYPENAME *set)                       \
    {                                                                                  \
        return set->numElements;                                                       \
    }                                                                                  \
                                                                                       \
    DE_INLINE int TYPENAME##_getKeyCount(const TYPENAME *set, KEYTYPE key)             \
    {                                                                                  \
        int *countPtr = TYPENAME##Hash_find(set->hash, key);                           \
        int count     = countPtr ? *countPtr : 0;                                      \
        DE_ASSERT(count > 0 || !countPtr);                                             \
        return count;                                                                  \
    }                                                                                  \
                                                                                       \
    DE_INLINE bool TYPENAME##_exists(const TYPENAME *set, KEYTYPE key)                 \
    {                                                                                  \
        return (TYPENAME##_getKeyCount(set, key) > 0);                                 \
    }                                                                                  \
                                                                                       \
    DE_INLINE bool TYPENAME##_insert(DE_PTR_TYPE(TYPENAME) set, KEYTYPE key)           \
    {                                                                                  \
        int oldCount = TYPENAME##_getKeyCount(set, key);                               \
        return TYPENAME##_setKeyCount(set, key, oldCount + 1);                         \
    }                                                                                  \
                                                                                       \
    DE_INLINE void TYPENAME##_delete(DE_PTR_TYPE(TYPENAME) set, KEYTYPE key)           \
    {                                                                                  \
        int oldCount = TYPENAME##_getKeyCount(set, key);                               \
        DE_ASSERT(oldCount > 0);                                                       \
        TYPENAME##_setKeyCount(set, key, oldCount - 1);                                \
    }                                                                                  \
                                                                                       \
    struct TYPENAME##DeclareUnused_s                                                   \
    {                                                                                  \
        int unused;                                                                    \
    }

/*--------------------------------------------------------------------*//*!
 * \brief Implement a template pool multiset class.
 * \param TYPENAME    Type name of the declared multiset.
 * \param KEYTYPE    Type of the key.
 * \param HASHFUNC    Function used for hashing the key.
 * \param CMPFUNC    Function used for exact matching of the keys.
 *
 * This macro has implements the set declared with DE_DECLARE_POOL_MULTISET.
 * Usually this macro should be used from a .c file, since the macro expands
 * into multiple functions. The TYPENAME and KEYTYPE parameters
 * must match those of the declare macro.
*//*--------------------------------------------------------------------*/
#define DE_IMPLEMENT_POOL_MULTISET(TYPENAME, KEYTYPE, HASHFUNC, CMPFUNC)              \
                                                                                      \
    DE_IMPLEMENT_POOL_HASH(TYPENAME##Hash, KEYTYPE, int, HASHFUNC, CMPFUNC);          \
                                                                                      \
    TYPENAME *TYPENAME##_create(deMemPool *pool)                                      \
    {                                                                                 \
        /* Alloc struct. */                                                           \
        DE_PTR_TYPE(TYPENAME) set = DE_POOL_NEW(pool, TYPENAME);                      \
        if (!set)                                                                     \
            return DE_NULL;                                                           \
                                                                                      \
        /* Init. */                                                                   \
        memset(set, 0, sizeof(TYPENAME));                                             \
        set->pool = pool;                                                             \
                                                                                      \
        set->hash = TYPENAME##Hash_create(pool);                                      \
                                                                                      \
        return set;                                                                   \
    }                                                                                 \
                                                                                      \
    void TYPENAME##_reset(DE_PTR_TYPE(TYPENAME) set)                                  \
    {                                                                                 \
        TYPENAME##Hash_reset(set->hash);                                              \
        set->numElements = 0;                                                         \
    }                                                                                 \
                                                                                      \
    bool TYPENAME##_setKeyCount(DE_PTR_TYPE(TYPENAME) set, KEYTYPE key, int newCount) \
    {                                                                                 \
        int *countPtr = TYPENAME##Hash_find(set->hash, key);                          \
        int oldCount  = countPtr ? *countPtr : 0;                                     \
                                                                                      \
        DE_ASSERT(oldCount > 0 || !countPtr);                                         \
        DE_ASSERT(newCount >= 0);                                                     \
        set->numElements += (newCount - oldCount);                                    \
                                                                                      \
        if (newCount == 0 && countPtr)                                                \
            TYPENAME##Hash_delete(set->hash, key);                                    \
        else if (newCount > 0 && countPtr)                                            \
            *countPtr = newCount;                                                     \
        else if (newCount > 0)                                                        \
            return TYPENAME##Hash_insert(set->hash, key, newCount);                   \
        return true;                                                                  \
    }                                                                                 \
                                                                                      \
    struct TYPENAME##ImplementUnused_s                                                \
    {                                                                                 \
        int unused;                                                                   \
    }

/*--------------------------------------------------------------------*//*!
 * \brief Declare set-wise operations for a multiset template.
 * \param TYPENAME    Type name of the declared set.
 * \param KEYTYPE    Type of the key.
 *
 * This macro declares union and intersection operations for a multiset.
 * For implementation see DE_IMPLEMENT_POOL_MULTISET_UNION_INTERSECT.
 *
 * \todo [petri] Detailed description.
 *
 * The functions for operating the set are:
 * \todo [petri] Figure out how to comment these in Doxygen-style.
 *
 * \code
 * bool    MultiSet_union                (Set* to, const Set* a, const Set* b);
 * bool    MultiSet_unionInplace        (Set* a, const Set* b);
 * bool    MultiSet_intersect            (Set* to, const Set* a, const Set* b);
 * void        MultiSet_intersectInplace    (Set* a, const Set* b);
 * bool   MultiSet_sum                (Set* to, const Set* a, const Set* b);
 * bool   MultiSet_sumInplace            (Set* a, const Set* b);
 * bool   MultiSet_difference            (Set* to, const Set* a, const Set* b);
 * void        MultiSet_differenceInplace    (Set* a, const Set* b);
 * \endcode
*//*--------------------------------------------------------------------*/
#define DE_DECLARE_POOL_MULTISET_SETWISE_OPERATIONS(TYPENAME)                                   \
    bool TYPENAME##_union(DE_PTR_TYPE(TYPENAME) to, const TYPENAME *a, const TYPENAME *b);      \
    bool TYPENAME##_unionInplace(DE_PTR_TYPE(TYPENAME) a, const TYPENAME *b);                   \
    bool TYPENAME##_intersect(DE_PTR_TYPE(TYPENAME) to, const TYPENAME *a, const TYPENAME *b);  \
    void TYPENAME##_intersectInplace(DE_PTR_TYPE(TYPENAME) a, const TYPENAME *b);               \
    bool TYPENAME##_sum(DE_PTR_TYPE(TYPENAME) to, const TYPENAME *a, const TYPENAME *b);        \
    bool TYPENAME##_sumInplace(DE_PTR_TYPE(TYPENAME) a, const TYPENAME *b);                     \
    bool TYPENAME##_difference(DE_PTR_TYPE(TYPENAME) to, const TYPENAME *a, const TYPENAME *b); \
    void TYPENAME##_differenceInplace(DE_PTR_TYPE(TYPENAME) a, const TYPENAME *b);              \
    struct TYPENAME##SetwiseDeclareUnused_s                                                     \
    {                                                                                           \
        int unused;                                                                             \
    }

#define DE_IMPLEMENT_POOL_MULTISET_SETWISE_OPERATIONS(TYPENAME, KEYTYPE)                                           \
    bool TYPENAME##_union(DE_PTR_TYPE(TYPENAME) to, const TYPENAME *a, const TYPENAME *b)                          \
    {                                                                                                              \
        TYPENAME##_reset(to);                                                                                      \
        return TYPENAME##_unionInplace(to, a) && TYPENAME##_unionInplace(to, b);                                   \
    }                                                                                                              \
                                                                                                                   \
    bool TYPENAME##_unionInplace(DE_PTR_TYPE(TYPENAME) a, const TYPENAME *b)                                       \
    {                                                                                                              \
        TYPENAME##HashIter iter;                                                                                   \
        for (TYPENAME##HashIter_init(b, &iter); TYPENAME##HashIter_hasItem(&iter); TYPENAME##HashIter_next(&iter)) \
        {                                                                                                          \
            KEYTYPE key = TYPENAME##HashIter_getKey(&iter);                                                        \
            int bCount  = TYPENAME##HashIter_getValue(&iter);                                                      \
            int aCount  = TYPENAME##_getKeyCount(a, key);                                                          \
            int count   = deMax32(aCount, bCount);                                                                 \
            if (bCount && !TYPENAME##_setKeyCount(a, key, aCount + bCount))                                        \
                return false;                                                                                      \
        }                                                                                                          \
        return true;                                                                                               \
    }                                                                                                              \
                                                                                                                   \
    bool TYPENAME##_intersect(DE_PTR_TYPE(TYPENAME) to, const TYPENAME *a, const TYPENAME *b)                      \
    {                                                                                                              \
        TYPENAME##HashIter iter;                                                                                   \
        TYPENAME##_reset(to);                                                                                      \
        for (TYPENAME##HashIter_init(a, &iter); TYPENAME##HashIter_hasItem(&iter); TYPENAME##HashIter_next(&iter)) \
        {                                                                                                          \
            KEYTYPE key = TYPENAME##HashIter_getKey(&iter);                                                        \
            int aCount  = TYPENAME##HashIter_getValue(&iter);                                                      \
            int bCount  = TYPENAME##_getKeyValue(b, key);                                                          \
            int count   = deMin32(aCount, bCount);                                                                 \
            if (count && !TYPENAME##_setKeyCount(to, key, count))                                                  \
                return false;                                                                                      \
        }                                                                                                          \
        return true;                                                                                               \
    }                                                                                                              \
                                                                                                                   \
    void TYPENAME##_intersectInplace(DE_PTR_TYPE(TYPENAME) a, const TYPENAME *b)                                   \
    {                                                                                                              \
        DE_FATAL("Not implemented.");                                                                              \
    }                                                                                                              \
                                                                                                                   \
    bool TYPENAME##_sum(DE_PTR_TYPE(TYPENAME) to, const TYPENAME *a, const TYPENAME *b)                            \
    {                                                                                                              \
        TYPENAME##_reset(to);                                                                                      \
        return TYPENAME##_sumInplace(to, a) && TYPENAME##_sumInplace(to, b);                                       \
    }                                                                                                              \
                                                                                                                   \
    bool TYPENAME##_sumInplace(DE_PTR_TYPE(TYPENAME) a, const TYPENAME *b)                                         \
    {                                                                                                              \
        TYPENAME##HashIter iter;                                                                                   \
        for (TYPENAME##HashIter_init(b, &iter); TYPENAME##HashIter_hasItem(&iter); TYPENAME##HashIter_next(&iter)) \
        {                                                                                                          \
            KEYTYPE key = TYPENAME##HashIter_getKey(&iter);                                                        \
            int aCount  = TYPENAME##_getKeyValue(a, key);                                                          \
            int bCount  = TYPENAME##HashIter_getValue(&iter);                                                      \
            int count   = aCount + bCount;                                                                         \
            if (!TYPENAME##_setKeyCount(a, key, count))                                                            \
                return false;                                                                                      \
        }                                                                                                          \
    }                                                                                                              \
                                                                                                                   \
    bool TYPENAME##_difference(DE_PTR_TYPE(TYPENAME) to, const TYPENAME *a, const TYPENAME *b)                     \
    {                                                                                                              \
        TYPENAME##HashIter iter;                                                                                   \
        TYPENAME##_reset(to);                                                                                      \
        for (TYPENAME##HashIter_init(a, &iter); TYPENAME##HashIter_hasItem(&iter); TYPENAME##HashIter_next(&iter)) \
        {                                                                                                          \
            KEYTYPE key = TYPENAME##HashIter_getKey(&iter);                                                        \
            int aCount  = TYPENAME##HashIter_getValue(&iter);                                                      \
            int bCount  = TYPENAME##_getKeyValue(b, key);                                                          \
            int count   = deMax32(0, aCount - bCount);                                                             \
            if (count && !TYPENAME##_setKeyCount(to, key, count))                                                  \
                return false;                                                                                      \
        }                                                                                                          \
        return true;                                                                                               \
    }                                                                                                              \
                                                                                                                   \
    void TYPENAME##_differenceInplace(DE_PTR_TYPE(TYPENAME) a, const TYPENAME *b)                                  \
    {                                                                                                              \
        DE_FATAL("Not implemented.");                                                                              \
    }                                                                                                              \
                                                                                                                   \
    struct TYPENAME##SetwiseImplementUnused_s                                                                      \
    {                                                                                                              \
        int unused;                                                                                                \
    }

#endif /* _DEPOOLMULTISET_H */