Generic interface.

[u/mdw/catacomb] / mparena.c

/* -*-c-*-
 *
 * $Id: mparena.c,v 1.3 1999/11/22 13:58:00 mdw Exp $
 *
 * Allocation and freeing of MP buffers
 *
 * (c) 1999 Straylight/Edgeware
 */

/*----- Licensing notice --------------------------------------------------* 
 *
 * This file is part of Catacomb.
 *
 * Catacomb is free software; you can redistribute it and/or modify
 * it under the terms of the GNU Library General Public License as
 * published by the Free Software Foundation; either version 2 of the
 * License, or (at your option) any later version.
 * 
 * Catacomb is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Library General Public License for more details.
 * 
 * You should have received a copy of the GNU Library General Public
 * License along with Catacomb; if not, write to the Free
 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
 * MA 02111-1307, USA.
 */

/*----- Revision history --------------------------------------------------* 
 *
 * $Log: mparena.c,v $
 * Revision 1.3  1999/11/22 13:58:00  mdw
 * Document the tweakables.
 *
 * Revision 1.2  1999/11/21 22:14:19  mdw
 * Fix bug.  Improve diagnostic capabilities.
 *
 * Revision 1.1  1999/11/17 18:02:16  mdw
 * New multiprecision integer arithmetic suite.
 *
 */

/*----- Header files ------------------------------------------------------*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include <mLib/alloc.h>
#include <mLib/sub.h>

#include "mparena.h"

/*----- Tweakables --------------------------------------------------------*/

/* --- @MPARENA_TRIVIAL@ --- *
 *
 * Make the allocator a passthrough.  It immediately calls the underlying
 * allocation functions rather than attempting to keep track of blocks
 * itself.
 */

/* #define MPARENA_TRIVIAL */

/* --- @MPARENA_DEBUG@ --- *
 *
 * The name of an output trace file to which logging information about the
 * state of arena trees should be written.  If unset, no logging is done.
 */

/* #define MPARENA_DEBUG "mparena.out" */

/*----- Default allocator -------------------------------------------------*/

static void *defalloc(mparena *a, size_t sz) { return xmalloc(sz); }
static void deffree(mparena *a, void *p) { free(p); }

mparena_ops mparena_defops = { defalloc, deffree };

/*----- Static variables --------------------------------------------------*/

#ifdef MPARENA_DEBUG
  static FILE *debugfp = 0;

#  define MPARENA_OPENFILE do {						\
    if (!debugfp) {							\
      if ((debugfp = fopen(MPARENA_DEBUG, "w")) == 0) {			\
	fprintf(stderr, "couldn't open debug output file\n");		\
	exit(EXIT_FAILURE);						\
      }									\
    }									\
  } while (0)

#endif

static mparena arena = { 0, &mparena_defops };

#define MPARENA_RESOLVE(a) do {						\
  if ((a) == MPARENA_GLOBAL)						\
    (a) = &arena;							\
} while (0)

/*----- Main code ---------------------------------------------------------*/

/* --- @tdump@ --- *
 *
 * Arguments:	@mparena_node *n@ = pointer to tree node to dump
 *
 * Returns:	---
 *
 * Use:		Recursively dumps out the allocation tree.
 */

#ifdef MPARENA_DEBUG

static void tdump(mparena_node *n)
{
  if (!n)
    putc('*', debugfp);
  else {
    putc('(', debugfp);
    tdump(n->left);
    fprintf(debugfp, ", %u, ", n->v[0]);
    tdump(n->right);
    putc(')', debugfp);
  }
}

#endif

/* --- @mparena_create@ --- *
 *
 * Arguments:	@mparena *a@ = pointer to arena block
 *
 * Returns:	---
 *
 * Use:		Initializes an MP arena so that blocks can be allocated from
 *		it.
 */

void mparena_create(mparena *a)
{
  a->root = 0;
  a->ops = &mparena_defops;
}

/* --- @mparena_setops@ --- *
 *
 * Arguments:	@mparena *a@ = pointer to arena block
 *		@mparena_ops *ops@ = pointer to operations block or null
 *
 * Returns:	The previous operations block.
 *
 * Use:		Sets or queries the operations attached to an arena.
 */

mparena_ops *mparena_setops(mparena *a, mparena_ops *ops)
{
  mparena_ops *o;
  MPARENA_RESOLVE(a);
  o = a->ops;
  if (ops)
    a->ops = ops;
  return (0);
}

