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

#ifndef _DEPOOLHASH_H
#define _DEPOOLHASH_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 class.
 *//*--------------------------------------------------------------------*/

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

#include <string.h> /* memset() */

enum
{
    DE_HASH_ELEMENTS_PER_SLOT = 4
};

DE_BEGIN_EXTERN_C

void dePoolHash_selfTest(void);

DE_END_EXTERN_C

/*--------------------------------------------------------------------*//*!
 * \brief Declare a template pool hash class interface.
 * \param TYPENAME    Type name of the declared hash.
 * \param KEYTYPE    Type of the key.
 * \param VALUETYPE    Type of the value.
 *
 * This macro declares the interface for a hash. For the implementation of
 * the hash, see DE_IMPLEMENT_POOL_HASH. 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 hash are:
 * \todo [petri] Figure out how to comment these in Doxygen-style.
 *
 * \code
 * Hash*    Hash_create            (deMemPool* pool);
 * int      Hash_getNumElements    (const Hash* hash);
 * Value*   Hash_find              (Hash* hash, Key key);
 * bool   Hash_insert            (Hash* hash, Key key, Value value);
 * void     Hash_delete            (Hash* hash, Key key);
 * \endcode
*//*--------------------------------------------------------------------*/
#define DE_DECLARE_POOL_HASH(TYPENAME, KEYTYPE, VALUETYPE)                                             \
                                                                                                       \
    typedef struct TYPENAME##Slot_s TYPENAME##Slot;                                                    \
                                                                                                       \
    struct TYPENAME##Slot_s                                                                            \
    {                                                                                                  \
        int numUsed;                                                                                   \
        TYPENAME##Slot *nextSlot;                                                                      \
        KEYTYPE keys[DE_HASH_ELEMENTS_PER_SLOT];                                                       \
        VALUETYPE values[DE_HASH_ELEMENTS_PER_SLOT];                                                   \
    };                                                                                                 \
                                                                                                       \
    typedef struct TYPENAME##_s                                                                        \
    {                                                                                                  \
        deMemPool *pool;                                                                               \
        int numElements;                                                                               \
                                                                                                       \
        int slotTableSize;                                                                             \
        TYPENAME##Slot **slotTable;                                                                    \
        TYPENAME##Slot *slotFreeList;                                                                  \
    } TYPENAME; /* NOLINT(TYPENAME) */                                                                 \
                                                                                                       \
    typedef struct TYPENAME##Iter_s                                                                    \
    {                                                                                                  \
        const TYPENAME *hash;                                                                          \
        int curSlotIndex;                                                                              \
        const TYPENAME##Slot *curSlot;                                                                 \
        int curElemIndex;                                                                              \
    } TYPENAME##Iter;                                                                                  \
                                                                                                       \
    TYPENAME *TYPENAME##_create(deMemPool *pool);                                                      \
    void TYPENAME##_reset(DE_PTR_TYPE(TYPENAME) hash);                                                 \
    bool TYPENAME##_reserve(DE_PTR_TYPE(TYPENAME) hash, int capacity);                                 \
    VALUETYPE *TYPENAME##_find(const TYPENAME *hash, KEYTYPE key);                                     \
    bool TYPENAME##_insert(DE_PTR_TYPE(TYPENAME) hash, KEYTYPE key, VALUETYPE value);                  \
    void TYPENAME##_delete(DE_PTR_TYPE(TYPENAME) hash, KEYTYPE key);                                   \
                                                                                                       \
    DE_INLINE int TYPENAME##_getNumElements(const TYPENAME *hash) DE_UNUSED_FUNCTION;                  \
    DE_INLINE void TYPENAME##Iter_init(const TYPENAME *hash, TYPENAME##Iter *iter) DE_UNUSED_FUNCTION; \
    DE_INLINE bool TYPENAME##Iter_hasItem(const TYPENAME##Iter *iter) DE_UNUSED_FUNCTION;              \
    DE_INLINE void TYPENAME##Iter_next(TYPENAME##Iter *iter) DE_UNUSED_FUNCTION;                       \
    DE_INLINE KEYTYPE TYPENAME##Iter_getKey(const TYPENAME##Iter *iter) DE_UNUSED_FUNCTION;            \
    DE_INLINE VALUETYPE TYPENAME##Iter_getValue(const TYPENAME##Iter *iter) DE_UNUSED_FUNCTION;        \
                                                                                                       \
    DE_INLINE int TYPENAME##_getNumElements(const TYPENAME *hash)                                      \
    {                                                                                                  \
        return hash->numElements;                                                                      \
    }                                                                                                  \
                                                                                                       \
    DE_INLINE void TYPENAME##Iter_init(const TYPENAME *hash, TYPENAME##Iter *iter)                     \
    {                                                                                                  \
        iter->hash         = hash;                                                                     \
        iter->curSlotIndex = 0;                                                                        \
        iter->curSlot      = DE_NULL;                                                                  \
        iter->curElemIndex = 0;                                                                        \
        if (TYPENAME##_getNumElements(hash) > 0)                                                       \
        {                                                                                              \
            int slotTableSize = hash->slotTableSize;                                                   \
            int slotNdx       = 0;                                                                     \
            while (slotNdx < slotTableSize)                                                            \
            {                                                                                          \
                if (hash->slotTable[slotNdx])                                                          \
                    break;                                                                             \
                slotNdx++;                                                                             \
            }                                                                                          \
            DE_ASSERT(slotNdx < slotTableSize);                                                        \
            iter->curSlotIndex = slotNdx;                                                              \
            iter->curSlot      = hash->slotTable[slotNdx];                                             \
            DE_ASSERT(iter->curSlot);                                                                  \
        }                                                                                              \
    }                                                                                                  \
                                                                                                       \
    DE_INLINE bool TYPENAME##Iter_hasItem(const TYPENAME##Iter *iter)                                  \
    {                                                                                                  \
        return (iter->curSlot != DE_NULL);                                                             \
    }                                                                                                  \
                                                                                                       \
    DE_INLINE void TYPENAME##Iter_next(TYPENAME##Iter *iter)                                           \
    {                                                                                                  \
        DE_ASSERT(TYPENAME##Iter_hasItem(iter));                                                       \
        if (++iter->curElemIndex == iter->curSlot->numUsed)                                            \
        {                                                                                              \
            iter->curElemIndex = 0;                                                                    \
            if (iter->curSlot->nextSlot)                                                               \
            {                                                                                          \
                iter->curSlot = iter->curSlot->nextSlot;                                               \
            }                                                                                          \
            else                                                                                       \
            {                                                                                          \
                const TYPENAME *hash = iter->hash;                                                     \
                int curSlotIndex     = iter->curSlotIndex;                                             \
                int slotTableSize    = hash->slotTableSize;                                            \
                while (++curSlotIndex < slotTableSize)                                                 \
                {                                                                                      \
                    if (hash->slotTable[curSlotIndex])                                                 \
                        break;                                                                         \
                }                                                                                      \
                iter->curSlotIndex = curSlotIndex;                                                     \
                if (curSlotIndex < slotTableSize)                                                      \
                    iter->curSlot = hash->slotTable[curSlotIndex];                                     \
                else                                                                                   \
                    iter->curSlot = DE_NULL;                                                           \
            }                                                                                          \
        }                                                                                              \
    }                                                                                                  \
                                                                                                       \
    DE_INLINE KEYTYPE TYPENAME##Iter_getKey(const TYPENAME##Iter *iter)                                \
    {                                                                                                  \
        DE_ASSERT(TYPENAME##Iter_hasItem(iter));                                                       \
        return iter->curSlot->keys[iter->curElemIndex];                                                \
    }                                                                                                  \
                                                                                                       \
    DE_INLINE VALUETYPE TYPENAME##Iter_getValue(const TYPENAME##Iter *iter)                            \
    {                                                                                                  \
        DE_ASSERT(TYPENAME##Iter_hasItem(iter));                                                       \
        return iter->curSlot->values[iter->curElemIndex];                                              \
    }                                                                                                  \
                                                                                                       \
    struct TYPENAME##Unused_s                                                                          \
    {                                                                                                  \
        int unused;                                                                                    \
    }

/*--------------------------------------------------------------------*//*!
 * \brief Implement a template pool hash 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(TYPENAME, KEYTYPE, VALUETYPE, HASHFUNC, CMPFUNC)                                       \
                                                                                                                      \
    TYPENAME *TYPENAME##_create(deMemPool *pool)                                                                      \
    {                                                                                                                 \
        /* Alloc struct. */                                                                                           \
        DE_PTR_TYPE(TYPENAME) hash = DE_POOL_NEW(pool, TYPENAME);                                                     \
        if (!hash)                                                                                                    \
            return DE_NULL;                                                                                           \
                                                                                                                      \
        memset(hash, 0, sizeof(TYPENAME));                                                                            \
        hash->pool = pool;                                                                                            \
                                                                                                                      \
        return hash;                                                                                                  \
    }                                                                                                                 \
                                                                                                                      \
    void TYPENAME##_reset(DE_PTR_TYPE(TYPENAME) hash)                                                                 \
    {                                                                                                                 \
        int slotNdx;                                                                                                  \
        for (slotNdx = 0; slotNdx < hash->slotTableSize; slotNdx++)                                                   \
        {                                                                                                             \
            TYPENAME##Slot *slot = hash->slotTable[slotNdx];                                                          \
            while (slot)                                                                                              \
            {                                                                                                         \
                TYPENAME##Slot *nextSlot = slot->nextSlot;                                                            \
                slot->nextSlot           = hash->slotFreeList;                                                        \
                hash->slotFreeList       = slot;                                                                      \
                slot->numUsed            = 0;                                                                         \
                slot                     = nextSlot;                                                                  \
            }                                                                                                         \
            hash->slotTable[slotNdx] = DE_NULL;                                                                       \
        }                                                                                                             \
        hash->numElements = 0;                                                                                        \
    }                                                                                                                 \
                                                                                                                      \
    TYPENAME##Slot *TYPENAME##_allocSlot(DE_PTR_TYPE(TYPENAME) hash)                                                  \
    {                                                                                                                 \
        TYPENAME##Slot *slot;                                                                                         \
        if (hash->slotFreeList)                                                                                       \
        {                                                                                                             \
            slot               = hash->slotFreeList;                                                                  \
            hash->slotFreeList = hash->slotFreeList->nextSlot;                                                        \
        }                                                                                                             \
        else                                                                                                          \
            slot = (TYPENAME##Slot *)deMemPool_alloc(hash->pool, sizeof(TYPENAME##Slot) * DE_HASH_ELEMENTS_PER_SLOT); \
                                                                                                                      \
        if (slot)                                                                                                     \
        {                                                                                                             \
            slot->nextSlot = DE_NULL;                                                                                 \
            slot->numUsed  = 0;                                                                                       \
        }                                                                                                             \
                                                                                                                      \
        return slot;                                                                                                  \
    }                                                                                                                 \
                                                                                                                      \
    bool TYPENAME##_rehash(DE_PTR_TYPE(TYPENAME) hash, int newSlotTableSize)                                          \
    {                                                                                                                 \
        DE_ASSERT(deIsPowerOfTwo32(newSlotTableSize) && newSlotTableSize > 0);                                        \
        if (newSlotTableSize > hash->slotTableSize)                                                                   \
        {                                                                                                             \
            TYPENAME##Slot **oldSlotTable = hash->slotTable;                                                          \
            TYPENAME##Slot **newSlotTable =                                                                           \
                (TYPENAME##Slot **)deMemPool_alloc(hash->pool, sizeof(TYPENAME##Slot *) * (size_t)newSlotTableSize);  \
            int oldSlotTableSize = hash->slotTableSize;                                                               \
            int slotNdx;                                                                                              \
                                                                                                                      \
            if (!newSlotTable)                                                                                        \
                return false;                                                                                         \
                                                                                                                      \
            for (slotNdx = 0; slotNdx < oldSlotTableSize; slotNdx++)                                                  \
                newSlotTable[slotNdx] = oldSlotTable[slotNdx];                                                        \
                                                                                                                      \
            for (slotNdx = oldSlotTableSize; slotNdx < newSlotTableSize; slotNdx++)                                   \
                newSlotTable[slotNdx] = DE_NULL;                                                                      \
                                                                                                                      \
            hash->slotTableSize = newSlotTableSize;                                                                   \
            hash->slotTable     = newSlotTable;                                                                       \
                                                                                                                      \
            for (slotNdx = 0; slotNdx < oldSlotTableSize; slotNdx++)                                                  \
            {                                                                                                         \
                TYPENAME##Slot *slot  = oldSlotTable[slotNdx];                                                        \
                newSlotTable[slotNdx] = DE_NULL;                                                                      \
                while (slot)                                                                                          \
                {                                                                                                     \
                    int elemNdx;                                                                                      \
                    for (elemNdx = 0; elemNdx < slot->numUsed; elemNdx++)                                             \
                    {                                                                                                 \
                        hash->numElements--;                                                                          \
                        if (!TYPENAME##_insert(hash, slot->keys[elemNdx], slot->values[elemNdx]))                     \
                            return false;                                                                             \
                    }                                                                                                 \
                    slot = slot->nextSlot;                                                                            \
                }                                                                                                     \
            }                                                                                                         \
        }                                                                                                             \
                                                                                                                      \
        return true;                                                                                                  \
    }                                                                                                                 \
                                                                                                                      \
    VALUETYPE *TYPENAME##_find(const TYPENAME *hash, KEYTYPE key)                                                     \
    {                                                                                                                 \
        if (hash->numElements > 0)                                                                                    \
        {                                                                                                             \
            int slotNdx          = (int)(HASHFUNC(key) & (uint32_t)(hash->slotTableSize - 1));                        \
            TYPENAME##Slot *slot = hash->slotTable[slotNdx];                                                          \
            DE_ASSERT(deInBounds32(slotNdx, 0, hash->slotTableSize));                                                 \
                                                                                                                      \
            while (slot)                                                                                              \
            {                                                                                                         \
                int elemNdx;                                                                                          \
                for (elemNdx = 0; elemNdx < slot->numUsed; elemNdx++)                                                 \
                {                                                                                                     \
                    if (CMPFUNC(slot->keys[elemNdx], key))                                                            \
                        return &slot->values[elemNdx];                                                                \
                }                                                                                                     \
                slot = slot->nextSlot;                                                                                \
            }                                                                                                         \
        }                                                                                                             \
                                                                                                                      \
        return DE_NULL;                                                                                               \
    }                                                                                                                 \
                                                                                                                      \
    bool TYPENAME##_insert(DE_PTR_TYPE(TYPENAME) hash, KEYTYPE key, VALUETYPE value)                                  \
    {                                                                                                                 \
        int slotNdx;                                                                                                  \
        TYPENAME##Slot *slot;                                                                                         \
                                                                                                                      \
        DE_ASSERT(!TYPENAME##_find(hash, key));                                                                       \
                                                                                                                      \
        if ((hash->numElements + 1) >= hash->slotTableSize * DE_HASH_ELEMENTS_PER_SLOT)                               \
            if (!TYPENAME##_rehash(hash, deMax32(4, 2 * hash->slotTableSize)))                                        \
                return false;                                                                                         \
                                                                                                                      \
        slotNdx = (int)(HASHFUNC(key) & (uint32_t)(hash->slotTableSize - 1));                                         \
        DE_ASSERT(slotNdx >= 0 && slotNdx < hash->slotTableSize);                                                     \
        slot = hash->slotTable[slotNdx];                                                                              \
                                                                                                                      \
        if (!slot)                                                                                                    \
        {                                                                                                             \
            slot = TYPENAME##_allocSlot(hash);                                                                        \
            if (!slot)                                                                                                \
                return false;                                                                                         \
            hash->slotTable[slotNdx] = slot;                                                                          \
        }                                                                                                             \
                                                                                                                      \
        for (;;)                                                                                                      \
        {                                                                                                             \
            if (slot->numUsed == DE_HASH_ELEMENTS_PER_SLOT)                                                           \
            {                                                                                                         \
                if (slot->nextSlot)                                                                                   \
                    slot = slot->nextSlot;                                                                            \
                else                                                                                                  \
                {                                                                                                     \
                    TYPENAME##Slot *nextSlot = TYPENAME##_allocSlot(hash);                                            \
                    if (!nextSlot)                                                                                    \
                        return false;                                                                                 \
                    slot->nextSlot = nextSlot;                                                                        \
                    slot           = nextSlot;                                                                        \
                }                                                                                                     \
            }                                                                                                         \
            else                                                                                                      \
            {                                                                                                         \
                slot->keys[slot->numUsed]   = key;                                                                    \
                slot->values[slot->numUsed] = value;                                                                  \
                slot->numUsed++;                                                                                      \
                hash->numElements++;                                                                                  \
                return true;                                                                                          \
            }                                                                                                         \
        }                                                                                                             \
    }                                                                                                                 \
                                                                                                                      \
    void TYPENAME##_delete(DE_PTR_TYPE(TYPENAME) hash, KEYTYPE key)                                                   \
    {                                                                                                                 \
        int slotNdx;                                                                                                  \
        TYPENAME##Slot *slot;                                                                                         \
        TYPENAME##Slot *prevSlot = DE_NULL;                                                                           \
                                                                                                                      \
        DE_ASSERT(hash->numElements > 0);                                                                             \
        slotNdx = (int)(HASHFUNC(key) & (uint32_t)(hash->slotTableSize - 1));                                         \
        DE_ASSERT(slotNdx >= 0 && slotNdx < hash->slotTableSize);                                                     \
        slot = hash->slotTable[slotNdx];                                                                              \
        DE_ASSERT(slot);                                                                                              \
                                                                                                                      \
        for (;;)                                                                                                      \
        {                                                                                                             \
            int elemNdx;                                                                                              \
            DE_ASSERT(slot->numUsed > 0);                                                                             \
            for (elemNdx = 0; elemNdx < slot->numUsed; elemNdx++)                                                     \
            {                                                                                                         \
                if (CMPFUNC(slot->keys[elemNdx], key))                                                                \
                {                                                                                                     \
                    TYPENAME##Slot *lastSlot = slot;                                                                  \
                    while (lastSlot->nextSlot)                                                                        \
                    {                                                                                                 \
                        prevSlot = lastSlot;                                                                          \
                        lastSlot = lastSlot->nextSlot;                                                                \
                    }                                                                                                 \
                                                                                                                      \
                    slot->keys[elemNdx]   = lastSlot->keys[lastSlot->numUsed - 1];                                    \
                    slot->values[elemNdx] = lastSlot->values[lastSlot->numUsed - 1];                                  \
                    lastSlot->numUsed--;                                                                              \
                                                                                                                      \
                    if (lastSlot->numUsed == 0)                                                                       \
                    {                                                                                                 \
                        if (prevSlot)                                                                                 \
                            prevSlot->nextSlot = DE_NULL;                                                             \
                        else                                                                                          \
                            hash->slotTable[slotNdx] = DE_NULL;                                                       \
                                                                                                                      \
                        lastSlot->nextSlot = hash->slotFreeList;                                                      \
                        hash->slotFreeList = lastSlot;                                                                \
                    }                                                                                                 \
                                                                                                                      \
                    hash->numElements--;                                                                              \
                    return;                                                                                           \
                }                                                                                                     \
            }                                                                                                         \
                                                                                                                      \
            prevSlot = slot;                                                                                          \
            slot     = slot->nextSlot;                                                                                \
            DE_ASSERT(slot);                                                                                          \
        }                                                                                                             \
    }                                                                                                                 \
    struct TYPENAME##Unused2_s                                                                                        \
    {                                                                                                                 \
        int unused;                                                                                                   \
    }

/* Copy-to-array templates. */

#define DE_DECLARE_POOL_HASH_TO_ARRAY(HASHTYPENAME, KEYARRAYTYPENAME, VALUEARRAYTYPENAME)            \
    bool HASHTYPENAME##_copyToArray(const HASHTYPENAME *set, DE_PTR_TYPE(KEYARRAYTYPENAME) keyArray, \
                                    DE_PTR_TYPE(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, DE_PTR_TYPE(KEYARRAYTYPENAME) keyArray, \
                                    DE_PTR_TYPE(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 /* _DEPOOLHASH_H */