[mLib] / darray.h

/* -*-c-*-
 *
 * $Id: darray.h,v 1.6 2001/03/03 12:20:23 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.6  2001/03/03 12:20:23  mdw
 * New macros @DA_FIRST@ and @DA_LAST@ for stack/queue peeking.
 *
 * Revision 1.5  2000/06/17 10:37:39  mdw
 * Add support for arena management.
 *
 * Revision 1.4  1999/12/10 23:42:04  mdw
 * Change header file guard names.
 *
 * 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 MLIB_DARRAY_H
#define MLIB_DARRAY_H

#ifdef __cplusplus
  extern "C" {
#endif

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

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

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

#ifndef MLIB_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 */
  arena *a;				/* Pointer to allocation arena */
} 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, &arena_stdlib }, 0 }

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

#define DA_CREATE(aa) do {						\
  (aa)->b.sz = (aa)->b.len = 0;						\
  (aa)->b.off = 0;							\
  (aa)->b.push = (aa)->b.unshift = 0;					\
  (aa)->b.a = &arena_stdlib;						\
  (aa)->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(aa) do {						\
  if ((aa)->v)								\
    x_free((aa)->b.a, (aa)->v - (aa)->b.off);				\
  DA_CREATE(aa);								\
} 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_FIRST@ --- *
 *
 * Arguments:	@a@ = pointer to an array block (multiply evaluated)
 *
 * Use:		Evaluates to the initial element in array @a@.  It is unsafe
 *		to do this if the array is empty.  The array is not changed. 
 */

#define DA_FIRST(a) (DA(a)[0])

/* --- @DA_LAST@ --- *
 *
 * Arguments:	@a@ = pointer to an array block (multiply evaluated)
 *
 * Use:		Evaluates to the final element in array @a@.  It is unsafe
 *		to do this if the array is empty.  The array is not changed.
 */

#define DA_LAST(a) (DA(a)[(a)->b.len - 1])

/* --- @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
Commit	Line	Data
3745e24b	1	/* --c--
3745e24b	2	*
706bf01d	3	* $Id: darray.h,v 1.6 2001/03/03 12:20:23 mdw Exp $
3745e24b	4	*
	5	* Dynamically growing dense arrays
	6	*
	7	* (c) 1999 Straylight/Edgeware
	8	*/
	9
	10	/----- Licensing notice --------------------------------------------------
	11	*
	12	* This file is part of the mLib utilities library.
	13	*
	14	* mLib 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	* mLib 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 mLib; 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: darray.h,v $
706bf01d	33	* Revision 1.6 2001/03/03 12:20:23 mdw
	34	* New macros @DA_FIRST@ and @DA_LAST@ for stack/queue peeking.
	35	*
20eb516f	36	* Revision 1.5 2000/06/17 10:37:39 mdw
	37	* Add support for arena management.
	38	*
c6e0eaf0	39	* Revision 1.4 1999/12/10 23:42:04 mdw
	40	* Change header file guard names.
	41	*
d4e0e50d	42	* Revision 1.3 1999/11/05 14:32:43 mdw
	43	* Minor change in argument naming.
	44	*
85bb21f7	45	* Revision 1.2 1999/10/29 22:59:22 mdw
	46	* New array adjustment macros for unsigned arguments.
	47	*
