/* alloc.c - memory allocator
 *
 * The point of this is that it is about 4 times faster than MANX malloc/free
 * in c.lib.  Malloc in heapmem.o will not allocate a second heap if the first
 * is exhausted.
 * :ts=8
 */


#define NULL		0L
#define HOWMUCH		4096L	/* how much memory to AllocMem() at a time */

typedef struct header {
      struct header *next;	/* next block */
      unsigned long size;	/* block size */
};

struct header first;

struct header *head = NULL;	/* start of list */


char *alloc (bytes)
unsigned bytes;
{
   struct header *getmem ();
   register struct header *p, *q;
   register long size;

   size = (((bytes + 2 * sizeof (struct header) - 1) >> 3) << 3);
   if ((q = head) == NULL) {
      first.next = head = q = &first;
      first.size = 0L;
   }
   for (p = q->next; ; q = p, p = p->next) {
      if (p->size >= size) {	/* if this block is large enough */
         if (p->size == size)
	    q ->next = p->next;
	 else {		/* remove memory from tail of block */
	    p->size -= size;
	    p = (struct header *) ((char *) p + p->size);
	       p->size = size;
	 }
	 head = q;
	 p->next = NULL;
	 return ((char *) (p+1));
      }
      if (p == head)	/* back where we started */
	 if ((p = getmem ()) == NULL)
	    return (NULL);	/* cannot allocate memory */
   }
}


/* freeit - put block back in free list */

freeit (ptr)
char *ptr;
{
   register struct header *p, *q;

   p = (struct header *) ptr - 1;
   for (q = head; ; q = q->next) {
      if (p > q && p < q->next)
	 break;		/* new block goes between q & q->next */
      if (q >= q->next && p > q)
	 break;		/* new block goes at end of list */
      if (q >= q->next && p < q->next)
	 break;		/* new block goes at beginning of list */
   }

   if ((struct header *) ((char *) p + p->size) == q->next) {
      p->size += q->next->size;
      p->next = q->next->next;
   } else {
      p->next = q->next;
   }
   if ((struct header *) ((char *) q + q->size) == p) {
      q->size += p->size;
      q->next = p->next;
   } else {
      q->next = p;
   }
   head = q;
}


/* getmem - request more memory from system */

struct header *getmem ()
{
   char *AllocMem ();
   register struct header *up;

   if ((up = (struct header *) AllocMem (HOWMUCH, 0L)) == NULL)
      return (NULL);	/* can't get more memory */
   up->next = NULL;
   up->size = HOWMUCH;
   freeit ((char *) (up + 1));
   return (head);
}


quit (code)
int code;
{
   register struct header *p, *q;
   unsigned long size;

   p = head;
   do {
      if (p == NULL)
         break;
      q = p->next;
      if ((size = p->size) > 0L) {
	 p->size = 0L;
         FreeMem (p, size);
      }
      p = q;
   } while (p != head);
   exit (code);
}