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 bool dePoolArray_reserve(dePoolArray *arr, int capacity); 54 bool 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 * bool Array_reserve (Array* array, int size); 83 * bool Array_setSize (Array* array, int size); 84 * void Array_reset (Array* array); 85 * Element Array_get (Array* array, int ndx); 86 * bool Array_set (Array* array, int ndx, Element elem); 87 * bool 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 bool TYPENAME##_reserve(DE_PTR_TYPE(TYPENAME) arr, int capacity) DE_UNUSED_FUNCTION; \ 109 DE_INLINE bool 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 bool 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 bool 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 bool TYPENAME##_reserve(DE_PTR_TYPE(TYPENAME) arr, int capacity) \ 129 { \ 130 if (capacity > arr->capacity) \ 131 return dePoolArray_reserve((dePoolArray *)arr, capacity); \ 132 return true; \ 133 } \ 134 \ 135 DE_INLINE bool 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 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 bool 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 false; \ 173 arr->numElements++; \ 174 TYPENAME##_set(arr, arr->numElements - 1, elem); \ 175 return 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 bool 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 false; \ 197 for (ndx = 0; ndx < numElements; ndx++) \ 198 TYPENAME##_set(dst, ndx, TYPENAME##_get(src, ndx)); \ 199 } \ 200 return 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##Unused_s \ 211 { \ 212 int unused; \ 213 } 214 215 /*--------------------------------------------------------------------*//*! 216 * \brief Declare a sort function for an array. 217 * \param TYPENAME Type name of the declared array. 218 * \param VALUETYPE Type of the value contained in the array. 219 * \param SORTNAME Name for this specific sort. 220 * \param CMPFUNC Comparison function for sorting. 221 * 222 * This macro declares a sort function for an array declared using 223 * DE_DECLARE_POOL_ARRAY macro. 224 * 225 * Sorting algorithm is heap sort since it requires constant amount of 226 * auxiliary space and is in-place sort. Worst-case run-time is O(n log n) 227 * and sort is NOT stable. 228 * 229 * CMPFUNC is used to compare elements in array. It must accept two 230 * parameters and return negative integer if first is smaller than, 0 if 231 * both are equal and positive integer if first is larger than second. 232 * 233 * The functions for sorting array are: 234 * \todo [petri] Figure out how to comment these in Doxygen-style. 235 * 236 * \code 237 * void Array_sortName (Array* array); 238 * void Array_sortNameHeapify (Array* array); 239 * void Array_sortNameShiftDown (Array* array, int start, int end); 240 * \endcode 241 *//*--------------------------------------------------------------------*/ 242 #define DE_DECLARE_POOL_ARRAY_SORT(TYPENAME, VALUETYPE, SORTNAME, CMPFUNC) \ 243 \ 244 DE_INLINE void TYPENAME##_##SORTNAME##ShiftDown(DE_PTR_TYPE(TYPENAME) arr, int startNdx, int endNdx) \ 245 { \ 246 int rootNdx = startNdx; \ 247 \ 248 while (rootNdx * 2 + 1 <= endNdx) \ 249 { \ 250 int childNdx = rootNdx * 2 + 1; \ 251 \ 252 if ((childNdx + 1 <= endNdx) && \ 253 (CMPFUNC(TYPENAME##_get(arr, childNdx), TYPENAME##_get(arr, childNdx + 1)) < 0)) \ 254 childNdx += 1; \ 255 \ 256 if (CMPFUNC(TYPENAME##_get(arr, rootNdx), TYPENAME##_get(arr, childNdx)) < 0) \ 257 { \ 258 TYPENAME##_swap(arr, rootNdx, childNdx); \ 259 rootNdx = childNdx; \ 260 } \ 261 else \ 262 break; \ 263 } \ 264 } \ 265 \ 266 DE_INLINE void TYPENAME##_##SORTNAME##Heapify(DE_PTR_TYPE(TYPENAME) arr) \ 267 { \ 268 int startNdx = (TYPENAME##_getNumElements(arr) - 2) / 2; \ 269 \ 270 while (startNdx >= 0) \ 271 { \ 272 TYPENAME##_##SORTNAME##ShiftDown(arr, startNdx, TYPENAME##_getNumElements(arr) - 1); \ 273 startNdx -= 1; \ 274 } \ 275 } \ 276 \ 277 DE_INLINE void TYPENAME##_##SORTNAME(DE_PTR_TYPE(TYPENAME) arr) \ 278 { \ 279 int endNdx = TYPENAME##_getNumElements(arr) - 1; \ 280 \ 281 TYPENAME##_##SORTNAME##Heapify(arr); \ 282 \ 283 while (endNdx > 0) \ 284 { \ 285 TYPENAME##_swap(arr, endNdx, 0); \ 286 endNdx -= 1; \ 287 TYPENAME##_##SORTNAME##ShiftDown(arr, 0, endNdx); \ 288 } \ 289 } \ 290 \ 291 struct TYPENAME##SORTNAME##unused_s \ 292 { \ 293 int unused; \ 294 } 295 296 /* Basic array types. */ 297 298 DE_DECLARE_POOL_ARRAY(deIntArray, int); 299 DE_DECLARE_POOL_ARRAY(deInt8Array, int8_t); 300 DE_DECLARE_POOL_ARRAY(deUint8Array, uint8_t); 301 DE_DECLARE_POOL_ARRAY(deInt16Array, int16_t); 302 DE_DECLARE_POOL_ARRAY(deUint16Array, uint16_t); 303 DE_DECLARE_POOL_ARRAY(deInt32Array, int32_t); 304 DE_DECLARE_POOL_ARRAY(deUint32Array, uint32_t); 305 306 #endif /* _DEPOOLARRAY_H */ 307