Minor changes to allocation strategy.

[mLib] / darray.h

/* -*-c-*-
 *
 * $Id: darray.h,v 1.3 1999/11/05 14:32:43 mdw Exp $
 *
 * Dynamically growing dense arrays
 *
 * (c) 1999 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: darray.h,v $
 * Revision 1.3  1999/11/05 14:32:43  mdw
 * Minor change in argument naming.
 *
 * Revision 1.2  1999/10/29 22:59:22  mdw
 * New array adjustment macros for unsigned arguments.
 *
 * Revision 1.1  1999/10/22 22:37:26  mdw
 * New dynamic array implementation replaces `dynarray.h'.
 *
 */

#ifndef DARRAY_H
#define DARRAY_H

#ifdef __cplusplus
  extern "C" {
#endif

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

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

#ifndef ALLOC_H
#  include "alloc.h"
#endif

#ifndef EXC_H
#  include "exc.h"
#endif

/*----- Various important constants ---------------------------------------*/

/* --- @DAEXC_UFLOW@, @DAEXC_OFLOW@ --- *
 *
 * Underflow and overflow exceptions raised by @DA_SHIFT@, and by @DA_POP@
 * and @DA_SHIFT@.
 */

#define DAEXC_UFLOW EXC_ALLOCN(EXC_MLIB, 0)
#define DAEXC_OFLOW EXC_ALLOCN(EXC_MLIB, 1)

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

/* --- Base structure for dynamic arrays --- *
 *
 * An actual array has a `vector' @v@ in addition to this data (which is
 * tucked away in the @b@ member).  The vector contains the actual storage
 * for the array elements.
 *
 * The vector pointer @v@ potentially points somewhere in the middle of the
 * allocated storage.  The @off@ member explains how far into the storage the
 * vector points.  The allocated storage is sufficient for @sz + off@ items
 * to be stored.  Valid array indices are integers between 0 (inclusive) and
 * @len@ (exclusive).  Thus, from @v@ onwards, there is space for @sz@
 * elements, and of these, @sz - len@ are currently not considered to be
 * within the array's bounds.
 *
 * The @push@ and @unshift@ counts record how many times these operations
 * have been performed since the last extension of the array.  They are used
 * by the extension algorithm to decide how to position the data offset.
 *
 * Try to use the access macros rather than the structure members.
 */

typedef struct da_base {
  size_t sz;				/* Size of allocated vector */
  size_t len;				/* Length of useful portion */
  size_t off;				/* Offset of @v@ into space */
  unsigned push, unshift;		/* Pushes/unshifts since growth */
} da_base;

/* --- @DA_DECL@ --- *
 *
 * Arguments:	@atype@ = type name for the array
 *		@type@ = item type for the array
 *
 * Use:		Declares a structure for decribing a dynamic array.
 */

#define DA_DECL(type_v, type)						\
  typedef struct type_v { da_base b; type *v; } type_v

/*----- Initialization, creation and destruction --------------------------*/

#define DA_INIT { { 0, 0, 0, 0, 0 }, 0 } /* Standard initializer */

/* --- @DA_CREATE@ --- *
 *
 * Arguments:	@a@ = pointer to an array block (multiply evaluated)
 *
 * Use:		Initializes an array block.
 */

#define DA_CREATE(a) do {						\
  (a)->b.sz = (a)->b.len = 0;						\
  (a)->b.off = 0;							\
  (a)->b.push = (a)->b.unshift = 0;					\
  (a)->v = 0;								\
} while (0)

/* --- @DA_DESTROY@ --- *
 *
 * Arguments:	@a@ = pointer to an array block (multiply evaluated)
 *
 * Use:		Destroys an array.  The array is left valid but empty.
 */

#define DA_DESTROY(a) do {						\
  if ((a)->v)								\
    free((a)->v - (a)->b.off);						\
  DA_CREATE(a);								\
} while (0)

/*----- Storage reservation -----------------------------------------------*/

/* --- @DA_ENSURE@ --- *
 *
 * Arguments:	@a@ = pointer to an array block (multiply evaluated)
 *		@n@ = required number of spare items in the array
 *
 * Use:		Ensures that there are at least @n@ spare slots at the end of
 *		the array.
 */

