--- /dev/null
+/* -*-c-*-
+ *
+ * $Id: mparena.c,v 1.1 1999/11/17 18:02:16 mdw Exp $
+ *
+ * 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.
+ */
+
+/*----- Revision history --------------------------------------------------*
+ *
+ * $Log: mparena.c,v $
+ * Revision 1.1 1999/11/17 18:02:16 mdw
+ * New multiprecision integer arithmetic suite.
+ *
+ */
+
+/*----- Header files ------------------------------------------------------*/
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include <mLib/alloc.h>
+#include <mLib/sub.h>
+
+#include "mparena.h"
+
+/*----- Default allocator -------------------------------------------------*/
+
+static void *defalloc(mparena *a, size_t sz) { return xmalloc(sz); }
+static void deffree(mparena *a, void *p) { free(p); }
+
+mparena_ops mparena_defops = { defalloc, deffree };
+
+/*----- Static variables --------------------------------------------------*/
+
+static mparena arena = { 0, &mparena_defops };
+
+#define MPARENA_RESOLVE(a) do { \
+ if ((a) == MPARENA_GLOBAL) \
+ (a) = &arena; \
+} while (0)
+
+/*----- Main code ---------------------------------------------------------*/
+
+/* --- @tdump@ --- *
+ *
+ * Arguments: @mparena_node *n@ = pointer to tree node to dump
+ *
+ * Returns: ---
+ *
+ * Use: Recursively dumps out the allocation tree.
+ */
+
+static void tdump(mparena_node *n)
+{
+ if (!n)
+ putchar('*');
+ else {
+ putchar('(');
+ tdump(n->left);
+ printf(", %u, ", n->v[0]);
+ tdump(n->right);
+ putchar(')');
+ }
+}
+
+/* --- @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->ops = &mparena_defops;
+}
+
+/* --- @mparena_setops@ --- *
+ *
+ * Arguments: @mparena *a@ = pointer to arena block
+ * @mparena_ops *ops@ = pointer to operations block or null
+ *
+ * Returns: The previous operations block.
+ *
+ * Use: Sets or queries the operations attached to an arena.
+ */
+
+mparena_ops *mparena_setops(mparena *a, mparena_ops *ops)
+{
+ mparena_ops *o;
+ MPARENA_RESOLVE(a);
+ o = a->ops;
+ if (ops)
+ a->ops = ops;
+ return (0);
+}
+
+/* --- @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->ops->free(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;
+}
+
+/* --- @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.
+ */
+
+mpw *mpalloc(mparena *a, size_t sz)
+{
+ mparena_node **nn, *n;
+ mpw *v;
+
+ MPARENA_RESOLVE(a);
+ nn = &a->root;
+
+#ifdef notdef
+ printf("*** alloc %u\n", sz);
+ tdump(a->root); putchar('\n');
+#endif
+
+ /* --- First, find a block which is big enough --- */
+
+again:
+ n = *nn;
+ if (!n) {
+ v = a->ops->alloc(a, MPWS(sz + 1));
+ v[0] = sz;
+ 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;
+ }
+
+ /* --- Get rid of this node now --- */
+
+ DESTROY(n);
+ return (v + 1);
+}
+
+/* --- @mpfree@ --- *
+ *
+ * Arguments: @mparena *a@ = pointer to arena block
+ * @mpw *v@ = pointer to allocated vector
+ *
+ * Returns: ---
+ *
+ * Use: Returns an MP vector to an arena. It doesn't have to be
+ * returned to the arena from which it was allocated.
+ */
+
+void mpfree(mparena *a, mpw *v)
+{
+ mparena_node **nn, *n;
+ size_t sz = *--v;
+
+ MPARENA_RESOLVE(a);
+ 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;
+
+#ifdef notdef
+ printf("*** free %u\n", sz);
+ tdump(a->root); putchar('\n');
+#endif
+}
+
+/*----- That's all, folks -------------------------------------------------*/
projects / u / mdw / catacomb / blobdiff