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

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