Initial revision
diff --git a/common/lists.c b/common/lists.c
new file mode 100644
index 0000000..3f117b5
--- /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 */