/*(LGPL)
---------------------------------------------------------------------------
	a_vvid.c - Virtual Voice ID Management
---------------------------------------------------------------------------
 * Copyright (C) 2002, David Olofson
 *
 * This program is free software; you can redistribute it and/or modify it
 * under the terms of the GNU Lesser General Public License as published by
 * the Free Software Foundation; either version 2.1 of the License, or (at
 * your option) any later version.
 * 
 * This program is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * Lesser General Public License for more details.
 * 
 * You should have received a copy of the GNU Lesser General Public License
 * along with this program; if not, write to the Free Software Foundation,
 * Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 */

#undef	VVID_TEST

#ifdef VVID_TEST
#include <stdio.h>
#include <stdlib.h>
#define VDBG(x)
#else
#define VDBG(x)
#endif

#include "types.h"
#include "a_vvid.h"

/*
 * The VVID entry table.
 *
 *	* The first VVID in each range is reserved, and contains the
 *	  number of VVIDs in the range. (Including the reserved VVID!)
 *
 *	* The MSB of this entry is "1" if the VVID is allocated.
 *
 *	* The VVID table is terminated with a zero length range, that
 *	  is marked as free. (Note that this is not even an empty
 *	  range! An empty range has a length of 1.)
 */
static int table_size = 0;
static ADY_vvid_entry *table = NULL;

#define	IN_USE_F	0x80000000
#define	LENGTH_MASK	0x7fffffff

#define	LENGTH(x)	((int)(table[(x)]) & LENGTH_MASK)
#define	IN_USE(x)	((int)(table[(x)]) & IN_USE_F)


static int alloc_fail(int count)
{
/*FIXME: Insert table reallocation here! */
	return -1;
}


static int do_alloc(int count)
{
	int i, best, best_i;

	++count;	/* For the reserved entry */

	best_i = -1;
	best = LENGTH_MASK;

	i = 0;
	while((int)(table[i]))
	{
		int space = LENGTH(i) - count;
		if(!IN_USE(i) && (space >= 0) && (space < best))
		{
			best_i = i;
			if(!space)
				break;	/* Exact fit! --> */
			best = space;
		}
		i += LENGTH(i);
	}

	if(best_i >= 0)
	{
		/* Split if large enough. */
		if(LENGTH(best_i) > count + 1)
		{
			table[best_i + count] = (void *)(LENGTH(best_i) - count);
			table[best_i] = (void *)(count | IN_USE_F);
		}
		else
			table[best_i] = (void *)(LENGTH(best_i) | IN_USE_F);
		return best_i + 1;
	}
	return -42;	/* Allocation failed! */
}


int ady_vvid_alloc(int count)
{
	int vvid;

	if(!count)
		return -1;	/* What's the point in this? */
	if(!table)
		return -2;	/* Not initialized...! */

	vvid = do_alloc(count);
	if(vvid < 0)
	{
		if(alloc_fail(count) < 0)
			return -3;
		vvid = do_alloc(count);
	}
	return vvid;
}


void ady_vvid_free(int first)
{
	--first;

	if(first < 0)
		return;
	if(first >= table_size)
		return;
	if(!IN_USE(first))
		return;		/* Already free, or bad index! */

	/* Free the range. */
	VDBG(printf("VVID: Freed range %d - %d.\n", first, first + LENGTH(first));)
	table[first] = (void *)LENGTH(first);

	/* Merge free ranges, if possible. */
	VDBG(printf("VVID: Merging ranges...\n");)
	first = 0;
	while((int)(table[first]))
	{
		int next = first + LENGTH(first);
		int do_merge = 0;
		if(IN_USE(first))
		{
			first = next;
			continue;
		}
		VDBG(printf("      Trying %d...\n", first);)
		while((int)(table[next]) && !IN_USE(next))
		{
			VDBG(printf("         Merging with range %d. ", next);)
			VDBG(printf("(%d - %d)\n", next, next + LENGTH(next));)
			next += LENGTH(next);
			do_merge = 1;
		}
		if(do_merge)
		{
			VDBG(printf("            first = %d; next = %d\n", first, next);)
			table[first] = (void *)(next - first);
			VDBG(printf("            table[%d] = %d\n", first, (int)(table[first]));)
		}
		first = next;
	}
	VDBG(printf("VVID: Done!\n");)
}


ADY_vvid_entry *ady_vvid_table(void)
{
	return table;
}


int ady_vvid_open(int count)
{
	table = malloc(count * sizeof(ADY_vvid_entry));
	if(!table)
		return -1;
	table_size = count;

	/* Create the initial free range. */
	table[0] = (void *)(count-1);

	/* Create the terminating fake range. */
	table[count-1] = (void *)0;
	return 0;
}


void ady_vvid_close(void)
{
	free(table);
	table = NULL;
	table_size = 0;
}


#ifdef VVID_TEST
int main(int argc, char *argv[])
{
	int i, fv;
	int v[8];

	i = ady_vvid_open(30);
	if(i < 0)
	{
		printf("VVID manager failed to open! (%d)\n", i);
		exit(1);
	}

	printf("Testing VVID manager; pass 1...\n");
	for(i = 0; i < 30; ++i)
	{
		fv = ady_vvid_alloc(i);
		if(fv < 0)
			printf("ady_vvid_alloc(%d) failed; %d\n", i, fv);
		else
		{
			printf("ady_vvid_alloc(%d) succeeded; %d\n", i, fv);
			ady_vvid_free(fv);
		}
	}
	fv = ady_vvid_alloc(28);
	if(fv < 0)
		printf("Pass 1 FAILED!\n\n");
	else
	{
		printf("Pass 1 completed.\n\n");
		ady_vvid_free(fv);
	}

	printf("Testing VVID manager; pass 2...\n");
	printf("Pass 2: Allocating ranges...\n\n");
	for(i = 0; i < 8; ++i)
	{
		v[i] = ady_vvid_alloc(i);
		if(v[i] < 0)
			printf("ady_vvid_alloc(%d) failed; %d\n", i, v[i]);
		else
			printf("ady_vvid_alloc(%d) succeeded; %d\n", i, v[i]);
	}
	printf("Pass 2: Freeing ranges...\n\n");
	for(i = 0; i < 8; ++i)
		if(v[i] >= 0)
			ady_vvid_free(v[i]);
	fv = ady_vvid_alloc(28);
	if(fv < 0)
		printf("Pass 2 FAILED!\n\n");
	else
		printf("Pass 2 completed.\n\n");

	ady_vvid_close();

	printf("====================================================\n");
	printf("  Note that the first and last allocation in pass 1\n");
	printf("  and 2 SHOULD fail, or something is very wrong!\n");
	printf("====================================================\n");
	
	return 0;
}
#endif