From: mdw Date: Fri, 22 Oct 1999 22:37:26 +0000 (+0000) Subject: New dynamic array implementation replaces `dynarray.h'. X-Git-Tag: 2.0.4~222 X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~mdw/git/mLib/commitdiff_plain/3745e24b5b5526174fda7f83999a0ca301c4c146 New dynamic array implementation replaces `dynarray.h'. --- diff --git a/darray.c b/darray.c new file mode 100644 index 0000000..0825bca --- /dev/null +++ b/darray.c @@ -0,0 +1,260 @@ +/* -*-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 +#include +#include + +#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 -------------------------------------------------*/ diff --git a/darray.h b/darray.h new file mode 100644 index 0000000..93a806f --- /dev/null +++ b/darray.h @@ -0,0 +1,442 @@ +/* -*-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 +#include +#include + +#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