lists.c

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

#include <armboot.h>
#include <malloc.h>
#include "lists.h"

#define MAX(a,b) 	(((a)>(b)) ? (a) : (b))
#define MIN(a,b) 	(((a)<(b)) ? (a) : (b))
#define CAT4CHARS(a,b,c,d)	((a<<24) | (b<<16) | (c<<8) | d)

#define kDefaultAllocationPercentIncrease   10  /* increase list size by 10% every time it is full */
#define kDefaultAllocationminNumItemsIncrease   4   /* always increase list size by 4 items when it is full */

 /* how many items to expand the list by when it becomes full = current listSize (in items) + (hiword percent of list size) +   loword */
#define NUMITEMSPERALLOC(list) MAX(((*list)->listSize * ((*list)->percentIncrease + 100)) / 100 , (*list)->minNumItemsIncrease)

#define ITEMPTR(list, item)     &(((char *)&(*list)->itemList)[ (*(list))->itemSize * (item)])

#define LIST_SIGNATURE          CAT4CHARS('L', 'I', 'S', 'T');

#define calloc(size,num)	malloc(size*num)

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

Handle NewHandle(unsigned int numBytes)
{
    void            *memPtr;
    HandleRecord    *hanPtr;

    memPtr = calloc(numBytes, 1);
    hanPtr = (HandleRecord*)calloc(sizeof(HandleRecord), 1);
    if (hanPtr && (memPtr || numBytes == 0))
        {
        hanPtr->ptr = memPtr;
        hanPtr->size = numBytes;
        return (Handle)hanPtr;
        }
    else
        {
        free(memPtr);
        free(hanPtr);
        return NULL;
        }
}

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

void  DisposeHandle(Handle handle)
{
    if (handle)
        {
        free(*handle);
        free((void *)handle);
        }
}

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

unsigned int  GetHandleSize(Handle handle)
{
    return ((HandleRecord *)handle)->size;
}

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

int  SetHandleSize(Handle handle, unsigned int newSize)
{
    HandleRecord    *hanRecPtr = (HandleRecord *)handle;
    void            *newPtr, *oldPtr;
    unsigned int    oldSize;


    oldPtr = hanRecPtr->ptr;
    oldSize = hanRecPtr->size;

    if (oldSize == newSize)
         return 1;

    if (oldPtr == NULL)
    {
        newPtr = malloc(newSize);
    }
    else
    {
        newPtr = realloc(oldPtr, newSize);
    }
    if (newPtr || (newSize == 0))
        {
        hanRecPtr->ptr = newPtr;
        hanRecPtr->size = newSize;
        if (newSize > oldSize)
            memset ((char *)newPtr+oldSize, 0, newSize-oldSize);
        return 1;
        }
    else
        return 0;
}

#ifdef	CFG_ALL_LIST_FUNCTIONS

    /*  Used to compare list elements by their raw data contents */
static int  ListMemBlockCmp(void *a, void *b, int size)
{
    return memcmp(a, b, size);
}


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

    /*  Binary search numElements of size elementSize in array for a match
        to the. item. Return the index of the element that matches (0 - numElements - 1).
        If no match is found return the -i-1 where i is the index (0 - numElements)
        where the item should be placed. (*theCmp)(a,b) should return  <0 if a<b,
        0 if a==b, >0 if a>b.

        This function is like the C-Library function bsearch() except that this
        function returns the index where the item should be placed if it is not
        found.
    */
int BinSearch(void *array, int numElements, int elementSize, void *itemPtr, CompareFunction compareFunction)
{
    int low, high, mid, cmp;
    void *arrayItemPtr;

    for(low=0, high= numElements-1, mid=0, cmp= -1; low <= high; )
        {
        mid = (low + high) >> 1;

        arrayItemPtr = (void *) (((char *)array) + (mid*elementSize));
        cmp = compareFunction ? compareFunction(itemPtr, arrayItemPtr)
                              : ListMemBlockCmp(itemPtr, arrayItemPtr, elementSize);
        if (cmp == 0)
            return mid;
        else
        if (cmp < 0)
            high= mid - 1;
        else
            low= mid + 1;
        }
    if (cmp > 0)
        mid++;

    return -mid-1;
}

#endif	/* CFG_ALL_LIST_FUNCTIONS */

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

    /* BEGIN PATCH to 4.0.1 - jag 8-29-96 */
    /*  If numNewItems == 0 then expand the list by the number of items
	indicated by its allocation policy.
        If numNewItems > 0 then expand the list by exactly the number of
	items indicated.
        If numNewItems < 0 then expand the list by the absolute value of
	numNewItems plus the number of items indicated by its allocation
	policy.
        Returns 1 for success, 0 if out of memory
    */
