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

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