framework/delibs/depool/dePoolArray.h

   1 #ifndef _DEPOOLARRAY_H
   2 #define _DEPOOLARRAY_H
   3 /*-------------------------------------------------------------------------
   4  * drawElements Memory Pool Library
   5  * --------------------------------
   6  *
   7  * Copyright 2014 The Android Open Source Project
   8  *
   9  * Licensed under the Apache License, Version 2.0 (the "License");
  10  * you may not use this file except in compliance with the License.
  11  * You may obtain a copy of the License at
  12  *
  13  *      http://www.apache.org/licenses/LICENSE-2.0
  14  *
  15  * Unless required by applicable law or agreed to in writing, software
  16  * distributed under the License is distributed on an "AS IS" BASIS,
  17  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  18  * See the License for the specific language governing permissions and
  19  * limitations under the License.
  20  *
  21  *//*!
  22  * \file
  23  * \brief Memory pool array class.
  24  *//*--------------------------------------------------------------------*/
  25
  26 #include "deDefs.h"
  27 #include "deMemPool.h"
  28
  29 enum
  30 {
  31         DE_ARRAY_ELEMENTS_PER_PAGE_LOG2 = 4             /*!< \internal 16 */
  32 };
  33
  34 /*--------------------------------------------------------------------*//*!
  35  * \internal
  36  * \brief Type-independent version of the array template class.
  37  *//*--------------------------------------------------------------------*/
  38 typedef struct dePoolArray_s
  39 {
  40         deMemPool*              pool;                           /*!< Pool from which all memory is allocated from.      */
  41
  42         int                             elementSize;            /*!< Size of the element (in bytes).                            */
  43         int                             numElements;            /*!< Number of elements in the array.                           */
  44         int                             capacity;                       /*!< Number of allocated elements in the array.         */
  45
  46         int                             pageTableCapacity;      /*!< Size of the page table.                                            */
  47         void**                  pageTable;                      /*!< Pointer to the page table.                                         */
  48 } dePoolArray;
  49
  50 DE_BEGIN_EXTERN_C
  51
  52 dePoolArray*    dePoolArray_create                      (deMemPool* pool, int elementSize);
  53 deBool                  dePoolArray_reserve                     (dePoolArray* arr, int capacity);
  54 deBool                  dePoolArray_setSize                     (dePoolArray* arr, int size);
  55
  56 void                    dePoolArray_selfTest            (void);
  57
  58 DE_END_EXTERN_C
  59
  60 /*--------------------------------------------------------------------*//*!
  61  * \brief Declare a template pool array class.
  62  * \param TYPENAME      Type name of the declared array.
  63  * \param VALUETYPE     Type of the value contained in the array.
  64  *
  65  * This macro declares a pool array with all the necessary functions for
  66  * operating with it. All allocated memory is taken from the memory pool
  67  * given to the constructor.
  68  *
  69  * The array is implemented by having a set of pages (which store the
  70  * elements) and a page table with pointers to each of them. The pages
  71  * are allocated individually whenever they are needed, but the page
  72  * table grows exponentially. This keeps the memory overhead for large
  73  * arrays very small. On the other hand, the relative overhead for very
  74  * small arrays is prohibitive (the minimum allocation is 16 elements).
  75  *
  76  * The functions for operating the array are:
  77  * \todo [petri] Figure out how to comment these in Doxygen-style.
  78  *
  79  * \code
  80  * Array*   Array_create            (deMemPool* pool);
  81  * int      Array_getNumElements    (const Array* array);
  82  * deBool   Array_reserve           (Array* array, int size);
  83  * deBool   Array_setSize           (Array* array, int size);
  84  * void         Array_reset                             (Array* array);
  85  * Element  Array_get               (Array* array, int ndx);
  86  * deBool   Array_set               (Array* array, int ndx, Element elem);
  87  * deBool   Array_pushBack          (Array* array, Element elem);
  88  * Element  Array_popBack           (Array* array);
  89  * void     Array_swap              (Array* array, int aNdx, int bNdx);
  90  * \endcode
  91 *//*--------------------------------------------------------------------*/
  92 #define DE_DECLARE_POOL_ARRAY(TYPENAME, VALUETYPE)              \
  93     \
  94 typedef struct TYPENAME##_s                                     \
  95 {                                                                                       \
  96         deMemPool*                      pool;                           \
  97                                                                                         \
  98         int                                     elementSize;            \
  99         int                                     numElements;            \
 100         int                                     capacity;                       \
 101                                                                                         \
 102         int                                     pageTableCapacity;      \
 103         DE_PTR_TYPE(VALUETYPE)* pageTable;              \
 104 } TYPENAME; /* NOLINT(TYPENAME) */                      \
 105 \
 106 DE_INLINE TYPENAME*     TYPENAME##_create                       (deMemPool* pool);                                                                                                                      \
 107 DE_INLINE int           TYPENAME##_getNumElements       (const TYPENAME* arr)                                                                   DE_UNUSED_FUNCTION;     \
 108 DE_INLINE deBool        TYPENAME##_reserve                      (DE_PTR_TYPE(TYPENAME) arr, int capacity)                               DE_UNUSED_FUNCTION;     \
 109 DE_INLINE deBool        TYPENAME##_setSize                      (DE_PTR_TYPE(TYPENAME) arr, int size)                                   DE_UNUSED_FUNCTION;     \
 110 DE_INLINE void          TYPENAME##_reset                        (DE_PTR_TYPE(TYPENAME) arr)                                                             DE_UNUSED_FUNCTION;     \
 111 DE_INLINE VALUETYPE     TYPENAME##_get                          (const TYPENAME* arr, int ndx)                                                  DE_UNUSED_FUNCTION;     \
 112 DE_INLINE void          TYPENAME##_set                          (DE_PTR_TYPE(TYPENAME) arr, int ndx, VALUETYPE elem)    DE_UNUSED_FUNCTION;     \
 113 DE_INLINE deBool        TYPENAME##_pushBack                     (DE_PTR_TYPE(TYPENAME) arr, VALUETYPE elem)                             DE_UNUSED_FUNCTION;     \
 114 DE_INLINE VALUETYPE     TYPENAME##_popBack                      (DE_PTR_TYPE(TYPENAME) arr)                                                             DE_UNUSED_FUNCTION;     \
 115 DE_INLINE deBool        TYPENAME##_copy                         (DE_PTR_TYPE(TYPENAME) dst, const TYPENAME* src)                DE_UNUSED_FUNCTION;     \
 116 DE_INLINE void          TYPENAME##_swap                         (DE_PTR_TYPE(TYPENAME) arr, int aNdx, int bNdx)                 DE_UNUSED_FUNCTION;     \
 117 \
 118 DE_INLINE TYPENAME* TYPENAME##_create (deMemPool* pool)    \
 119 {    \
 120         return (TYPENAME*)dePoolArray_create(pool, sizeof(VALUETYPE));    \
 121 }    \
 122 \
 123 DE_INLINE int TYPENAME##_getNumElements (const TYPENAME* arr)    \
 124 {    \
 125         return arr->numElements;    \
 126 }    \
 127 \
 128 DE_INLINE deBool TYPENAME##_reserve (DE_PTR_TYPE(TYPENAME) arr, int capacity)    \
 129 {    \
 130         if (capacity > arr->capacity)    \
 131                 return dePoolArray_reserve((dePoolArray*)arr, capacity);    \
 132         return  DE_TRUE;    \
 133 }    \
 134 \
 135 DE_INLINE deBool TYPENAME##_setSize (DE_PTR_TYPE(TYPENAME) arr, int size)    \
 136 {    \
 137         if (size > arr->capacity)    \
 138                 return dePoolArray_setSize((dePoolArray*)arr, size);    \
 139 \
 140         arr->numElements = size;    \
 141         return DE_TRUE;    \
 142 }    \
 143 \
 144 DE_INLINE void TYPENAME##_reset (DE_PTR_TYPE(TYPENAME) arr)    \
 145 {    \
 146         arr->numElements = 0;    \
 147 }    \
 148 \
 149 DE_INLINE VALUETYPE TYPENAME##_get (const TYPENAME* arr, int ndx)    \
 150 {    \
 151         DE_ASSERT(ndx >= 0 && ndx < arr->numElements);    \
 152         {    \
 153                 int pageNdx     = (ndx >> DE_ARRAY_ELEMENTS_PER_PAGE_LOG2);    \
 154                 int subNdx      = ndx & ((1 << DE_ARRAY_ELEMENTS_PER_PAGE_LOG2) - 1);    \
 155                 return ((VALUETYPE*)arr->pageTable[pageNdx])[subNdx];    \
 156         }    \
 157 }    \
 158 \
 159 DE_INLINE void TYPENAME##_set (DE_PTR_TYPE(TYPENAME) arr, int ndx, VALUETYPE elem)    \
 160 {    \
 161         DE_ASSERT(ndx >= 0 && ndx < arr->numElements);    \
 162         {    \
 163                 int pageNdx     = (ndx >> DE_ARRAY_ELEMENTS_PER_PAGE_LOG2);    \
 164                 int subNdx      = ndx & ((1 << DE_ARRAY_ELEMENTS_PER_PAGE_LOG2) - 1);    \
 165                 ((VALUETYPE*)arr->pageTable[pageNdx])[subNdx] = elem;    \
 166         }    \
 167 }    \
 168 \
 169 DE_INLINE deBool TYPENAME##_pushBack (DE_PTR_TYPE(TYPENAME) arr, VALUETYPE elem)    \
 170 {    \
 171         if ((arr->numElements + 1 >= arr->capacity) && !TYPENAME##_reserve(arr, arr->numElements + 1)) \
 172                 return DE_FALSE; \
 173         arr->numElements++; \
 174         TYPENAME##_set(arr, arr->numElements - 1, elem); \
 175         return DE_TRUE;    \
 176 }    \
 177 \
 178 DE_INLINE VALUETYPE TYPENAME##_popBack (DE_PTR_TYPE(TYPENAME) arr)    \
 179 {    \
 180         int ndx         = arr->numElements - 1; \
 181         int pageNdx     = (ndx >> DE_ARRAY_ELEMENTS_PER_PAGE_LOG2);    \
 182         int subNdx      = ndx & ((1 << DE_ARRAY_ELEMENTS_PER_PAGE_LOG2) - 1);    \
 183         DE_ASSERT(arr->numElements > 0); \
 184         arr->numElements--; \
 185         /* \note We access a value which is out-of-bounds, but we know it to be safe. */ \
 186         return ((VALUETYPE*)arr->pageTable[pageNdx])[subNdx];    \
 187 }    \
 188 \
 189 DE_INLINE deBool TYPENAME##_copy (DE_PTR_TYPE(TYPENAME) dst, const TYPENAME* src)               \
 190 {                                                                                                                                                       \
 191         DE_ASSERT(dst && src);                                                                                                  \
 192         {                                                                                                                                               \
 193                 int numElements = src->numElements;                                                                     \
 194                 int ndx;                                                                                                                        \
 195                 if (!TYPENAME##_setSize(dst, numElements))                                                      \
 196                         return DE_FALSE;                                                                                                \
 197                 for (ndx = 0; ndx < numElements; ndx++)                                                         \
 198                         TYPENAME##_set(dst, ndx, TYPENAME##_get(src, ndx));                             \
 199         }                                                                                                                                               \
 200         return DE_TRUE;                                                                                                                 \
 201 }                                                                                                                                                       \
 202 \
 203 DE_INLINE void TYPENAME##_swap (DE_PTR_TYPE(TYPENAME) arr, int aNdx, int bNdx)  \
 204 {       \
 205         VALUETYPE tmp = TYPENAME##_get(arr, aNdx);      \
 206         TYPENAME##_set(arr, aNdx, TYPENAME##_get(arr, bNdx));   \
 207         TYPENAME##_set(arr, bNdx, tmp); \
 208 }       \
 209 \
 210 struct TYPENAME##Dummy_s { int dummy; }
 211
 212 /*--------------------------------------------------------------------*//*!
 213  * \brief Declare a sort function for an array.
 214  * \param TYPENAME      Type name of the declared array.
 215  * \param VALUETYPE     Type of the value contained in the array.
 216  * \param SORTNAME      Name for this specific sort.
 217  * \param CMPFUNC       Comparison function for sorting.
 218  *
 219  * This macro declares a sort function for an array declared using
 220  * DE_DECLARE_POOL_ARRAY macro.
 221  *
 222  * Sorting algorithm is heap sort since it requires constant amount of
 223  * auxiliary space and is in-place sort. Worst-case run-time is O(n log n)
 224  * and sort is NOT stable.
 225  *
 226  * CMPFUNC is used to compare elements in array. It must accept two
 227  * parameters and return negative integer if first is smaller than, 0 if
 228  * both are equal and positive integer if first is larger than second.
 229  *
 230  * The functions for sorting array are:
 231  * \todo [petri] Figure out how to comment these in Doxygen-style.
 232  *
 233  * \code
 234  * void         Array_sortName                  (Array* array);
 235  * void         Array_sortNameHeapify   (Array* array);
 236  * void         Array_sortNameShiftDown (Array* array, int start, int end);
 237  * \endcode
 238 *//*--------------------------------------------------------------------*/
 239 #define DE_DECLARE_POOL_ARRAY_SORT(TYPENAME, VALUETYPE, SORTNAME, CMPFUNC)      \
 240 \
 241 DE_INLINE void TYPENAME##_##SORTNAME##ShiftDown (DE_PTR_TYPE(TYPENAME) arr, int startNdx, int endNdx)   \
 242 {       \
 243         int rootNdx = startNdx; \
 244         \
 245         while (rootNdx * 2 + 1 <= endNdx)       \
 246         {       \
 247                 int childNdx = rootNdx * 2 + 1; \
 248                 \
 249                 if ((childNdx + 1 <= endNdx) && (CMPFUNC(TYPENAME##_get(arr, childNdx), TYPENAME##_get(arr, childNdx + 1)) < 0))        \
 250                         childNdx += 1;  \
 251                 \
 252                 if (CMPFUNC(TYPENAME##_get(arr, rootNdx), TYPENAME##_get(arr, childNdx)) < 0)   \
 253                 {       \
 254                         TYPENAME##_swap(arr, rootNdx, childNdx);        \
 255                         rootNdx = childNdx;     \
 256                 }       \
 257                 else    \
 258                         break;  \
 259         }       \
 260 }       \
 261 \
 262 DE_INLINE void TYPENAME##_##SORTNAME##Heapify (DE_PTR_TYPE(TYPENAME) arr)       \
 263 {       \
 264         int startNdx = (TYPENAME##_getNumElements(arr) - 2) / 2;        \
 265         \
 266         while (startNdx >= 0)   \
 267         {       \
 268                 TYPENAME##_##SORTNAME##ShiftDown(arr, startNdx, TYPENAME##_getNumElements(arr) - 1);    \
 269                 startNdx -= 1;  \
 270         }       \
 271 }       \
 272 \
 273 DE_INLINE void TYPENAME##_##SORTNAME (DE_PTR_TYPE(TYPENAME) arr)        \
 274 {       \
 275         int endNdx = TYPENAME##_getNumElements(arr) - 1;        \
 276         \
 277         TYPENAME##_##SORTNAME##Heapify(arr);    \
 278         \
 279         while (endNdx > 0)      \
 280         {       \
 281                 TYPENAME##_swap(arr, endNdx, 0);        \
 282                 endNdx -= 1;    \
 283                 TYPENAME##_##SORTNAME##ShiftDown(arr, 0, endNdx);       \
 284         }       \
 285 }       \
 286 \
 287 struct TYPENAME##SORTNAME##Dummy_s { int dummy; }
 288
 289 /* Basic array types. */
 290
 291 DE_DECLARE_POOL_ARRAY(deIntArray, int);
 292 DE_DECLARE_POOL_ARRAY(deInt8Array, deInt8);
 293 DE_DECLARE_POOL_ARRAY(deUint8Array, deUint8);
 294 DE_DECLARE_POOL_ARRAY(deInt16Array, deInt16);
 295 DE_DECLARE_POOL_ARRAY(deUint16Array, deUint16);
 296 DE_DECLARE_POOL_ARRAY(deInt32Array, deInt32);
 297 DE_DECLARE_POOL_ARRAY(deUint32Array, deUint32);
 298
 299 #endif /* _DEPOOLARRAY_H */