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

#ifndef _DEPOOLHASHSET_H
#define _DEPOOLHASHSET_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 hash-set class.
 *//*--------------------------------------------------------------------*/

#include "deDefs.h"
#include "dePoolHash.h"
#include "dePoolSet.h"

DE_BEGIN_EXTERN_C

void dePoolHashSet_selfTest(void);

DE_END_EXTERN_C

/*--------------------------------------------------------------------*//*!
 * \brief Declare a template pool hash-set (hash of sets) class interface.
 * \param TYPENAME    Type name of the declared hash-set.
 * \param KEYTYPE    Type of the key.
 * \param VALUETYPE    Type of the value.
 *
 * \todo [petri] Description.
 *
 * The functions for operating the hash are:
 * \todo [petri] Figure out how to comment these in Doxygen-style.
 *
 * \code
 * HashSet*    HashSet_create            (deMemPool* pool);
 * int         HashSet_getNumElements    (const HashSet* hashSet);
 * Set<Value>* HashSet_find              (const HashSet* hashSet, Key key); TODO: better API
 * Hash<Set*>* HashSet_getHash           (const HashSet* hashSet); TODO: better API
 * bool      HashSet_insert            (HashSet* hashSet, Key key, Value value);
 * void        HashSet_delete            (HashSet* hashSet, Key key, Value value);
 * bool      HashSet_exists            (const HashSet* hashSet, Key key, Value value);
 * \endcode
*//*--------------------------------------------------------------------*/
#define DE_DECLARE_POOL_HASH_SET(TYPENAME, KEYTYPE, VALUETYPE)                                                        \
                                                                                                                      \
    DE_DECLARE_POOL_SET(TYPENAME##Set, VALUETYPE);                                                                    \
    DE_DECLARE_POOL_HASH(TYPENAME##Hash, KEYTYPE, TYPENAME##Set *);                                                   \
    typedef struct TYPENAME##_s                                                                                       \
    {                                                                                                                 \
        TYPENAME##Hash *hash;                                                                                         \
    } TYPENAME; /* NOLINT(TYPENAME) */                                                                                \
                                                                                                                      \
    DE_INLINE TYPENAME *TYPENAME##_create(deMemPool *pool);                                                           \
    DE_INLINE int TYPENAME##_getNumElements(const TYPENAME *hashSet) DE_UNUSED_FUNCTION;                              \
    DE_INLINE TYPENAME##Hash *TYPENAME##_getHash(const TYPENAME *hashSet) DE_UNUSED_FUNCTION;                         \
    DE_INLINE bool TYPENAME##_insert(DE_PTR_TYPE(TYPENAME) hashSet, KEYTYPE key, VALUETYPE value) DE_UNUSED_FUNCTION; \
    DE_INLINE bool TYPENAME##_safeInsert(DE_PTR_TYPE(TYPENAME) hashSet, KEYTYPE key, VALUETYPE value)                 \
        DE_UNUSED_FUNCTION;                                                                                           \
    DE_INLINE TYPENAME##Set *TYPENAME##_find(const TYPENAME *hashSet, KEYTYPE key) DE_UNUSED_FUNCTION;                \
    DE_INLINE void TYPENAME##_delete(DE_PTR_TYPE(TYPENAME) hashSet, KEYTYPE key, VALUETYPE value) DE_UNUSED_FUNCTION; \
    DE_INLINE bool TYPENAME##_exists(const TYPENAME *hashSet, KEYTYPE key, VALUETYPE value) DE_UNUSED_FUNCTION;       \
                                                                                                                      \
    DE_INLINE TYPENAME *TYPENAME##_create(deMemPool *pool)                                                            \
    {                                                                                                                 \
        DE_PTR_TYPE(TYPENAME) hashSet = DE_POOL_NEW(pool, TYPENAME);                                                  \
        if (!hashSet)                                                                                                 \
            return DE_NULL;                                                                                           \
        if ((hashSet->hash = TYPENAME##Hash_create(pool)) == DE_NULL)                                                 \
            return DE_NULL;                                                                                           \
        return hashSet;                                                                                               \
    }                                                                                                                 \
                                                                                                                      \
    DE_INLINE int TYPENAME##_getNumElements(const TYPENAME *hashSet)                                                  \
    {                                                                                                                 \
        return TYPENAME##Hash_getNumElements(hashSet->hash);                                                          \
    }                                                                                                                 \
                                                                                                                      \
    DE_INLINE TYPENAME##Hash *TYPENAME##_getHash(const TYPENAME *hashSet)                                             \
    {                                                                                                                 \
        return hashSet->hash;                                                                                         \
    }                                                                                                                 \
                                                                                                                      \
    DE_INLINE bool TYPENAME##_insert(DE_PTR_TYPE(TYPENAME) hashSet, KEYTYPE key, VALUETYPE value)                     \
    {                                                                                                                 \
        TYPENAME##Set **setPtr = TYPENAME##Hash_find(hashSet->hash, key);                                             \
        TYPENAME##Set *set     = setPtr ? *setPtr : DE_NULL;                                                          \
        if (!set)                                                                                                     \
        {                                                                                                             \
            set = TYPENAME##Set_create(hashSet->hash->pool);                                                          \
            if (!set)                                                                                                 \
                return false;                                                                                         \
            if (!TYPENAME##Set_insert(set, value))                                                                    \
                return false;                                                                                         \
            return TYPENAME##Hash_insert(hashSet->hash, key, set);                                                    \
        }                                                                                                             \
        else                                                                                                          \
        {                                                                                                             \
            return TYPENAME##Set_insert(set, value);                                                                  \
        }                                                                                                             \
    }                                                                                                                 \
                                                                                                                      \
    DE_INLINE bool TYPENAME##_safeInsert(DE_PTR_TYPE(TYPENAME) hashSet, KEYTYPE key, VALUETYPE value)                 \
    {                                                                                                                 \
        TYPENAME##Set **setPtr = TYPENAME##Hash_find(hashSet->hash, key);                                             \
        TYPENAME##Set *set     = setPtr ? *setPtr : DE_NULL;                                                          \
        if (!set)                                                                                                     \
        {                                                                                                             \
            return TYPENAME##_insert(hashSet, key, value);                                                            \
        }                                                                                                             \
        else                                                                                                          \
        {                                                                                                             \
            return TYPENAME##Set_safeInsert(set, value);                                                              \
        }                                                                                                             \
    }                                                                                                                 \
                                                                                                                      \
    DE_INLINE TYPENAME##Set *TYPENAME##_find(const TYPENAME *hashSet, KEYTYPE key)                                    \
    {                                                                                                                 \
        TYPENAME##Set **setPtr = TYPENAME##Hash_find(hashSet->hash, key);                                             \
        return setPtr ? *setPtr : DE_NULL;                                                                            \
    }                                                                                                                 \
                                                                                                                      \
    DE_INLINE void TYPENAME##_delete(DE_PTR_TYPE(TYPENAME) hashSet, KEYTYPE key, VALUETYPE value)                     \
    {                                                                                                                 \
        TYPENAME##Set **setPtr = TYPENAME##Hash_find(hashSet->hash, key);                                             \
        TYPENAME##Set *set;                                                                                           \
        DE_ASSERT(setPtr);                                                                                            \
        set = *setPtr;                                                                                                \
        TYPENAME##Set_delete(set, value);                                                                             \
    }                                                                                                                 \
                                                                                                                      \
    DE_INLINE bool TYPENAME##_exists(const TYPENAME *hashSet, KEYTYPE key, VALUETYPE value)                           \
    {                                                                                                                 \
        TYPENAME##Set **setPtr = TYPENAME##Hash_find(hashSet->hash, key);                                             \
        if (setPtr)                                                                                                   \
            return TYPENAME##Set_exists(*setPtr, value);                                                              \
        else                                                                                                          \
            return false;                                                                                             \
    }                                                                                                                 \
                                                                                                                      \
    struct TYPENAME##Unused_s                                                                                         \
    {                                                                                                                 \
        int unused;                                                                                                   \
    }

/*--------------------------------------------------------------------*//*!
 * \brief Implement a template pool hash-set class.
 * \param TYPENAME    Type name of the declared hash.
 * \param KEYTYPE    Type of the key.
 * \param VALUETYPE    Type of the value.
 * \param HASHFUNC    Function used for hashing the key.
 * \param CMPFUNC    Function used for exact matching of the keys.
 *
 * This macro has implements the hash declared with DE_DECLARE_POOL_HASH.
 * Usually this macro should be used from a .c file, since the macro expands
 * into multiple functions. The TYPENAME, KEYTYPE, and VALUETYPE parameters
 * must match those of the declare macro.
*//*--------------------------------------------------------------------*/
#define DE_IMPLEMENT_POOL_HASH_SET(TYPENAME, KEYTYPE, VALUETYPE, KEYHASHFUNC, KEYCMPFUNC, VALUEHASHFUNC, VALUECMPFUNC) \
    DE_IMPLEMENT_POOL_SET(TYPENAME##Set, VALUETYPE, VALUEHASHFUNC, VALUECMPFUNC);                                      \
    DE_IMPLEMENT_POOL_HASH(TYPENAME##Hash, KEYTYPE, TYPENAME##Set *, KEYHASHFUNC, KEYCMPFUNC);                         \
    struct TYPENAME##Unused2_s                                                                                         \
    {                                                                                                                  \
        int unused;                                                                                                    \
    }

/* Copy-to-array templates. */

#if 0

#define DE_DECLARE_POOL_HASH_TO_ARRAY(HASHTYPENAME, KEYARRAYTYPENAME, VALUEARRAYTYPENAME) \
    bool HASHTYPENAME##_copyToArray(const HASHTYPENAME *set, KEYARRAYTYPENAME *keyArray,  \
                                    VALUEARRAYTYPENAME *valueArray);                      \
    struct HASHTYPENAME##_##KEYARRAYTYPENAME##_##VALUEARRAYTYPENAME##_declare_unused      \
    {                                                                                     \
        int unused;                                                                       \
    }

#define DE_IMPLEMENT_POOL_HASH_TO_ARRAY(HASHTYPENAME, KEYARRAYTYPENAME, VALUEARRAYTYPENAME)    \
    bool HASHTYPENAME##_copyToArray(const HASHTYPENAME *hash, KEYARRAYTYPENAME *keyArray,      \
                                    VALUEARRAYTYPENAME *valueArray)                            \
    {                                                                                          \
        int numElements = hash->numElements;                                                   \
        int arrayNdx    = 0;                                                                   \
        int slotNdx;                                                                           \
                                                                                               \
        if ((keyArray && !KEYARRAYTYPENAME##_setSize(keyArray, numElements)) ||                \
            (valueArray && !VALUEARRAYTYPENAME##_setSize(valueArray, numElements)))            \
            return false;                                                                      \
                                                                                               \
        for (slotNdx = 0; slotNdx < hash->slotTableSize; slotNdx++)                            \
        {                                                                                      \
            const HASHTYPENAME##Slot *slot = hash->slotTable[slotNdx];                         \
            while (slot)                                                                       \
            {                                                                                  \
                int elemNdx;                                                                   \
                for (elemNdx = 0; elemNdx < slot->numUsed; elemNdx++)                          \
                {                                                                              \
                    if (keyArray)                                                              \
                        KEYARRAYTYPENAME##_set(keyArray, arrayNdx, slot->keys[elemNdx]);       \
                    if (valueArray)                                                            \
                        VALUEARRAYTYPENAME##_set(valueArray, arrayNdx, slot->values[elemNdx]); \
                    arrayNdx++;                                                                \
                }                                                                              \
                slot = slot->nextSlot;                                                         \
            }                                                                                  \
        }                                                                                      \
        DE_ASSERT(arrayNdx == numElements);                                                    \
        return true;                                                                           \
    }                                                                                          \
    struct HASHTYPENAME##_##KEYARRAYTYPENAME##_##VALUEARRAYTYPENAME##_implement_unused         \
    {                                                                                          \
        int unused;                                                                            \
    }

#endif

#endif /* _DEPOOLHASHSET_H */