#define DA_ENSURE(a, n) do {						\
  size_t _n = (n);							\
  if (_n > (a)->b.sz - (a)->b.len)					\
    (a)->v = da_ensure(&(a)->b, (a)->v, sizeof((a)->v[0]), _n);		\
  else									\
    (a)->b.push += _n;							\
} while (0)

/* --- @DA_SHUNT@ --- *
 *
 * Arguments:	@a@ = pointer to an array block (multiply evaluated)
 *		@n@ = required number of spare items in the array
 *
 * Use:		Ensures that there are at least @n@ spare slots at the start
 *		of the array.
 */

#define DA_SHUNT(a, n) do {						\
  size_t _n = (n);							\
  if (_n > (a)->b.off)							\
    (a)->v = da_shunt(&(a)->b, (a)->v, sizeof((a)->v[0]), _n);		\
  else									\
    (a)->b.unshift += _n;						\
} while (0)

/* --- @DA_TIDY@ --- *
 *
 * Arguments:	@a@ = pointer to an array block (multiply evaluated)
 *
 * Use:		Reduces the amount of storage required by an array to its
 *		minimum possible.
 */

#define DA_TIDY(a) ((a)->v = da_tidy(&(a)->b, (a)->v, sizeof((a)->v[0])))

/* --- @DA_RESET@ --- *
 *
 * Arguments:	@a@ = pointer to array block
 *
 * Use:		Removes all the items from the named array.  This might not
 *		be a good idea.  No storage is freed.
 */

#define DA_RESET(a) ((a)->b.len = 0)

/*----- Access operations -------------------------------------------------*/

/* --- @DA@ --- *
 *
 * Arguments:	@a@ = pointer to array block
 *
 * Use:		Expands to a reference to the array proper.  Given an array
 *		@a@, item @i@ may be located using the expression @DA(a)[i]@.
 */

#define DA(a) ((a)->v + 0)

/* --- @DA_LEN@ --- *
 *
 * Arguments:	@a@ = pointer to array block
 *
 * Use:		Expands to the number of elements in the array.  Elements are
 *		assigned integer indices in the half-open interval
 *		[0, @DA_LEN(a)@).  Don't change the length directly; use
 *		@DA_EXTEND@ instead.
 */

#define DA_LEN(a) ((a)->b.len + 0)

/* --- @DA_SPARE@ --- *
 *
 * Arguments:	@a@ = pointer to array block (multiply evaluated)
 *
 * Use:		Evaluates to the number of spare array elements above the
 *		end of the array.
 */

#define DA_SPARE(a) ((a)->b.sz - (a)->b.len)

/* --- @DA_INCLUDE@ --- *
 *
 * Arguments:	@a@ = pointer to array block (multiply evaluated)
 *		@i@ = index into array
 *
 * Use:		Extends the array (if necessary) so that it includes the
 *		index @i@.
 */

#define DA_INCLUDE(a, i) do {						\
  size_t _i = (i);							\
  size_t _len = DA_LEN(a);						\
  if (_i >= _len) {							\
    size_t _nn = _i - _len + 1;						\
    DA_ENSURE(a, _nn);							\
    DA_UNSAFE_EXTEND(a, _nn);						\
  }									\
} while (0)

/* --- @DA_OFFSET@ --- *
 *
 * Arguments:	@a@ = pointer to array block
 *
 * Use:		Evaluates to the number of spare elements before the
 *		beginning of the array.  Don't modify the offset directly;
 *		use @DA_SLIDE@ instead.
 */

#define DA_OFFSET(a) ((a)->b.off + 0)

/* --- @DA_EXTEND@ --- *
 *
 * Arguments:	@a@ = pointer to array block (multiply evaluated)
 *		@n@ = number of slots to add (multiply evaluated)
 *
 * Use:		Extends the end of the array by @n@ elements.  The exception
 *		@DAEXC_OFLOW@ is thrown if there is not enough space for the
 *		new elements (i.e., @n > DA_SPARE(a)@) -- call @DA_ENSURE@ to
 *		prevent this from happening.  The integer @n@ may be
 *		negative; @DAEXC_UFLOW@ is called if @n < DA_LEN(a)@.
 */

