New program to make fixed tables for universal hashing.

[mLib] / sub.h

/* -*-c-*-
 *
 * $Id: sub.h,v 1.7 2003/10/12 14:44:46 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.h,v $
 * Revision 1.7  2003/10/12 14:44:46  mdw
 * Various fixes.
 *
 * Revision 1.6  2000/06/17 10:35:51  mdw
 * Major overhaul for arena support.
 *
 * Revision 1.5  1999/12/10 23:42:04  mdw
 * Change header file guard names.
 *
 * Revision 1.4  1999/05/13 22:48:55  mdw
 * Change `-ise' to `-ize' throughout.
 *
 * 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
 *
 */

#ifndef MLIB_SUB_H
#define MLIB_SUB_H

#ifdef __cplusplus
  extern "C" {
#endif

/*----- Required header files ---------------------------------------------*/

#include <stdlib.h>

#ifndef MLIB_ALIGN_H
#  include "align.h"
#endif

#ifndef MLIB_ARENA_H
#  include "arena.h"
#endif

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

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

#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.
 */

#define SUB_GRANULE sizeof(union align)

/* --- 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)

/*----- Data structures ---------------------------------------------------*/

typedef struct subarena {
  arena *a;
  void *bin[SUB_BINS];
} subarena;

/*----- Global variables --------------------------------------------------*/

extern subarena sub_global;

/*----- Functions provided ------------------------------------------------*/

/* --- @subarena_create@ --- *
 *
 * Arguments:	@subarena *s@ = pointer to arena to initialize
 *		@arena *a@ = pointer to underlying arena block
 *
 * Returns:	---
 *
 * Use:		Initialize a suballocation arena based on an underlying large
 *		blocks arena.
 */

extern void subarena_create(subarena */*s*/, arena */*a*/);

/* --- @subarena_destroy@ --- *
 *
 * Arguments:	@subarena *s@ = pointer to arena to destroy
 *
 * Returns:	---
 *
 * Use:		Destroys a suballocation arena, freeing all of the memory it
 *		contains back to the underlying large blocks arena.
 */

extern void subarena_destroy(subarena */*s*/);

/* --- @subarena_alloc@ --- *
 *
 * Arguments:	@subarena *s@ = pointer to arena
 *		@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 from the given pool.  The
 *		exception @EXC_NOMEM@ is raised if the underlying arena is
 *		full.
 */

extern void *subarena_alloc(subarena */*s*/, size_t /*sz*/);

/* --- @subarena_free@ --- *
 *
 * Arguments:   @subarena *s@ = pointer to arena
 *		@void *p@ = address of block to free
 *              @size_t s@ = size of block
 *
 * Returns:     ---
 *
 * Use:         Frees a block allocated by @subarena_alloc@.
 */

extern void subarena_free(subarena */*s*/, void */*p*/, size_t /*sz*/);

/* --- @A_CREATE@ --- *
 *
 * Arguments:	@subarena *s@ = pointer to arena
 *		@type@ = type of object required; must be passable to
 *			@sizeof@
 *
 * Returns:	Pointer to a block sufficiently big to hold an object of the
 *		named type.
 *
 * Use:		Allocates a block of the required type.
 */

#define A_CREATE(a, type) subarena_alloc((a), sizeof(type))

/* --- @A_DESTROY@ --- *
 *
 * Arguments:	@subarena *s@ = pointer to arena
 *		@void *p@ = pointer to an object
 *
 * Returns:	---
 *
 * Use:		Frees the thing pointed to by @p@.
 */

#define A_DESTROY(a, p) subarena_free((a), (p), sizeof(*p))

/*----- Shortcuts for the global pool -------------------------------------*/

/* --- @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 from the @sub_global@ pool.
 */

extern void *sub_alloc(size_t /*sz*/);
#define sub_alloc(sz) subarena_alloc(&sub_global, (sz))

/* --- @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@.
 */

extern void sub_free(void */*p*/, size_t /*sz*/);
#define sub_free(p, sz) subarena_free(&sub_global, (p), (sz))

/* --- @CREATE@ --- *
 *
 * Arguments:	@type@ = type of object required; must be passable to
 *			@sizeof@
 *
 * Returns:	Pointer to a block sufficiently big to hold an object of the
 *		named type.
 *
 * Use:		Allocates a block of the required type.
 */

#define CREATE(type) sub_alloc(sizeof(type))

/* --- @DESTROY@ --- *
 *
 * Arguments:	@void *p@ = pointer to an object
 *
 * Returns:	---
 *
 * Use:		Frees the thing pointed to by @p@.
 */

#define DESTROY(p) sub_free(p, sizeof(*p))

/* --- @sub_init@ --- *
 *
 * Arguments:   ---
 *
 * Returns:     ---
 *
 * Use:         Initializes the magic allocator.  This is no longer
 *		necessary.
 */

extern void sub_init(void);

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

#ifdef __cplusplus
  }
#endif

#endif