#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_FUNCTIONSvoid  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)