3745e24b	48	* Revision 1.1 1999/10/22 22:37:26 mdw
	49	* New dynamic array implementation replaces `dynarray.h'.
	50	*
	51	*/
	52
c6e0eaf0	53	#ifndef MLIB_DARRAY_H
c6e0eaf0	54	#define MLIB_DARRAY_H
3745e24b	55
	56	#ifdef __cplusplus
	57	extern "C" {
	58	#endif
	59
	60	/----- Header files ------------------------------------------------------/
	61
	62	#include <stdio.h>
	63	#include <stdlib.h>
	64	#include <string.h>
	65
c6e0eaf0	66	#ifndef MLIB_ALLOC_H
3745e24b	67	# include "alloc.h"
	68	#endif
	69
c6e0eaf0	70	#ifndef MLIB_EXC_H
3745e24b	71	# include "exc.h"
	72	#endif
	73
	74	/----- Various important constants ---------------------------------------/
	75
	76	/* --- @DAEXC_UFLOW@, @DAEXC_OFLOW@ --- *
	77	*
	78	* Underflow and overflow exceptions raised by @DA_SHIFT@, and by @DA_POP@
	79	* and @DA_SHIFT@.
	80	*/
	81
	82	#define DAEXC_UFLOW EXC_ALLOCN(EXC_MLIB, 0)
	83	#define DAEXC_OFLOW EXC_ALLOCN(EXC_MLIB, 1)
	84
	85	/----- Data structures ---------------------------------------------------/
	86
	87	/* --- Base structure for dynamic arrays --- *
	88	*
	89	* An actual array has a `vector' @v@ in addition to this data (which is
	90	* tucked away in the @b@ member). The vector contains the actual storage
	91	* for the array elements.
	92	*
	93	* The vector pointer @v@ potentially points somewhere in the middle of the
	94	* allocated storage. The @off@ member explains how far into the storage the
	95	* vector points. The allocated storage is sufficient for @sz + off@ items
	96	* to be stored. Valid array indices are integers between 0 (inclusive) and
	97	* @len@ (exclusive). Thus, from @v@ onwards, there is space for @sz@
	98	* elements, and of these, @sz - len@ are currently not considered to be
	99	* within the array's bounds.
	100	*
	101	* The @push@ and @unshift@ counts record how many times these operations
	102	* have been performed since the last extension of the array. They are used
	103	* by the extension algorithm to decide how to position the data offset.
	104	*
	105	* Try to use the access macros rather than the structure members.
	106	*/
	107
	108	typedef struct da_base {
	109	size_t sz; /* Size of allocated vector */
	110	size_t len; /* Length of useful portion */
	111	size_t off; /* Offset of @v@ into space */
	112	unsigned push, unshift; /* Pushes/unshifts since growth */
20eb516f	113	arena a; / Pointer to allocation arena */
3745e24b	114	} da_base;
	115
	116	/* --- @DA_DECL@ --- *
	117	*
	118	* Arguments: @atype@ = type name for the array
	119	* @type@ = item type for the array
	120	*
	121	* Use: Declares a structure for decribing a dynamic array.
	122	*/
	123
d4e0e50d	124	#define DA_DECL(type_v, type) \
d4e0e50d	125	typedef struct type_v { da_base b; type *v; } type_v
3745e24b	126
	127	/----- Initialization, creation and destruction --------------------------/
	128
20eb516f	129	#define DA_INIT { { 0, 0, 0, 0, 0, &arena_stdlib }, 0 }
3745e24b	130
	131	/* --- @DA_CREATE@ --- *
	132	*
	133	* Arguments: @a@ = pointer to an array block (multiply evaluated)
	134	*
	135	* Use: Initializes an array block.
	136	*/
	137
20eb516f	138	#define DA_CREATE(aa) do { \
	139	(aa)->b.sz = (aa)->b.len = 0; \
	140	(aa)->b.off = 0; \
	141	(aa)->b.push = (aa)->b.unshift = 0; \
	142	(aa)->b.a = &arena_stdlib; \
	143	(aa)->v = 0; \
3745e24b	144	} while (0)
	145
	146	/* --- @DA_DESTROY@ --- *
	147	*
	148	* Arguments: @a@ = pointer to an array block (multiply evaluated)
	149	*
	150	* Use: Destroys an array. The array is left valid but empty.
	151	*/
	152
20eb516f	153	#define DA_DESTROY(aa) do { \
	154	if ((aa)->v) \
	155	x_free((aa)->b.a, (aa)->v - (aa)->b.off); \
	156	DA_CREATE(aa); \
