Programmer 7500/MAX_PROGRAMMERS.iso/INFO/C/DLIBSSRC.ZIP/MALLOC.C

C/C++ Source or Header | 1987-10-02 | 4.6 KB | 182 lines

#include <osbind.h>
#include <stdio.h>
#include <malloc.h>

#define    MAXBLK        16
#define    FREE        0x00
#define    USED        0x80
#define    NULLBLK        0x80000000L

char    *_mblk[MAXBLK] = {        /* system memory heaps */
    NULL, NULL, NULL, NULL,
    NULL, NULL, NULL, NULL,
    NULL, NULL, NULL, NULL,
    NULL, NULL, NULL, NULL };

long    _msiz[MAXBLK] = {        /* allocated heap sizes */
    0L, 0L, 0L, 0L,
    0L, 0L, 0L, 0L,
    0L, 0L, 0L, 0L,
    0L, 0L, 0L, 0L };

/*
 *    Up to 16 heaps are allocated from the operating system as they are
 *    needed to fill requests for dynamic memory.  These heaps are them
 *    divided into blocks for parcelling out by the user-callable memory
 *    allocation routines.  If all the storage in a heap is freed, the heap
 *    will be freed to the OS.  Each heap beings with a pointer to the first
 *    free block, or NULL if there are no free blocks in this heap.  Each
 *    block begins with a 4-byte header which defines the number of bytes
 *    in the block, including the header.  Since blocks in a heap are known
 *    to be contiguous, this value also defines the beginning of the next
 *    block in the heap.  The high bit of the header is set if the block
 *    is used and clear if it is free.  The heaps ends with a block header
 *    which indicates a used block containing 0 bytes.  The is the constant
 *    value NULLBLK.  Free blocks contain an additional pointer field,
 *    immediatly following the header, which is a pointer to the header of
 *    the next free block, or NULL.
 */

static char *makeblk(size)
long size;
/*
 *    Get a new major block from the system that will hold at least
 *    <size> bytes.
 */
{
    register int i;
    register char *p;
    register long n, minsiz, bsiz, *q;

    minsiz = (size + 0x200L) & ~0x1FFL;    /* round up to nearest 512 */
    if(minsiz < _BLKSIZ)
        bsiz = _BLKSIZ;
    else
        bsiz = minsiz;
    for(i=0; i<MAXBLK; ++i) {
        if(_mblk[i] != NULL)
            continue;        /* skip used heaps */
        n = Malloc(-1L);
        n = ~0x1FFL & (n - 512L);    /* system memory available */
        if(n < bsiz) {
            if(n < minsiz)
                return(NULL);
            else
                bsiz = minsiz;
        }
        _mblk[i] = p = Malloc(bsiz);
        _msiz[i] = bsiz;
        q = p + bsiz;            /* thread starting blocks */
        q[-1] = NULLBLK;
        q = p + 4L;
        q[-1] = q;
        q[0] = bsiz - 8L;
        q[1] = NULL;
        p[4] = FREE;
        return(p);
    }
    return(NULL);
}

static char *splitblk(addr, size)
register long **addr;
register long size;
/*
 *    Split block at *<addr> into a used block containing <size> bytes
 *    and a free block containing the remainder.
 */
{
    register long n, *p, *q;

    n = *(p = *addr);            /* get actual block size */
    if(n > (size + 8L)) {            /* is it worth splitting? */
        n -= size;
        q = ((char *) p) + size;    /* calculate "break" point */
        p[0] = size;
        q[0] = n;
        q[1] = p[1];
        *addr = q;
    }
    else                    /* not worth splitting */
        *addr = p[1];            /* remove from free list */
    *((char *) p) = USED;            /* mark block "used" */
    return(p);
}

static char *findblk(size)
register long size;
/*
 *    Find the smallest unused block containing at least <size> bytes.
 */
{
    register int i;
    register long n, tsiz = 0x7FFFFFFFL, **p, *q, *tptr = NULL;

    for(i=0; i<MAXBLK; ++i) {
        if((p = _mblk[i]) == NULL)
            continue;        /* skip unavailable heaps */
        while(q = *p) {
            n = *q;
            if((n >= size) && (n < tsiz)) {        /* it fits */
                tsiz = n;
                tptr = p;
            }
            p = q + 1;
        }
    }
    return(tptr);
}

/*--------------------- Documented Functions ---------------------------*/

char *lalloc(size)
register long size;
/*
 *    Allocate at least <size> bytes of memory.  A pointer to the
 *    requested block is returned, or NULL if there is not enough
 *    free memory available.
 */
{
    register char *p;

    if (size <= 4L)
        size = 8L;            /* minimum allocation */
    else
        size = (size + 5L) & ~1L;    /* header & alignment */
    if((p = findblk(size)) == NULL)
        if((p = makeblk(size)) == NULL)
            return(NULL);
    p = splitblk(p, size);
    return(p + 4);            /* skip over header */
}

char *malloc(size)
unsigned int size;
/*
 *    Allocate at least <size> bytes of memory.  A pointer to the
 *    requested block is returned, or NULL if there is not enough
 *    free memory available.
 */
{
    return(lalloc((long) size));
}

char *calloc(n, size)
unsigned int n;
unsigned int size;
/*
 *    Allocate space for an array of <n> element of <size> bytes each.
 *    If the storage can be allocated, it is initialized to all zero.
 *    NULL is returned is there is not enough free memory.
 */
{
    register long total;
    register char *p, *q;

    total = (((long) n) * ((long) size));
    if(p = lalloc(total))
        for(q=p; total--; *q++ = 0)
            ;
    return(p);
}