source: trunk/minix/lib/sysutil/kmalloc.c@ 16

/*      malloc(), realloc(), free() - simple memory allocation routines
 *
 * This is a very small and simple minded malloc        Author: Kees J. Bot
 * implementation.  Ideal for things like a                     29 Jan 1994
 * bootstrap program, or for debugging.  Six times
 * slower than any good malloc.
 */
#define nil 0

#define sbrk _sbrk
#include <stddef.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
#include <limits.h>
#if !DEBUG
#define NDEBUG  1
#define debug(expr)     ((void) 0)
#else
#define debug(expr)     expr
#endif
#include <assert.h>

typedef struct cell {
        size_t          size;           /* Size of a malloc()'ed object. */
#if DEBUG
        unsigned        magic;          /* To recognize a cell. */
#endif
        struct cell     *next;          /* Next cell on the free list. */
#if DEBUG
        unsigned        sacred;         /* Don't touch while unallocated. */
#endif
} cell_t;

#if UINT_MAX <= 0xFFFF
#define MAGIC   0x537B
#else
#define MAGIC   0x537BC0D8
#endif

/* Size of the header of an object. */
#define HDR_SIZE        offsetof(cell_t, next)

/* An offset from a cell pointer to a next cell. */
#define offset(cp, size)        ((cell_t *) ((char *) (cp) + (size)))

/* Address of the object in a cell and back. */
#define cell2obj(cp)            ((void *) ((char *) (cp) + HDR_SIZE))
#define obj2cell(op)            ((cell_t *) ((char *) (op) - HDR_SIZE))

/* The free list. */
static cell_t *freelist;

void *malloc(size_t size)
/* Allocate an object of at least the given size. */
{
        cell_t **pcp, *cp;

        size += HDR_SIZE;
        if (size < sizeof(cell_t)) size= sizeof(cell_t);

        /* Align to a word.  Use a real malloc if you need better alignment. */
        size= (size + sizeof(int) - 1) & ~(sizeof(int) - 1);

        /* Space for a magic number at the end of the chunk. */
        debug(size += sizeof(unsigned));

        for (;;) {
                /* Do a first fit search. */
                pcp= &freelist;
                while ((cp= *pcp) != nil) {
                        cell_t *next= cp->next;

                        assert(cp->magic == MAGIC);
                        assert(cp->sacred == MAGIC);

                        if (offset(cp, cp->size) == next) {
                                /* Join adjacent free cells. */
                                assert(next->magic == MAGIC);
                                assert(next->sacred == MAGIC);

                                cp->size+= next->size;
                                cp->next= next->next;

                                continue;               /* Try again. */
                        }
                        if (size <= cp->size) break;    /* Big enough. */

                        /* Next cell. */
                        pcp= &cp->next;
                }

                if (cp != nil) break;   /* Found a big enough chunk. */

                /* Allocate a new chunk at the break. */
                if ((cp= (cell_t *) sbrk(size)) == (cell_t *) -1) {
                        return nil;
                }

                cp->size= size;
                cp->next= nil;
                debug(cp->magic= MAGIC);
                debug(cp->sacred= MAGIC);
                *pcp= cp;
        }

        /* We've got a cell that is big enough.  Can we break it up? */
        if (cp->size >= size + sizeof(cell_t)) {
                cell_t *next= offset(cp, size);

                next->size= cp->size - size;
                next->next= cp->next;
                debug(next->magic= MAGIC);
                debug(next->sacred= MAGIC);
                cp->size= size;
                cp->next= next;
        }

        /* Unchain the cell we've found and return an address in it. */
        *pcp= cp->next;
        debug(memset(cell2obj(cp), 0xAA, cp->size - HDR_SIZE));
        debug(((unsigned *) offset(cp, cp->size))[-1]= MAGIC);

        return cell2obj(cp);
}

void free(void *op)
/* Deallocate an object. */
{
        cell_t **prev, *next, *cp;

        if (op == nil) return;          /* Aaargh. */

        cp= obj2cell(op);
        assert(cp->magic == MAGIC);
        assert(((unsigned *) offset(cp, cp->size))[-1] == MAGIC);
        debug(cp->sacred= MAGIC);

        /* Find the spot where the object belongs. */
        prev= &freelist;
        while ((next= *prev) != nil && next < cp) {
                assert(next->magic == MAGIC);
                assert(next->sacred == MAGIC);
                prev= &next->next;
        }

        /* Put the new free cell in the list. */
        *prev= cp;
        cp->next= next;

#if DEBUG
        /* Check the rest of the list. */
        while (next != nil) {
                assert(next->magic == MAGIC);
                assert(next->sacred == MAGIC);
                next= next->next;
        }
#endif
}

void *realloc(void *op, size_t size)
/* Change the size of an object.  Don't bother being smart, just copy it. */
{
        size_t oldsize;
        void *new;

        oldsize= op == nil ? 0 : obj2cell(op)->size - HDR_SIZE;

        new= malloc(size);
        memcpy(new, op, oldsize > size ? size : oldsize);
        free(op);
        return new;
}

/*
 * $PchId: malloc.c,v 1.4 1996/02/22 09:15:56 philip Exp $
 */