/*****************************************************************************/
/* */
-/* coll.c */
+/* coll.c */
/* */
-/* Collection (dynamic array) */
+/* Collection (dynamic array) */
/* */
/* */
/* */
-/* (C) 2000-2001 Ullrich von Bassewitz */
-/* Wacholderweg 14 */
-/* D-70597 Stuttgart */
-/* EMail: uz@cc65.org */
+/* (C) 2000-2011, Ullrich von Bassewitz */
+/* Roemerstrasse 52 */
+/* D-70794 Filderstadt */
+/* EMail: uz@cc65.org */
/* */
/* */
/* This software is provided 'as-is', without any expressed or implied */
/*****************************************************************************/
-/* Data */
+/* Data */
/*****************************************************************************/
/*****************************************************************************/
-/* Code */
+/* Code */
/*****************************************************************************/
void DoneCollection (Collection* C)
/* Free the data for a collection. This will not free the data contained in
- * the collection.
- */
+** the collection.
+*/
{
/* Free the pointer array */
xfree (C->Items);
+void CollGrow (Collection* C, unsigned Size)
+/* Grow the collection C so it is able to hold Size items without a resize
+** being necessary. This can be called for performance reasons if the number
+** of items to be placed in the collection is known in advance.
+*/
+{
+ void** NewItems;
+
+ /* Ignore the call if the collection is already large enough */
+ if (Size <= C->Size) {
+ return;
+ }
+
+ /* Grow the collection */
+ C->Size = Size;
+ NewItems = xmalloc (C->Size * sizeof (void*));
+ memcpy (NewItems, C->Items, C->Count * sizeof (void*));
+ xfree (C->Items);
+ C->Items = NewItems;
+}
+
+
+
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 */
- 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;
+ /* Must grow */
+ CollGrow (C, (C->Size == 0)? 4 : C->Size * 2);
}
/* 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 (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)
+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.
- */
+** 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;
- }
+ if (Item == C->Items[I]) {
+ /* Found */
+ return (int)I;
+ }
}
/* Not found */
void CollDelete (Collection* C, unsigned Index)
/* Remove the item with the given index from the collection. This will not
- * free the item itself, just the pointer. All items with higher indices
- * will get moved to a lower position.
- */
+** free the item itself, just the pointer. All items with higher indices
+** will get moved to a lower position.
+*/
{
/* Check the index */
PRECONDITION (Index < C->Count);
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.
- */
+** collection, otherwise FAIL will be called.
+*/
{
/* Get the index of the entry */
int Index = CollIndex (C, Item);
+#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 get replaced.
+*/
+{
+ /* Check the index */
+ PRECONDITION (Index < C->Count);
+
+ /* Replace the item pointer */
+ C->Items[Index] = Item;
+}
+#endif
+
+
+
+void CollReplaceExpand (Collection* C, void* Item, unsigned Index)
+/* If Index is a valid index for the collection, replace the item at this
+** position by the one passed. If the collection is too small, expand it,
+** filling unused pointers with NULL, then add the new item at the given
+** position.
+*/
+{
+ if (Index < C->Count) {
+ /* Collection is already large enough */
+ C->Items[Index] = Item;
+ } else {
+ /* Must expand the collection */
+ unsigned Size = C->Size;
+ if (Size == 0) {
+ Size = 4;
+ }
+ while (Index >= Size) {
+ Size *= 2;
+ }
+ CollGrow (C, Size);
+
+ /* Fill up unused slots with NULL */
+ while (C->Count < Index) {
+ C->Items[C->Count++] = 0;
+ }
+
+ /* Fill in the item */
+ C->Items[C->Count++] = Item;
+ }
+}
+
+
+
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.
- */
+** is the current position of the item, NewIndex is the new index before
+** the function has done it's work. Existing entries with indices NewIndex
+** and up might be moved one position upwards.
+*/
{
- /* Get the item and remove it from the collection */
+ /* 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;
+ if (NewIndex > OldIndex) {
+ /* Position has changed with removal */
+ --NewIndex;
}
- /* Now insert it at the new position */
+ /* 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.
- */
+** 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 for trivial parameters */
if (Count == 0 || Start == Target) {
- return;
+ return;
}
/* Calculate the raw memory space used by the items to move */
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.
- */
+ ** 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);
+ /* 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");
+ /* 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);
+ /* 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;
+ /* Adjust the target index */
+ Target -= Count;
}
/* Move the old items to their final location */
static void QuickSort (Collection* C, int Lo, int Hi,
- int (*Compare) (void*, const void*, const void*),
- void* Data)
+ int (*Compare) (void*, const void*, const void*),
+ void* Data)
/* Internal recursive sort function. */
{
/* Get a pointer to the 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;
- }
+ 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 CollTransfer (Collection* Dest, const Collection* Source)
+/* Transfer all items from Source to Dest. Anything already in Dest is left
+** untouched. The items in Source are not changed and are therefore in both
+** Collections on return.
+*/
+{
+ /* Be sure there's enough room in Dest */
+ CollGrow (Dest, Dest->Count + Source->Count);
+
+ /* Copy the items */
+ memcpy (Dest->Items + Dest->Count,
+ Source->Items,
+ Source->Count * sizeof (Source->Items[0]));
+
+ /* Bump the counter */
+ Dest->Count += Source->Count;
+}
+
+
+
void CollSort (Collection* C,
- int (*Compare) (void*, const void*, const void*),
- void* Data)
+ 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.
- */
+** 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);
+ QuickSort (C, 0, C->Count-1, Compare, Data);
}
}
-
-
-
projects / cc65 / blobdiff