lists.c.svn-base

u-boot loader common files, like cpu, clock, environment...etc...

#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;
	}