/* My own malloc routines */
#include "misc.h"
#include "msdos.h"

#define INIT_MBUF	64

extern Bool _near Must_have_memory;

struct mbuf {
	struct mbuf _based((_segment)_self) *next;
	unsigned size;
	char _based((_segment)_self) *ptr;
};

/* must be same size as struct mbuf */
struct mem_head {
	unsigned size;
	struct mbuf _based((_segment)_self) *mem;
	struct mbuf _based((_segment)_self) *free;
};

#define free_mbuf    (*(struct mbuf _based(seg) * _based(seg) *)4)
#define free_mbufs    (*(struct mbuf _based((_segment)_self) * _based(seg) *)4)
#define mem_mbuf	(*(struct mbuf _based(seg) * _based(seg) *)2)

void
mem_init(seg, size)
_segment seg;
unsigned size;
{
	struct mem_head _based(seg) *mh;
	struct mbuf _based(seg) *m;
	u_short _based(seg) *sp;
	int mbufs;

printf("init segment %x\n", seg);
	mh = 0;
	/* point to first mbuf */
	m = (struct mbuf _based(seg) *)(mh + 1);
	mh->mem = (struct mbuf _based(void) *)m;
	mh->size = size;
	/*
	 * In an attempt to avoid fragmentation of the memory, we
	 * allocate some empty mbufs at the beginning of the memory.
	 * Let's start with 1 per 1k of memory.
	 */
	mbufs = size / 1024 + 2;
	/* Put all of memory (minus mbufs allocated) in the first mbuf */
	m->size = size - sizeof (struct mbuf) * (mbufs + 1);
	m->ptr = (char _based(void) *)(m + mbufs);
	m->next = 0;

	mbufs--;	/* At this point, mbufs is number of "free" mbufs. */

	m++; mbufs--;
	free_mbuf = m;
	while (mbufs-- > 0) {
		m->size = 0;
		m->next = (struct mbuf _based(void) *)(m + 1);
		m++;
	}
	m->next = 0;
	m->size = 0;
}

char _based(void) *
bMalloc(seg, size)
_segment seg;
unsigned size;
{
	struct mbuf _based(seg) *m;
	struct mbuf _based(seg) * _based(seg) *mpp;
	char _based(void) *cp;

	size += 2;	/* save room for size word */
	mpp = &mem_mbuf;
	while (m = *mpp) {
		if (m->size >= size) {
			cp = (char _based(void) *)m->ptr;
			*(unsigned _based(seg) *)cp = size;
			cp += 2;
			m->ptr += size;
			m->size -= size;
			if (!m->size) {
			    /* remove from buf list */
			    *mpp = (struct mbuf _based(seg) *)m->next;
			    /* add to free list */
			    m->next = free_mbufs;
			    free_mbuf = m;
printf("%");
			}
			return cp;
		}
		mpp = (struct mbuf _based(seg) * _based(seg) *)&m->next;
	}
	if (Must_have_memory)
	    FatalError("Out of memory in segment %x", seg);
	return 0;
}

void
bFree(seg, ptr)
_segment seg;
char _based(void) *ptr;
{
	unsigned size;
	struct mbuf _based(seg) *m, _based(seg) *n;
	struct mbuf _based(seg) * _based(seg) *mpp, _based(seg) *npp;

	if (!ptr)
		return;
	ptr -= 2;
	size = *(unsigned _based(seg) *)ptr;
again:
	mpp = &mem_mbuf;
	/* Step 1:  Find mbuf nearest to this memory address. */
	while (m = *mpp) {
		if (m->ptr + m->size >= ptr)
			break;
		mpp = (struct mbuf _based(seg) * _based(seg) *)&m->next;
	}
	/* Four cases:
	 *  1: This pointer fits on the end of m.
	 *  2: It fits on the start of m->next.
	 *  3: It fits on both m and m->next.
	 *  4: It doesn't fit.
	 */
	if (m) {
		n = (struct mbuf _based(seg) *)m->next;
		if (m->ptr + m->size == ptr) {
			/* case 1 or 3 */
			m->size += size;	/* add to end of m */
			if (n && m->ptr + m->size == n->ptr) {
				/* case 3: free n */
				m->size += n->size;
				m->next = n->next;
				n->next = free_mbufs;
				free_mbuf = n;
			}
			return;
		}
		if (ptr + size == (char _based(void) *)n->ptr) {
			/* case 2 */
			n->size += size;
			n->ptr = ptr;
			return;
		}
	}
	/* case 4: we need to allocate a new mbuf */
	n = free_mbuf;
	if (!n) {
		char _based(seg) *cp;

		cp = bMalloc(seg, sizeof (struct mbuf) - 2);
		if (!cp) {
			printf("bFree: can't free %d bytes at %x\n",
			    size, (short)ptr);
			return;
		}
		n = (struct mbuf _based(seg) *)(cp - 2);
		n->next = 0;
		free_mbuf = n;
		/* The call to bMalloc may have changed our data
		 * strutures.  Therefore the only solution is...
		 */
printf("bFree: goto again\n");
		goto again;
	}
	free_mbufs = n->next;
	n->ptr = ptr;
	n->size = size;
	n->next = (struct mbuf _based(void) *)m;
	*mpp = n;
}

char _based(void) *
bRealloc(seg, ptr, size)
_segment seg;
char _based(void) *ptr;
unsigned size;
{
	struct mbuf _based(seg) *m;
	struct mbuf _based(seg) * _based(seg) *mpp;
	char _based(void) *cp;
	unsigned oldsize;

	if (!ptr) {
		cp = bMalloc(seg, size);
		return cp;
	}
	size += 2;	/* save room for size word */
	ptr -= 2;
	oldsize = *(unsigned _based(seg) *)ptr;
	if (size == oldsize)
		return ptr + 2;		/* realloc with no change */
	if (size < oldsize) {
		/* Easy - just free the excess */
		cp = ptr + size;
		oldsize -= size;
		*(unsigned _based(seg) *)cp = oldsize;
		*(unsigned _based(seg) *)ptr = size;
		bFree(seg, cp + 2);
		return ptr + 2;
	}
	/* See if we can just extend this buffer a little (and avoid
	 * copying!)
	 */
	cp = ptr + oldsize;
	mpp = &mem_mbuf;
	while (m = *mpp) {
		if (m->ptr == cp) {
			if (m->size >= size - oldsize) {
			    *(unsigned _based(seg) *)ptr = size;
			    size -= oldsize;
			    m->size -= size;
			    if (m->size == 0) {
				/* remove from buf list */
				*mpp = (struct mbuf _based(seg) *)m->next;
				/* add to free list */
				m->next = free_mbufs;
				free_mbuf = m;
printf("+");
			    } else
				    m->ptr += size;
			    return ptr + 2;
			}
		        break;
		}
		if (m->ptr > cp)
			break;	/* missed */
		mpp = (struct mbuf _based(seg) * _based(seg) *)&m->next;
	}
	/* If we got here, then it's not that simple.  We'll have to malloc
	 * some new space and memcopy the old data. */
	ptr += 2;
	cp = bMalloc(seg, size-2);
	if (!cp) {
	    if (Must_have_memory)
		FatalError("Out of memory in bRealloc\n");
	} else
	    memcpy(seg:>cp, seg:>ptr, oldsize-2);
	bFree(seg, ptr);
	return cp;
}