3745e24b	157	} while (0)
	158
	159	/----- Storage reservation -----------------------------------------------/
	160
	161	/* --- @DA_ENSURE@ --- *
	162	*
	163	* Arguments: @a@ = pointer to an array block (multiply evaluated)
	164	* @n@ = required number of spare items in the array
	165	*
	166	* Use: Ensures that there are at least @n@ spare slots at the end of
	167	* the array.
	168	*/
	169
	170	#define DA_ENSURE(a, n) do { \
	171	size_t _n = (n); \
	172	if (_n > (a)->b.sz - (a)->b.len) \
	173	(a)->v = da_ensure(&(a)->b, (a)->v, sizeof((a)->v[0]), _n); \
	174	else \
	175	(a)->b.push += _n; \
	176	} while (0)
	177
	178	/* --- @DA_SHUNT@ --- *
	179	*
	180	* Arguments: @a@ = pointer to an array block (multiply evaluated)
	181	* @n@ = required number of spare items in the array
	182	*
	183	* Use: Ensures that there are at least @n@ spare slots at the start
	184	* of the array.
	185	*/
	186
	187	#define DA_SHUNT(a, n) do { \
	188	size_t _n = (n); \
	189	if (_n > (a)->b.off) \
	190	(a)->v = da_shunt(&(a)->b, (a)->v, sizeof((a)->v[0]), _n); \
	191	else \
	192	(a)->b.unshift += _n; \
	193	} while (0)
	194
	195	/* --- @DA_TIDY@ --- *
	196	*
	197	* Arguments: @a@ = pointer to an array block (multiply evaluated)
	198	*
	199	* Use: Reduces the amount of storage required by an array to its
	200	* minimum possible.
	201	*/
	202
	203	#define DA_TIDY(a) ((a)->v = da_tidy(&(a)->b, (a)->v, sizeof((a)->v[0])))
	204
85bb21f7	205	/* --- @DA_RESET@ --- *
	206	*
	207	* Arguments: @a@ = pointer to array block
	208	*
	209	* Use: Removes all the items from the named array. This might not
	210	* be a good idea. No storage is freed.
	211	*/
	212
	213	#define DA_RESET(a) ((a)->b.len = 0)
	214
3745e24b	215	/----- Access operations -------------------------------------------------/
	216
	217	/* --- @DA@ --- *
	218	*
	219	* Arguments: @a@ = pointer to array block
	220	*
	221	* Use: Expands to a reference to the array proper. Given an array
	222	* @a@, item @i@ may be located using the expression @DA(a)[i]@.
	223	*/
	224
	225	#define DA(a) ((a)->v + 0)
	226
	227	/* --- @DA_LEN@ --- *
	228	*
	229	* Arguments: @a@ = pointer to array block
	230	*
	231	* Use: Expands to the number of elements in the array. Elements are
	232	* assigned integer indices in the half-open interval
	233	* [0, @DA_LEN(a)@). Don't change the length directly; use
	234	* @DA_EXTEND@ instead.
	235	*/
	236
	237	#define DA_LEN(a) ((a)->b.len + 0)
	238
	239	/* --- @DA_SPARE@ --- *
	240	*
	241	* Arguments: @a@ = pointer to array block (multiply evaluated)
	242	*
	243	* Use: Evaluates to the number of spare array elements above the
	244	* end of the array.
	245	*/
	246
	247	#define DA_SPARE(a) ((a)->b.sz - (a)->b.len)
	248
	249	/* --- @DA_INCLUDE@ --- *
	250	*
	251	* Arguments: @a@ = pointer to array block (multiply evaluated)
	252	* @i@ = index into array
	253	*
	254	* Use: Extends the array (if necessary) so that it includes the
	255	* index @i@.
	256	*/
	257
	258	#define DA_INCLUDE(a, i) do { \
	259	size_t _i = (i); \
	260	size_t _len = DA_LEN(a); \
	261	if (_i >= _len) { \
	262	size_t _nn = _i - _len + 1; \
	263	DA_ENSURE(a, _nn); \
	264	DA_UNSAFE_EXTEND(a, _nn); \
	265	} \
	266	} while (0)
	267
	268	/* --- @DA_OFFSET@ --- *
	269	*
	270	* Arguments: @a@ = pointer to array block
	271	*
	272	* Use: Evaluates to the number of spare elements before the
	273	* beginning of the array. Don't modify the offset directly;
	274	* use @DA_SLIDE@ instead.
	275	*/
	276
	277	#define DA_OFFSET(a) ((a)->b.off + 0)
	278
