/*

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

 * All rights reserved.

 * This component and the accompanying materials are made available

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

 * which accompanies this distribution, and is available

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

 *

 * Initial Contributors:

 * Nokia Corporation - initial contribution.

 *

 * Contributors:

 *

 * Description: Dynamic pointer array implementation

 *

 */

 /*!

  * \internal

  * \file

  * \brief Dynamic pointer array implementation

  *

  */

 #ifndef M3G_CORE_INCLUDE

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

 #endif

 #include "m3g_array.h"

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

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

 #define MIN_CAPACITY 8  /* 32 bytes */

 #define MAX_GROWTH 1024 /* 4 KB */

 M3G_CT_ASSERT(MIN_CAPACITY < MAX_GROWTH);

 /*----------------------------------------------------------------------

  * Private functions

  *--------------------------------------------------------------------*/

 /*!

  * \internal

  * \brief Resizes an array to the given size

  */

 static M3Gbool m3gReallocateArray(PointerArray *array,

                                   M3Gsizei newCapacity,

                                   Interface *m3g)

 {

     void **newItems;

     M3G_VALIDATE_INTERFACE(m3g);

     /* Allocate the new data block */

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

     if (newItems == NULL) {

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

     }

     /* Copy array contents */

     if (array->items != NULL) {

         int i;

         M3G_ASSERT(array->size <= newCapacity);

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

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

         }

         m3gFree(m3g, array->items);

     }

     array->capacity = newCapacity;

     array->items = newItems;

     return M3G_TRUE;

 }

 /*!

  * \internal

  * \brief Increases the capacity of the array

  *

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

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

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

  * recycling of memory blocks.

  */

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

 {

     M3Gsizei capacity = array->capacity;

     M3Gsizei newCapacity;

     /* Calculate the new capacity for the array */

     if (capacity >= MIN_CAPACITY) {

         if (capacity < MAX_GROWTH) {

             newCapacity = MIN_CAPACITY << 1;

             while (newCapacity <= capacity) {

                 newCapacity <<= 1;

             }

         }

         else {

             newCapacity = capacity + MAX_GROWTH;

         }

     }

     else {

         newCapacity = MIN_CAPACITY;

     }

     /* Reallocate the array to the new capacity */

     return m3gReallocateArray(array, newCapacity, m3g);

 }

 /*----------------------------------------------------------------------

  * M3G internal functions

  *--------------------------------------------------------------------*/

 /*!

  * \internal

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

  *

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

  * interface \c m3g.

  */

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

 {

     M3G_VALIDATE_PTR(array);

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

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

         if (!m3gGrowArray(array, m3g)) {

             return -1;

         }

     }

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

     return (array->size++);

 }

 /*!

  * \internal

  * \brief Deletes an element in the array

  *

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

  * size of the array decremented by one.

  */

 static void m3gArrayDelete(PointerArray *array, M3Gint idx)

 {

     int i, n;

     M3G_VALIDATE_PTR(array);

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

     n = --array->size;

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

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

     }

     M3G_ASSERT(array->size >= 0);

 }

 /*!

  * \internal

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

  *

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

  */

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

 {

     int i;

     M3G_VALIDATE_PTR(array);

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

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

             return i;

         }

     }

     return -1;

 }

 /*!

  * \internal

  * \brief Inserts an element into the array

  *

  * All subsequent elements move forward by one index.

  */

 static M3Gint m3gArrayInsert(PointerArray *array,

                              M3Gint idx,

                              void *item,

                              Interface *m3g)

 {

     int i;

     M3G_VALIDATE_PTR(array);

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

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

         if (!m3gGrowArray(array, m3g)) {

             return -1;

         }

     }

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

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

     }

     array->items[idx] = item;

     return idx;

 }

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

 /*!

  * \internal

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

  *

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

  */

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

 {

     M3Gint idx = m3gArrayFind(array, item);

     if (idx >= 0) {

         m3gArrayDelete(array, idx);

         return M3G_TRUE;

     }

     return M3G_FALSE;

 }

 #endif

 /*!

  * \internal

  * \brief Clears all array elements

  *

  * Does not affect the capacity of the array

  */

 static void m3gClearArray(PointerArray *array)

 {

     M3G_VALIDATE_PTR(array);

     array->size = 0;

 }

 /*!

  * \internal

  * \brief Destroys the array, freeing any resources allocated

  */

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

 {

     M3G_VALIDATE_PTR(array);

     m3gFree(m3g, array->items);

     array->items = NULL;

 }

 /*!

  * \internal

  * \brief Initializes an array prior to its first use

  *

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

  * zero

  */

 static void m3gInitArray(PointerArray *array)

 {

     M3G_VALIDATE_PTR(array);

     m3gZero(array, sizeof(PointerArray));

 }

 /*!

  * \internal

  * \brief Ensures that the array has a specified capacity

  */

 static M3Gbool m3gEnsureArrayCapacity(PointerArray *array,

                                       M3Gsizei capacity,

                                       Interface *m3g)

 {

     M3G_VALIDATE_PTR(array);    

     if (array->capacity < capacity) {

         return m3gReallocateArray(array, capacity, m3g);

     }

     return M3G_TRUE;

 }

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

 /*!

  * \internal

  * \brief Minimizes the memory usage of the array

  */

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

 {

     M3G_VALIDATE_PTR(array);

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

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

 }

 #endif

 #undef MIN_CAPACITY

 #undef MAX_GROWTH