#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 */