2.11BSD#431 - /usr/src/new/PORT/apl/src/aq.c

   1: static char Sccsid[] = "aq.c @(#)aq.c	1.1	10/1/82 Berkeley ";
   2: /*
   3:  *      malloc/free/afreset -- dynamic memory allocation
   4:  *
   5:  *
   6:  * This source file is a slight modificattion of the alloc/free system
   7:  * described by Kernighan and Ritchie in "The C Programming Language",
   8:  * pp. 174-177.
   9:  *
  10:  * The modifications include allocation by a bestfit (rather than
  11:  * firstfit) strategy, and ability to reset memory completely.
  12:  */
  13: 
  14: /* NOTE: the "afnfree" and "afnused" values are not precise.  They
  15:  * do not currently refect the allocation and release of headers.
  16:  * This will be changed soon (I hope).
  17:  * --J. Bruner
  18:  */
  19: 
  20: 
  21: #define NULL    0               /* null value */
  22: #ifndef vax
  23: #define NALLOC  128             /* # of units requested on each "sbrk" */
  24: #else
  25: #define NALLOC  1024        /* lots of memory each time for vaxes */
  26: #endif
  27: 
  28: typedef int     ALIGN;          /* force alignment on PDP-11 and VAX */
  29: 
  30: union header {                          /* free block header structure */
  31:     struct {
  32:         union header *ptr;      /* next free block */
  33:         unsigned size;          /* size of this free block */
  34:     } s;
  35:     ALIGN x;                        /* force alignment of blocks */
  36: };
  37: 
  38: 
  39: typedef union header HEADER;
  40: 
  41: 
  42: static HEADER base;                     /* empty list to get started */
  43: static HEADER *allocp = NULL;           /* last allocated block */
  44: 
  45: int aftrace = 0;
  46: int afnfree, afnused;
  47: 
  48: 
  49: char *
  50: malloc(nbytes)
  51: unsigned nbytes;
  52: {
  53:     HEADER *morecore();
  54:     register HEADER *p, *q;
  55:     register HEADER *rp;
  56:     HEADER *rq;
  57:     register unsigned nunits;
  58: 
  59:     /* malloc is a general-purpose memory allocator.  It is called
  60: 	 * with the desired number of bytes, expressed as an unsigned
  61: 	 * integer, and it returns the address of the allocated memory.
  62: 	 * If "aftrace" is non-zero, a trace of the allocation will
  63: 	 * be printed.  If it is not possible to alloate what is
  64: 	 * requested, the error "workspace exceeded" will result.
  65: 	 *
  66: 	 * This routine was originally called "alloc" but was changed
  67: 	 * to "malloc" because an increasing number of library routines
  68: 	 * perform dynamic memory allocation.  A macro in "apl.h"
  69: 	 * converts calls on "alloc" to calls on "malloc".
  70: 	 */
  71: 
  72:     nunits = 1+(nbytes+sizeof(HEADER)-1)/sizeof(HEADER);
  73:     if ((q=allocp) == NULL){
  74:         base.s.ptr = allocp = q = &base;        /* start list */
  75:         base.s.size = 0;
  76:     }
  77: 
  78: 
  79:     /* Search list for smallest free block */
  80: 
  81:     rp = NULL;
  82:     for(p=q->s.ptr;;q=p, p=p->s.ptr){
  83:         while(1){
  84:             if (p->s.size >= nunits){
  85:                 if ((!rp) || p->s.size < rp->s.size){
  86:                     rp = p;
  87:                     rq = q;
  88:                 }
  89:                 if (p->s.size == nunits) break;
  90:             }
  91: 
  92:             if (p == allocp)
  93:                 break;
  94: 
  95:             q = p;
  96:             p = p->s.ptr;
  97:         }
  98: 
  99:         if (rp) break;
 100:         if ((p=morecore(nunits)) == NULL)
 101:             error("workspace exceeded");
 102:     }
 103: 
 104: 
 105: 
 106:     /* Allocate memory as needed */
 107: 
 108:     if (rp->s.size == nunits)
 109:         rq->s.ptr = rp->s.ptr;
 110:     else {
 111:         rp->s.size -= nunits;
 112:         rp += rp->s.size;
 113:         rp->s.size = nunits;
 114:     }
 115:     allocp = rq;
 116: 
 117:     if (aftrace)
 118:         printf("[alloc: %d at %o]\n",
 119:             (int)nunits*sizeof(HEADER), rp);
 120: 
 121:     afnfree -= nunits;
 122:     afnused += nunits;
 123:     return((char *)(rp+1));
 124: }
 125: 
 126: 
 127: static HEADER *
 128: morecore(nu)
 129: unsigned nu;
 130: {
 131:     char *sbrk();
 132:     register char *cp;
 133:     register HEADER *up;
 134:     register int rnu;
 135: 
 136:     /* Ask system for more memory.  Requests are made in blocks
 137: 	 * of NALLOC header units.  Returns NULL if request fails,
 138: 	 * "allocp" on success.
 139: 	 */
 140: 
 141:     rnu = NALLOC * ((nu+NALLOC-1) / NALLOC);
 142:     cp = sbrk(rnu * sizeof(HEADER));
 143:     if ((int)cp == -1)
 144:         return(NULL);                   /* no more space */
 145: 
 146:     if (aftrace)
 147:         printf("[morecore: %d at %o]\n", rnu*sizeof(HEADER),
 148:             cp);
 149: 
 150:     up = (HEADER *)cp;
 151:     up->s.size = rnu;
 152:     free((char *)(up+1));
 153:     return(allocp);
 154: }
 155: 
 156: 
 157: free(ap)
 158: char *ap;
 159: {
 160:     register HEADER *p, *q;
 161:     register unsigned fsize;
 162: 
 163: 
 164:     /* Put block into free list.  Used by "morecore" to put a newly-
 165: 	 * allocated block of memory into the freelist -- also used to
 166: 	 * return a previously allocated block to the freelist.
 167: 	 */
 168: 
 169:     p = (HEADER *)ap - 1;           /* point to header */
 170:     fsize = p->s.size;
 171: 
 172:     for (q=allocp; !(p > q && p < q->s.ptr); q=q->s.ptr)
 173:         if (q >= q->s.ptr && (p > q || p < q->s.ptr))
 174:             break;
 175: 
 176:     if (p+p->s.size == q->s.ptr){   /* join to upper nbr */
 177:         p->s.size += q->s.ptr->s.size;
 178:         p->s.ptr = q->s.ptr->s.ptr;
 179:     } else
 180:         p->s.ptr = q->s.ptr;
 181: 
 182:     if (q+q->s.size == p){          /* join to lower nbr */
 183:         q->s.size += p->s.size;
 184:         q->s.ptr = p->s.ptr;
 185:     } else
 186:         q->s.ptr = p;
 187: 
 188:     allocp = q;
 189: 
 190:     afnfree += fsize;
 191:     afnused -= fsize;
 192:     if (aftrace)
 193:         printf("[free: %d at %o]\n", fsize*sizeof(HEADER),  ap);
 194: 
 195: }
 196: 
 197: 
 198: afreset(){
 199: 
 200:     extern end;
 201: 
 202:     /* Zap all dynamic allocation by resettting the lists and
 203: 	 * releasing all additional memory.
 204: 	 */
 205: 
 206:     allocp = NULL;
 207:     brk((char *)&end);
 208:     afnfree = afnused = 0;
 209:     if (aftrace)
 210:         printf("[afreset: dynamic allocation released]\n");
 211: 
 212: }

Defined functions

Defined variables

Defined union's

Defined typedef's

Defined macros