summaryrefslogtreecommitdiff
path: root/common/lists.c
diff options
context:
space:
mode:
Diffstat (limited to 'common/lists.c')
-rw-r--r--common/lists.c734
1 files changed, 0 insertions, 734 deletions
diff --git a/common/lists.c b/common/lists.c
deleted file mode 100644
index 0dc090a..0000000
--- a/common/lists.c
+++ /dev/null
@@ -1,734 +0,0 @@
-#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 */