/*-
 * Copyright (c) 2000-2001
 * Tatsuya Kudoh(CDR/TK),ROYALPANDA.    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.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``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 THE AUTHOR OR CONTRIBUTORS 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.
 *
 */

#include<stdlib.h>
#include<stdio.h>
#include"malloc.h"

#pragma noregalo

/**********************************
*
*   low-level memory allocation
*
**********************************/

extern char *_heap;

static char *sbrk( int cnt )
{
	char *p;
	unsigned s;

	if( (unsigned)_heap == 0 )
		return NULL;

	s = ((unsigned)_heap ^ 0xffff) + 1;	/* 0x10000 - _heap */
	if( s < cnt )
		return NULL;

	p = _heap;
	_heap += cnt;
	return p;
}

/*********************************
*
* High-level memory allocation
*
*********************************/


typedef struct cell_t{
	unsigned size;
	struct cell_t *next;
}cell_t;

static cell_t FreeHead = {0,NULL};

static char *reuse( int size )
{
	cell_t *p,*prev;
	int newsize;

	prev = &FreeHead;
	p = prev->next;
	while( p != NULL && p->size < size ){
		prev = p;
		p = p->next;
	}
	if( p == NULL )
		return NULL;

	newsize = p->size - size;
	if( newsize < sizeof(cell_t) ){
		prev->next = p->next;
	}else{
		p->size = newsize;
		p = (cell_t*)((char*)p + newsize);
		p->size = size;
	}
	return (char*)p + sizeof(unsigned);
}


void *malloc( unsigned size )
{
	char *p;
	cell_t *cp;

	size = (size + sizeof(unsigned) + 1) & ~1;
	if( size < sizeof(cell_t) )
		size = sizeof(cell_t);

	p = reuse(size);
	if( p != NULL )
		return (void*)p;

	cp = (cell_t*)sbrk(size);
	if( cp == NULL )
		return NULL;

	cp->size = size;
	return (char*)cp + sizeof(unsigned);
}


void free( void *ptr )
{
	cell_t *p,*q,*prev;
	int flag;

	if( ptr == NULL )
		return;

	q = (cell_t*)((char*)ptr - sizeof(unsigned));

	prev = &FreeHead;
	p = prev->next;
	flag = 0;
	while( p != NULL ){
		if( (char*)p + p->size == (char*)q ){
			prev->next = p->next;
			p->size += q->size;
			q = p;
			flag |= 1;
			if( flag == 3 )
				break;
			p = prev->next;
		}else if( (char*)q + q->size == (char*)p ){
			prev->next = p->next;
			q->size += p->size;
			flag |= 2;
			if( flag == 3 )
				break;
			p = prev->next;
		}else{
			prev = p;
			p = p->next;
		}
	}
	q->next = FreeHead.next;
	FreeHead.next = q;
}