--- /dev/null
+/* -*-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 <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