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 bool 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 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 *)((uint8_t *)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 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 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 bool dePoolArray_setSize(dePoolArray *arr, int size)
142 {
143 if (!dePoolArray_reserve(arr, size))
144 return false;
145
146 arr->numElements = size;
147 return true;
148 }
149
150 DE_DECLARE_POOL_ARRAY(dePoolIntArray, int);
151 DE_DECLARE_POOL_ARRAY(dePoolInt16Array, int16_t);
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 /* Unused alloc to try to break alignments. */
168 deMemPool_alloc(pool, 1);
169
170 dePoolIntArray_pushBack(arr, i);
171 dePoolInt16Array_pushBack(arr16, (int16_t)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, (int16_t)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