framework/delibs/depool/dePoolArray.c

   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  *//*--------------------------------------------------------------------*/
  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  *//*--------------------------------------------------------------------*/
  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  *//*--------------------------------------------------------------------*/
 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  *//*--------------------------------------------------------------------*/
 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, (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 }