_A SIMPLE HANDLE-BASED MEMORY MANAGER_
by David Betz

[LISTING ONE]

/* hmm.h - definitions for a simple handle based memory manager */

typedef char **HANDLE;

/* heap header structure */
typedef struct heaphdr {
    int hh_nhandles;    /* number of handles */
    char *hh_next;  /* next free location */
    char *hh_base;  /* base of heap memory */
    char *hh_top;   /* top of heap memory */
    HANDLE hh_handles;  /* base of handle array */
} HEAPHDR;

HEAPHDR *NewHeap(int,int);
void FreeHeap(HEAPHDR *);
HANDLE HeapAlloc(HEAPHDR *,int);
void HeapFree(HEAPHDR *,HANDLE);



[LISTING TWO]

/* hmm.c - a simple handle based memory manager  -- by David Betz */

#include <stdio.h>
#include "hmm.h"

/* number of handles to add when expanding the handle table */
#define HINC    32

/* block prefix structure */
typedef struct blockpfx {
    HANDLE bp_handle;   /* handle for this block */
} BLOCKPFX;

/* block suffix structure */
typedef struct blocksfx {
    int bs_size;    /* size of block */
} BLOCKSFX;

static HANDLE FindMemory(HEAPHDR *,HANDLE,int);
static HANDLE NewHandle(HEAPHDR *);
static HANDLE UnusedHandle(HEAPHDR *);
static void ExpandHandleTable(HEAPHDR *,int);
static void CompactHeap(HEAPHDR *);

/* NewHeap - allocate and initialize a new heap */
HEAPHDR *NewHeap(nhandles,nbytes)
  int nhandles;     /* initial number of handles */
  int nbytes;       /* initial number of free bytes */
{
    char *malloc();
    HEAPHDR *h;
    int tsize;
    HANDLE p;
    tsize = nhandles * sizeof(char *);
    if ((h = (HEAPHDR *)malloc(sizeof(HEAPHDR) + tsize + nbytes)) == NULL)
    return (NULL);
    h->hh_nhandles = nhandles;
    h->hh_handles = p = (HANDLE)((char *)h + sizeof(HEAPHDR));
    while (--nhandles >= 0) *p++ = NULL;
    h->hh_base = (char *)h->hh_handles + tsize;
    h->hh_top = h->hh_base + nbytes;
    h->hh_next = h->hh_top;
    return (h);
}

/* FreeHeap - free a heap allocated by NewHeap() */
void FreeHeap(h)
  HEAPHDR *h;       /* heap to free */
{
    free(h);
}

/* HeapAlloc - allocate a block of memory from the heap */
HANDLE HeapAlloc(h,size)
  HEAPHDR *h;       /* the heap */
  int size;     /* size of block to allocate */
{
    HANDLE p;
    if ((p = NewHandle(h)) == NULL)
    return (NULL);
    return (FindMemory(h,p,size));
}

/* HeapFree - free a block of memory allocated by HeapAlloc() */
void HeapFree(h,p)
  HEAPHDR *h;       /* the heap */
  HANDLE p;     /* the handle to free */
{
    BLOCKPFX *bp;
    bp = (BLOCKPFX *)(*p - sizeof(BLOCKPFX));
    bp->bp_handle = NULL;
    *p = NULL;
}

static HANDLE NewHandle(h)
  HEAPHDR *h;       /* the heap */
{
    HANDLE p;
    if ((p = UnusedHandle(h)) == NULL)
    ExpandHandleTable(h,HINC);
    return (UnusedHandle(h));
}

static HANDLE UnusedHandle(h)
  HEAPHDR *h;       /* the heap */
{
    HANDLE p;
    int n;
    for (p = h->hh_handles, n = h->hh_nhandles; --n >= 0; ++p)
    if (*p == NULL)
        return (p);
    return (NULL);
}

static void ExpandHandleTable(h,n)
  HEAPHDR *h;       /* the heap */
  int n;        /* number of handles to add */
{
    char *base;
    HANDLE p;
    CompactHeap(h);
    base = h->hh_base + (n * sizeof(char *));
    if (base <= h->hh_next) {
    p = (HANDLE)h->hh_base;
    h->hh_base = base;
    h->hh_nhandles += n;
    while (--n >= 0)
        *p++ = NULL;
    }
}

