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

   1 /* -*-c-*-
   2  *
   3  * $Id: mparena.c,v 1.6 2004/04/03 03:32:05 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.6  2004/04/03 03:32:05  mdw
  34  * General robustification.
  35  *
  36  * Revision 1.5  2000/06/17 11:35:48  mdw
  37  * Overhaul to use mLib's arena system underneath.
  38  *
  39  * Revision 1.4  1999/12/10 23:28:52  mdw
  40  * Memory allocation counting.
  41  *
  42  * Revision 1.3  1999/11/22 13:58:00  mdw
  43  * Document the tweakables.
  44  *
  45  * Revision 1.2  1999/11/21 22:14:19  mdw
  46  * Fix bug.  Improve diagnostic capabilities.
  47  *
  48  * Revision 1.1  1999/11/17 18:02:16  mdw
  49  * New multiprecision integer arithmetic suite.
  50  *
  51  */
  52
  53 /*----- Header files ------------------------------------------------------*/
  54
  55 #include <stdio.h>
  56 #include <stdlib.h>
  57 #include <string.h>
  58
  59 #include <mLib/arena.h>
  60 #include <mLib/exc.h>
  61 #include <mLib/sub.h>
  62
  63 #include "mparena.h"
  64
  65 /*----- Tweakables --------------------------------------------------------*/
  66
  67 /* --- @MPARENA_TRIVIAL@ --- *
  68  *
  69  * Make the allocator a passthrough.  It immediately calls the underlying
  70  * allocation functions rather than attempting to keep track of blocks
  71  * itself.
  72  */
  73
  74 /* #define MPARENA_TRIVIAL */
  75
  76 /* --- @MPARENA_DEBUG@ --- *
  77  *
  78  * The name of an output trace file to which logging information about the
  79  * state of arena trees should be written.  If unset, no logging is done.
  80  */
  81
  82 /* #define MPARENA_DEBUG "mparena.out" */
  83
  84 /*----- Static variables --------------------------------------------------*/
  85
  86 #ifdef MPARENA_DEBUG
  87   static FILE *debugfp = 0;
  88
  89 #  define MPARENA_OPENFILE do {                                         \
  90     if (!debugfp) {                                                     \
  91       if ((debugfp = fopen(MPARENA_DEBUG, "w")) == 0) {                 \
  92         fprintf(stderr, "couldn't open debug output file\n");           \
  93         exit(EXIT_FAILURE);                                             \
  94       }                                                                 \
  95     }                                                                   \
  96   } while (0)
  97
  98 #endif
  99
 100 /*----- Standard arenas ---------------------------------------------------*/
 101
 102 mparena mparena_global = MPARENA_INIT;
 103 mparena mparena_secure = MPARENA_INIT;
 104
 105 /*----- Main code ---------------------------------------------------------*/
 106
 107 /* --- @tdump@ --- *
 108  *
 109  * Arguments:   @mparena_node *n@ = pointer to tree node to dump
 110  *
 111  * Returns:     ---
 112  *
 113  * Use:         Recursively dumps out the allocation tree.
 114  */
 115
 116 #ifdef MPARENA_DEBUG
 117
 118 static void tdump(mparena_node *n)
 119 {
 120   if (!n)
 121     putc('*', debugfp);
 122   else {
 123     putc('(', debugfp);
 124     tdump(n->left);
 125     fprintf(debugfp, ", %u, ", n->v[0]);
 126     tdump(n->right);
 127     putc(')', debugfp);
 128   }
 129 }
 130
 131 #endif
 132
 133 /* --- @mparena_create@ --- *
 134  *
 135  * Arguments:   @mparena *a@ = pointer to arena block
 136  *
 137  * Returns:     ---
 138  *
 139  * Use:         Initializes an MP arena so that blocks can be allocated from
 140  *              it.
 141  */
 142
 143 void mparena_create(mparena *a)
 144 {
 145   a->root = 0;
 146   a->n = 0;
 147   a->a = &arena_stdlib;
 148 }
 149
 150 /* --- @mparena_setarena@ --- *
 151  *
 152  * Arguments:   @mparena *a@ = pointer to MP arena block
 153  *              @arena *aa@ = pointer to arena
 154  *
 155  * Returns:     ---
 156  *
 157  * Use:         Sets the underlying arena for an MP arena.
 158  */
 159
 160 extern void mparena_setarena(mparena *a, arena *aa) { a->a = aa; }
 161
 162 /* --- @mparena_destroy@ --- *
 163  *
 164  * Arguments:   @mparena *a@ = pointer to arena block
 165  *
 166  * Returns:     ---
 167  *
 168  * Use:         Frees an MP arena, and all the vectors held within it.  The
 169  *              blocks which are currently allocated can be freed into some
 170  *              other arena.
 171  */
 172
 173 static void tfree(mparena *a, mparena_node *n)
 174 {
 175   A_FREE(a->a, n->v);
 176   if (n->left)
 177     tfree(a, n->left);
 178   if (n->right)
 179     tfree(a, n->right);
 180   DESTROY(n);
 181 }
 182
 183 void mparena_destroy(mparena *a)
 184 {
 185   tfree(a, a->root);
 186   a->root = 0;
 187 }
 188
 189 /* --- @mparena_count@ --- *
 190  *
 191  * Arguments:   @mparena *a@ = pointer to arena block
 192  *
 193  * Returns:     Number of allocated blocks from this arena.
 194  *
 195  * Use:         Reports the number of blocks allocated from the arena and not
 196  *              yet freed.
 197  */
 198
 199 unsigned mparena_count(mparena *a)
 200 {
 201   return (a->n);
 202 }
 203
 204 /* --- @mpalloc@ --- *
 205  *
 206  * Arguments:   @mparena *a@ = pointer to arena block
 207  *              @size_t sz@ = number of digits required
 208  *
 209  * Returns:     Pointer to a suitably sized block.
 210  *
 211  * Use:         Allocates a lump of data suitable for use as an array of MP
 212  *              digits.
 213  */
 214
 215 #ifdef MPARENA_TRIVIAL
 216
 217 mpw *mpalloc(mparena *a, size_t sz)
 218 {
 219   mpw *v;
 220   if (!sz) return (0);
 221   a->n++;
 222   v = A_ALLOC(a->a, MPWS(sz));
 223   if (!v)
 224     THROW(EXC_NOMEM);
 225   return (v);
 226 }
 227
 228 #else
 229
 230 mpw *mpalloc(mparena *a, size_t sz)
 231 {
 232   mparena_node **nn, *n;
 233   mpw *v;
 234
 235   nn = &a->root;
 236
 237 #ifdef MPARENA_DEBUG
 238   MPARENA_OPENFILE;
 239   fprintf(debugfp, "alloc %u\n  before: ", sz);
 240   tdump(a->root); putc('\n', debugfp);
 241 #endif
 242
 243   /* --- First, find a block which is big enough --- */
 244
 245 again:
 246   n = *nn;
 247   if (!n) {
 248 #ifdef MPARENA_DEBUG
 249     fputs("  failed\n", debugfp);
 250 #endif
 251     if ((v = A_ALLOC(a->a, MPWS(sz + 1))) == 0)
 252       THROW(EXC_NOMEM);
 253     v[0] = sz;
 254     a->n++;
 255     return (v + 1);
 256   }
 257   if (n->v[0] < sz) {
 258     nn = &n->right;
 259     goto again;
 260   }
 261
 262   /* --- Now try to find a smaller block which is suitable --- */
 263
 264   while (n->left && n->left->v[0] >= sz) {
 265     nn = &n->left;
 266     n = *nn;
 267   }
 268
 269   /* --- If the block we've got is still too large, start digging --- */
 270
 271   if (n->v[0] > sz * 2) {
 272     nn = &n->left;
 273     goto again;
 274   }
 275
 276   /* --- I've now found a suitable block --- */
 277
 278   v = n->v;
 279
 280   /* --- Remove this node from the tree --- */
 281
 282   if (!n->left)
 283     *nn = n->right;
 284   else if (!n->right)
 285     *nn = n->left;
 286   else {
 287     mparena_node *left = n->left;
 288     mparena_node *p = *nn = n->right;
 289     while (p->left)
 290       p = p->left;
 291     p->left = left;
 292   }
 293
 294 #ifdef MPARENA_DEBUG
 295   fputs("  after: ", debugfp);
 296   tdump(a->root); putc('\n', debugfp);
 297 #endif
 298
 299   /* --- Get rid of this node now --- */
 300
 301   DESTROY(n);
 302   a->n++;
 303   return (v + 1);
 304 }
 305
 306 #endif
 307
 308 /* --- @mpfree@ --- *
 309  *
 310  * Arguments:   @mparena *a@ = pointer to arena block
 311  *              @mpw *v@ = pointer to allocated vector
 312  *
 313  * Returns:     ---
 314  *
 315  * Use:         Returns an MP vector to an arena.
 316  */
 317
 318 #ifdef MPARENA_TRIVIAL
 319
 320 void mpfree(mparena *a, mpw *v)
 321 {
 322   if (!v) return;
 323   a->n--;
 324   A_FREE(a->a, v);
 325 }
 326
 327 #else
 328
 329 void mpfree(mparena *a, mpw *v)
 330 {
 331   mparena_node **nn, *n;
 332   size_t sz = *--v;
 333
 334 #ifdef MPARENA_DEBUG
 335   MPARENA_OPENFILE;
 336   fprintf(debugfp, "free %u\n  before: ", sz);
 337   tdump(a->root); putc('\n', debugfp);
 338 #endif
 339
 340   nn = &a->root;
 341   while (*nn) {
 342     n = *nn;
 343     if (n->v[0] > sz)
 344       nn = &n->left;
 345     else
 346       nn = &n->right;
 347   }
 348
 349   n = CREATE(mparena_node);
 350   n->left = n->right = 0;
 351   n->v = v;
 352   *nn = n;
 353   a->n--;
 354
 355 #ifdef MPARENA_DEBUG
 356   fputs("  after: ", debugfp);
 357   tdump(a->root); putc('\n', debugfp);
 358 #endif
 359 }
 360
 361 #endif
 362
 363 /*----- That's all, folks -------------------------------------------------*/