--- /dev/null
+/* -*-c-*-
+ *
+ * $Id: darray.c,v 1.1 1999/10/22 22:37:26 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.c,v $
+ * Revision 1.1 1999/10/22 22:37:26 mdw
+ * New dynamic array implementation replaces `dynarray.h'.
+ *
+ */
+
+/*----- Header files ------------------------------------------------------*/
+
+#include <stdio.h>
+#include <string.h>
+#include <stdlib.h>
+
+#include "alloc.h"
+#include "darray.h"
+
+/*----- Magic numbers -----------------------------------------------------*/
+
+#define DA_INITSZ 64 /* Default size for new array */
+#define DA_SLOTS 8 /* Number of preshifted slots */
+
+/*----- Main code ---------------------------------------------------------*/
+
+/* --- @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.
+ */
+
+void *da_ensure(da_base *b, void *v, size_t sz, size_t n)
+{
+ size_t rq = n + b->len;
+ char *p = v, *q;
+ size_t nsz;
+ size_t slots;
+
+ /* --- Make sure there's something which needs doing --- *
+ *
+ * If there's enough space already then return immediately.
+ */
+
+ if (rq < b->sz)
+ return (p);
+
+ /* --- Compute a number of `unshift' slots --- *
+ *
+ * When returning from this function, the offset will be set to @slots@.
+ * If @unshift@ is zero, there's no point in reserving slots. Otherwise
+ * choose a power of two greater than @unshift@, with a minimum of
+ * @DA_SLOTS@. Then add the number of slots to the requirement.
+ */
+
+ if (!b->unshift)
+ slots = 0;
+ else {
+ slots = DA_SLOTS;
+ while (slots < b->unshift)
+ slots <<= 1;
+ }
+ rq += slots;
+
+ /* --- Maybe just shunt data around a bit --- *
+ *
+ * If the vector is large enough, then theoretically we could cope by
+ * moving the objects about in their existing storage.
+ */
+
+ if (rq < b->sz + b->off) {
+ q = p - (b->off - slots) * sz;
+ memmove(q, p, b->len * sz);
+ b->sz += b->off - slots;
+ b->off = slots;
+ b->unshift = b->push = 0;
+ return (q);
+ }
+
+ /* --- Reallocate the array --- */
+
+ nsz = v ? b->sz + b->off : DA_INITSZ;
+ do nsz <<= 1; while (nsz < rq);
+ q = xmalloc(nsz * sz);
+ q += slots * sz;
+ memcpy(q, p, b->len * sz);
+ if (p)
+ free(p - b->off * sz);
+ b->off = slots;
+ b->sz = nsz - slots;
+ b->unshift = b->push = 0;
+ return (q);
+}
+
+/* --- @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.
+ */
+
+void *da_shunt(da_base *b, void *v, size_t sz, size_t n)
+{
+ size_t rq;
+ char *p = v, *q;
+ size_t nsz;
+ size_t slots;
+
+ /* --- Make sure there's something which needs doing --- *
+ *
+ * If there's enough space already then return immediately.
+ */
+
+ if (n < b->off)
+ return (p);
+
+ /* --- Compute a number of `push' slots --- *
+ *
+ * When returning from this function, there will be @slots@ free spaces at
+ * the end of the array. If @push@ is zero, there's no point in reserving
+ * slots. Otherwise choose a power of two greater than @push@, with a
+ * minimum of @DA_SLOTS@. To simplify matters, add the number of items
+ * already in the array to @slots@, and then add the number of slots to the
+ * requirement.
+ */
+
+ if (!b->push)
+ slots = 0;
+ else {
+ slots = DA_SLOTS;
+ while (slots < b->push)
+ slots <<= 1;
+ }
+ slots += b->len;
+ rq = n + slots;
+
+ /* --- Maybe just shunt data around a bit --- *
+ *
+ * If the vector is large enough, then theoretically we could cope by
+ * moving the objects about in their existing storage.
+ */
+
+ if (rq < b->sz + b->off) {
+ q = p + (b->sz - slots) * sz;
+ memmove(q, p, b->len * sz);
+ b->off += b->sz - slots;
+ b->sz = slots;
+ b->unshift = b->push = 0;
+ return (q);
+ }
+
+ /* --- Reallocate the array --- */
+
+ nsz = v ? b->sz + b->off : DA_INITSZ;
+ do nsz <<= 1; while (nsz < rq);
+ q = xmalloc(nsz * sz);
+ q += (nsz - slots) * sz;
+ memcpy(q, p, b->len * sz);
+ if (p)
+ free(p - b->off * sz);
+ b->off = nsz - slots;
+ b->sz = slots;
+ b->unshift = b->push = 0;
+ return (q);
+}
+
+/* --- @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.
+ */
+
+void *da_tidy(da_base *b, void *v, size_t sz)
+{
+ char *p = v, *q;
+
+ b->unshift = b->push = 0;
+
+ if (!p)
+ return (0);
+ if (b->sz == b->len && b->off == 0)
+ return (p);
+
+ if (!b->len) {
+ free(p - b->off * sz);
+ return (0);
+ }
+
+ q = xmalloc(b->len * sz);
+ memcpy(q, p, b->len * sz);
+ free(p - b->off * sz);
+ b->sz = b->len;
+ b->off = 0;
+ return (q);
+}
+
+/* --- Note about testing --- *
+ *
+ * The test rig for this code is split into three parts. There's `da-gtest',
+ * which is a Perl script which generates a list of commands. The `da-ref'
+ * Perl script interprets these commands as operations on a Perl array. It's
+ * relatively conservatively written and believed to be reliable. The
+ * `da-test.c' file implements a command reader for the same syntax and
+ * performs the operations on an integer darray, producing output in the same
+ * format. To test darray, generate a command script with `da-gtest', pass
+ * it through both `da-ref' and `da-test' (the result of compiling
+ * da-test.c'), and compare the results. If they're not byte-for-byte
+ * identical, there's something wrong.
+ */
+
+/*----- That's all, folks -------------------------------------------------*/
--- /dev/null
+/* -*-c-*-
+ *
+ * $Id: darray.h,v 1.1 1999/10/22 22:37:26 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.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(atype, type) \
+ typedef struct atype { da_base b; type *v; } atype
+
+/*----- 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])))
+
+/*----- 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_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)
+
+/*----- 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
~mdw / mLib / commitdiff