1 /*------------------------------------------------------------------------- 2 * drawElements Memory Pool Library 3 * -------------------------------- 4 * 5 * Copyright 2014 The Android Open Source Project 6 * 7 * Licensed under the Apache License, Version 2.0 (the "License"); 8 * you may not use this file except in compliance with the License. 9 * You may obtain a copy of the License at 10 * 11 * http://www.apache.org/licenses/LICENSE-2.0 12 * 13 * Unless required by applicable law or agreed to in writing, software 14 * distributed under the License is distributed on an "AS IS" BASIS, 15 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 16 * See the License for the specific language governing permissions and 17 * limitations under the License. 18 * 19 *//*! 20 * \file 21 * \brief Memory pool array class. 22 * 23 * Features of the pooled arrays: 24 * - single indirection layer (grows exponentially) 25 * - constant # elements per page 26 * - recycles old indirection tables as element pages 27 * - about 10% overhead on large arrays 28 *//*--------------------------------------------------------------------*/ 29 30 #include "dePoolArray.h" 31 #include "deInt32.h" 32 33 #include <stdlib.h> 34 #include <string.h> 35 36 /*--------------------------------------------------------------------*//*! 37 * \internal 38 * \brief Create a new pool array. 39 * \param pool Pool to allocate memory from. 40 * \param elementSize Size of the element to be put in array. 41 * \param Pointer to the created array, or null on failure. 42 *//*--------------------------------------------------------------------*/ dePoolArray_create(deMemPool * pool,int elementSize)43 dePoolArray* dePoolArray_create (deMemPool* pool, int elementSize) 44 { 45 /* Alloc struct. */ 46 dePoolArray* arr = DE_POOL_NEW(pool, dePoolArray); 47 if (!arr) 48 return DE_NULL; 49 50 /* Init array. */ 51 memset(arr, 0, sizeof(dePoolArray)); 52 arr->pool = pool; 53 arr->elementSize = elementSize; 54 55 return arr; 56 } 57 58 /*--------------------------------------------------------------------*//*! 59 * \internal 60 * \brief Ensure that the array can hold at least N elements. 61 * \param arr Array pointer. 62 * \param size Number of elements for which to reserve memory. 63 * \param True on success, false on failure. 64 *//*--------------------------------------------------------------------*/ dePoolArray_reserve(dePoolArray * arr,int size)65 deBool dePoolArray_reserve (dePoolArray* arr, int size) 66 { 67 if (size >= arr->capacity) 68 { 69 void* oldPageTable = DE_NULL; 70 int oldPageTableSize = 0; 71 72 int newCapacity = deAlign32(size, 1 << DE_ARRAY_ELEMENTS_PER_PAGE_LOG2); 73 int reqPageTableCapacity = newCapacity >> DE_ARRAY_ELEMENTS_PER_PAGE_LOG2; 74 75 if (arr->pageTableCapacity < reqPageTableCapacity) 76 { 77 int newPageTableCapacity = deMax32(2*arr->pageTableCapacity, reqPageTableCapacity); 78 void** newPageTable = (void**)deMemPool_alloc(arr->pool, (size_t)newPageTableCapacity * sizeof(void*)); 79 int i; 80 81 if (!newPageTable) 82 return DE_FALSE; 83 84 for (i = 0; i < arr->pageTableCapacity; i++) 85 newPageTable[i] = arr->pageTable[i]; 86 87 for (; i < newPageTableCapacity; i++) 88 newPageTable[i] = DE_NULL; 89 90 /* Grab information about old page table for recycling purposes. */ 91 oldPageTable = arr->pageTable; 92 oldPageTableSize = arr->pageTableCapacity * (int)sizeof(void*); 93 94 arr->pageTable = newPageTable; 95 arr->pageTableCapacity = newPageTableCapacity; 96 } 97 98 /* Allocate new pages. */ 99 { 100 int pageAllocSize = arr->elementSize << DE_ARRAY_ELEMENTS_PER_PAGE_LOG2; 101 int pageTableNdx = arr->capacity >> DE_ARRAY_ELEMENTS_PER_PAGE_LOG2; 102 103 /* Allocate new pages from recycled old page table. */ 104 while (oldPageTableSize >= pageAllocSize) 105 { 106 void* newPage = oldPageTable; 107 DE_ASSERT(arr->pageTableCapacity > pageTableNdx); /* \todo [petri] is this always true? */ 108 DE_ASSERT(!arr->pageTable[pageTableNdx]); 109 arr->pageTable[pageTableNdx++] = newPage; 110 111 oldPageTable = (void*)((deUint8*)oldPageTable + pageAllocSize); 112 oldPageTableSize -= pageAllocSize; 113 } 114 115 /* Allocate the rest of the needed pages from the pool. */ 116 for (; pageTableNdx < reqPageTableCapacity; pageTableNdx++) 117 { 118 void* newPage = deMemPool_alloc(arr->pool, (size_t)pageAllocSize); 119 if (!newPage) 120 return DE_FALSE; 121 122 DE_ASSERT(!arr->pageTable[pageTableNdx]); 123 arr->pageTable[pageTableNdx] = newPage; 124 } 125 126 arr->capacity = pageTableNdx << DE_ARRAY_ELEMENTS_PER_PAGE_LOG2; 127 DE_ASSERT(arr->capacity >= newCapacity); 128 } 129 } 130 131 return DE_TRUE; 132 } 133 134 /*--------------------------------------------------------------------*//*! 135 * \internal 136 * \brief Set the size of the array (also reserves capacity). 137 * \param arr Array pointer. 138 * \param size New size of the array (in elements). 139 * \param True on success, false on failure. 140 *//*--------------------------------------------------------------------*/ dePoolArray_setSize(dePoolArray * arr,int size)141 deBool dePoolArray_setSize (dePoolArray* arr, int size) 142 { 143 if (!dePoolArray_reserve(arr, size)) 144 return DE_FALSE; 145 146 arr->numElements = size; 147 return DE_TRUE; 148 } 149 150 DE_DECLARE_POOL_ARRAY(dePoolIntArray, int); 151 DE_DECLARE_POOL_ARRAY(dePoolInt16Array, deInt16); 152 153 /*--------------------------------------------------------------------*//*! 154 * \internal 155 * \brief Test array functionality. 156 *//*--------------------------------------------------------------------*/ dePoolArray_selfTest(void)157 void dePoolArray_selfTest (void) 158 { 159 deMemPool* pool = deMemPool_createRoot(DE_NULL, 0); 160 dePoolIntArray* arr = dePoolIntArray_create(pool); 161 dePoolInt16Array* arr16 = dePoolInt16Array_create(pool); 162 int i; 163 164 /* Test pushBack(). */ 165 for (i = 0; i < 5000; i++) 166 { 167 /* Dummy alloc to try to break alignments. */ 168 deMemPool_alloc(pool, 1); 169 170 dePoolIntArray_pushBack(arr, i); 171 dePoolInt16Array_pushBack(arr16, (deInt16)i); 172 } 173 174 DE_TEST_ASSERT(dePoolIntArray_getNumElements(arr) == 5000); 175 DE_TEST_ASSERT(dePoolInt16Array_getNumElements(arr16) == 5000); 176 for (i = 0; i < 5000; i++) 177 { 178 DE_TEST_ASSERT(dePoolIntArray_get(arr, i) == i); 179 DE_TEST_ASSERT(dePoolInt16Array_get(arr16, i) == i); 180 } 181 182 /* Test popBack(). */ 183 for (i = 0; i < 1000; i++) 184 { 185 DE_TEST_ASSERT(dePoolIntArray_popBack(arr) == (4999 - i)); 186 DE_TEST_ASSERT(dePoolInt16Array_popBack(arr16) == (4999 - i)); 187 } 188 189 DE_TEST_ASSERT(dePoolIntArray_getNumElements(arr) == 4000); 190 DE_TEST_ASSERT(dePoolInt16Array_getNumElements(arr16) == 4000); 191 for (i = 0; i < 4000; i++) 192 { 193 DE_TEST_ASSERT(dePoolIntArray_get(arr, i) == i); 194 DE_TEST_ASSERT(dePoolInt16Array_get(arr16, i) == i); 195 } 196 197 /* Test setSize(). */ 198 dePoolIntArray_setSize(arr, 1000); 199 dePoolInt16Array_setSize(arr16, 1000); 200 for (i = 1000; i < 5000; i++) 201 { 202 dePoolIntArray_pushBack(arr, i); 203 dePoolInt16Array_pushBack(arr16, (deInt16)i); 204 } 205 206 DE_TEST_ASSERT(dePoolIntArray_getNumElements(arr) == 5000); 207 DE_TEST_ASSERT(dePoolInt16Array_getNumElements(arr16) == 5000); 208 for (i = 0; i < 5000; i++) 209 { 210 DE_TEST_ASSERT(dePoolIntArray_get(arr, i) == i); 211 DE_TEST_ASSERT(dePoolInt16Array_get(arr16, i) == i); 212 } 213 214 /* Test set() and pushBack() with reserve(). */ 215 arr = dePoolIntArray_create(pool); 216 dePoolIntArray_setSize(arr, 1500); 217 dePoolIntArray_reserve(arr, 2000); 218 for (i = 0; i < 1500; i++) 219 dePoolIntArray_set(arr, i, i); 220 for (; i < 5000; i++) 221 dePoolIntArray_pushBack(arr, i); 222 223 DE_TEST_ASSERT(dePoolIntArray_getNumElements(arr) == 5000); 224 for (i = 0; i < 5000; i++) 225 { 226 int val = dePoolIntArray_get(arr, i); 227 DE_TEST_ASSERT(val == i); 228 } 229 230 deMemPool_destroy(pool); 231 } 232