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

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