
/*
 * Storage allocator based on Kernighan & Ritchie model but
 * simplified since there are no alignment requirements on
 * 8080/Z80 and obtaining free space under CP/M is cheap
 */

#define NULL 0

struct _header {
	struct _header	*_next; /* next free block */
	unsigned	_bsize; /* size of block */
	};
typedef struct _header HEADER;

HEADER		_base,		/* empty free space list */
		*_allocp;	/* last allocated block */
char *malloc(nbytes)
unsigned nbytes;
	{
	register HEADER *p, *q;
	register unsigned nunits;
	char *sbrk();

	nunits = 1 + (nbytes + (sizeof(HEADER) - 1)) / sizeof(HEADER);
	if ((q = _allocp) == NULL)	/* no free list */
		_base._next = _allocp = q = &_base;
	for (p = q->_next; ; q = p, p = p->_next) {
		if (p->_bsize >= nunits) {
			if (p->_bsize == nunits)
				q->_next = p->_next;
			else {
				p->_bsize -= nunits;
				p += p->_bsize;
				p->_bsize = nunits;
				}
			_allocp = q;
			return ((char *)(p+1));
			}
		if (p == _allocp) {	/* wrapped around */
			p = (HEADER *) sbrk(nunits * sizeof(HEADER));
			if ((int) p == -1)
				return NULL;
			p->_bsize = nunits;
			free((char *)(p+1)); /* add to free list */
			p = _allocp;
			}
		}
	}


free(pblk)
char *pblk;
	{
	register HEADER *p, *q;

	p = (HEADER *)pblk - 1; 	/* point to block header */
	for (q=_allocp; !(p>q && p<q->_next); q=q->_next)
		if (q >= q->_next && (p>q || p<q->_next))
			break;
	if (p+p->_bsize == q->_next) {	/* join to upper neighbor */
		p->_bsize += q->_next->_bsize;
		p->_next = q->_next->_next;
		}
	else
		p->_next = q->_next;
	if (q+q->_bsize == p) { 	/* join to lower neighbor */
		q->_bsize += p->_bsize;
		q->_next = p->_next;
		}
	else
		q->_next = p;
	_allocp = q;
	}
