luxos/Kernel/library/array/ord_arr.c

/*
 * ord-arr.c
 *
 *  Created on: Aug 25, 2011
 *      Author: Tiberiu
 */


/*
 * memory.c
 *
 *  Created on: Aug 24, 2011
 *      Author: Tiberiu
 */

#include <stdlib.h>
#include <memory.h>
#include <array.h>

int StandardComparePredicate (uint32 a, uint32 b)
{
	if (a > b) return 1;
	else if (a == b) return 0;
	return -1;
}

OrderedArray OrderedArrayCreate (uint32 maxSize, ComparePredicate p)
{
	OrderedArray ret;
	ret.Data = (unsigned*) kmalloc(maxSize);
	memset(ret.Data, 0, maxSize);
	ret.Size = 0;
	ret.SizeLimit = maxSize;
	ret.Compare = (p == 0) ? StandardComparePredicate : p;

	return ret;
}

OrderedArray OrderedArrayPlace (uint32 addr, uint32 maxSize, ComparePredicate p)
{
	OrderedArray ret;
	ret.Data = (unsigned*)addr;
	memset(ret.Data, 0, maxSize);
	ret.Size = 0;
	ret.SizeLimit = maxSize;
	ret.Compare = (p == 0) ? StandardComparePredicate : p;

	return ret;
}

void OrderedArrayDispose (OrderedArray* arr)
{
	kfree(arr->Data);
}

uint32 OrderedArrayBinarySearch (uint32 key, uint32* array, uint32 length, ComparePredicate predicate)
{
	if (!predicate) return 0;

	uint32 left = 0, right = length, mid;

	while (left < right)
	{
		mid = left + (right-left) / 2;

		int r = (*predicate)(key, array[mid]);

		if (r > 0) left = mid + 1;
		else if (r < 0) right = mid;
		else return mid;
	}
	mid = left + (right-left) / 2;

	return mid;
}

uint32 OrderedArraySearch (uint32 key, OrderedArray* arr, ComparePredicate predicate)
{
	uint32 r = OrderedArrayBinarySearch(key,arr->Data,arr->Size,predicate);

	if (arr->Data[r] != key) return 0xffffffff;
	return r;
}

void OrderedArrayInsert (uint32 item, OrderedArray* arr)
{
	if (arr->Size >= arr->SizeLimit) return;

	uint32 location = OrderedArrayBinarySearch(item, arr->Data, arr->Size, arr->Compare);

	uint32 i;
	for (i = arr->Size; i > location && arr->Size > 0; i--)
		arr->Data[i] = arr->Data[i-1];

	arr->Data[location] = item;
	arr->Size++;
}

uint32 OrderedArrayLookup (uint32 index, OrderedArray* arr)
{
	if (index >= arr->Size) return 0;
	return arr->Data[index];
}

void OrderedArrayDeleteIndex (uint32 index, OrderedArray* arr)
{
	if (index >= arr->Size) return;

	uint32 i;
	for (i = index + 1; i < arr->Size; i++)
		arr->Data[i - 1] = arr->Data[i];
	arr->Size--;
}