cc65/src/common/coll.c

/*****************************************************************************/
/*                                                                           */
/*                                  coll.c                                   */
/*                                                                           */
/*                        Collection (dynamic array)                         */
/*                                                                           */
/*                                                                           */
/*                                                                           */
/* (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       */
/* warranty.  In no event will the authors be held liable for any damages    */
/* arising from the use of this software.                                    */
/*                                                                           */
/* Permission is granted to anyone to use this software for any purpose,     */
/* including commercial applications, and to alter it and redistribute it    */
/* freely, subject to the following restrictions:                            */
/*                                                                           */
/* 1. The origin of this software must not be misrepresented; you must not   */
/*    claim that you wrote the original software. If you use this software   */
/*    in a product, an acknowledgment in the product documentation would be  */
/*    appreciated but is not required.                                       */
/* 2. Altered source versions must be plainly marked as such, and must not   */
/*    be misrepresented as being the original software.                      */
/* 3. This notice may not be removed or altered from any source              */
/*    distribution.                                                          */
/*                                                                           */
/*****************************************************************************/



#include <stdlib.h>
#include <string.h>

/* common */
#include "check.h"
#include "xmalloc.h"

/* cc65 */
#include "coll.h"



/*****************************************************************************/
/*                                   Data                                    */
/*****************************************************************************/



/* An empty collection */
const Collection EmptyCollection = STATIC_COLLECTION_INITIALIZER;



/*****************************************************************************/
/*                                   Code                                    */
/*****************************************************************************/



Collection* InitCollection (Collection* C)
/* Initialize a collection and return it. */
{
    /* Intialize the fields. */
    C->Count = 0;
    C->Size  = 0;
    C->Items = 0;

    /* Return the new struct */
    return C;
}



void DoneCollection (Collection* C)
/* Free the data for a collection. This will not free the data contained in
** the collection.
*/
{
    /* Free the pointer array */
    xfree (C->Items);
}



Collection* NewCollection (void)
/* Create and return a new collection with the given initial size */
{
    /* Allocate memory, intialize the collection and return it */
    return InitCollection (xmalloc (sizeof (Collection)));
}



void FreeCollection (Collection* C)
/* Free a collection */
{
    /* Free the data */
    DoneCollection (C);

    /* Free the structure itself */
    xfree (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 */
{
    /* Check for invalid indices */
    PRECONDITION (Index <= C->Count);

    /* Grow the array if necessary */
    if (C->Count >= C->Size) {
        /* 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*));
    }
    ++C->Count;

    /* Store the new item */
    C->Items[Index] = Item;
}



#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.
*/
{
    /* 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 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.
*/
{
    /* Check the index */
    PRECONDITION (Index < C->Count);

    /* Remove the item pointer */
    --C->Count;
    memmove (C->Items+Index, C->Items+Index+1, (C->Count-Index) * sizeof (void*));
}



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 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 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 */
    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);
    }
}