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 VALUETYPE** pageTable; \ 104 } 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 (TYPENAME* arr, int capacity) DE_UNUSED_FUNCTION; \ 109 DE_INLINE deBool TYPENAME##_setSize (TYPENAME* arr, int size) DE_UNUSED_FUNCTION; \ 110 DE_INLINE void TYPENAME##_reset (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 (TYPENAME* arr, int ndx, VALUETYPE elem) DE_UNUSED_FUNCTION; \ 113 DE_INLINE deBool TYPENAME##_pushBack (TYPENAME* arr, VALUETYPE elem) DE_UNUSED_FUNCTION; \ 114 DE_INLINE VALUETYPE TYPENAME##_popBack (TYPENAME* arr) DE_UNUSED_FUNCTION; \ 115 DE_INLINE deBool TYPENAME##_copy (TYPENAME* dst, const TYPENAME* src) DE_UNUSED_FUNCTION; \ 116 DE_INLINE void TYPENAME##_swap (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 (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 (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 (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 (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 (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 (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 (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 (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 (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 (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 (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 */ 300