/*
* 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