#include <stdio.h>

typedef struct s_mlump {
     unsigned int Size;
     struct s_mlump *Next;
     char Where[1];
} t_mlump;

#define SLOP 3

extern char *sbrk();

static t_mlump *UsedList = 0;
static t_mlump *FreeList = 0;

static t_mlump *MakeMore();

char *
Malloc(nbytes)
    unsigned nbytes;
{
    /* traverse the free list looking for a fit */
    t_mlump **Fpp;
    t_mlump *tmp;

    for (Fpp = &FreeList; *Fpp; Fpp = &(*Fpp)->Next) {
	if ((*Fpp)->Size >= nbytes && (*Fpp)->Size - nbytes <= SLOP) {
	    /* move from free list to used list */

	    tmp = (*Fpp);
	    (*Fpp) = (*Fpp)->Next;
	    tmp->Next = UsedList;
	    UsedList = tmp;
	    /* return the area */
	    return &(tmp->Where)[0];
	}
    }
    /* Nothing good */
    *Fpp = MakeMore(nbytes);
    /* move from free list to used list */
    (*Fpp)->Next = UsedList;
    UsedList = (*Fpp);
    /* return the area */
    return &((*Fpp)->Where)[0];
}

void
Free(lump)
    char *lump;
{
    register t_mlump **lpp;

    for (lpp = &UsedList; *lpp; lpp = &(*lpp)->Next) {
	if (&((*lpp)->Where)[0] == lump) {
	    t_mlump *tmp;

	    char *Top = sbrk(0);
	    char *AmITop = &((*lpp)->Where)[0];
	    
(void) fprintf(stderr, "Top 0x%x AmITop 0x%x Size 0x%x lpp 0x%x Where 0x%x size %u\n",
	Top, AmITop, (*lpp)->Size, *lpp, &((*lpp)->Where)[0], sizeof(t_mlump));
	    if (AmITop + (*lpp)->Size + sizeof(t_mlump) - 1 == Top) {
		/* Return the memory */
		int Amount = (*lpp)->Size + sizeof(t_mlump);

		(*lpp) = (*lpp)->Next;
		if ((AmITop = sbrk(-Amount)) == (char *) 0) {
		    (void) fprintf(stderr, "sbrk(%d) returned 0!\n", -Amount);
		} else {
		    Top = AmITop;
		    return;
		}

	    } else {
		tmp = (*lpp);
		*lpp = tmp->Next;
		tmp->Next = FreeList;
		FreeList = tmp;
	    }
	    return;
	}
    }
    fprintf(stderr, "Free: lump 0x%x was not in use!\n", lump);
}

static t_mlump *
MakeMore(size)
    unsigned int size;
{

    t_mlump *L;

    L = (t_mlump *) sbrk(size + sizeof(t_mlump) - 1); /* -1 for Where[0] */
	/* assume it always works for now */
    L->Next = 0;
    L->Size = size;
    return L;
}