/* --- @mparena_destroy@ --- *
 *
 * Arguments:	@mparena *a@ = pointer to arena block
 *
 * Returns:	---
 *
 * Use:		Frees an MP arena, and all the vectors held within it.  The
 *		blocks which are currently allocated can be freed into some
 *		other arena.
 */

static void tfree(mparena *a, mparena_node *n)
{
  a->ops->free(a, n->v);
  if (n->left)
    tfree(a, n->left);
  if (n->right)
    tfree(a, n->right);
  DESTROY(n);
}

void mparena_destroy(mparena *a)
{
  tfree(a, a->root);
  a->root = 0;
}

/* --- @mpalloc@ --- *
 *
 * Arguments:	@mparena *a@ = pointer to arena block
 *		@size_t sz@ = number of digits required
 *
 * Returns:	Pointer to a suitably sized block.
 *
 * Use:		Allocates a lump of data suitable for use as an array of MP
 *		digits.
 */

#ifdef MPARENA_TRIVIAL

mpw *mpalloc(mparena *a, size_t sz)
{
  MPARENA_RESOLVE(a);
  return (a->ops->alloc(a, MPWS(sz)));
}

#else

mpw *mpalloc(mparena *a, size_t sz)
{
  mparena_node **nn, *n;
  mpw *v;

  MPARENA_RESOLVE(a);
  nn = &a->root;

#ifdef MPARENA_DEBUG
  MPARENA_OPENFILE;
  fprintf(debugfp, "alloc %u\n  before: ", sz);
  tdump(a->root); putc('\n', debugfp);
  if (sz == 0)
    asm("nop");
#endif

  /* --- First, find a block which is big enough --- */

again:
  n = *nn;
  if (!n) {
#ifdef MPARENA_DEBUG
    fputs("  failed\n", debugfp);
#endif
    v = a->ops->alloc(a, MPWS(sz + 1));
    v[0] = sz;
    return (v + 1);
  }
  if (n->v[0] < sz) {
    nn = &n->right;
    goto again;
  }

  /* --- Now try to find a smaller block which is suitable --- */

  while (n->left && n->left->v[0] >= sz) {
    nn = &n->left;
    n = *nn;
  }

  /* --- If the block we've got is still too large, start digging --- */

  if (n->v[0] > sz * 2) {
    nn = &n->left;
    goto again;
  }

  /* --- I've now found a suitable block --- */

  v = n->v;

  /* --- Remove this node from the tree --- */

  if (!n->left)
    *nn = n->right;
  else if (!n->right)
    *nn = n->left;
  else {
    mparena_node *left = n->left;
    mparena_node *p = *nn = n->right;
    while (p->left)
      p = p->left;
    p->left = left;
  }

#ifdef MPARENA_DEBUG
  fputs("  after: ", debugfp);
  tdump(a->root); putc('\n', debugfp);
#endif

  /* --- Get rid of this node now --- */

  DESTROY(n);
  return (v + 1);
}

#endif

/* --- @mpfree@ --- *
 *
 * Arguments:	@mparena *a@ = pointer to arena block
 *		@mpw *v@ = pointer to allocated vector
 *
 * Returns:	---
 *
 * Use:		Returns an MP vector to an arena.  It doesn't have to be
 *		returned to the arena from which it was allocated.
 */

#ifdef MPARENA_TRIVIAL

void mpfree(mparena *a, mpw *v)
{
  MPARENA_RESOLVE(a);
  a->ops->free(a, v);
}

#else

void mpfree(mparena *a, mpw *v)
{
  mparena_node **nn, *n;
  size_t sz = *--v;

  MPARENA_RESOLVE(a);

#ifdef MPARENA_DEBUG
  MPARENA_OPENFILE;
  fprintf(debugfp, "free %u\n  before: ", sz);
  tdump(a->root); putc('\n', debugfp);
#endif

  nn = &a->root;
  while (*nn) {
    n = *nn;
    if (n->v[0] > sz)
      nn = &n->left;
    else
      nn = &n->right;
  }

  n = CREATE(mparena_node);
  n->left = n->right = 0;
  n->v = v;
  *nn = n;

#ifdef MPARENA_DEBUG
  fputs("  after: ", debugfp);
  tdump(a->root); putc('\n', debugfp);
#endif
}

#endif

/*----- That's all, folks -------------------------------------------------*/