lists.c

曾仕强——中国式管理——总裁领导学

        return 0;

    if ((*list)->numItems >= (*list)->listSize)
    {
	if (!ExpandListSpace (list, -numItemsToInsert)) /* PATCH to 4.0.1 - jag 8-29-96 */
            return 0;
    }

    if (firstItemPosition == LIST_START)
    {
        if (numItems == 0)
           firstItemPosition = LIST_END; /* special case for empty list */
        else
           firstItemPosition = 1;
    }

    if (firstItemPosition == LIST_END)  /* add at the end of the list */
        {
        if (ptrToItems)
            memcpy (ITEMPTR(list, numItems), ptrToItems, (*list)->itemSize * numItemsToInsert);
        else
            memset (ITEMPTR(list, numItems), 0,
                (*list)->itemSize * numItemsToInsert);

        (*list)->numItems += numItemsToInsert;
        }
    else
        {                                  /* move part of list up to make room for new item */
        memmove (ITEMPTR(list,firstItemPosition-1+numItemsToInsert),
            ITEMPTR(list,firstItemPosition-1),
            (numItems + 1 - firstItemPosition) * (*list)->itemSize);

        if (ptrToItems)
            memmove (ITEMPTR(list,firstItemPosition-1), ptrToItems,
                (*list)->itemSize * numItemsToInsert);
        else
            memset (ITEMPTR(list,firstItemPosition-1), 0,
                (*list)->itemSize * numItemsToInsert);

        (*list)->numItems += numItemsToInsert;
        }

    return 1;
}

#ifdef	CFG_ALL_LIST_FUNCTIONS

/*******************************/

int  ListEqual (list_t list1, list_t list2)
{
    if (list1 == list2)
        return 1;

    if (list1 == NULL || list2 == NULL)
        return 0;

    if ((*list1)->itemSize == (*list1)->itemSize)
        if ((*list1)->numItems == (*list2)->numItems)
            return (memcmp (ITEMPTR(list1,0), ITEMPTR(list2,0),
                (*list1)->itemSize * (*list1)->numItems) == 0);

    return 0;
}

/*******************************/

     /* The item pointed to by ptrToItem is copied over the current item at itemPosition */
void  ListReplaceItem (list_t list, void *ptrToItem, int itemPosition)
{
    ListReplaceItems (list, ptrToItem, itemPosition, 1);
}

/*******************************/

     /* The item pointed to by ptrToItems is copied over the current item at itemPosition */
void  ListReplaceItems (list_t list, void *ptrToItems, int firstItemPosition, int numItemsToReplace)
{

    if (firstItemPosition == LIST_END)
        firstItemPosition = (*list)->numItems;
    else
    if (firstItemPosition == LIST_START)
        firstItemPosition = 1;

    memmove (ITEMPTR(list,firstItemPosition-1), ptrToItems,
        (*list)->itemSize * numItemsToReplace);
}

/*******************************/

void  ListRemoveItem (list_t list, void *itemDestination, int itemPosition)
{
    ListRemoveItems (list, itemDestination, itemPosition, 1);
}

/*******************************/

void  ListRemoveItems (list_t list, void *itemsDestination, int firstItemPosition, int numItemsToRemove)
{
    int firstItemAfterChunk, numToMove;

    if (firstItemPosition == LIST_START)
        firstItemPosition = 1;
    else
    if (firstItemPosition == LIST_END)
        firstItemPosition = (*list)->numItems;

    if (itemsDestination != NULL)
         memcpy (itemsDestination, ITEMPTR(list,firstItemPosition-1),
            (*list)->itemSize * numItemsToRemove);

    firstItemAfterChunk = firstItemPosition + numItemsToRemove;
    numToMove = (*list)->numItems - (firstItemAfterChunk - 1);

    if (numToMove > 0)  /* move part of list down to cover hole left by removed item */
        memmove (ITEMPTR(list,firstItemPosition-1),
                 ITEMPTR(list,firstItemAfterChunk-1),
                 (*list)->itemSize * numToMove);

    (*list)->numItems -= numItemsToRemove;
}

/*******************************/

void  ListGetItem (list_t list, void *itemDestination, int itemPosition)
{
    ListGetItems (list, itemDestination, itemPosition, 1);
}

#endif	/* CFG_ALL_LIST_FUNCTIONS */

/*******************************/

void  ListGetItems(list_t list, void *itemsDestination, int firstItemPosition, int numItemsToGet)
{

    if (firstItemPosition == LIST_START)
        firstItemPosition = 1;
    else
    if (firstItemPosition == LIST_END)
        firstItemPosition = (*list)->numItems;

    memcpy (itemsDestination, ITEMPTR(list,firstItemPosition-1),
        (*list)->itemSize * numItemsToGet);
}