279	/* --- @DA_EXTEND@ --- *
280	*
281	* Arguments: @a@ = pointer to array block (multiply evaluated)
282	* @n@ = number of slots to add (multiply evaluated)
283	*
284	* Use: Extends the end of the array by @n@ elements. The exception
285	* @DAEXC_OFLOW@ is thrown if there is not enough space for the
286	* new elements (i.e., @n > DA_SPARE(a)@) -- call @DA_ENSURE@ to
287	* prevent this from happening. The integer @n@ may be
288	* negative; @DAEXC_UFLOW@ is called if @n < DA_LEN(a)@.
289	*/
290
291	#define DA_EXTEND(a, n) do { \
292	if ((n) > 0 && (n) > DA_SPARE(a)) \
293	THROW(DAEXC_OFLOW); \
294	else if ((n) < 0 && -(n) > DA_LEN(a)) \
295	THROW(DAEXC_UFLOW); \
296	DA_UNSAFE_EXTEND(a, n); \
297	} while (0)
298
85bb21f7	299	/* --- @DA_UNSAFE_EXTEND@ --- *
3745e24b	300	*
	301	* Arguments: @a@ = pointer to array block (multiply evaluated)
	302	* @n@ = number of slots to add (multiply evaluated)
	303	*
	304	* Use: As for @DA_EXTEND@, only it doesn't check for errors.
	305	*/
	306
	307	#define DA_UNSAFE_EXTEND(a, n) do { \
	308	(a)->b.len += (n); \
	309	} while (0)
	310
	311	/* --- @DA_SLIDE@ --- *
	312	*
	313	* Arguments: @a@ = pointer to array block (multiply evaluated)
	314	* @n@ = number of positions to slide the array (multiply
	315	* evaluated)
	316	*
	317	*
	318	* Use: Slides the array elements by @n@ positions. A positive @n@
	319	* slides upwards, introducing new elements at the bottom; a
	320	* negative @n@ slides downwards, removing low-numbered
	321	* elements. Formally, what was at index @i - n@ before the
	322	* slide is moved to index @i@. It is an error to slide by more
	323	* than @DA_OFFSET(a)@ or less than @-DA_LEN(a)@. The exception
	324	* @DAEXC_OFLOW@ is raised in the former case, and @DAEXC_UFLOW@
	325	* in the latter.
	326	*/
	327
	328	#define DA_SLIDE(a, n) do { \
	329	if ((n) > 0 && (n) > DA_OFFSET(a)) \
	330	THROW(DAEXC_OFLOW); \
	331	else if ((n) < 0 && -(n) > DA_LEN(a)) \
	332	THROW(DAEXC_UFLOW); \
	333	DA_UNSAFE_SLIDE((a), (n)); \
	334	} while (0)
	335
	336	/* --- @DA_UNSAFE_SLIDE@ --- *
	337	*
	338	* Arguments: @a@ = pointer to array block (multiply evaluated)
	339	* @n@ = number of positions to slide the array (multiply
	340	* evaluated)
	341	*
	342	* Use: As for @DA_SLIDE@, only it doesn't check for errors.
	343	*/
	344
	345	#define DA_UNSAFE_SLIDE(a, n) do { \
	346	(a)->v -= (n); \
	347	(a)->b.len += (n); \
	348	(a)->b.sz += (n); \
	349	(a)->b.off -= (n); \
	350	} while (0)
	351
