1 /*

     2 * Copyright (c) 2003 Nokia Corporation and/or its subsidiary(-ies).

     3 * All rights reserved.

     4 * This component and the accompanying materials are made available

     5 * under the terms of the License "Eclipse Public License v1.0"

     6 * which accompanies this distribution, and is available

     7 * at the URL "http://www.eclipse.org/legal/epl-v10.html".

     8 *

     9 * Initial Contributors:

    10 * Nokia Corporation - initial contribution.

    11 *

    12 * Contributors:

    13 *

    14 * Description: Dynamic pointer array implementation

    15 *

    16 */

    17 

    18 

    19 /*!

    20  * \internal

    21  * \file

    22  * \brief Dynamic pointer array implementation

    23  *

    24  */

    25 

    26 #ifndef M3G_CORE_INCLUDE

    27 #   error included by m3g_core.c; do not compile separately.

    28 #endif

    29 

    30 #include "m3g_array.h"

    31 

    32 

    33 /* Define a minimum (default) capacity and a maximum amount of growth

    34  * for the array, to try and keep memory usage reasonable */

    35 

    36 #define MIN_CAPACITY 8  /* 32 bytes */

    37 #define MAX_GROWTH 1024 /* 4 KB */

    38 

    39 M3G_CT_ASSERT(MIN_CAPACITY < MAX_GROWTH);

    40 

    41 /*----------------------------------------------------------------------

    42  * Private functions

    43  *--------------------------------------------------------------------*/

    44 

    45 /*!

    46  * \internal

    47  * \brief Resizes an array to the given size

    48  */

    49 static M3Gbool m3gReallocateArray(PointerArray *array,

    50                                   M3Gsizei newCapacity,

    51                                   Interface *m3g)

    52 {

    53     void **newItems;

    54     M3G_VALIDATE_INTERFACE(m3g);

    55     

    56     /* Allocate the new data block */

    57     

    58     newItems = m3gAlloc(m3g, (M3Gsize) newCapacity * sizeof(void*));

    59     if (newItems == NULL) {

    60         return M3G_FALSE; /* automatic out of memory raised by m3gAlloc */

    61     }

    62 

    63     /* Copy array contents */

    64     

    65     if (array->items != NULL) {

    66         int i;

    67         M3G_ASSERT(array->size <= newCapacity);

    68         

    69         for (i = 0; i < array->size; ++i) {

    70             newItems[i] = array->items[i];

    71         }

    72         m3gFree(m3g, array->items);

    73     }

    74 

    75     array->capacity = newCapacity;

    76     array->items = newItems;

    77     return M3G_TRUE;

    78 }

    79 

    80 /*!

    81  * \internal

    82  * \brief Increases the capacity of the array

    83  *

    84  * Array growth is limited by the \c MAX_GROWTH constant, to avoid

    85  * blowing memory management for very large arrays. Small arrays are

    86  * always grown to the next power of two, to allow for easier

    87  * recycling of memory blocks.

    88  */

    89 static M3Gbool m3gGrowArray(PointerArray *array, Interface *m3g)

    90 {

    91     M3Gsizei capacity = array->capacity;

    92     M3Gsizei newCapacity;

    93 

    94     /* Calculate the new capacity for the array */

    95 

    96     if (capacity >= MIN_CAPACITY) {

    97         if (capacity < MAX_GROWTH) {

    98             newCapacity = MIN_CAPACITY << 1;

    99             while (newCapacity <= capacity) {

   100                 newCapacity <<= 1;

   101             }

   102         }

   103         else {

   104             newCapacity = capacity + MAX_GROWTH;

   105         }

   106     }

   107     else {

   108         newCapacity = MIN_CAPACITY;

   109     }

   110 

   111     /* Reallocate the array to the new capacity */

   112 

   113     return m3gReallocateArray(array, newCapacity, m3g);

   114 }

   115 

   116 /*----------------------------------------------------------------------

   117  * M3G internal functions

   118  *--------------------------------------------------------------------*/

   119 

   120 /*!

   121  * \internal

   122  * \brief Appends a new item to the end of the array

   123  *

   124  * Grows the array if necessary, by allocating new data from the

   125  * interface \c m3g.

   126  */

   127 static M3Gint m3gArrayAppend(PointerArray *array, void *item, Interface *m3g)

   128 {

   129     M3G_VALIDATE_PTR(array);

   130     M3G_ASSERT(array->size <= array->capacity);

   131     if (array->size == array->capacity) {

   132         if (!m3gGrowArray(array, m3g)) {

   133             return -1;

   134         }

   135     }

   136     array->items[array->size] = item;

   137     return (array->size++);

   138 }

   139 

   140 /*!

   141  * \internal

   142  * \brief Deletes an element in the array

   143  *

   144  * All subsequent elements will move back to fill the gap, and the

   145  * size of the array decremented by one.

   146  */

   147 static void m3gArrayDelete(PointerArray *array, M3Gint idx)

   148 {

   149     int i, n;

   150     M3G_VALIDATE_PTR(array);

   151     M3G_ASSERT(idx >= 0 && idx < array->size);

   152 

   153     n = --array->size;

   154     for (i = idx; i < n; ++i) {

   155         array->items[i] = array->items[i+1];

   156     }

   157 

   158     M3G_ASSERT(array->size >= 0);

   159 }

   160 

   161 /*!

   162  * \internal

   163  * \brief Finds the first occurrence of an item in the array

   164  *

   165  * \return index of \c item, or -1 if not found

   166  */

   167 static M3Gint m3gArrayFind(const PointerArray *array, void *item)

   168 {

   169     int i;

   170     M3G_VALIDATE_PTR(array);

   171 

   172     for (i = 0; i < array->size; ++i) {

   173         if (array->items[i] == item) {

   174             return i;

   175         }

   176     }

   177     return -1;

   178 }

   179 

   180 /*!

   181  * \internal

   182  * \brief Inserts an element into the array

   183  *

   184  * All subsequent elements move forward by one index.

   185  */

   186 static M3Gint m3gArrayInsert(PointerArray *array,

   187                              M3Gint idx,

   188                              void *item,

   189                              Interface *m3g)

   190 {

   191     int i;

   192     M3G_VALIDATE_PTR(array);

   193     M3G_ASSERT(idx >= 0 && idx <= array->size);

   194     

   195     if (array->size == array->capacity) {

   196         if (!m3gGrowArray(array, m3g)) {

   197             return -1;

   198         }

   199     }

   200 

   201     for (i = array->size++; i > idx; --i) {

   202         array->items[i] = array->items[i-1];

   203     }

   204     array->items[idx] = item;

   205     return idx;

   206 }

   207 

   208 #if 0 /* currently unused, but available here */

   209 /*!

   210  * \internal

   211  * \brief Removes the first instance of an item from the array

   212  *

   213  * \return true if \c item found, false otherwise

   214  */

   215 static M3Gbool m3gArrayRemove(PointerArray *array, void *item)

   216 {

   217     M3Gint idx = m3gArrayFind(array, item);

   218     if (idx >= 0) {

   219         m3gArrayDelete(array, idx);

   220         return M3G_TRUE;

   221     }

   222     return M3G_FALSE;

   223 }

   224 #endif

   225 

   226 /*!

   227  * \internal

   228  * \brief Clears all array elements

   229  *

   230  * Does not affect the capacity of the array

   231  */

   232 static void m3gClearArray(PointerArray *array)

   233 {

   234     M3G_VALIDATE_PTR(array);

   235     array->size = 0;

   236 }

   237 

   238 /*!

   239  * \internal

   240  * \brief Destroys the array, freeing any resources allocated

   241  */

   242 static void m3gDestroyArray(PointerArray *array, Interface *m3g)

   243 {

   244     M3G_VALIDATE_PTR(array);

   245     m3gFree(m3g, array->items);

   246     array->items = NULL;

   247 }

   248 

   249 /*!

   250  * \internal

   251  * \brief Initializes an array prior to its first use

   252  *

   253  * \note This is also accomplished by clearing the array structure to

   254  * zero

   255  */

   256 static void m3gInitArray(PointerArray *array)

   257 {

   258     M3G_VALIDATE_PTR(array);

   259     m3gZero(array, sizeof(PointerArray));

   260 }

   261 

   262 /*!

   263  * \internal

   264  * \brief Ensures that the array has a specified capacity

   265  */

   266 static M3Gbool m3gEnsureArrayCapacity(PointerArray *array,

   267                                       M3Gsizei capacity,

   268                                       Interface *m3g)

   269 {

   270     M3G_VALIDATE_PTR(array);    

   271     if (array->capacity < capacity) {

   272         return m3gReallocateArray(array, capacity, m3g);

   273     }

   274     return M3G_TRUE;

   275 }

   276 

   277 #if 0 /* currently unused, but available here */

   278 /*!

   279  * \internal

   280  * \brief Minimizes the memory usage of the array

   281  */

   282 static M3Gbool m3gTrimArray(PointerArray *array, Interface *m3g)

   283 {

   284     M3G_VALIDATE_PTR(array);

   285     M3G_ASSERT(array->size <= array->capacity);

   286     return m3gReallocateArray(array, array->size, m3g);

   287 }

   288 #endif

   289 

   290 

   291 #undef MIN_CAPACITY

   292 #undef MAX_GROWTH

   293