X-Git-Url: https://git.sur5r.net/?a=blobdiff_plain;f=src%2Fcommon%2Fcoll.c;h=0fa0d152e717683134d015f89c9c41097b5dcdcf;hb=74108cd74fc3ca3ad4f69b743233fa79791106b9;hp=6748ff12d9763f20ad07025d424b6baccb98ec5f;hpb=ddc60c20fe7cdbdc4f5ace0510a363d5ad1c4503;p=cc65 diff --git a/src/common/coll.c b/src/common/coll.c index 6748ff12d..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@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 */ @@ -45,6 +45,17 @@ +/*****************************************************************************/ +/* Data */ +/*****************************************************************************/ + + + +/* An empty collection */ +const Collection EmptyCollection = STATIC_COLLECTION_INITIALIZER; + + + /*****************************************************************************/ /* Code */ /*****************************************************************************/ @@ -97,10 +108,25 @@ void FreeCollection (Collection* C) -unsigned CollCount (const 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; } @@ -113,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; @@ -138,16 +155,19 @@ 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 -void* CollAt (Collection* C, unsigned Index) +#if !defined(HAVE_INLINE) +void* CollAt (const Collection* C, unsigned Index) /* Return the item at the given index */ { /* Check the index */ @@ -156,9 +176,11 @@ void* CollAt (Collection* C, unsigned 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 */ { @@ -168,9 +190,11 @@ const void* CollConstAt (const 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 */ { @@ -180,9 +204,11 @@ 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 */ { @@ -192,6 +218,43 @@ const void* CollConstLast (const Collection* C) /* 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; +} @@ -211,20 +274,26 @@ void CollDelete (Collection* C, unsigned Index) -void CollDeleteAll (Collection* C) -/* Delete all items from the given collection. This will not free the items - * itself, it will only remove the pointers. - */ +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. + */ { - /* This one is easy... */ - C->Count = 0; + /* 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 */ @@ -233,12 +302,132 @@ 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) + int (*Compare) (void*, const void*, const void*), + void* Data) /* Internal recursive sort function. */ { /* Get a pointer to the items */ @@ -282,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)