#define DA_EXTEND(a, n) do {						\
  if ((n) > 0 && (n) > DA_SPARE(a))					\
    THROW(DAEXC_OFLOW);							\
  else if ((n) < 0 && -(n) > DA_LEN(a))					\
    THROW(DAEXC_UFLOW);							\
  DA_UNSAFE_EXTEND(a, n);						\
} while (0)

/* --- @DA_UNSAFE_EXTEND@ --- *
 *
 * Arguments:	@a@ = pointer to array block (multiply evaluated)
 *		@n@ = number of slots to add (multiply evaluated)
 *
 * Use:		As for @DA_EXTEND@, only it doesn't check for errors.
 */

#define DA_UNSAFE_EXTEND(a, n) do {					\
  (a)->b.len += (n);							\
} while (0)

/* --- @DA_SLIDE@ --- *
 *
 * Arguments:	@a@ = pointer to array block (multiply evaluated)
 *		@n@ = number of positions to slide the array (multiply
 *			evaluated)
 *
 *
 * Use:		Slides the array elements by @n@ positions.  A positive @n@
 *		slides upwards, introducing new elements at the bottom; a
 *		negative @n@ slides downwards, removing low-numbered
 *		elements.  Formally, what was at index @i - n@ before the
 *		slide is moved to index @i@.  It is an error to slide by more
 *		than @DA_OFFSET(a)@ or less than @-DA_LEN(a)@.  The exception
 *		@DAEXC_OFLOW@ is raised in the former case, and @DAEXC_UFLOW@
 *		in the latter.
 */

#define DA_SLIDE(a, n) do {						\
  if ((n) > 0 && (n) > DA_OFFSET(a))					\
    THROW(DAEXC_OFLOW);							\
  else if ((n) < 0 && -(n) > DA_LEN(a))					\
    THROW(DAEXC_UFLOW);							\
  DA_UNSAFE_SLIDE((a), (n));						\
} while (0)

/* --- @DA_UNSAFE_SLIDE@ --- *
 *
 * Arguments:	@a@ = pointer to array block (multiply evaluated)
 *		@n@ = number of positions to slide the array (multiply
 *			evaluated)
 *
 * Use:		As for @DA_SLIDE@, only it doesn't check for errors.
 */

#define DA_UNSAFE_SLIDE(a, n) do {					\
  (a)->v -= (n);							\
  (a)->b.len += (n);							\
  (a)->b.sz += (n);							\
  (a)->b.off -= (n);							\
} while (0)

/* --- @DA_SHRINK@ --- *
 *
 * Arguments:	@a@ = pointer to array block (multiply evaluated)
 *		@n@ = number of slots to remove (multiply evaluated)
 *
 * Use:		As for @DA_EXTEND@, with the sense of the argument reversed.
 */

#define DA_SHRINK(a, n) do {						\
  if ((n) > 0 && (n) > DA_LEN(a))					\
    THROW(DAEXC_UFLOW);							\
  else if ((n) < 0 && -(n) > DA_SPARE(a))				\
    THROW(DAEXC_OFLOW);							\
  DA_UNSAFE_SHRINK(a, n);						\
} while (0)

/* --- @DA_UNSAFE_SHRINK@ --- *
 *
 * Arguments:	@a@ = pointer to array block (multiply evaluated)
 *		@n@ = number of slots to add (multiply evaluated)
 *
 * Use:		As for @DA_SHRINK@, only it doesn't check for errors.
 */

#define DA_UNSAFE_SHRINK(a, n) do {					\
  (a)->b.len -= (n);							\
} while (0)

/* --- @DA_UNSLIDE@ --- *
 *
 * Arguments:	@a@ = pointer to array block (multiply evaluated)
 *		@n@ = number of positions to slide the array (multiply
 *			evaluated)
 *
 *
 * Use:		As for @DA_SLIDE@, only in the other direction.
 */

#define DA_UNSLIDE(a, n) do {						\
  if ((n) > 0 && (n) > DA_LEN(a))					\
    THROW(DAEXC_UFLOW);							\
  else if ((n) < 0 && -(n) > DA_OFFSET(a))				\
    THROW(DAEXC_OFLOW);							\
  DA_UNSAFE_UNSLIDE((a), (n));						\
} while (0)

/* --- @DA_UNSAFE_UNSLIDE@ --- *
 *
 * Arguments:	@a@ = pointer to array block (multiply evaluated)
 *		@n@ = number of positions to slide the array (multiply
 *			evaluated)
 *
 * Use:		As for @DA_UNSLIDE@, only it doesn't check for errors.
 */

