BSD 4_3 release

[unix-history] / usr / contrib / apl / src / aq.c

static char Sccsid[] = "aq.c @(#)aq.c   1.1     10/1/82 Berkeley ";
/*
*      malloc/free/afreset -- dynamic memory allocation
*
*
* This source file is a slight modificattion of the alloc/free system
* described by Kernighan and Ritchie in "The C Programming Language",
* pp. 174-177.
*
* The modifications include allocation by a bestfit (rather than
* firstfit) strategy, and ability to reset memory completely.
*/

/* NOTE: the "afnfree" and "afnused" values are not precise.  They
* do not currently refect the allocation and release of headers.
* This will be changed soon (I hope).
* --J. Bruner
*/


#define NULL    0               /* null value */
#ifndef vax
#define NALLOC  128             /* # of units requested on each "sbrk" */
#else
#define NALLOC  1024            /* lots of memory each time for vaxes */
#endif

typedef int     ALIGN;          /* force alignment on PDP-11 and VAX */

union header {                          /* free block header structure */
       struct {
               union header *ptr;      /* next free block */
               unsigned size;          /* size of this free block */
       } s;
       ALIGN x;                        /* force alignment of blocks */
};


typedef union header HEADER;


static HEADER base;                     /* empty list to get started */
static HEADER *allocp = NULL;           /* last allocated block */

int aftrace = 0;
int afnfree, afnused;


char *
malloc(nbytes)
unsigned nbytes;
{
       HEADER *morecore();
       register HEADER *p, *q;
       register HEADER *rp;
       HEADER *rq;
       register unsigned nunits;

       /* malloc is a general-purpose memory allocator.  It is called
        * with the desired number of bytes, expressed as an unsigned
        * integer, and it returns the address of the allocated memory.
        * If "aftrace" is non-zero, a trace of the allocation will
        * be printed.  If it is not possible to alloate what is
        * requested, the error "workspace exceeded" will result.
        *
        * This routine was originally called "alloc" but was changed
        * to "malloc" because an increasing number of library routines
        * perform dynamic memory allocation.  A macro in "apl.h"
        * converts calls on "alloc" to calls on "malloc".
        */

       nunits = 1+(nbytes+sizeof(HEADER)-1)/sizeof(HEADER);
       if ((q=allocp) == NULL){
               base.s.ptr = allocp = q = &base;        /* start list */
               base.s.size = 0;
       }


       /* Search list for smallest free block */

       rp = NULL;
       for(p=q->s.ptr;;q=p, p=p->s.ptr){
               while(1){
                       if (p->s.size >= nunits){
                               if ((!rp) || p->s.size < rp->s.size){
                                       rp = p;
                                       rq = q;
                               }
                               if (p->s.size == nunits) break;
                       }

                       if (p == allocp)
                               break;

                       q = p;
                       p = p->s.ptr;
               }

               if (rp) break;
               if ((p=morecore(nunits)) == NULL)
                       error("workspace exceeded");
       }



       /* Allocate memory as needed */

       if (rp->s.size == nunits)
               rq->s.ptr = rp->s.ptr;
       else {
               rp->s.size -= nunits;
               rp += rp->s.size;
               rp->s.size = nunits;
       }
       allocp = rq;

       if (aftrace)
               printf("[alloc: %d at %o]\n",
                       (int)nunits*sizeof(HEADER), rp);

       afnfree -= nunits;
       afnused += nunits;
       return((char *)(rp+1));
}


static HEADER *
morecore(nu)
unsigned nu;
{
       char *sbrk();
       register char *cp;
       register HEADER *up;
       register int rnu;

       /* Ask system for more memory.  Requests are made in blocks
        * of NALLOC header units.  Returns NULL if request fails,
        * "allocp" on success.
        */

       rnu = NALLOC * ((nu+NALLOC-1) / NALLOC);
       cp = sbrk(rnu * sizeof(HEADER));
       if ((int)cp == -1)
               return(NULL);                   /* no more space */

       if (aftrace)
               printf("[morecore: %d at %o]\n", rnu*sizeof(HEADER),
                       cp);

       up = (HEADER *)cp;
       up->s.size = rnu;
       free((char *)(up+1));
       return(allocp);
}


free(ap)
char *ap;
{
       register HEADER *p, *q;
       register unsigned fsize;


       /* Put block into free list.  Used by "morecore" to put a newly-
        * allocated block of memory into the freelist -- also used to
        * return a previously allocated block to the freelist.
        */

       p = (HEADER *)ap - 1;           /* point to header */
       fsize = p->s.size;

       for (q=allocp; !(p > q && p < q->s.ptr); q=q->s.ptr)
               if (q >= q->s.ptr && (p > q || p < q->s.ptr))
                       break;

       if (p+p->s.size == q->s.ptr){   /* join to upper nbr */
               p->s.size += q->s.ptr->s.size;
               p->s.ptr = q->s.ptr->s.ptr;
       } else
               p->s.ptr = q->s.ptr;

       if (q+q->s.size == p){          /* join to lower nbr */
               q->s.size += p->s.size;
               q->s.ptr = p->s.ptr;
       } else
               q->s.ptr = p;

       allocp = q;

       afnfree += fsize;
       afnused -= fsize;
       if (aftrace)
               printf("[free: %d at %o]\n", fsize*sizeof(HEADER),  ap);

}


afreset(){

       extern end;

       /* Zap all dynamic allocation by resettting the lists and
        * releasing all additional memory.
        */

       allocp = NULL;
       brk((char *)&end);
       afnfree = afnused = 0;
       if (aftrace)
               printf("[afreset: dynamic allocation released]\n");

}