X-Git-Url: https://git.distorted.org.uk/u/mdw/catacomb/blobdiff_plain/ba6e6b64033b1f9de49feccb5c9cd438354481f7..0f00dc4c8eb47e67bc0f148c2dd109f73a451e0a:/math/mparena.c diff --git a/math/mparena.c b/math/mparena.c new file mode 100644 index 0000000..bbe5867 --- /dev/null +++ b/math/mparena.c @@ -0,0 +1,338 @@ +/* -*-c-*- + * + * Allocation and freeing of MP buffers + * + * (c) 1999 Straylight/Edgeware + */ + +/*----- Licensing notice --------------------------------------------------* + * + * This file is part of Catacomb. + * + * Catacomb is free software; you can redistribute it and/or modify + * it under the terms of the GNU Library General Public License as + * published by the Free Software Foundation; either version 2 of the + * License, or (at your option) any later version. + * + * Catacomb is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU Library General Public License for more details. + * + * You should have received a copy of the GNU Library General Public + * License along with Catacomb; if not, write to the Free + * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, + * MA 02111-1307, USA. + */ + +/*----- Header files ------------------------------------------------------*/ + +#include +#include +#include + +#include +#include +#include + +#include "mparena.h" + +/*----- Tweakables --------------------------------------------------------*/ + +/* --- @MPARENA_TRIVIAL@ --- * + * + * Make the allocator a passthrough. It immediately calls the underlying + * allocation functions rather than attempting to keep track of blocks + * itself. + */ + +#define MPARENA_TRIVIAL + +/* --- @MPARENA_DEBUG@ --- * + * + * The name of an output trace file to which logging information about the + * state of arena trees should be written. If unset, no logging is done. + */ + +/* #define MPARENA_DEBUG "mparena.out" */ + +/*----- Static variables --------------------------------------------------*/ + +#ifdef MPARENA_DEBUG + static FILE *debugfp = 0; + +# define MPARENA_OPENFILE do { \ + if (!debugfp) { \ + if ((debugfp = fopen(MPARENA_DEBUG, "w")) == 0) { \ + fprintf(stderr, "couldn't open debug output file\n"); \ + exit(EXIT_FAILURE); \ + } \ + } \ + } while (0) + +#endif + +/*----- Standard arenas ---------------------------------------------------*/ + +mparena mparena_global = MPARENA_INIT; +mparena mparena_secure = MPARENA_INIT; + +/*----- Main code ---------------------------------------------------------*/ + +/* --- @tdump@ --- * + * + * Arguments: @mparena_node *n@ = pointer to tree node to dump + * + * Returns: --- + * + * Use: Recursively dumps out the allocation tree. + */ + +#ifdef MPARENA_DEBUG + +static void tdump(mparena_node *n) +{ + if (!n) + putc('*', debugfp); + else { + putc('(', debugfp); + tdump(n->left); + fprintf(debugfp, ", %u, ", n->v[0]); + tdump(n->right); + putc(')', debugfp); + } +} + +#endif + +/* --- @mparena_create@ --- * + * + * Arguments: @mparena *a@ = pointer to arena block + * + * Returns: --- + * + * Use: Initializes an MP arena so that blocks can be allocated from + * it. + */ + +void mparena_create(mparena *a) +{ + a->root = 0; + a->n = 0; + a->a = &arena_stdlib; +} + +/* --- @mparena_setarena@ --- * + * + * Arguments: @mparena *a@ = pointer to MP arena block + * @arena *aa@ = pointer to arena + * + * Returns: --- + * + * Use: Sets the underlying arena for an MP arena. + */ + +extern void mparena_setarena(mparena *a, arena *aa) { a->a = aa; } + +/* --- @mparena_destroy@ --- * + * + * Arguments: @mparena *a@ = pointer to arena block + * + * Returns: --- + * + * Use: Frees an MP arena, and all the vectors held within it. The + * blocks which are currently allocated can be freed into some + * other arena. + */ + +static void tfree(mparena *a, mparena_node *n) +{ + A_FREE(a->a, n->v); + if (n->left) + tfree(a, n->left); + if (n->right) + tfree(a, n->right); + DESTROY(n); +} + +void mparena_destroy(mparena *a) +{ + tfree(a, a->root); + a->root = 0; +} + +/* --- @mparena_count@ --- * + * + * Arguments: @mparena *a@ = pointer to arena block + * + * Returns: Number of allocated blocks from this arena. + * + * Use: Reports the number of blocks allocated from the arena and not + * yet freed. + */ + +unsigned mparena_count(mparena *a) +{ + return (a->n); +} + +/* --- @mpalloc@ --- * + * + * Arguments: @mparena *a@ = pointer to arena block + * @size_t sz@ = number of digits required + * + * Returns: Pointer to a suitably sized block. + * + * Use: Allocates a lump of data suitable for use as an array of MP + * digits. + */ + +#ifdef MPARENA_TRIVIAL + +mpw *mpalloc(mparena *a, size_t sz) +{ + mpw *v; + if (!sz) return (0); + a->n++; + v = A_ALLOC(a->a, MPWS(sz)); + if (!v) + THROW(EXC_NOMEM); + return (v); +} + +#else + +mpw *mpalloc(mparena *a, size_t sz) +{ + mparena_node **nn, *n; + mpw *v; + + nn = &a->root; + +#ifdef MPARENA_DEBUG + MPARENA_OPENFILE; + fprintf(debugfp, "alloc %u\n before: ", sz); + tdump(a->root); putc('\n', debugfp); +#endif + + /* --- First, find a block which is big enough --- */ + +again: + n = *nn; + if (!n) { +#ifdef MPARENA_DEBUG + fputs(" failed\n", debugfp); +#endif + if ((v = A_ALLOC(a->a, MPWS(sz + 1))) == 0) + THROW(EXC_NOMEM); + v[0] = sz; + a->n++; + return (v + 1); + } + if (n->v[0] < sz) { + nn = &n->right; + goto again; + } + + /* --- Now try to find a smaller block which is suitable --- */ + + while (n->left && n->left->v[0] >= sz) { + nn = &n->left; + n = *nn; + } + + /* --- If the block we've got is still too large, start digging --- */ + + if (n->v[0] > sz * 2) { + nn = &n->left; + goto again; + } + + /* --- I've now found a suitable block --- */ + + v = n->v; + + /* --- Remove this node from the tree --- */ + + if (!n->left) + *nn = n->right; + else if (!n->right) + *nn = n->left; + else { + mparena_node *left = n->left; + mparena_node *p = *nn = n->right; + while (p->left) + p = p->left; + p->left = left; + } + +#ifdef MPARENA_DEBUG + fputs(" after: ", debugfp); + tdump(a->root); putc('\n', debugfp); +#endif + + /* --- Get rid of this node now --- */ + + DESTROY(n); + a->n++; + return (v + 1); +} + +#endif + +/* --- @mpfree@ --- * + * + * Arguments: @mparena *a@ = pointer to arena block + * @mpw *v@ = pointer to allocated vector + * + * Returns: --- + * + * Use: Returns an MP vector to an arena. + */ + +#ifdef MPARENA_TRIVIAL + +void mpfree(mparena *a, mpw *v) +{ + if (!v) return; + a->n--; + A_FREE(a->a, v); +} + +#else + +void mpfree(mparena *a, mpw *v) +{ + mparena_node **nn, *n; + size_t sz = *--v; + +#ifdef MPARENA_DEBUG + MPARENA_OPENFILE; + fprintf(debugfp, "free %u\n before: ", sz); + tdump(a->root); putc('\n', debugfp); +#endif + + nn = &a->root; + while (*nn) { + n = *nn; + if (n->v[0] > sz) + nn = &n->left; + else + nn = &n->right; + } + + n = CREATE(mparena_node); + n->left = n->right = 0; + n->v = v; + *nn = n; + a->n--; + +#ifdef MPARENA_DEBUG + fputs(" after: ", debugfp); + tdump(a->root); putc('\n', debugfp); +#endif +} + +#endif + +/*----- That's all, folks -------------------------------------------------*/