/* ==== cluster.c ============================================================
 * Copyright (c) 1995 by Chris Provenzano, proven@mit.edu
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 * 3. All advertising materials mentioning features or use of this software
 *    must display the following acknowledgement:
 *  This product includes software developed by Chris Provenzano.
 * 4. The name of Chris Provenzano may not be used to endorse or promote 
 *	  products derived from this software without specific prior written
 *	  permission.
 *
 * THIS SOFTWARE IS PROVIDED BY CHRIS PROVENZANO ``AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED.  IN NO EVENT SHALL CHRIS PROVENZANO BE LIABLE FOR ANY 
 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR 
 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 
 * SUCH DAMAGE.
 *
 * Description : Main fc functions.
 *
 *  1.00 95/06/28  proven
 *      -Started coding this file.
 */

#include <stdio.h>
#include <errno.h>
#include "cluster.h"
#include "util.h"

/* ==========================================================================
 * cluster_count()
 */
static inline int cluster_count(cluster * cluster)
{
	struct cluster_block * block;
	unsigned int count = 0;

	for (block = cluster->first; block; block = block->next) 
		count += block->count_free;
	return(count);
}

/* ==========================================================================
 * cluster_init()
 */
int cluster_init(cluster * cluster, size_t size)
{
	cluster->first = NULL;
	cluster->last = NULL;
	cluster->cmin = 16;			/* This should be settable */
	cluster->size = size;
	return(OK);
}

/* ==========================================================================
 * cluster_prealloc()
 */
int cluster_prealloc(cluster * cluster, unsigned int count)
{
	struct cluster_header * new_header;
	struct cluster_block * new_block;
	size_t size;
	int i;

	if (count) {
		/* Don't bother searching the list for enough free elements */
		size = (sizeof(struct cluster_header) + cluster->size) * count +
		  sizeof(struct cluster_block);

		if ((new_block = (struct cluster_block *)malloc(size))) {
			/* Insert new block into front of cluster list */
			if ((new_block->next = cluster->first) == NULL) {
				cluster->last = new_block;
			}
			cluster->first = new_block;

			/* Initialize new cluster block */
			new_block->count_free = new_block->count_total = count;
			new_block->first_free = (struct cluster_header *)new_block->data;
			new_block->first_used = NULL;

			/* Initialize cluster headers */
			new_header = new_block->first_free;
			for (i = 0; i < (count - 1); i++) {
				new_header->next = (struct cluster_header *)((char *)new_header
				  + cluster->size + sizeof(struct cluster_header));
				new_header->block = new_block;
				new_header = new_header->next;
			}
			new_header->block = new_block;
			new_header->next = NULL;
		} else {
			return(ENOMEM);
		}
	} else {
		return(EINVAL);
	}
	return(OK);
}

/* ==========================================================================
 * cluster_alloc()
 *
 * This should be made into a macro.
 */
void * cluster_alloc(cluster * cluster)
{
	struct cluster_header * header;
	struct cluster_block * block;

	for (block = cluster->first; block; block = block->next) {
		if (header = block->first_free) {
			block->first_free = header->next;
			header->next = block->first_used;
			block->first_used = header;
			block->count_free--;
			return(header->data);
		}
	}
	if (cluster_prealloc(cluster, cluster->cmin) == OK) {
		header = cluster->first->first_free;
		cluster->first->first_free = header->next;
		header->next = cluster->first->first_used;
		cluster->first->first_used = header;
		cluster->first->count_free--;
		return(header->data);
	}
	return(NULL);
}

/* ==========================================================================
 * cluster_free()
 */
void cluster_free(cluster * cluster, void * data)
{
	struct cluster_header ** pheader;
	struct cluster_header * header;
	struct cluster_block * block;

	header = (struct cluster_header *)(data - sizeof(struct cluster_header));
    block = header->block;
	for (pheader = &block->first_used; *pheader; pheader = &((*pheader)->next)){
		if (*pheader == header) {
			*pheader = header->next;
			header->next = block->first_free;
			block->first_free = header;

			/* See if we can free some memory */
			if (++block->count_free == block->count_total) {
				struct cluster_block ** pblock;
				unsigned int count;

				/* This is a sanity check */
				if (((count = cluster_count(cluster)) < block->count_free) ||
				  (block->first_used))
					abort(); 

				if (count > cluster->cmin) {
					for (pblock = &cluster->first; *pblock; 
					  pblock = &((*pblock)->next)) {
						if (*pblock == block) {
							*pblock = block->next;
							free(block);
						}
					}
				}
			}
			return;
		}
	}
	/* We didn't find it */
	abort();
}