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 *//*--------------------------------------------------------------------*/
43dePoolArray* 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 *//*--------------------------------------------------------------------*/
65deBool			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, 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 * 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, 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 *//*--------------------------------------------------------------------*/
141deBool			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
150DE_DECLARE_POOL_ARRAY(dePoolIntArray, int);
151DE_DECLARE_POOL_ARRAY(dePoolInt16Array, deInt16);
152
153/*--------------------------------------------------------------------*//*!
154 * \internal
155 * \brief Test array functionality.
156 *//*--------------------------------------------------------------------*/
157void 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