static int  ExpandListSpace (list_t list, int numNewItems)
{
    if (numNewItems == 0)
        numNewItems = NUMITEMSPERALLOC(list);
    else
    if (numNewItems < 0)
        numNewItems = (-numNewItems) + NUMITEMSPERALLOC(list);

    if (SetHandleSize ((Handle)list,
        sizeof(ListStruct) +
	((*list)->listSize + numNewItems) * (*list)->itemSize))
	{
    	    (*list)->listSize += numNewItems;
    	    return 1;
        }
    else
    {
        return 0;
    }
}

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

#ifdef	CFG_ALL_LIST_FUNCTIONS

     /* This function reallocate the list, minus any currently unused portion of its allotted memory. */
void  ListCompact (list_t list)
{

    if (!SetHandleSize ((Handle)list,
        sizeof (ListStruct) + (*list)->numItems * (*list)->itemSize))
        return;

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

#endif	/* CFG_ALL_LIST_FUNCTIONS */

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

list_t  ListCreate (int elementSize)
{
    list_t    list;

    list = (list_t)(NewHandle (sizeof(ListStruct)));   /* create empty list */
    if (list)
        {
        (*list)->signature = LIST_SIGNATURE;
        (*list)->numItems = 0;
        (*list)->listSize = 0;
        (*list)->itemSize = elementSize;
        (*list)->percentIncrease = kDefaultAllocationPercentIncrease;
        (*list)->minNumItemsIncrease = kDefaultAllocationminNumItemsIncrease;
        }

    return list;
}

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

void  ListSetAllocationPolicy (list_t list, int minItemsPerAlloc, int percentIncreasePerAlloc)
{

    (*list)->percentIncrease = percentIncreasePerAlloc;
    (*list)->minNumItemsIncrease = minItemsPerAlloc;
}

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

void  ListDispose (list_t list)
{
    DisposeHandle ((Handle)list);
}

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

#ifdef	CFG_ALL_LIST_FUNCTIONS

void  ListDisposePtrList(list_t list)
{
    int index;
    int numItems;

    if (list)
        {
        numItems = ListNumItems(list);

        for (index = 1; index <= numItems; index++)
            free(*(void **)ListGetPtrToItem(list, index));

        ListDispose(list);
        }
}

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

void   ListClear (list_t list)  /* keeps memory, resets the number of items to 0 */
{
    if (!list)
        return;
    (*list)->numItems = 0;
}

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

list_t  ListCopy (list_t originalList)   /* copy is only as large as necessary */
{
    list_t    tempList = NULL;
    int         numItems;

    if (!originalList)
        return NULL;

    tempList = ListCreate ((*originalList)->itemSize);
    if (tempList) {
        numItems = ListNumItems (originalList);

        if (!SetHandleSize ((Handle)tempList,
            sizeof (ListStruct) + numItems * (*tempList)->itemSize)) {
            ListDispose (tempList);
            return NULL;
            }

        (*tempList)->numItems = (*originalList)->numItems;
        (*tempList)->listSize = (*originalList)->numItems;
        (*tempList)->itemSize = (*originalList)->itemSize;
        (*tempList)->percentIncrease = (*originalList)->percentIncrease;
        (*tempList)->minNumItemsIncrease = (*originalList)->minNumItemsIncrease;

        memcpy (ITEMPTR(tempList,0), ITEMPTR(originalList,0),
            numItems * (*tempList)->itemSize);
        }

    return tempList;
}

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

int  ListAppend (list_t list1, list_t list2)  /* list1 = list1 + list2 */
{
    int numItemsL1, numItemsL2;

    if (!list2)
        return 1;

    if (!list1)
        return 0;
    if ((*list1)->itemSize != (*list2)->itemSize)
        return 0;

    numItemsL1 = ListNumItems (list1);
    numItemsL2 = ListNumItems (list2);

    if (numItemsL2 == 0)
        return 1;

    if (!SetHandleSize ((Handle)list1,
        sizeof (ListStruct) + (numItemsL1 + numItemsL2) * (*list1)->itemSize))
        return 0;

    (*list1)->numItems = numItemsL1 + numItemsL2;
    (*list1)->listSize = numItemsL1 + numItemsL2;

    memmove (ITEMPTR(list1,numItemsL1), ITEMPTR(list2,0),
        numItemsL2 * (*list2)->itemSize);

    return 1;
}

#endif	/* CFG_ALL_LIST_FUNCTIONS */

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

    /*  returns 1 if the item is inserted, returns 0 if out of memory or
        bad arguments were passed.
    */
int  ListInsertItem (list_t list, void *ptrToItem, int itemPosition)
{
    return ListInsertItems (list, ptrToItem, itemPosition, 1);
}

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

int  ListInsertItems (list_t list, void *ptrToItems, int firstItemPosition, int numItemsToInsert)
{
    int numItems = (*list)->numItems;

    if (firstItemPosition == numItems + 1)
        firstItemPosition = LIST_END;
    else
    if (firstItemPosition > numItems)