Return to alloc.c CVS log

Up to [MW Coherent from dump] / coherent / a / usr / bob / korn

coherent

/*
 * area-based allocation built on malloc/free
 */

static char *RCSid = "$Header";

#include <stddef.h>
#include <stdlib.h>
#include <setjmp.h>
#include "sh.h"

#define	ICELLS	100		/* number of Cells in small Block */

typedef union Cell Cell;
typedef struct Block Block;

/*
 * The Cells in a Block are organized as a set of objects.
 * Each object (pointed to by dp) begins with a size in (dp-1)->size,
 * followed with "size" data Cells.  Free objects are
 * linked together via dp->next.
 */

union Cell {
	size_t	size;
	Cell   *next;
	struct {int _;} junk;	/* alignment */
};

struct Block {
	Block  *next;		/* list of Blocks in Area */
	Cell   *free;		/* object free list */
	Cell   *last;		/* &b.cell[size] */
	Cell	cell [1];	/* [size] Cells for allocation */
};

Block aempty = {&aempty, aempty.cell, aempty.cell};

/* create empty Area */
Area *
ainit(ap)
	register Area *ap;
{
	ap->free = &aempty;
	return ap;
}

/* free all object in Area */
void
afreeall(ap)
	register Area *ap;
{
	register Block *bp;

	if (ap->free == NULL || ap->free == &aempty)
		return;
	for (bp = ap->free; ; bp = bp->next) {
		free((Void*)bp);
		if (bp->next == ap->free)
			break;
	}
	ap->free = &aempty;
}

/* allocate object from Area */
Void *
alloc(size, ap)
	size_t size;
	register Area *ap;
{
	int cells, split;
	register Block *bp;
	register Cell *dp, *fp, *fpp;
#if 0
	mypr("alloc: size %d area x%x\n", size, ap);
#endif
	if (size <= 0) {
		aerror(ap, "allocate bad size");
		return NULL;
	}
	cells = (unsigned)(size - 1) / sizeof(Cell) + 1;

	/* find Cell large enough */
	for (bp = ap->free; ; bp = bp->next) {
		for (fpp = NULL, fp = bp->free;
		     fp != bp->last; fpp = fp, fp = fpp->next)
			if ((fp-1)->size >= cells)
				goto Found;

		/* wrapped around Block list, create new Block */
		if (bp == ap->free) {
			bp = malloc(offsetof(Block, cell[ICELLS + cells]));
			if (bp == NULL) {
				aerror(ap, "cannot allocate");
				return NULL;
			}
			if (ap->free == &aempty)
				bp->next = bp;
			else {
				bp->next = ap->free->next;
				ap->free->next = bp;
			}
			bp->last = bp->cell + ICELLS + cells;
			fp = bp->free = bp->cell + 1; /* initial free list */
			(fp-1)->size = ICELLS + cells - 1;
			fp->next = bp->last;
			fpp = NULL;
			break;
		}
	}
  Found:
	ap->free = bp;
	dp = fp;		/* allocated object */
	split = (dp-1)->size - cells;
	if (split < 0)
		aerror(ap, "allocated object too small");
	if (--split <= 0) {	/* allocate all */
		fp = fp->next;
	} else {		/* allocate head, free tail */
		(fp-1)->size = cells;
		fp += cells + 1;
		(fp-1)->size = split;
		fp->next = dp->next;
	}
	if (fpp == NULL)
		bp->free = fp;
	else
		fpp->next = fp;
	return (Void*) dp;
}

/* change size of object */
/* todo: allow expansion */
Void *
aresize(ptr, size, ap)
	register Void *ptr;
	size_t size;
	register Area *ap;
{
	int cells, split;
	register Cell *dp = (Cell*)ptr;

#if 0
	mypr("aresize: size %d area x%x ptr x%x\n", size, ap, ptr);
#endif
	if (size <= 0) {
		aerror(ap, "allocate bad size");
		return NULL;
	}
	cells = (unsigned)(size - 1) / sizeof(Cell) + 1;

	split = (dp-1)->size - cells;
	if (split < 0)
		aerror(ap, "cannot resize larger");
	if (--split <= 0)	/* cannot split */
		;
	else {			/* shrink head, free tail */
		(dp-1)->size = cells;
		dp += cells + 1;
		(dp-1)->size = split;
		afree((Void*)dp, ap);
	}

	return (Void*) ptr;
}

void
afree(ptr, ap)
	Void *ptr;
	register Area *ap;
{
	register Block *bp;
	register Cell *fp, *fpp;
	register Cell *dp = (Cell*)ptr;

#if 0
	mypr("afree: area x%x ptr x%x\n", ap, ptr);
#endif
	/* find Block containing Cell */
	for (bp = ap->free; ; bp = bp->next) {
		if (bp->cell <= dp && dp < bp->last)
			break;
		if (bp->next == ap->free) {
			aerror(ap, "freeing with invalid area");
			return;
		}
	}

	/* find position in free list */
	for (fpp = NULL, fp = bp->free; fp < dp; fpp = fp, fp = fpp->next)
		;

	if (fp == dp) {
		aerror(ap, "freeing free object");
		return;
	}

	/* join object with next */
	if (dp + (dp-1)->size == fp-1) { /* adjacent */
		(dp-1)->size += (fp-1)->size + 1;
		dp->next = fp->next;
	} else			/* non-adjacent */
		dp->next = fp;

	/* join previous with object */
	if (fpp == NULL)
		bp->free = dp;
	else if (fpp + (fpp-1)->size == dp-1) { /* adjacent */
		(fpp-1)->size += (dp-1)->size + 1;
		fpp->next = dp->next;
	} else			/* non-adjacent */
		fpp->next = dp;
}


#if TEST_ALLOC

Area a;

main(argc, argv)
int argc;
char **argv;
{
	int i;
	char *p [9];

	ainit(&a);
	for (i = 0; i < 9; i++) {
		p[i] = alloc(124, &a);
		printf("alloc: %x\n", p[i]);
	}
	for (i = 1; i < argc; i++)
		afree(p[atoi(argv[i])], &a);
	afreeall(&a);
	return 0;
}

void aerror(ap, msg)
Area *ap;
char *msg;
{
	printf("%r\n", &msg);
	sleep(1);
	abort();
}

#endif

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