/* -*-c-*-
*
- * $Id: darray.h,v 1.1 1999/10/22 22:37:26 mdw Exp $
+ * $Id: darray.h,v 1.7 2004/04/08 01:36:11 mdw Exp $
*
* Dynamically growing dense arrays
*
* (c) 1999 Straylight/Edgeware
*/
-/*----- Licensing notice --------------------------------------------------*
+/*----- Licensing notice --------------------------------------------------*
*
* This file is part of the mLib utilities library.
*
* 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.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" {
#include <stdlib.h>
#include <string.h>
-#ifndef ALLOC_H
+#ifndef MLIB_ALLOC_H
# include "alloc.h"
#endif
-#ifndef EXC_H
+#ifndef MLIB_EXC_H
# include "exc.h"
#endif
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@ --- *
* 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@ --- *
*
* 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@ --- *
* 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 -----------------------------------------------*/
#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@ --- *
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)
(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)
* element to return.
*/
-#define DA_SHIFT(a) \
- ((a)->b.len ? ((void)0) : THROW(DAEXC_UFLOW), \
+#define DA_SHIFT(a) \
+ ((a)->b.len ? ((void)0) : THROW(DAEXC_UFLOW), \
(a)->b.len--, \
(a)->b.sz--, \
(a)->b.off++, \
~mdw / mLib / blobdiff