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

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

#include "deDefs.h"
#include "deMemPool.h"

enum
{
    DE_ARRAY_ELEMENTS_PER_PAGE_LOG2 = 4 /*!< \internal 16 */
};

/*--------------------------------------------------------------------*//*!
 * \internal
 * \brief Type-independent version of the array template class.
 *//*--------------------------------------------------------------------*/
typedef struct dePoolArray_s
{
    deMemPool *pool; /*!< Pool from which all memory is allocated from.    */

    int elementSize; /*!< Size of the element (in bytes).                */
    int numElements; /*!< Number of elements in the array.                */
    int capacity;    /*!< Number of allocated elements in the array.        */

    int pageTableCapacity; /*!< Size of the page table.                        */
    void **pageTable;      /*!< Pointer to the page table.                        */
} dePoolArray;

DE_BEGIN_EXTERN_C

dePoolArray *dePoolArray_create(deMemPool *pool, int elementSize);
bool dePoolArray_reserve(dePoolArray *arr, int capacity);
bool dePoolArray_setSize(dePoolArray *arr, int size);

void dePoolArray_selfTest(void);

DE_END_EXTERN_C

/*--------------------------------------------------------------------*//*!
 * \brief Declare a template pool array class.
 * \param TYPENAME    Type name of the declared array.
 * \param VALUETYPE    Type of the value contained in the array.
 *
 * This macro declares a pool array with all the necessary functions for
 * operating with it. All allocated memory is taken from the memory pool
 * given to the constructor.
 *
 * The array is implemented by having a set of pages (which store the
 * elements) and a page table with pointers to each of them. The pages
 * are allocated individually whenever they are needed, but the page
 * table grows exponentially. This keeps the memory overhead for large
 * arrays very small. On the other hand, the relative overhead for very
 * small arrays is prohibitive (the minimum allocation is 16 elements).
 *
 * The functions for operating the array are:
 * \todo [petri] Figure out how to comment these in Doxygen-style.
 *
 * \code
 * Array*   Array_create            (deMemPool* pool);
 * int      Array_getNumElements    (const Array* array);
 * bool   Array_reserve           (Array* array, int size);
 * bool   Array_setSize           (Array* array, int size);
 * void        Array_reset                (Array* array);
 * Element  Array_get               (Array* array, int ndx);
 * bool   Array_set               (Array* array, int ndx, Element elem);
 * bool   Array_pushBack          (Array* array, Element elem);
 * Element  Array_popBack           (Array* array);
 * void     Array_swap              (Array* array, int aNdx, int bNdx);
 * \endcode
*//*--------------------------------------------------------------------*/
#define DE_DECLARE_POOL_ARRAY(TYPENAME, VALUETYPE)                                                               \
                                                                                                                 \
    typedef struct TYPENAME##_s                                                                                  \
    {                                                                                                            \
        deMemPool *pool;                                                                                         \
                                                                                                                 \
        int elementSize;                                                                                         \
        int numElements;                                                                                         \
        int capacity;                                                                                            \
                                                                                                                 \
        int pageTableCapacity;                                                                                   \
        DE_PTR_TYPE(VALUETYPE) * pageTable;                                                                      \
    } TYPENAME; /* NOLINT(TYPENAME) */                                                                           \
                                                                                                                 \
    DE_INLINE TYPENAME *TYPENAME##_create(deMemPool *pool);                                                      \
    DE_INLINE int TYPENAME##_getNumElements(const TYPENAME *arr) DE_UNUSED_FUNCTION;                             \
    DE_INLINE bool TYPENAME##_reserve(DE_PTR_TYPE(TYPENAME) arr, int capacity) DE_UNUSED_FUNCTION;               \
    DE_INLINE bool TYPENAME##_setSize(DE_PTR_TYPE(TYPENAME) arr, int size) DE_UNUSED_FUNCTION;                   \
    DE_INLINE void TYPENAME##_reset(DE_PTR_TYPE(TYPENAME) arr) DE_UNUSED_FUNCTION;                               \
    DE_INLINE VALUETYPE TYPENAME##_get(const TYPENAME *arr, int ndx) DE_UNUSED_FUNCTION;                         \
    DE_INLINE void TYPENAME##_set(DE_PTR_TYPE(TYPENAME) arr, int ndx, VALUETYPE elem) DE_UNUSED_FUNCTION;        \
    DE_INLINE bool TYPENAME##_pushBack(DE_PTR_TYPE(TYPENAME) arr, VALUETYPE elem) DE_UNUSED_FUNCTION;            \
    DE_INLINE VALUETYPE TYPENAME##_popBack(DE_PTR_TYPE(TYPENAME) arr) DE_UNUSED_FUNCTION;                        \
    DE_INLINE bool TYPENAME##_copy(DE_PTR_TYPE(TYPENAME) dst, const TYPENAME *src) DE_UNUSED_FUNCTION;           \
    DE_INLINE void TYPENAME##_swap(DE_PTR_TYPE(TYPENAME) arr, int aNdx, int bNdx) DE_UNUSED_FUNCTION;            \
                                                                                                                 \
    DE_INLINE TYPENAME *TYPENAME##_create(deMemPool *pool)                                                       \
    {                                                                                                            \
        return (TYPENAME *)dePoolArray_create(pool, sizeof(VALUETYPE));                                          \
    }                                                                                                            \
                                                                                                                 \
    DE_INLINE int TYPENAME##_getNumElements(const TYPENAME *arr)                                                 \
    {                                                                                                            \
        return arr->numElements;                                                                                 \
    }                                                                                                            \
                                                                                                                 \
    DE_INLINE bool TYPENAME##_reserve(DE_PTR_TYPE(TYPENAME) arr, int capacity)                                   \
    {                                                                                                            \
        if (capacity > arr->capacity)                                                                            \
            return dePoolArray_reserve((dePoolArray *)arr, capacity);                                            \
        return true;                                                                                             \
    }                                                                                                            \
                                                                                                                 \
    DE_INLINE bool TYPENAME##_setSize(DE_PTR_TYPE(TYPENAME) arr, int size)                                       \
    {                                                                                                            \
        if (size > arr->capacity)                                                                                \
            return dePoolArray_setSize((dePoolArray *)arr, size);                                                \
                                                                                                                 \
        arr->numElements = size;                                                                                 \
        return true;                                                                                             \
    }                                                                                                            \
                                                                                                                 \
    DE_INLINE void TYPENAME##_reset(DE_PTR_TYPE(TYPENAME) arr)                                                   \
    {                                                                                                            \
        arr->numElements = 0;                                                                                    \
    }                                                                                                            \
                                                                                                                 \
    DE_INLINE VALUETYPE TYPENAME##_get(const TYPENAME *arr, int ndx)                                             \
    {                                                                                                            \
        DE_ASSERT(ndx >= 0 && ndx < arr->numElements);                                                           \
        {                                                                                                        \
            int pageNdx = (ndx >> DE_ARRAY_ELEMENTS_PER_PAGE_LOG2);                                              \
            int subNdx  = ndx & ((1 << DE_ARRAY_ELEMENTS_PER_PAGE_LOG2) - 1);                                    \
            return ((VALUETYPE *)arr->pageTable[pageNdx])[subNdx];                                               \
        }                                                                                                        \
    }                                                                                                            \
                                                                                                                 \
    DE_INLINE void TYPENAME##_set(DE_PTR_TYPE(TYPENAME) arr, int ndx, VALUETYPE elem)                            \
    {                                                                                                            \
        DE_ASSERT(ndx >= 0 && ndx < arr->numElements);                                                           \
        {                                                                                                        \
            int pageNdx                                    = (ndx >> DE_ARRAY_ELEMENTS_PER_PAGE_LOG2);           \
            int subNdx                                     = ndx & ((1 << DE_ARRAY_ELEMENTS_PER_PAGE_LOG2) - 1); \
            ((VALUETYPE *)arr->pageTable[pageNdx])[subNdx] = elem;                                               \
        }                                                                                                        \
    }                                                                                                            \
                                                                                                                 \
    DE_INLINE bool TYPENAME##_pushBack(DE_PTR_TYPE(TYPENAME) arr, VALUETYPE elem)                                \
    {                                                                                                            \
        if ((arr->numElements + 1 >= arr->capacity) && !TYPENAME##_reserve(arr, arr->numElements + 1))           \
            return false;                                                                                        \
        arr->numElements++;                                                                                      \
        TYPENAME##_set(arr, arr->numElements - 1, elem);                                                         \
        return true;                                                                                             \
    }                                                                                                            \
                                                                                                                 \
    DE_INLINE VALUETYPE TYPENAME##_popBack(DE_PTR_TYPE(TYPENAME) arr)                                            \
    {                                                                                                            \
        int ndx     = arr->numElements - 1;                                                                      \
        int pageNdx = (ndx >> DE_ARRAY_ELEMENTS_PER_PAGE_LOG2);                                                  \
        int subNdx  = ndx & ((1 << DE_ARRAY_ELEMENTS_PER_PAGE_LOG2) - 1);                                        \
        DE_ASSERT(arr->numElements > 0);                                                                         \
        arr->numElements--;                                                                                      \
        /* \note We access a value which is out-of-bounds, but we know it to be safe. */                         \
        return ((VALUETYPE *)arr->pageTable[pageNdx])[subNdx];                                                   \
    }                                                                                                            \
                                                                                                                 \
    DE_INLINE bool TYPENAME##_copy(DE_PTR_TYPE(TYPENAME) dst, const TYPENAME *src)                               \
    {                                                                                                            \
        DE_ASSERT(dst &&src);                                                                                    \
        {                                                                                                        \
            int numElements = src->numElements;                                                                  \
            int ndx;                                                                                             \
            if (!TYPENAME##_setSize(dst, numElements))                                                           \
                return false;                                                                                    \
            for (ndx = 0; ndx < numElements; ndx++)                                                              \
                TYPENAME##_set(dst, ndx, TYPENAME##_get(src, ndx));                                              \
        }                                                                                                        \
        return true;                                                                                             \
    }                                                                                                            \
                                                                                                                 \
    DE_INLINE void TYPENAME##_swap(DE_PTR_TYPE(TYPENAME) arr, int aNdx, int bNdx)                                \
    {                                                                                                            \
        VALUETYPE tmp = TYPENAME##_get(arr, aNdx);                                                               \
        TYPENAME##_set(arr, aNdx, TYPENAME##_get(arr, bNdx));                                                    \
        TYPENAME##_set(arr, bNdx, tmp);                                                                          \
    }                                                                                                            \
                                                                                                                 \
    struct TYPENAME##Unused_s                                                                                    \
    {                                                                                                            \
        int unused;                                                                                              \
    }

/*--------------------------------------------------------------------*//*!
 * \brief Declare a sort function for an array.
 * \param TYPENAME    Type name of the declared array.
 * \param VALUETYPE    Type of the value contained in the array.
 * \param SORTNAME    Name for this specific sort.
 * \param CMPFUNC    Comparison function for sorting.
 *
 * This macro declares a sort function for an array declared using
 * DE_DECLARE_POOL_ARRAY macro.
 *
 * Sorting algorithm is heap sort since it requires constant amount of
 * auxiliary space and is in-place sort. Worst-case run-time is O(n log n)
 * and sort is NOT stable.
 *
 * CMPFUNC is used to compare elements in array. It must accept two
 * parameters and return negative integer if first is smaller than, 0 if
 * both are equal and positive integer if first is larger than second.
 *
 * The functions for sorting array are:
 * \todo [petri] Figure out how to comment these in Doxygen-style.
 *
 * \code
 * void        Array_sortName            (Array* array);
 * void        Array_sortNameHeapify    (Array* array);
 * void        Array_sortNameShiftDown    (Array* array, int start, int end);
 * \endcode
*//*--------------------------------------------------------------------*/
#define DE_DECLARE_POOL_ARRAY_SORT(TYPENAME, VALUETYPE, SORTNAME, CMPFUNC)                               \
                                                                                                         \
    DE_INLINE void TYPENAME##_##SORTNAME##ShiftDown(DE_PTR_TYPE(TYPENAME) arr, int startNdx, int endNdx) \
    {                                                                                                    \
        int rootNdx = startNdx;                                                                          \
                                                                                                         \
        while (rootNdx * 2 + 1 <= endNdx)                                                                \
        {                                                                                                \
            int childNdx = rootNdx * 2 + 1;                                                              \
                                                                                                         \
            if ((childNdx + 1 <= endNdx) &&                                                              \
                (CMPFUNC(TYPENAME##_get(arr, childNdx), TYPENAME##_get(arr, childNdx + 1)) < 0))         \
                childNdx += 1;                                                                           \
                                                                                                         \
            if (CMPFUNC(TYPENAME##_get(arr, rootNdx), TYPENAME##_get(arr, childNdx)) < 0)                \
            {                                                                                            \
                TYPENAME##_swap(arr, rootNdx, childNdx);                                                 \
                rootNdx = childNdx;                                                                      \
            }                                                                                            \
            else                                                                                         \
                break;                                                                                   \
        }                                                                                                \
    }                                                                                                    \
                                                                                                         \
    DE_INLINE void TYPENAME##_##SORTNAME##Heapify(DE_PTR_TYPE(TYPENAME) arr)                             \
    {                                                                                                    \
        int startNdx = (TYPENAME##_getNumElements(arr) - 2) / 2;                                         \
                                                                                                         \
        while (startNdx >= 0)                                                                            \
        {                                                                                                \
            TYPENAME##_##SORTNAME##ShiftDown(arr, startNdx, TYPENAME##_getNumElements(arr) - 1);         \
            startNdx -= 1;                                                                               \
        }                                                                                                \
    }                                                                                                    \
                                                                                                         \
    DE_INLINE void TYPENAME##_##SORTNAME(DE_PTR_TYPE(TYPENAME) arr)                                      \
    {                                                                                                    \
        int endNdx = TYPENAME##_getNumElements(arr) - 1;                                                 \
                                                                                                         \
        TYPENAME##_##SORTNAME##Heapify(arr);                                                             \
                                                                                                         \
        while (endNdx > 0)                                                                               \
        {                                                                                                \
            TYPENAME##_swap(arr, endNdx, 0);                                                             \
            endNdx -= 1;                                                                                 \
            TYPENAME##_##SORTNAME##ShiftDown(arr, 0, endNdx);                                            \
        }                                                                                                \
    }                                                                                                    \
                                                                                                         \
    struct TYPENAME##SORTNAME##unused_s                                                                  \
    {                                                                                                    \
        int unused;                                                                                      \
    }

/* Basic array types. */

DE_DECLARE_POOL_ARRAY(deIntArray, int);
DE_DECLARE_POOL_ARRAY(deInt8Array, int8_t);
DE_DECLARE_POOL_ARRAY(deUint8Array, uint8_t);
DE_DECLARE_POOL_ARRAY(deInt16Array, int16_t);
DE_DECLARE_POOL_ARRAY(deUint16Array, uint16_t);
DE_DECLARE_POOL_ARRAY(deInt32Array, int32_t);
DE_DECLARE_POOL_ARRAY(deUint32Array, uint32_t);

#endif /* _DEPOOLARRAY_H */