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

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