git.distorted.org.uk Git - u/mdw/catacomb/blob - mparena.c

   1 /* -*-c-*-
   2  *
   3  * $Id: mparena.c,v 1.2 1999/11/21 22:14:19 mdw Exp $
   4  *
   5  * Allocation and freeing of MP buffers
   6  *
   7  * (c) 1999 Straylight/Edgeware
   8  */
   9
  10 /*----- Licensing notice --------------------------------------------------*
  11  *
  12  * This file is part of Catacomb.
  13  *
  14  * Catacomb is free software; you can redistribute it and/or modify
  15  * it under the terms of the GNU Library General Public License as
  16  * published by the Free Software Foundation; either version 2 of the
  17  * License, or (at your option) any later version.
  18  *
  19  * Catacomb is distributed in the hope that it will be useful,
  20  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  21  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  22  * GNU Library General Public License for more details.
  23  *
  24  * You should have received a copy of the GNU Library General Public
  25  * License along with Catacomb; if not, write to the Free
  26  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  27  * MA 02111-1307, USA.
  28  */
  29
  30 /*----- Revision history --------------------------------------------------*
  31  *
  32  * $Log: mparena.c,v $
  33  * Revision 1.2  1999/11/21 22:14:19  mdw
  34  * Fix bug.  Improve diagnostic capabilities.
  35  *
  36  * Revision 1.1  1999/11/17 18:02:16  mdw
  37  * New multiprecision integer arithmetic suite.
  38  *
  39  */
  40
  41 /*----- Header files ------------------------------------------------------*/
  42
  43 #include <stdio.h>
  44 #include <stdlib.h>
  45 #include <string.h>
  46
  47 #include <mLib/alloc.h>
  48 #include <mLib/sub.h>
  49
  50 #include "mparena.h"
  51
  52 /*----- Tweakables --------------------------------------------------------*/
  53
  54 /* #define MPARENA_TRIVIAL */
  55
  56 /* #define MPARENA_DEBUG "mparena.out" */
  57
  58 /*----- Default allocator -------------------------------------------------*/
  59
  60 static void *defalloc(mparena *a, size_t sz) { return xmalloc(sz); }
  61 static void deffree(mparena *a, void *p) { free(p); }
  62
  63 mparena_ops mparena_defops = { defalloc, deffree };
  64
  65 /*----- Static variables --------------------------------------------------*/
  66
  67 #ifdef MPARENA_DEBUG
  68   static FILE *debugfp = 0;
  69
  70 #  define MPARENA_OPENFILE do {                                         \
  71     if (!debugfp) {                                                     \
  72       if ((debugfp = fopen(MPARENA_DEBUG, "w")) == 0) {                 \
  73         fprintf(stderr, "couldn't open debug output file\n");           \
  74         exit(EXIT_FAILURE);                                             \
  75       }                                                                 \
  76     }                                                                   \
  77   } while (0)
  78
  79 #endif
  80
  81 static mparena arena = { 0, &mparena_defops };
  82
  83 #define MPARENA_RESOLVE(a) do {                                         \
  84   if ((a) == MPARENA_GLOBAL)                                            \
  85     (a) = &arena;                                                       \
  86 } while (0)
  87
  88 /*----- Main code ---------------------------------------------------------*/
  89
  90 /* --- @tdump@ --- *
  91  *
  92  * Arguments:   @mparena_node *n@ = pointer to tree node to dump
  93  *
  94  * Returns:     ---
  95  *
  96  * Use:         Recursively dumps out the allocation tree.
  97  */
  98
  99 #ifdef MPARENA_DEBUG
 100
 101 static void tdump(mparena_node *n)
 102 {
 103   if (!n)
 104     putc('*', debugfp);
 105   else {
 106     putc('(', debugfp);
 107     tdump(n->left);
 108     fprintf(debugfp, ", %u, ", n->v[0]);
 109     tdump(n->right);
 110     putc(')', debugfp);
 111   }
 112 }
 113
 114 #endif
 115
 116 /* --- @mparena_create@ --- *
 117  *
 118  * Arguments:   @mparena *a@ = pointer to arena block
 119  *
 120  * Returns:     ---
 121  *
 122  * Use:         Initializes an MP arena so that blocks can be allocated from
 123  *              it.
 124  */
 125
 126 void mparena_create(mparena *a)
 127 {
 128   a->root = 0;
 129   a->ops = &mparena_defops;
 130 }
 131
 132 /* --- @mparena_setops@ --- *
 133  *
 134  * Arguments:   @mparena *a@ = pointer to arena block
 135  *              @mparena_ops *ops@ = pointer to operations block or null
 136  *
 137  * Returns:     The previous operations block.
 138  *
 139  * Use:         Sets or queries the operations attached to an arena.
 140  */
 141
 142 mparena_ops *mparena_setops(mparena *a, mparena_ops *ops)
 143 {
 144   mparena_ops *o;
 145   MPARENA_RESOLVE(a);
 146   o = a->ops;
 147   if (ops)
 148     a->ops = ops;
 149   return (0);
 150 }
 151
 152 /* --- @mparena_destroy@ --- *
 153  *
 154  * Arguments:   @mparena *a@ = pointer to arena block
 155  *
 156  * Returns:     ---
 157  *
 158  * Use:         Frees an MP arena, and all the vectors held within it.  The
 159  *              blocks which are currently allocated can be freed into some
 160  *              other arena.
 161  */
 162
 163 static void tfree(mparena *a, mparena_node *n)
 164 {
 165   a->ops->free(a, n->v);
 166   if (n->left)
 167     tfree(a, n->left);
 168   if (n->right)
 169     tfree(a, n->right);
 170   DESTROY(n);
 171 }
 172
 173 void mparena_destroy(mparena *a)
 174 {
 175   tfree(a, a->root);
 176   a->root = 0;
 177 }
 178
 179 /* --- @mpalloc@ --- *
 180  *
 181  * Arguments:   @mparena *a@ = pointer to arena block
 182  *              @size_t sz@ = number of digits required
 183  *
 184  * Returns:     Pointer to a suitably sized block.
 185  *
 186  * Use:         Allocates a lump of data suitable for use as an array of MP
 187  *              digits.
 188  */
 189
 190 #ifdef MPARENA_TRIVIAL
 191
 192 mpw *mpalloc(mparena *a, size_t sz)
 193 {
 194   MPARENA_RESOLVE(a);
 195   return (a->ops->alloc(a, MPWS(sz)));
 196 }
 197
 198 #else
 199
 200 mpw *mpalloc(mparena *a, size_t sz)
 201 {
 202   mparena_node **nn, *n;
 203   mpw *v;
 204
 205   MPARENA_RESOLVE(a);
 206   nn = &a->root;
 207
 208 #ifdef MPARENA_DEBUG
 209   MPARENA_OPENFILE;
 210   fprintf(debugfp, "alloc %u\n  before: ", sz);
 211   tdump(a->root); putc('\n', debugfp);
 212   if (sz == 0)
 213     asm("nop");
 214 #endif
 215
 216   /* --- First, find a block which is big enough --- */
 217
 218 again:
 219   n = *nn;
 220   if (!n) {
 221 #ifdef MPARENA_DEBUG
 222     fputs("  failed\n", debugfp);
 223 #endif
 224     v = a->ops->alloc(a, MPWS(sz + 1));
 225     v[0] = sz;
 226     return (v + 1);
 227   }
 228   if (n->v[0] < sz) {
 229     nn = &n->right;
 230     goto again;
 231   }
 232
 233   /* --- Now try to find a smaller block which is suitable --- */
 234
 235   while (n->left && n->left->v[0] >= sz) {
 236     nn = &n->left;
 237     n = *nn;
 238   }
 239
 240   /* --- If the block we've got is still too large, start digging --- */
 241
 242   if (n->v[0] > sz * 2) {
 243     nn = &n->left;
 244     goto again;
 245   }
 246
 247   /* --- I've now found a suitable block --- */
 248
 249   v = n->v;
 250
 251   /* --- Remove this node from the tree --- */
 252
 253   if (!n->left)
 254     *nn = n->right;
 255   else if (!n->right)
 256     *nn = n->left;
 257   else {
 258     mparena_node *left = n->left;
 259     mparena_node *p = *nn = n->right;
 260     while (p->left)
 261       p = p->left;
 262     p->left = left;
 263   }
 264
 265 #ifdef MPARENA_DEBUG
 266   fputs("  after: ", debugfp);
 267   tdump(a->root); putc('\n', debugfp);
 268 #endif
 269
 270   /* --- Get rid of this node now --- */
 271
 272   DESTROY(n);
 273   return (v + 1);
 274 }
 275
 276 #endif
 277
 278 /* --- @mpfree@ --- *
 279  *
 280  * Arguments:   @mparena *a@ = pointer to arena block
 281  *              @mpw *v@ = pointer to allocated vector
 282  *
 283  * Returns:     ---
 284  *
 285  * Use:         Returns an MP vector to an arena.  It doesn't have to be
 286  *              returned to the arena from which it was allocated.
 287  */
 288
 289 #ifdef MPARENA_TRIVIAL
 290
 291 void mpfree(mparena *a, mpw *v)
 292 {
 293   MPARENA_RESOLVE(a);
 294   a->ops->free(a, v);
 295 }
 296
 297 #else
 298
 299 void mpfree(mparena *a, mpw *v)
 300 {
 301   mparena_node **nn, *n;
 302   size_t sz = *--v;
 303
 304   MPARENA_RESOLVE(a);
 305
 306 #ifdef MPARENA_DEBUG
 307   MPARENA_OPENFILE;
 308   fprintf(debugfp, "free %u\n  before: ", sz);
 309   tdump(a->root); putc('\n', debugfp);
 310 #endif
 311
 312   nn = &a->root;
 313   while (*nn) {
 314     n = *nn;
 315     if (n->v[0] > sz)
 316       nn = &n->left;
 317     else
 318       nn = &n->right;
 319   }
 320
 321   n = CREATE(mparena_node);
 322   n->left = n->right = 0;
 323   n->v = v;
 324   *nn = n;
 325
 326 #ifdef MPARENA_DEBUG
 327   fputs("  after: ", debugfp);
 328   tdump(a->root); putc('\n', debugfp);
 329 #endif
 330 }
 331
 332 #endif
 333
 334 /*----- That's all, folks -------------------------------------------------*/