X-Git-Url: https://git.distorted.org.uk/u/mdw/catacomb/blobdiff_plain/ba6e6b64033b1f9de49feccb5c9cd438354481f7..0f00dc4c8eb47e67bc0f148c2dd109f73a451e0a:/mparena.c diff --git a/mparena.c b/mparena.c deleted file mode 100644 index c726912..0000000 --- a/mparena.c +++ /dev/null @@ -1,340 +0,0 @@ -/* -*-c-*- - * - * $Id$ - * - * 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 -------------------------------------------------*/