/* */
/* */
/* */
-/* (C) 2000 Ullrich von Bassewitz */
+/* (C) 2000-2001 Ullrich von Bassewitz */
/* Wacholderweg 14 */
/* D-70597 Stuttgart */
-/* EMail: uz@musoftware.de */
+/* EMail: uz@cc65.org */
/* */
/* */
/* This software is provided 'as-is', without any expressed or implied */
+#include <stdlib.h>
#include <string.h>
/* common */
+/*****************************************************************************/
+/* Data */
+/*****************************************************************************/
+
+
+
+/* An empty collection */
+const Collection EmptyCollection = STATIC_COLLECTION_INITIALIZER;
+
+
+
/*****************************************************************************/
/* Code */
/*****************************************************************************/
{
/* Intialize the fields. */
C->Count = 0;
- C->Size = 8;
- C->Items = xmalloc (8 * sizeof (void*));
+ C->Size = 0;
+ C->Items = 0;
/* Return the new struct */
return C;
-unsigned CollCount (Collection* C)
-/* Return the number of items in the collection */
-{
- return C->Count;
-}
-
-
-
void CollInsert (Collection* C, void* Item, unsigned Index)
/* Insert the data at the given position in the collection */
{
/* Grow the array if necessary */
if (C->Count >= C->Size) {
- /* Must grow */
+ /* Must grow */
void** NewItems;
- if (C->Size > 0) {
- C->Size *= 2;
- } else {
- C->Size = 8;
- }
- NewItems = xmalloc (C->Size * sizeof (void*));
- memcpy (NewItems, C->Items, C->Count * sizeof (void*));
- xfree (C->Items);
- C->Items = NewItems;
+ if (C->Size > 0) {
+ C->Size *= 2;
+ } else {
+ C->Size = 8;
+ }
+ NewItems = xmalloc (C->Size * sizeof (void*));
+ memcpy (NewItems, C->Items, C->Count * sizeof (void*));
+ xfree (C->Items);
+ C->Items = NewItems;
}
/* Move the existing elements if needed */
if (C->Count != Index) {
- memmove (C->Items+Index+1, C->Items+Index, (C->Count-Index) * sizeof (void*));
+ memmove (C->Items+Index+1, C->Items+Index, (C->Count-Index) * sizeof (void*));
}
++C->Count;
+#if !defined(HAVE_INLINE)
void CollAppend (Collection* C, void* Item)
/* Append an item to the end of the collection */
{
/* Insert the item at the end of the current list */
CollInsert (C, Item, C->Count);
}
+#endif
+#if !defined(HAVE_INLINE)
void* CollAt (Collection* C, unsigned Index)
/* Return the item at the given index */
{
/* Return the element */
return C->Items[Index];
}
+#endif
+
+
+
+#if !defined(HAVE_INLINE)
+const void* CollConstAt (const Collection* C, unsigned Index)
+/* Return the item at the given index */
+{
+ /* Check the index */
+ PRECONDITION (Index < C->Count);
+
+ /* Return the element */
+ return C->Items[Index];
+}
+#endif
+
+
+
+#if !defined(HAVE_INLINE)
+void* CollLast (Collection* C)
+/* Return the last item in a collection */
+{
+ /* We must have at least one entry */
+ PRECONDITION (C->Count > 0);
+
+ /* Return the element */
+ return C->Items[C->Count-1];
+}
+#endif
+
+
+
+#if !defined(HAVE_INLINE)
+const void* CollConstLast (const Collection* C)
+/* Return the last item in a collection */
+{
+ /* We must have at least one entry */
+ PRECONDITION (C->Count > 0);
+
+ /* Return the element */
+ return C->Items[C->Count-1];
+}
+#endif
+
+
+
+#if !defined(HAVE_INLINE)
+void* CollPop (Collection* C)
+/* Remove the last segment from the stack and return it. Calls FAIL if the
+ * collection is empty.
+ */
+{
+ /* We must have at least one entry */
+ PRECONDITION (C->Count > 0);
+
+ /* Return the element */
+ return C->Items[--C->Count];
+}
+#endif
+
+
+
+int CollIndex (Collection* C, const void* Item)
+/* Return the index of the given item in the collection. Return -1 if the
+ * item was not found in the collection.
+ */
+{
+ /* Linear search */
+ unsigned I;
+ for (I = 0; I < C->Count; ++I) {
+ if (Item == C->Items[I]) {
+ /* Found */
+ return (int)I;
+ }
+ }
+
+ /* Not found */
+ return -1;
+}
+void CollDeleteItem (Collection* C, const void* Item)
+/* Delete the item pointer from the collection. The item must be in the
+ * collection, otherwise FAIL will be called.
+ */
+{
+ /* Get the index of the entry */
+ int Index = CollIndex (C, Item);
+ CHECK (Index >= 0);
+
+ /* Delete the item with this index */
+ --C->Count;
+ memmove (C->Items+Index, C->Items+Index+1, (C->Count-Index) * sizeof (void*));
+}
+
+
+
+#if !defined(HAVE_INLINE)
void CollReplace (Collection* C, void* Item, unsigned Index)
/* Replace the item at the given position. The old item will not be freed,
- * just the pointer will et replaced.
+ * just the pointer will get replaced.
*/
{
/* Check the index */
/* Replace the item pointer */
C->Items[Index] = Item;
}
+#endif
+
+
+
+void CollMove (Collection* C, unsigned OldIndex, unsigned NewIndex)
+/* Move an item from one position in the collection to another. OldIndex
+ * is the current position of the item, NewIndex is the new index after
+ * the function has done it's work. Existing entries with indices NewIndex
+ * and up are moved one position upwards.
+ */
+{
+ /* Get the item and remove it from the collection */
+ void* Item = CollAt (C, OldIndex);
+ CollDelete (C, OldIndex);
+
+ /* Correct NewIndex if needed */
+ if (NewIndex >= OldIndex) {
+ /* Position has changed with removal */
+ --NewIndex;
+ }
+
+ /* Now insert it at the new position */
+ CollInsert (C, Item, NewIndex);
+}
+
+
+
+void CollMoveMultiple (Collection* C, unsigned Start, unsigned Count, unsigned Target)
+/* Move a range of items from one position to another. Start is the index
+ * of the first item to move, Count is the number of items and Target is
+ * the index of the target item. The item with the index Start will later
+ * have the index Target. All items with indices Target and above are moved
+ * to higher indices.
+ */
+{
+ void** TmpItems;
+ unsigned Bytes;
+
+ /* Check the range */
+ PRECONDITION (Start < C->Count && Start + Count <= C->Count && Target <= C->Count);
+
+ /* Check for trivial parameters */
+ if (Count == 0 || Start == Target) {
+ return;
+ }
+
+ /* Calculate the raw memory space used by the items to move */
+ Bytes = Count * sizeof (void*);
+ /* Allocate temporary storage for the items */
+ TmpItems = xmalloc (Bytes);
+
+ /* Copy the items we have to move to the temporary storage */
+ memcpy (TmpItems, C->Items + Start, Bytes);
+
+ /* Check if the range has to be moved upwards or downwards. Move the
+ * existing items to their final location, so that the space needed
+ * for the items now in temporary storage is unoccupied.
+ */
+ if (Target < Start) {
+
+ /* Move downwards */
+ unsigned BytesToMove = (Start - Target) * sizeof (void*);
+ memmove (C->Items+Target+Count, C->Items+Target, BytesToMove);
+
+ } else if (Target < Start + Count) {
+
+ /* Target is inside range */
+ FAIL ("Not supported");
+
+ } else {
+
+ /* Move upwards */
+ unsigned ItemsToMove = (Target - Start - Count);
+ unsigned BytesToMove = ItemsToMove * sizeof (void*);
+ memmove (C->Items+Start, C->Items+Target-ItemsToMove, BytesToMove);
+
+ /* Adjust the target index */
+ Target -= Count;
+ }
+
+ /* Move the old items to their final location */
+ memcpy (C->Items + Target, TmpItems, Bytes);
+
+ /* Delete the temporary item space */
+ xfree (TmpItems);
+}
+
+
+
+static void QuickSort (Collection* C, int Lo, int Hi,
+ int (*Compare) (void*, const void*, const void*),
+ void* Data)
+/* Internal recursive sort function. */
+{
+ /* Get a pointer to the items */
+ void** Items = C->Items;
+
+ /* Quicksort */
+ while (Hi > Lo) {
+ int I = Lo + 1;
+ int J = Hi;
+ while (I <= J) {
+ while (I <= J && Compare (Data, Items[Lo], Items[I]) >= 0) {
+ ++I;
+ }
+ while (I <= J && Compare (Data, Items[Lo], Items[J]) < 0) {
+ --J;
+ }
+ if (I <= J) {
+ /* Swap I and J */
+ void* Tmp = Items[I];
+ Items[I] = Items[J];
+ Items[J] = Tmp;
+ ++I;
+ --J;
+ }
+ }
+ if (J != Lo) {
+ /* Swap J and Lo */
+ void* Tmp = Items[J];
+ Items[J] = Items[Lo];
+ Items[Lo] = Tmp;
+ }
+ if (J > (Hi + Lo) / 2) {
+ QuickSort (C, J + 1, Hi, Compare, Data);
+ Hi = J - 1;
+ } else {
+ QuickSort (C, Lo, J - 1, Compare, Data);
+ Lo = J + 1;
+ }
+ }
+}
+
+
+
+void CollSort (Collection* C,
+ int (*Compare) (void*, const void*, const void*),
+ void* Data)
+/* Sort the collection using the given compare function. The data pointer is
+ * passed as *first* element to the compare function, it's not used by the
+ * sort function itself. The other two pointer passed to the Compare function
+ * are pointers to objects.
+ */
+{
+ if (C->Count > 1) {
+ QuickSort (C, 0, C->Count-1, Compare, Data);
+ }
+}