X-Git-Url: https://git.sur5r.net/?a=blobdiff_plain;f=src%2Fcommon%2Fcoll.c;h=0fa0d152e717683134d015f89c9c41097b5dcdcf;hb=74108cd74fc3ca3ad4f69b743233fa79791106b9;hp=465a65987a5d74644bd8ad58a0b23b88801eca51;hpb=87e9f7379bee3a18c3984f8e1e33520aee2e1520;p=cc65 diff --git a/src/common/coll.c b/src/common/coll.c index 465a65987..0fa0d152e 100644 --- a/src/common/coll.c +++ b/src/common/coll.c @@ -6,10 +6,10 @@ /* */ /* */ /* */ -/* (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 */ @@ -45,6 +45,17 @@ +/*****************************************************************************/ +/* Data */ +/*****************************************************************************/ + + + +/* An empty collection */ +const Collection EmptyCollection = STATIC_COLLECTION_INITIALIZER; + + + /*****************************************************************************/ /* Code */ /*****************************************************************************/ @@ -97,6 +108,29 @@ void FreeCollection (Collection* C) +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 */ { @@ -105,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; @@ -130,6 +155,89 @@ 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 + + + +#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. @@ -138,9 +246,9 @@ int CollIndex (Collection* C, const void* Item) /* 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; } } @@ -182,9 +290,144 @@ void CollDeleteItem (Collection* C, const void* 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. + */ +{ + /* 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) + int (*Compare) (void*, const void*, const void*), + void* Data) /* Internal recursive sort function. */ { /* Get a pointer to the items */ @@ -228,6 +471,26 @@ static void QuickSort (Collection* C, int Lo, int Hi, +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)