Return to aq.c CVS log

Up to [CSRG BSD Unix] / 43BSD / contrib / apl / src

Annotation of 43BSD/contrib/apl/src/aq.c, revision 1.1

1.1     ! root        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: }

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.