From: Shawn Hargreaves <Shawn AT talula DOT demon DOT co DOT uk>
Newsgroups: comp.os.msdos.djgpp
Subject: Re: A misfeature re malloc() and new
Date: Wed, 29 Jan 1997 21:08:15 +0000
Organization: None
Distribution: world
Message-ID: <oVZZyRA$w77yEwcJ@talula.demon.co.uk>
References: <957C9527FA AT fs2 DOT mt DOT umist DOT ac DOT uk>
 <Pine DOT SUN DOT 3 DOT 91 DOT 970128110407 DOT 10987B-100000 AT is>
NNTP-Posting-Host: talula.demon.co.uk
MIME-Version: 1.0
Lines: 259
To: djgpp AT delorie DOT com
DJ-Gateway: from newsgroup comp.os.msdos.djgpp

>If the problem is indeed a real one, nothing short of replacing the malloc
>algorithms would do, IMHO.  If you don't care about GPL restrictions, you
>can download the GNU Malloc library and use it instead (the Emacs source
>distribution includes it, and Emacs uses those functions instead of those
>from libc). 

In a virtual memory environment, surely the wastefulness of malloc() and 
co. doesn't make a great deal of difference? I think the wasted space would 
only be a problem in non-VM environments, and if that is a problem, a 
heap manager is an easy thing to implement.

I've got some code sitting around which I put together for a project a few 
years back. This is based on the dlibs package from the Atari ST, which is
freeware, so there are no GPL hassles involved with using it. It's 
significantly slower than djgpp's libc implementation, but doesn't waste 
any space (there is 8 bytes overhead per allocated block). Here you go:


/* 
 *  Replacements for the C library malloc routines, based on the malloc
 *  from the Atari ST gcc libc, which in turn was based on Dave Schumakers
 *  dlibs routines.
 * 
 *  Shawn Hargreaves, shawn AT talula DOT demon DOT co DOT uk
 */


#include <stdlib.h>
#include <libc/stubs.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>



/* how much space to reserve on each call to sbrk() */
#define GROW_MARGIN  1024*256



/* linked list of memory chunks */
typedef struct MemChunk
{
   struct MemChunk *next;
   unsigned long size;
} MemChunk;



/* list of free chunks */
static MemChunk the_heap = { NULL, 0 };



/* malloc:
 *  Allocates n bytes of memory, and returns a pointer to it. 
 */
void *malloc(size_t n)
{
   MemChunk *p, *q;

   static int virgin = 1;

   /* first time we are called, align the break point */
   if (virgin) {
      int pagesize, x;
      void *p;

      pagesize = x = getpagesize();
      p = sbrk(0);

      x = x - ((int)p & (x - 1));
      if (x < 0)
         x += pagesize;

      sbrk(x);
      virgin = 0;
   }

   /* add sizeof(MemChunk) to the requested size, and round up */
   n += sizeof(MemChunk);
   n = (n+7) & ~7;

   do {
      /* look for a big enough block in the free list */
      p = &the_heap;
      q = the_heap.next;

      while ((q) && (q->size < n)) {
         p = q;
         q = q->next;
      }

      /* if not enough memory, expand the heap */
      if (!q) {
         int grow = (n + (GROW_MARGIN-1)) & ~(GROW_MARGIN-1);
         p = sbrk(grow);
         if (p == (MemChunk *)-1)
            return NULL;

         p->size = grow;
         free(p+1);
      }

   } while (!q);

   if (q->size > n + sizeof(MemChunk)) {
      /* split this block, leaving part of it in the free list */
      q->size -= n;
      q = (MemChunk *)(((long)q) + q->size);
      q->size = n;
   }
   else {
      /* unlink the entire chunk */
      p->next = q->next;
   }

   /* skip past the block size information */
   q->next = NULL; 
   q++; 

   return ((void *)q);
}



/* realloc:
 *  Changes the size of a block of memory previously allocated by malloc().
 */
void *realloc(void *_r, size_t n)
{
   MemChunk *s, *t, *p, *q, *r = _r;
   long sz;

   /* obscure features: realloc(NULL,n) is the same as malloc(n)
    *                   realloc(p, 0) is the same as free(p)
    */
   if (!r)
      return malloc(n);

   if (!n) {
      free(_r);
      return NULL;
   }

   p = r - 1;
   sz = (n + sizeof(MemChunk)+7) & ~7;

   if (p->size > sz) { 
      /* block too big - split it in two */
      q = (MemChunk *)(((long)p) + sz);
      q->size = p->size - sz;
      free(q+1);
      p->size = sz;
   }
   else {
      if (p->size < sz) { 
         /* block too small, need to expand it */
         q = &the_heap;
         t = the_heap.next;

         while ((t) && (t<p)) {
            q = t;
            t = t->next;
         }

         s = (MemChunk *)(((long)p) + p->size);
         if ((t) && (s >= t) && (p->size + t->size >= sz)) {
            /* expand the block in-situ */
            p->size += t->size;
            q->next = t->next;
            t->size = 0;
            t->next = NULL;
         }
         else {
            /* argh! have to move the block */
            q = (MemChunk *)malloc(n);
            if (!q)
               return NULL;

            n = p->size - sizeof(MemChunk);
            memcpy(q, r, n);
            free(r);
            r = q;
         }
      }
   }

   return ((void *)r);
}



/* free:
 *  Frees a block of memory previously allocated by malloc().
 */
void free(void *_r)
{
   MemChunk *p, *q, *s;
   MemChunk *r = (MemChunk *)_r;

   if (!r)
      return;

   /* move back to uncover the MemChunk structure */
   r--;

   /* insert into free list, sorting by address */
   p = &the_heap;
   q = the_heap.next;

   while ((q) && (q<r)) {
      p = q;
      q = q->next;
   }

   /* merge with the following block if possible */
   s = (MemChunk *)(((long)r) + r->size);
   if ((q) && (s >= q)) {
      r->size += q->size;
      q = q->next;
      s->size = 0;
      s->next = NULL;
   }
   r->next = q;

   /* merge with the preceding block if possible, otherwise link it in */
   s = (MemChunk *)(((long)p) + p->size);
   if ((s >= r) && (p != &the_heap)) {
      p->size += r->size;
      p->next = r->next;
      r->size = 0;
      r->next = NULL;
   }
   else
      p->next = r;
}



/* __heap_trace:
 *  Diagnostic routine, prints free memory blocks to stdout.
 */
void __heap_trace()
{
    MemChunk *p = the_heap.next;

    while (p) {
        printf("Free block at 0x%X, size %ld\n", (int)p, p->size);
        p = p->next;
    }
}


/*
 *  Shawn Hargreaves - shawn AT talula DOT demon DOT co DOT uk - http://www.talula.demon.co.uk/
 *  Ghoti: 'gh' as in 'enough', 'o' as in 'women', and 'ti' as in 'nation'.
 */