85bb21f7	352	/* --- @DA_SHRINK@ --- *
	353	*
	354	* Arguments: @a@ = pointer to array block (multiply evaluated)
	355	* @n@ = number of slots to remove (multiply evaluated)
	356	*
	357	* Use: As for @DA_EXTEND@, with the sense of the argument reversed.
	358	*/
	359
	360	#define DA_SHRINK(a, n) do { \
	361	if ((n) > 0 && (n) > DA_LEN(a)) \
	362	THROW(DAEXC_UFLOW); \
	363	else if ((n) < 0 && -(n) > DA_SPARE(a)) \
	364	THROW(DAEXC_OFLOW); \
	365	DA_UNSAFE_SHRINK(a, n); \
	366	} while (0)
	367
	368	/* --- @DA_UNSAFE_SHRINK@ --- *
	369	*
	370	* Arguments: @a@ = pointer to array block (multiply evaluated)
	371	* @n@ = number of slots to add (multiply evaluated)
	372	*
	373	* Use: As for @DA_SHRINK@, only it doesn't check for errors.
	374	*/
	375
	376	#define DA_UNSAFE_SHRINK(a, n) do { \
	377	(a)->b.len -= (n); \
	378	} while (0)
	379
	380	/* --- @DA_UNSLIDE@ --- *
	381	*
	382	* Arguments: @a@ = pointer to array block (multiply evaluated)
	383	* @n@ = number of positions to slide the array (multiply
	384	* evaluated)
	385	*
	386	*
	387	* Use: As for @DA_SLIDE@, only in the other direction.
	388	*/
	389
	390	#define DA_UNSLIDE(a, n) do { \
	391	if ((n) > 0 && (n) > DA_LEN(a)) \
	392	THROW(DAEXC_UFLOW); \
	393	else if ((n) < 0 && -(n) > DA_OFFSET(a)) \
	394	THROW(DAEXC_OFLOW); \
	395	DA_UNSAFE_UNSLIDE((a), (n)); \
	396	} while (0)
	397
	398	/* --- @DA_UNSAFE_UNSLIDE@ --- *
	399	*
	400	* Arguments: @a@ = pointer to array block (multiply evaluated)
	401	* @n@ = number of positions to slide the array (multiply
	402	* evaluated)
	403	*
	404	* Use: As for @DA_UNSLIDE@, only it doesn't check for errors.
	405	*/
	406
	407	#define DA_UNSAFE_UNSLIDE(a, n) do { \
	408	(a)->v += (n); \
	409	(a)->b.len -= (n); \
	410	(a)->b.sz -= (n); \
	411	(a)->b.off += (n); \
	412	} while (0)
	413
3745e24b	414	/----- Stack-like operations ---------------------------------------------/
3745e24b	415
706bf01d	416	/* --- @DA_FIRST@ --- *
	417	*
	418	* Arguments: @a@ = pointer to an array block (multiply evaluated)
	419	*
	420	* Use: Evaluates to the initial element in array @a@. It is unsafe
	421	* to do this if the array is empty. The array is not changed.
	422	*/
	423
	424	#define DA_FIRST(a) (DA(a)[0])
	425
	426	/* --- @DA_LAST@ --- *
	427	*
	428	* Arguments: @a@ = pointer to an array block (multiply evaluated)
	429	*
	430	* Use: Evaluates to the final element in array @a@. It is unsafe
	431	* to do this if the array is empty. The array is not changed.
	432	*/
	433
	434	#define DA_LAST(a) (DA(a)[(a)->b.len - 1])
	435