/*******************************/

    /*  Returns a pointer to the item at itemPosition. returns null if an errors occurred.
    */
void *  ListGetPtrToItem (list_t list, int itemPosition)
{
    if (itemPosition == LIST_START)
        itemPosition = 1;
    else
    if (itemPosition == LIST_END)
        itemPosition = (*list)->numItems;

    return ITEMPTR(list,itemPosition-1);
}

/*******************************/

     /* returns a pointer the lists data (abstraction violation for optimization) */
void *  ListGetDataPtr (list_t list)
{
    return &((*list)->itemList[0]);
}

/********************************/

#ifdef	CFG_ALL_LIST_FUNCTIONS

int  ListApplyToEach (list_t list, int ascending, ListApplicationFunc funcToApply, void *callbackData)
{
    int result = 0, index;

    if (!list || !funcToApply)
        goto Error;

    if (ascending)
        {
        for (index = 1; index <= ListNumItems (list); index++)
            {
            result  = funcToApply (index, ListGetPtrToItem (list, index),
                callbackData);
            if (result < 0)
                goto Error;
            }
        }
    else
        {
        for (index = ListNumItems (list); index > 0 &&
            index <= ListNumItems (list); index--)
            {
            result  = funcToApply (index, ListGetPtrToItem (list, index),
                callbackData);
            if (result < 0)
                goto Error;
            }
        }

Error:
    return result;
}

#endif	/* CFG_ALL_LIST_FUNCTIONS */

/********************************/

int  ListGetItemSize (list_t list)
{
    return (*list)->itemSize;
}

/********************************/

int  ListNumItems (list_t list)
{
    return (*list)->numItems;
}

/*******************************/

#ifdef	CFG_ALL_LIST_FUNCTIONS

void  ListRemoveDuplicates (list_t list, CompareFunction compareFunction)
{
    int numItems, index, startIndexForFind, duplicatesIndex;

    numItems = ListNumItems (list);

    for (index = 1; index < numItems; index++)
        {
        startIndexForFind = index + 1;
        while (startIndexForFind <= numItems)
            {
            duplicatesIndex = ListFindItem (list, ListGetPtrToItem (list, index),
                startIndexForFind, compareFunction);
            if (duplicatesIndex > 0)
                {
                ListRemoveItem (list, NULL, duplicatesIndex);
                numItems--;
                startIndexForFind = duplicatesIndex;
                }
             else
                break;
            }
        }
}

/*******************************/


/*******************************/

int  ListFindItem (list_t list, void *ptrToItem, int startingPosition, CompareFunction compareFunction)
{
    int numItems, size, index, cmp;
    void *listItemPtr;

    if ((numItems = (*list)->numItems) == 0)
        return 0;

    size = (*list)->itemSize;

    if (startingPosition == LIST_START)
        startingPosition = 1;
    else
    if (startingPosition == LIST_END)
        startingPosition = numItems;

    for (index = startingPosition; index <= numItems; index++)
        {
        listItemPtr = ITEMPTR(list,index-1);
        cmp = compareFunction ? compareFunction(ptrToItem, listItemPtr)
                              : ListMemBlockCmp(ptrToItem, listItemPtr, size);
        if (cmp == 0)
            return index;
        }

    return 0;
}

/*******************************/

int  ShortCompare(void *a, void *b)
{
    if (*(short *)a < *(short *)b) return -1;
    if (*(short *)a > *(short *)b) return  1;
    return 0;
}

/*******************************/

int  IntCompare(void *a, void *b)
{
   if (*(int *)a < *(int *)b) return -1;
   if (*(int *)a > *(int *)b) return  1;
   return 0;
}

/*******************************/

int  CStringCompare(void *a, void *b)
{
    return strcmp(*(char **)a, *(char **)b);
}

/*******************************/


int  ListBinSearch (list_t list, void *ptrToItem, CompareFunction compareFunction)
{
    int index;

    index = BinSearch (ITEMPTR(list,0), (int)(*list)->numItems,
        (int)(*list)->itemSize, ptrToItem, compareFunction);

    if (index >= 0)
        index++;        /* lists start from 1 */
    else
        index = 0;      /* item not found */

    return index;
}

/**************************************************************************/

    /*  Reserves memory for numItems in the list. If it succeeds then
        numItems items can be inserted without possibility of an
        out of memory error (useful to simplify error recovery in
        complex functions). Returns 1 if success, 0 if
        out of memory.
    */
int  ListPreAllocate (list_t list, int numItems)
{

    if ((*list)->listSize - (*list)->numItems < numItems)
        return ExpandListSpace (list,
            numItems - ((*list)->listSize - (*list)->numItems));
    else
        return 1;    /* enough items are already pre-allocated */
}

#endif	/* CFG_ALL_LIST_FUNCTIONS */