chiark - git - mdw - catacomb/blob - math/mparena.c

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