X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~mdw/git/mLib/blobdiff_plain/8c6d948bbb87df8f1ffb49d3af1419b84ea34a0e..9dc511e46d5acad665175981f824288062e27671:/sub.c diff --git a/sub.c b/sub.c index bb264a2..a0d4981 100644 --- a/sub.c +++ b/sub.c @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: sub.c,v 1.4 1999/05/13 22:48:55 mdw Exp $ + * $Id: sub.c,v 1.9 2004/04/08 01:36:13 mdw Exp $ * * Allocation of known-size blocks * @@ -27,23 +27,6 @@ * MA 02111-1307, USA. */ -/*----- Revision history --------------------------------------------------* - * - * $Log: sub.c,v $ - * Revision 1.4 1999/05/13 22:48:55 mdw - * Change `-ise' to `-ize' throughout. - * - * Revision 1.3 1999/05/06 19:51:35 mdw - * Reformatted the LGPL notice a little bit. - * - * Revision 1.2 1999/05/05 18:50:31 mdw - * Change licensing conditions to LGPL. - * - * Revision 1.1.1.1 1998/06/17 23:44:42 mdw - * Initial version of mLib - * - */ - /*----- The big idea ------------------------------------------------------* * * This file provides an extra layer over @malloc@. It provides fast @@ -77,138 +60,257 @@ /* --- ANSI headers --- */ +#include #include #include #include /* --- Local headers --- */ -#undef TRACK_ENABLE /* Can't track suballoc routines */ -#include "alloc.h" +#include "arena.h" +#include "exc.h" +#include "sub.h" -/*----- Configuration and tuning ------------------------------------------*/ +/*----- Configuration tweaks ----------------------------------------------*/ -/* --- The largest block I'll handle here --- * - * - * Anything larger will be handed on to @malloc@. - */ +/* #define SUBARENA_TRIVIAL */ -#define SUB_MAXBIN 256 +/*----- Static variables --------------------------------------------------*/ -/* --- Preferred chunk size --- * - * - * When a bin is empty, I'll allocate a large chunk of approximately this - * size and divvy it up into small bin-sized blocks. - */ +static size_t sizes[SUB_BINS]; -#define SUB_CHUNK 4096 +/*----- Global variables --------------------------------------------------*/ -/*----- Other useful macros -----------------------------------------------*/ +subarena sub_global; -/* --- The granularity of bin buffers --- * - * - * All blocks allocated by the binner are a multiple of this size. I've - * chosen @void *@ because I need to store @void *@ things in here. - */ +#ifdef SUBARENA_TRIVIAL + +typedef struct sub_link { + struct sub_link *next; + void *p; + size_t sz; +} sub_link; -#define SUB_GRANULE sizeof(void *) +#endif + +/*----- Main code ---------------------------------------------------------*/ -/* --- Finding the right bin for a given size --- * +/* --- @subarena_create@ --- * + * + * Arguments: @subarena *s@ = pointer to arena to initialize + * @arena *a@ = pointer to underlying arena block + * + * Returns: --- * - * This chooses the correct bin for an allocation. Input is the size of - * block wanted; result is the bin index. + * Use: Initialize a suballocation arena based on an underlying large + * blocks arena. */ -#define SUB_BIN(x) (((x) + SUB_GRANULE - 1) / SUB_GRANULE) +void subarena_create(subarena *s, arena *a) +{ +#ifdef SUBARENA_TRIVIAL + s->bin[0] = 0; +#else + size_t i; + if (!sizes[1]) + sub_init(); + for (i = 0; i < SUB_BINS; i++) + s->bin[i] = 0; +#endif + s->a = a; +} -/* --- Convert a bin back to the block size --- * +/* --- @subarena_destroy@ --- * + * + * Arguments: @subarena *s@ = pointer to arena to destroy + * + * Returns: --- * - * This gives the size of block contained in a given bin. + * Use: Destroys a suballocation arena, freeing all of the memory it + * contains back to the underlying large blocks arena. */ -#define SUB_BINSZ(x) ((x) * SUB_GRANULE) +void subarena_destroy(subarena *s) +{ +#ifdef SUBARENA_TRIVIAL -/* --- Number of bins required --- */ + sub_link *l, *ll; -#define SUB_BINS (SUB_MAXBIN / SUB_GRANULE + 1) + for (l = s->bin[0]; l; l = ll) { + ll = l; + a_free(s->a, l->p); + a_free(s->a, l); + } + s->bin[0] = 0; -/*----- Static variables --------------------------------------------------*/ +#else -static void *sub__bins[SUB_BINS]; -static size_t sub__sizes[SUB_BINS]; + size_t i; + for (i = 0; i < SUB_BINS; i++) { + void *p = s->bin[i]; + while (p) { + void *q = p; + p = *(void **)q; + A_FREE(s->a, q); + } + s->bin[i] = 0; + } -/*----- Main code ---------------------------------------------------------*/ +#endif +} -/* --- @sub_alloc@ --- * +/* --- @subarena_alloc@ --- * * - * Arguments: @size_t s@ = size of chunk wanted + * Arguments: @subarena *s@ = pointer to arena + * @size_t s@ = size of chunk wanted * * Returns: Pointer to a block at least as large as the one wanted. * - * Use: Allocates a small block of memory. If there is no more - * memory left, the exception @EXC_NOMEM@ is raised. + * Use: Allocates a small block of memory from the given pool. The + * exception @EXC_NOMEM@ is raised if the underlying arena is + * full. */ -void *sub_alloc(size_t s) +void *subarena_alloc(subarena *s, size_t sz) { - int bin = SUB_BIN(s); +#ifdef SUBARENA_TRIVIAL + + sub_link *l; void *p; + if (!s->a) + subarena_create(s, arena_global); + + if ((l = a_alloc(s->a, sizeof(*l))) == 0) + return (0); + if ((p = a_alloc(s->a, sz)) == 0) { + a_free(s->a, l); + return (0); + } + l->p = p; + l->sz = sz; + l->next = s->bin[0]; + s->bin[0] = l; + return (p); + +#else + + int bin; + void *p; + + /* --- Ensure that everything is initialized --- */ + + if (!s->a) + subarena_create(s, arena_global); + /* --- Handle oversize blocks --- */ - if (bin >= SUB_BINS) - return (xmalloc(s)); + bin = SUB_BIN(sz); + if (bin >= SUB_BINS) { + void *p = A_ALLOC(s->a, sz); + if (!p) + THROW(EXC_NOMEM); + return (p); + } /* --- If the bin is empty, find some memory --- */ - if (!sub__bins[bin]) { + if (!s->bin[bin]) { char *p, *q; - p = xmalloc(sub__sizes[bin]); - q = p + sub__sizes[bin]; + p = A_ALLOC(s->a, sizes[bin]); + if (!p) + THROW(EXC_NOMEM); + q = p + sizes[bin]; - s = SUB_BINSZ(bin); + sz = SUB_BINSZ(bin); - q -= s; + q -= sz; *(void **)q = 0; while (q > p) { - q -= s; - *(void **)q = q + s; + q -= sz; + *(void **)q = q + sz; } - sub__bins[bin] = p; + s->bin[bin] = p; } /* --- Extract the first block in the list --- */ - p = sub__bins[bin]; - sub__bins[bin] = *(void **)p; + p = s->bin[bin]; + s->bin[bin] = *(void **)p; return (p); + +#endif } -/* --- @sub_free@ --- * +/* --- @subarena_free@ --- * * - * Arguments: @void *p@ = address of block to free + * Arguments: @subarena *s@ = pointer to arena + * @void *p@ = address of block to free * @size_t s@ = size of block * * Returns: --- * - * Use: Frees a block allocated by @sub_alloc@. + * Use: Frees a block allocated by @subarena_alloc@. */ -void sub_free(void *p, size_t s) +void subarena_free(subarena *s, void *p, size_t sz) { - int bin = SUB_BIN(s); +#ifdef SUBARENA_TRIVIAL + + sub_link *lh = s->bin[0], **l, *ll; + + for (l = &lh; *l && (*l)->p != p; l = &(*l)->next) + ; + ll = *l; + assert(ll); + assert(ll->sz == sz); + *l = ll->next; + a_free(s->a, ll); + a_free(s->a, p); + s->bin[0] = lh; + +#else + + int bin = SUB_BIN(sz); if (bin >= SUB_BINS) - free(p); + A_FREE(s->a, p); else { - *(void **)p = sub__bins[bin]; - sub__bins[bin] = p; + *(void **)p = s->bin[bin]; + s->bin[bin] = p; } + +#endif } +/*----- Compatibility stuff -----------------------------------------------*/ + +/* --- @sub_alloc@ --- * + * + * Arguments: @size_t s@ = size of chunk wanted + * + * Returns: Pointer to a block at least as large as the one wanted. + * + * Use: Allocates a small block of memory from the @sub_global@ pool. + */ + +void *(sub_alloc)(size_t sz) { return sub_alloc(sz); } + +/* --- @sub_free@ --- * + * + * Arguments: @void *p@ = address of block to free + * @size_t s@ = size of block + * + * Returns: --- + * + * Use: Frees a block allocated by @sub_alloc@. + */ + +void (sub_free)(void *p, size_t sz) { sub_free(p, sz); } + /* --- @sub_init@ --- * * * Arguments: --- @@ -220,14 +322,16 @@ void sub_free(void *p, size_t s) void sub_init(void) { +#ifndef SUBARENA_TRIVIAL int i; /* --- Initialize the sizes bins --- */ for (i = 1; i < SUB_BINS; i++) { - sub__sizes[i] = ((SUB_CHUNK + SUB_BINSZ(i) - 1) / + sizes[i] = ((SUB_CHUNK + SUB_BINSZ(i) - 1) / SUB_BINSZ(i) * SUB_BINSZ(i)); } +#endif } /*----- Debugging code ----------------------------------------------------*/