+++ /dev/null
-/* -*-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 <stdio.h>
-#include <stdlib.h>
-#include <string.h>
-
-#include <mLib/arena.h>
-#include <mLib/exc.h>
-#include <mLib/sub.h>
-
-#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 -------------------------------------------------*/
projects / u / mdw / catacomb / blobdiff