static HANDLE FindMemory(h,p,size)
  HEAPHDR *h;       /* the heap */
  HANDLE p;     /* the handle to allocate space for */
  int size;     /* size of block to allocate */
{
    BLOCKPFX *bp;
    BLOCKSFX *bs;
    int tsize;
    char *d;
    tsize = sizeof(BLOCKPFX) + size + sizeof(BLOCKSFX);
    if ((d = h->hh_next - tsize) < h->hh_base) {
    CompactHeap(h);
    if ((d = h->hh_next - tsize) < h->hh_base)
        return (NULL);
    }
    h->hh_next = d;
    bp = (BLOCKPFX *)d;
    bp->bp_handle = p;
    d += sizeof(BLOCKPFX);
    bs = (BLOCKSFX *)(d + size);
    bs->bs_size = size;
    *p = d;
    return (p);
}

static void CompactHeap(h)
  HEAPHDR *h;       /* the heap */
{
    char *src,*dst;
    BLOCKPFX *hp;
    BLOCKSFX *hs;
    src = dst = h->hh_top;
    while (src > h->hh_next) {
    hs = (BLOCKSFX *)(src - sizeof(BLOCKSFX));
    hp = (BLOCKPFX *)((char *)hs - hs->bs_size - sizeof(BLOCKPFX));
    if (hp->bp_handle) {
        if (src == dst)
        src = dst = (char *)hp;
        else {
        while (src > (char *)hp)
            *--dst = *--src;
        *hp->bp_handle = dst + sizeof(BLOCKPFX);
        }
    }
    else
        src = (char *)hp;
    }
    h->hh_next = dst;
}



[LISTING THREE]


OFILES=hmmtest.obj hmm.obj

hmmtest.exe:    $(OFILES)
    cl $(OFILES)



[LISTING FOUR]

#include <stdio.h>
#include "hmm.h"

HANDLE allocshow(int);
void showheap(void);
void pause(void);

#define HMAX    100

HEAPHDR *h;
HANDLE handles[HMAX];

main()
{
    int i;

    /* allocate a heap */
    h = NewHeap(16,4096);
    showheap();
    pause();

    /* allocate a bunch of blocks of memory from the heap */
    printf("Allocating...\n");
    for (i = 0; i < HMAX; ++i) {
    printf("%2d: ",i);
    handles[i] = allocshow(32);
    sprintf(*handles[i],"%d",i);    /* put something in the block */
    putchar('\n');
    }

    /* show the state of the heap after the allocations */
    showheap();
    pause();

    /* free every other block (to test the compaction algorithm) */
    printf("Deallocating...\n");
    for (i = 0; i < HMAX; i += 2)
    HeapFree(h,handles[i]);

    /* show the state of the heap after the deallocations */
    showheap();
    pause();

    /* now reallocate the blocks we freed (causes compaction) */
    printf("Reallocating...\n");
    for (i = 0; i < HMAX; i += 2) {
    printf("%2d: ",i);
    handles[i] = allocshow(32);
    sprintf(*handles[i],"%d",i);
    putchar('\n');
    }

    /* show the state of the heap after the new allocations */
    showheap();
    pause();

    /* make sure all of the blocks contain what we expect */
    printf("Checking...\n");
    for (i = 0; i < HMAX; ++i) {
    printf("%2d: %04x->%04x=",i,handles[i],*handles[i]);
    printf("%s",*handles[i]);
    if (atoi(*handles[i]) != i)
        printf(" *** ERROR");
    putchar('\n');
    }

    /* free the heap and exit */
    FreeHeap(h);
}

HANDLE allocshow(size)
  int size;
{
    HANDLE p;
    if (p = HeapAlloc(h,size))
    printf("%04x->%04x",p,*p);
    return (p);
}

void pause()
{
    while (getchar() != '\n')
    ;
}

void showheap()
{
    printf("nhandles: %d\n",h->hh_nhandles);
    printf("handles:  %04x\n",h->hh_handles);
    printf("base:     %04x\n",h->hh_base);
    printf("next:     %04x\n",h->hh_next);
    printf("top:      %04x\n",h->hh_top);
}