--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/m3g/m3gcore11/src/m3g_array.c Tue Feb 02 01:47:50 2010 +0200
@@ -0,0 +1,293 @@
+/*
+* 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
+