3745e24b	436	/* --- @DA_PUSH@ --- *
	437	*
	438	* Arguments: @a@ = pointer to an array block (multiply evaluated)
	439	* @x@ = item to append to the end
	440	*
	441	* Use: Appends @x@ as the final element in the array @a@.
	442	*/
	443
	444	#define DA_PUSH(a, x) do { \
	445	DA_ENSURE(a, 1); \
	446	DA(a)[(a)->b.len++] = x; \
	447	} while (0)
	448
	449	/* --- @DA_POP@ --- *
	450	*
	451	* Arguments: @a@ = pointer to an array block (multiply evaluated)
	452	*
	453	* Use: Evaluates to the final element in array @a@. The element is
	454	* removed. An exception @DAEXC_UFLOW@ is raised if there is
	455	* no item available to pop.
	456	*/
	457
	458	#define DA_POP(a) \
	459	((a)->b.len ? ((void)0) : THROW(DAEXC_UFLOW), \
	460	DA(a)[--(a)->b.len])
	461
	462	/* --- @DA_UNSHIFT@ --- *
	463	*
	464	* Arguments: @a@ = pointer to an array block (multiply evaluated)
	465	* @x@ = the new element to insert
	466	*
	467	* Use: Inserts a new element at the beginning of an array. This
	468	* might take a while.
	469	*/
	470
	471	#define DA_UNSHIFT(a, x) do { \
	472	DA_SHUNT(a, 1); \
	473	DA_UNSAFE_SLIDE(a, 1); \
	474	DA(a)[0] = x; \
	475	} while (0)
	476
	477	/* --- @DA_SHIFT@ --- *
	478	*
	479	* Arguments: @a@ = pointer to an array block (multiply evaluated)
	480	*
	481	* Use: Evaluates to the initial element in array @a@. The element
	482	* is removed, and all other elements are shifted down one
	483	* place. The exception @DAEXC_UFLOW@ is raised if there is no
	484	* element to return.
	485	*/
	486
	487	#define DA_SHIFT(a) \
706bf01d	488	((a)->b.len ? ((void)0) : THROW(DAEXC_UFLOW), \
3745e24b	489	(a)->b.len--, \
	490	(a)->b.sz--, \
	491	(a)->b.off++, \
	492	*(a)->v++)
	493
	494	/----- Functions provided ------------------------------------------------/
	495
	496	/* --- @da_ensure@ --- *
	497	*
	498	* Arguments: @da_base *b@ = pointer to array base structure
	499	* @void *v@ = pointer to array vector
	500	* @size_t sz@ = size of individual array elements
	501	* @size_t n@ = number of items required at the end
	502	*
	503	* Returns: Pointer to newly allocated or adjusted array vector.
	504	*
	505	* Use: Extends a dynamic array to accommodate a number of new items
	506	* at its end. This function is a helper for the @DA_ENSURE@
	507	* macro, which should be used by preference.
	508	*/
	509
	510	extern void da_ensure(da_base /b/, void /v*/,
	511	size_t /sz/, size_t /n/);
	512
	513	/* --- @da_shunt@ --- *
	514	*
	515	* Arguments: @da_base *b@ = pointer to array base structure
	516	* @void *v@ = pointer to array vector
	517	* @size_t sz@ = size of the array elements
	518	* @size_t n@ = number of items required at the start
	519	*
	520	* Returns: Pointer to appropriately bodged vector.
	521	*
	522	* Use: Extends an array to accommodate items inserted at its front.
	523	* This function is a helper for the @DA_SHUNT@ macro, which
	524	* should be used by preference.
	525	*/
	526
	527	extern void da_shunt(da_base /b/, void /v*/,
	528	size_t /sz/, size_t /n/);
	529
	530	/* --- @da_tidy@ --- *
	531	*
	532	* Arguments: @da_base *b@ = pointer to array base structure
	533	* @void *v@ = pointer to vector
	534	* @size_t sz@ = size of the array elements
	535	*
	536	* Returns: Newly allocated vector.
	537	*
	538	* Use: Minimizes the space occupied by an array. This function is a
	539	* helper for the @DA_TIDY@ macro, which should be used by
	540	* preference.
	541	*/
	542
	543	extern void da_tidy(da_base /b/, void /v/, size_t /sz*/);
	544
	545	/----- That's all, folks -------------------------------------------------/
	546
	547	#ifdef __cplusplus
	548	}
	549	#endif
	550
	551	#endif