Reformatted the LGPL notice a little bit.

[mLib] / sub.c

/* -*-c-*-
 *
 * $Id: sub.c,v 1.3 1999/05/06 19:51:35 mdw Exp $
 *
 * Allocation of known-size blocks
 *
 * (c) 1998 Straylight/Edgeware
 */

/*----- Licensing notice --------------------------------------------------* 
 *
 * This file is part of the mLib utilities library.
 *
 * mLib 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.
 * 
 * mLib 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 mLib; if not, write to the Free
 * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
 * MA 02111-1307, USA.
 */

/*----- Revision history --------------------------------------------------*
 *
 * $Log: sub.c,v $
 * Revision 1.3  1999/05/06 19:51:35  mdw
 * Reformatted the LGPL notice a little bit.
 *
 * Revision 1.2  1999/05/05 18:50:31  mdw
 * Change licensing conditions to LGPL.
 *
 * Revision 1.1.1.1  1998/06/17 23:44:42  mdw
 * Initial version of mLib
 *
 */

/*----- The big idea ------------------------------------------------------*
 *
 * This file provides an extra layer over @malloc@.  It provides fast
 * turnover for small blocks, and tries to minimise the per-block overhead.
 *
 * To do its job, @alloc@ must place an extra restriction on you: you must
 * know the size of a block when you free it.  Usually you'll have this
 * information encoded in some way either in the block or in the thing that
 * referenced it, so this isn't a hardship.
 *
 * It works fairly simply.  If a request for a big block (as defined by the
 * constants below) comes in, it gets sent on to @malloc@ unmolested.  For
 * small blocks, it goes straight to a `bin' -- a list containing free blocks
 * of exactly that size, or the nearest bigger size we can manage.  If the
 * bin is empty, a `chunk' is allocated from @malloc@: this has enough room
 * for lots of blocks of the requested size, so it ets split up and each
 * individual small block is added to the bin list.  The first block in the
 * bin list is then removed and given to the caller.  In this way, @malloc@
 * only stores its information once for lots of little blocks, so we save
 * memory.  Because I know where the correct bin is just from the block size,
 * and I don't need to do any searching at all in the usual case (because the
 * list isn't empty) I can get a speed advantage too.
 *
 * This code is almost certainly not ANSI conformant, although I'm not
 * actually sure.  If some kind soul would let me know how seriously I've
 * violated the standard, and whether this is easily fixable, I'd be
 * grateful.
 */

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

/* --- ANSI headers --- */

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

/* --- Local headers --- */

#undef TRACK_ENABLE			/* Can't track suballoc routines */
#include "alloc.h"

/*----- Configuration and tuning ------------------------------------------*/

/* --- The largest block I'll handle here --- *
 *
 * Anything larger will be handed on to @malloc@.
 */

#define SUB_MAXBIN 256

/* --- Preferred chunk size --- *
 *
 * When a bin is empty, I'll allocate a large chunk of approximately this
 * size and divvy it up into small bin-sized blocks.
 */

#define SUB_CHUNK 4096

/*----- Other useful macros -----------------------------------------------*/

/* --- The granularity of bin buffers --- *
 *
 * All blocks allocated by the binner are a multiple of this size.  I've
 * chosen @void *@ because I need to store @void *@ things in here.
 */

#define SUB_GRANULE sizeof(void *)

/* --- Finding the right bin for a given size --- *
 *
 * This chooses the correct bin for an allocation.  Input is the size of
 * block wanted; result is the bin index.
 */

#define SUB_BIN(x) (((x) + SUB_GRANULE - 1) / SUB_GRANULE)

/* --- Convert a bin back to the block size --- *
 *
 * This gives the size of block contained in a given bin.
 */

#define SUB_BINSZ(x) ((x) * SUB_GRANULE)

/* --- Number of bins required --- */

#define SUB_BINS (SUB_MAXBIN / SUB_GRANULE + 1)

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

static void *sub__bins[SUB_BINS];
static size_t sub__sizes[SUB_BINS];

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

/* --- @sub_alloc@ --- *
 *
 * Arguments:   @size_t s@ = size of chunk wanted
 *
 * Returns:     Pointer to a block at least as large as the one wanted.
 *
 * Use:         Allocates a small block of memory.  If there is no more
 *		memory left, the exception @EXC_NOMEM@ is raised.
 */

void *sub_alloc(size_t s)
{
  int bin = SUB_BIN(s);
  void *p;

  /* --- Handle oversize blocks --- */

  if (bin >= SUB_BINS)
    return (xmalloc(s));

  /* --- If the bin is empty, find some memory --- */

  if (!sub__bins[bin]) {
    char *p, *q;

    p = xmalloc(sub__sizes[bin]);
    q = p + sub__sizes[bin];

    s = SUB_BINSZ(bin);

    q -= s;
    *(void **)q = 0;

    while (q > p) {
      q -= s;
      *(void **)q = q + s;
    }

    sub__bins[bin] = p;
  }

  /* --- Extract the first block in the list --- */

  p = sub__bins[bin];
  sub__bins[bin] = *(void **)p;
  return (p);
}

/* --- @sub_free@ --- *
 *
 * Arguments:   @void *p@ = address of block to free
 *              @size_t s@ = size of block
 *
 * Returns:     ---
 *
 * Use:         Frees a block allocated by @sub_alloc@.
 */

void sub_free(void *p, size_t s)
{
  int bin = SUB_BIN(s);

  if (bin >= SUB_BINS)
    free(p);
  else {
    *(void **)p = sub__bins[bin];
    sub__bins[bin] = p;
  }
}

/* --- @sub_init@ --- *
 *
 * Arguments:   ---
 *
 * Returns:     ---
 *
 * Use:         Initialises the magic allocator.
 */

void sub_init(void)
{
  int i;

  /* --- Initialise the sizes bins --- */

  for (i = 1; i < SUB_BINS; i++) {
    sub__sizes[i] = ((SUB_CHUNK + SUB_BINSZ(i) - 1) /
		     SUB_BINSZ(i) * SUB_BINSZ(i));
  }
}

/*----- Debugging code ----------------------------------------------------*/

#ifdef TEST_RIG

#define BLOCKS 1024
#define SIZE_MAX 2048
#define ITERATIONS 500000

int main(void)
{
  static void *block[BLOCKS];
  static size_t size[BLOCKS];
  size_t allocced = 0;
  int i;
  long count;

  sub_init();

  for (count = 0; count < ITERATIONS; count++) {
    i = rand() % BLOCKS;
    if (block[i]) {
      sub_free(block[i], size[i]);
      block[i] = 0;
      allocced -= size[i];
    } else {
      block[i] = sub_alloc(size[i] =
			   rand() % (SUB_MAXBIN - 128) + 128);
      allocced += size[i];
      memset(block[i], 0, size[i]);    /* trample allocated storage */
    }
  }

  return (0);
}

#endif

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