#define DA_UNSAFE_UNSLIDE(a, n) do {					\
  (a)->v += (n);							\
  (a)->b.len -= (n);							\
  (a)->b.sz -= (n);							\
  (a)->b.off += (n);							\
} while (0)

/*----- Stack-like operations ---------------------------------------------*/

/* --- @DA_PUSH@ --- *
 *
 * Arguments:	@a@ = pointer to an array block (multiply evaluated)
 *		@x@ = item to append to the end
 *
 * Use:		Appends @x@ as the final element in the array @a@.
 */

#define DA_PUSH(a, x) do {						\
  DA_ENSURE(a, 1);							\
  DA(a)[(a)->b.len++] = x;						\
} while (0)

/* --- @DA_POP@ --- *
 *
 * Arguments:	@a@ = pointer to an array block (multiply evaluated)
 *
 * Use:		Evaluates to the final element in array @a@.  The element is
 *		removed.  An exception @DAEXC_UFLOW@ is raised if there is
 *		no item available to pop.
 */

#define DA_POP(a)							\
  ((a)->b.len ? ((void)0) : THROW(DAEXC_UFLOW),				\
   DA(a)[--(a)->b.len])

/* --- @DA_UNSHIFT@ --- *
 *
 * Arguments:	@a@ = pointer to an array block (multiply evaluated)
 *		@x@ = the new element to insert
 *
 * Use:		Inserts a new element at the beginning of an array.  This
 *		might take a while.
 */

#define DA_UNSHIFT(a, x) do {						\
  DA_SHUNT(a, 1);							\
  DA_UNSAFE_SLIDE(a, 1);						\
  DA(a)[0] = x;								\
} while (0)

/* --- @DA_SHIFT@ --- *
 *
 * Arguments:	@a@ = pointer to an array block (multiply evaluated)
 *
 * Use:		Evaluates to the initial element in array @a@.  The element
 *		is removed, and all other elements are shifted down one
 *		place.  The exception @DAEXC_UFLOW@ is raised if there is no
 *		element to return.
 */

#define DA_SHIFT(a) 							\
  ((a)->b.len ? ((void)0) : THROW(DAEXC_UFLOW),			\
   (a)->b.len--,							\
   (a)->b.sz--,								\
   (a)->b.off++,							\
   *(a)->v++)

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

/* --- @da_ensure@ --- *
 *
 * Arguments:	@da_base *b@ = pointer to array base structure
 *		@void *v@ = pointer to array vector
 *		@size_t sz@ = size of individual array elements
 *		@size_t n@ = number of items required at the end
 *
 * Returns:	Pointer to newly allocated or adjusted array vector.
 *
 * Use:		Extends a dynamic array to accommodate a number of new items
 *		at its end.  This function is a helper for the @DA_ENSURE@
 *		macro, which should be used by preference.
 */

extern void *da_ensure(da_base */*b*/, void */*v*/,
		       size_t /*sz*/, size_t /*n*/);

/* --- @da_shunt@ --- *
 *
 * Arguments:	@da_base *b@ = pointer to array base structure
 *		@void *v@ = pointer to array vector
 *		@size_t sz@ = size of the array elements
 *		@size_t n@ = number of items required at the start
 *
 * Returns:	Pointer to appropriately bodged vector.
 *
 * Use:		Extends an array to accommodate items inserted at its front.
 *		This function is a helper for the @DA_SHUNT@ macro, which
 *		should be used by preference.
 */

extern void *da_shunt(da_base */*b*/, void */*v*/,
		      size_t /*sz*/, size_t /*n*/);

/* --- @da_tidy@ --- *
 *
 * Arguments:	@da_base *b@ = pointer to array base structure
 *		@void *v@ = pointer to vector
 *		@size_t sz@ = size of the array elements
 *
 * Returns:	Newly allocated vector.
 *
 * Use:		Minimizes the space occupied by an array.  This function is a
 *		helper for the @DA_TIDY@ macro, which should be used by
 *		preference.
 */

extern void *da_tidy(da_base */*b*/, void */*v*/, size_t /*sz*/);

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

#ifdef __cplusplus
  }
#endif

#endif