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

#ifndef _DEPOOLHASHARRAY_H
#define _DEPOOLHASHARRAY_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-array class.
 *//*--------------------------------------------------------------------*/

#include "deDefs.h"
#include "dePoolHash.h"
#include "dePoolArray.h"

DE_BEGIN_EXTERN_C

void dePoolHashArray_selfTest(void);

DE_END_EXTERN_C

/*--------------------------------------------------------------------*//*!
 * \brief Declare a template pool hash-array (array with hash) class interface.
 * \param TYPENAME            Type name of the declared hash-array.
 * \param KEYTYPE            Type of the key.
 * \param VALUETYPE            Type of the value.
 * \param KEYARRAYTYPE        Type of the key array.
 * \param VALUEARRAYTYPE    Type of the value array.
 *
 * \todo [petri] Description.
 *
 * The functions for operating the hash are:
 * \todo [petri] Figure out how to comment these in Doxygen-style.
 *
 * \todo [pyry] HashArray_find() will break if dePoolArray implementation changes.
 *
 * \code
 * HashArray*  HashArray_create            (deMemPool* pool);
 * int         HashArray_getNumElements    (const HashArray* hashArray);
 * Value*      HashArray_find              (Hash* hashArray, Key key);
 * bool      HashArray_insert            (Hash* hashArray, Key key, Value value);
 * bool      HashArray_copyToArray       (Hash* hashArray, KeyArray* keys, ValueArray* values);
 * \endcode
*//*--------------------------------------------------------------------*/
#define DE_DECLARE_POOL_HASH_ARRAY(TYPENAME, KEYTYPE, VALUETYPE, KEYARRAYTYPE, VALUEARRAYTYPE)       \
                                                                                                     \
    DE_DECLARE_POOL_ARRAY(TYPENAME##Array, VALUETYPE);                                               \
    DE_DECLARE_POOL_HASH(TYPENAME##Hash, KEYTYPE, int);                                              \
                                                                                                     \
    typedef struct TYPENAME_s                                                                        \
    {                                                                                                \
        TYPENAME##Hash *hash;                                                                        \
        TYPENAME##Array *array;                                                                      \
    } TYPENAME; /* NOLINT(TYPENAME) */                                                               \
                                                                                                     \
    TYPENAME *TYPENAME##_create(deMemPool *pool);                                                    \
    bool TYPENAME##_insert(DE_PTR_TYPE(TYPENAME) hashArray, KEYTYPE key, VALUETYPE value);           \
    bool TYPENAME##_copyToArray(const TYPENAME *hashArray, DE_PTR_TYPE(KEYARRAYTYPE) keys,           \
                                DE_PTR_TYPE(VALUEARRAYTYPE) values);                                 \
                                                                                                     \
    DE_INLINE int TYPENAME##_getNumElements(const TYPENAME *hashArray) DE_UNUSED_FUNCTION;           \
    DE_INLINE VALUETYPE *TYPENAME##_find(const TYPENAME *hashArray, KEYTYPE key) DE_UNUSED_FUNCTION; \
    DE_INLINE void TYPENAME##_reset(DE_PTR_TYPE(TYPENAME) hashArray) DE_UNUSED_FUNCTION;             \
                                                                                                     \
    DE_INLINE int TYPENAME##_getNumElements(const TYPENAME *hashArray)                               \
    {                                                                                                \
        return TYPENAME##Array_getNumElements(hashArray->array);                                     \
    }                                                                                                \
                                                                                                     \
    DE_INLINE VALUETYPE *TYPENAME##_find(const TYPENAME *hashArray, KEYTYPE key)                     \
    {                                                                                                \
        int *ndxPtr = TYPENAME##Hash_find(hashArray->hash, key);                                     \
        if (!ndxPtr)                                                                                 \
            return DE_NULL;                                                                          \
        else                                                                                         \
        {                                                                                            \
            int ndx = *ndxPtr;                                                                       \
            DE_ASSERT(ndx >= 0 && ndx < hashArray->array->numElements);                              \
            {                                                                                        \
                int pageNdx = (ndx >> DE_ARRAY_ELEMENTS_PER_PAGE_LOG2);                              \
                int subNdx  = ndx & ((1 << DE_ARRAY_ELEMENTS_PER_PAGE_LOG2) - 1);                    \
                return &((VALUETYPE *)hashArray->array->pageTable[pageNdx])[subNdx];                 \
            }                                                                                        \
        }                                                                                            \
    }                                                                                                \
                                                                                                     \
    DE_INLINE void TYPENAME##_reset(DE_PTR_TYPE(TYPENAME) hashArray)                                 \
    {                                                                                                \
        TYPENAME##Hash_reset(hashArray->hash);                                                       \
        TYPENAME##Array_reset(hashArray->array);                                                     \
    }                                                                                                \
                                                                                                     \
    struct TYPENAME##Unused_s                                                                        \
    {                                                                                                \
        int unused;                                                                                  \
    }

/*--------------------------------------------------------------------*//*!
 * \brief Implement a template pool hash-array class.
 * \param TYPENAME            Type name of the declared hash.
 * \param KEYTYPE            Type of the key.
 * \param VALUETYPE            Type of the value.
 * \param KEYARRAYTYPE        Type of the key array.
 * \param VALUEARRAYTYPE    Type of the value array.
 * \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_ARRAY(TYPENAME, KEYTYPE, VALUETYPE, KEYARRAYTYPE, VALUEARRAYTYPE, KEYHASHFUNC,         \
                                     KEYCMPFUNC)                                                                      \
                                                                                                                      \
    DE_IMPLEMENT_POOL_HASH(TYPENAME##Hash, KEYTYPE, int, KEYHASHFUNC, KEYCMPFUNC);                                    \
                                                                                                                      \
    TYPENAME *TYPENAME##_create(deMemPool *pool)                                                                      \
    {                                                                                                                 \
        DE_PTR_TYPE(TYPENAME) hashArray = DE_POOL_NEW(pool, TYPENAME);                                                \
        if (!hashArray)                                                                                               \
            return DE_NULL;                                                                                           \
        if ((hashArray->hash = TYPENAME##Hash_create(pool)) == DE_NULL)                                               \
            return DE_NULL;                                                                                           \
        if ((hashArray->array = TYPENAME##Array_create(pool)) == DE_NULL)                                             \
            return DE_NULL;                                                                                           \
        return hashArray;                                                                                             \
    }                                                                                                                 \
                                                                                                                      \
    bool TYPENAME##_insert(DE_PTR_TYPE(TYPENAME) hashArray, KEYTYPE key, VALUETYPE value)                             \
    {                                                                                                                 \
        int numElements = TYPENAME##Array_getNumElements(hashArray->array);                                           \
        DE_ASSERT(TYPENAME##Hash_getNumElements(hashArray->hash) == numElements);                                     \
        DE_ASSERT(!TYPENAME##Hash_find(hashArray->hash, key));                                                        \
        if (!TYPENAME##Array_setSize(hashArray->array, numElements + 1) ||                                            \
            !TYPENAME##Hash_insert(hashArray->hash, key, numElements))                                                \
            return false;                                                                                             \
        TYPENAME##Array_set(hashArray->array, numElements, value);                                                    \
        return true;                                                                                                  \
    }                                                                                                                 \
                                                                                                                      \
    bool TYPENAME##_copyToArray(const TYPENAME *hashArray, DE_PTR_TYPE(KEYARRAYTYPE) keys,                            \
                                DE_PTR_TYPE(VALUEARRAYTYPE) values)                                                   \
    {                                                                                                                 \
        int numElements      = TYPENAME##Array_getNumElements(hashArray->array);                                      \
        TYPENAME##Hash *hash = hashArray->hash;                                                                       \
        TYPENAME##HashIter iter;                                                                                      \
        DE_ASSERT(TYPENAME##Hash_getNumElements(hashArray->hash) == numElements);                                     \
        if ((keys && !KEYARRAYTYPE##_setSize(keys, numElements)) ||                                                   \
            (values && !VALUEARRAYTYPE##_setSize(values, numElements)))                                               \
            return false;                                                                                             \
        for (TYPENAME##HashIter_init(hash, &iter); TYPENAME##HashIter_hasItem(&iter); TYPENAME##HashIter_next(&iter)) \
        {                                                                                                             \
            KEYTYPE key = TYPENAME##HashIter_getKey(&iter);                                                           \
            int ndx     = TYPENAME##HashIter_getValue(&iter);                                                         \
            if (keys)                                                                                                 \
                KEYARRAYTYPE##_set(keys, ndx, key);                                                                   \
            if (values)                                                                                               \
                VALUEARRAYTYPE##_set(values, ndx, TYPENAME##Array_get(hashArray->array, ndx));                        \
        }                                                                                                             \
        return true;                                                                                                  \
    }                                                                                                                 \
                                                                                                                      \
    struct TYPENAME##Unused2_s                                                                                        \
    {                                                                                                                 \
        int unused;                                                                                                   \
    }

#endif /* _DEPOOLHASHARRAY_H */