X-Git-Url: https://git.sur5r.net/?a=blobdiff_plain;f=src%2Fcommon%2Fcoll.c;h=0fa0d152e717683134d015f89c9c41097b5dcdcf;hb=74108cd74fc3ca3ad4f69b743233fa79791106b9;hp=0b36ca4630021520f26760b78f94383c0656fa9f;hpb=8198af9844e1e7abf36ed0a0634d79e50fbdc4f2;p=cc65 diff --git a/src/common/coll.c b/src/common/coll.c index 0b36ca463..0fa0d152e 100644 --- a/src/common/coll.c +++ b/src/common/coll.c @@ -6,10 +6,10 @@ /* */ /* */ /* */ -/* (C) 2000 Ullrich von Bassewitz */ -/* Wacholderweg 14 */ -/* D-70597 Stuttgart */ -/* EMail: uz@musoftware.de */ +/* (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 */ @@ -33,6 +33,7 @@ +#include #include /* common */ @@ -44,6 +45,17 @@ +/*****************************************************************************/ +/* Data */ +/*****************************************************************************/ + + + +/* An empty collection */ +const Collection EmptyCollection = STATIC_COLLECTION_INITIALIZER; + + + /*****************************************************************************/ /* Code */ /*****************************************************************************/ @@ -55,8 +67,8 @@ Collection* InitCollection (Collection* C) { /* 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; @@ -96,10 +108,25 @@ void FreeCollection (Collection* C) -unsigned CollCount (Collection* C) -/* Return the number of items in the collection */ +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. + */ { - return C->Count; + 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; } @@ -112,22 +139,13 @@ void CollInsert (Collection* C, void* Item, unsigned Index) /* 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; @@ -137,16 +155,33 @@ void CollInsert (Collection* C, void* Item, unsigned Index) +#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 -void* CollAt (Collection* C, unsigned Index) +#if !defined(HAVE_INLINE) +const void* CollConstAt (const Collection* C, unsigned Index) /* Return the item at the given index */ { /* Check the index */ @@ -155,9 +190,11 @@ void* CollAt (Collection* C, unsigned Index) /* Return the element */ return C->Items[Index]; } +#endif +#if !defined(HAVE_INLINE) void* CollLast (Collection* C) /* Return the last item in a collection */ { @@ -167,6 +204,57 @@ void* CollLast (Collection* C) /* 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; +} @@ -186,9 +274,26 @@ void CollDelete (Collection* C, unsigned Index) +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 */ @@ -197,7 +302,208 @@ void CollReplace (Collection* C, void* Item, unsigned Index) /* 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. + */ +{ + /* 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 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) +/* 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); + } +}