diff options
Diffstat (limited to 'common/lists.c')
| -rw-r--r-- | common/lists.c | 734 |
1 files changed, 734 insertions, 0 deletions
diff --git a/common/lists.c b/common/lists.c new file mode 100644 index 0000000000..3f117b568e --- /dev/null +++ b/common/lists.c @@ -0,0 +1,734 @@ +#include <common.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) + +/* increase list size by 10% every time it is full */ +#define kDefaultAllocationPercentIncrease 10 + +/* always increase list size by 4 items when it is full */ +#define kDefaultAllocationminNumItemsIncrease 4 + +/* + * 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 */ + +/*******************************************************************************/ + +/* + * 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); + } +} + +/*******************************/ + +/* + * keeps memory, resets the number of items to 0 + */ +void ListClear (list_t list) +{ + if (!list) + return; + (*list)->numItems = 0; +} + +/*******************************/ + +/* + * copy is only as large as necessary + */ +list_t ListCopy (list_t originalList) +{ + 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; +} + +/********************************/ + +/* + * list1 = list1 + list2 + */ +int ListAppend (list_t list1, list_t 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) + return 0; + + if ((*list)->numItems >= (*list)->listSize) { + if (!ExpandListSpace (list, -numItemsToInsert)) + return 0; + } + + if (firstItemPosition == LIST_START) { + if (numItems == 0) { + /* special case for empty list */ + firstItemPosition = LIST_END; + } 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 ListGetItem (list_t list, void *itemDestination, int itemPosition) +{ + ListGetItems (list, itemDestination, itemPosition, 1); +} + +#endif /* CFG_ALL_LIST_FUNCTIONS */ + +/*******************************/ + +#if defined(CFG_ALL_LIST_FUNCTIONS) || defined(CFG_DEVICE_DEREGISTER) + +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; +} +#endif /* CFG_ALL_LIST_FUNCTIONS || CFG_DEVICE_DEREGISTER */ + +/*******************************/ + +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 */ |
