X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~mdw/git/mLib/blobdiff_plain/3745e24b5b5526174fda7f83999a0ca301c4c146..78b1464e4a78dc364ecc8aebcfd5ec13b3f6bb07:/darray.h diff --git a/darray.h b/darray.h index 93a806f..003c6d7 100644 --- a/darray.h +++ b/darray.h @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: darray.h,v 1.1 1999/10/22 22:37:26 mdw Exp $ + * $Id: darray.h,v 1.6 2001/03/03 12:20:23 mdw Exp $ * * Dynamically growing dense arrays * @@ -30,13 +30,28 @@ /*----- 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 DARRAY_H -#define DARRAY_H +#ifndef MLIB_DARRAY_H +#define MLIB_DARRAY_H #ifdef __cplusplus extern "C" { @@ -48,11 +63,11 @@ #include #include -#ifndef ALLOC_H +#ifndef MLIB_ALLOC_H # include "alloc.h" #endif -#ifndef EXC_H +#ifndef MLIB_EXC_H # include "exc.h" #endif @@ -95,6 +110,7 @@ typedef struct da_base { 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@ --- * @@ -105,12 +121,12 @@ typedef struct da_base { * Use: Declares a structure for decribing a dynamic array. */ -#define DA_DECL(atype, type) \ - typedef struct atype { da_base b; type *v; } atype +#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 */ +#define DA_INIT { { 0, 0, 0, 0, 0, &arena_stdlib }, 0 } /* --- @DA_CREATE@ --- * * @@ -119,11 +135,12 @@ typedef struct da_base { * 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; \ +#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@ --- * @@ -133,10 +150,10 @@ typedef struct da_base { * 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); \ +#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 -----------------------------------------------*/ @@ -185,6 +202,16 @@ typedef struct da_base { #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@ --- * @@ -269,7 +296,7 @@ typedef struct da_base { DA_UNSAFE_EXTEND(a, n); \ } while (0) -/* --- @DA_EXTEND@ --- * +/* --- @DA_UNSAFE_EXTEND@ --- * * * Arguments: @a@ = pointer to array block (multiply evaluated) * @n@ = number of slots to add (multiply evaluated) @@ -322,8 +349,90 @@ typedef struct da_base { (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) @@ -376,7 +485,7 @@ typedef struct da_base { */ #define DA_SHIFT(a) \ - ((a)->b.len ? ((void)0) : THROW(DAEXC_UFLOW), \ + ((a)->b.len ? ((void)0) : THROW(DAEXC_UFLOW), \ (a)->b.len--, \ (a)->b.sz--, \ (a)->b.off++, \