From 85bb21f7edaa024657a09129d52edf66d8ab7fa2 Mon Sep 17 00:00:00 2001 Message-Id: <85bb21f7edaa024657a09129d52edf66d8ab7fa2.1714678679.git.mdw@distorted.org.uk> From: Mark Wooding Date: Fri, 29 Oct 1999 22:59:22 +0000 Subject: [PATCH] New array adjustment macros for unsigned arguments. Organization: Straylight/Edgeware From: mdw --- da-test.c | 4 +-- darray.c | 39 ++++++++++++++++++------- darray.h | 79 ++++++++++++++++++++++++++++++++++++++++++++++++-- man/.cvsignore | 5 ++++ man/darray.3 | 33 ++++++++++++++++++++- 5 files changed, 145 insertions(+), 15 deletions(-) diff --git a/da-test.c b/da-test.c index 6a73b0b..4b1966a 100644 --- a/da-test.c +++ b/da-test.c @@ -82,10 +82,10 @@ int main(void) DA_DESTROY(&vv); } else if (strcmp(p, "delete") == 0) { int n = atoi(strtok(0, " ")); - DA_SLIDE(&v, -n); + DA_UNSLIDE(&v, n); } else if (strcmp(p, "reduce") == 0) { int n = atoi(strtok(0, " ")); - DA_EXTEND(&v, -n); + DA_SHRINK(&v, n); } else if (strcmp(p, "set") == 0) { size_t i = atoi(strtok(0, " ")); int n = atoi(strtok(0, " ")); diff --git a/darray.c b/darray.c index bee6955..d7967c6 100644 --- a/darray.c +++ b/darray.c @@ -1,6 +1,6 @@ /* -*-c-*- * - * $Id: darray.c,v 1.2 1999/10/28 22:05:28 mdw Exp $ + * $Id: darray.c,v 1.3 1999/10/29 22:59:22 mdw Exp $ * * Dynamically growing dense arrays * @@ -30,6 +30,9 @@ /*----- Revision history --------------------------------------------------* * * $Log: darray.c,v $ + * Revision 1.3 1999/10/29 22:59:22 mdw + * New array adjustment macros for unsigned arguments. + * * Revision 1.2 1999/10/28 22:05:28 mdw * Modify and debug allocation routines. * @@ -115,15 +118,26 @@ void *da_ensure(da_base *b, void *v, size_t sz, size_t n) return (q); } - /* --- Reallocate the array --- */ + /* --- Reallocate the array --- * + * + * If the offset isn't changing, it's sensible to use @realloc@ if + * available. Otherwise the overhead of copying all the data twice + * probably isn't worth it. + */ nsz = v ? b->sz + b->off : (DA_INITSZ >> 1); 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); + if (p && slots == b->off) { + q = xrealloc(p - b->off * sz, nsz * sz); + q += slots * sz; + } else { + q = xmalloc(nsz * sz); + q += slots * sz; + if (p) { + memcpy(q, p, b->len * sz); + free(p - b->off * sz); + } + } b->off = slots; b->sz = nsz - slots; b->unshift = b->push = 0; @@ -194,15 +208,20 @@ void *da_shunt(da_base *b, void *v, size_t sz, size_t n) return (q); } - /* --- Reallocate the array --- */ + /* --- Reallocate the array --- * + * + * The neat @realloc@ code doesn't need to be here: the offset changes + * almost all the time -- that's the whole point of this routine! + */ nsz = v ? b->sz + b->off : (DA_INITSZ >> 1); do nsz <<= 1; while (nsz < rq); q = xmalloc(nsz * sz); q += (nsz - slots) * sz; - memcpy(q, p, b->len * sz); - if (p) + if (p) { + memcpy(q, p, b->len * sz); free(p - b->off * sz); + } b->off = nsz - slots; b->sz = slots; b->unshift = b->push = 0; diff --git a/darray.h b/darray.h index 93a806f..c04ca8b 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.2 1999/10/29 22:59:22 mdw Exp $ * * Dynamically growing dense arrays * @@ -30,6 +30,9 @@ /*----- Revision history --------------------------------------------------* * * $Log: darray.h,v $ + * 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'. * @@ -185,6 +188,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 +282,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,6 +335,68 @@ 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_PUSH@ --- * diff --git a/man/.cvsignore b/man/.cvsignore index dae32dd..f70943b 100644 --- a/man/.cvsignore +++ b/man/.cvsignore @@ -14,14 +14,19 @@ DA_LEN.3 DA_OFFSET.3 DA_POP.3 DA_PUSH.3 +DA_RESET.3 DA_SHIFT.3 +DA_SHRINK.3 DA_SHUNT.3 DA_SLIDE.3 DA_SPARE.3 DA_TIDY.3 DA_UNSAFE_EXTEND.3 +DA_UNSAFE_SHRINK.3 DA_UNSAFE_SLIDE.3 +DA_UNSAFE_UNSLIDE.3 DA_UNSHIFT.3 +DA_UNSLIDE.3 DCREATE.3 DDESTROY.3 DENSURE.3 diff --git a/man/darray.3 b/man/darray.3 index 76b0ced..548299b 100644 --- a/man/darray.3 +++ b/man/darray.3 @@ -29,6 +29,7 @@ darray \- dense, dynamically resizing arrays .\" @DA_ENSURE .\" @DA_SHUNT .\" @DA_TIDY +.\" @DA_RESET .\" @DA .\" @DA_LEN .\" @DA_SPARE @@ -38,6 +39,10 @@ darray \- dense, dynamically resizing arrays .\" @DA_UNSAFE_EXTEND .\" @DA_SLIDE .\" @DA_UNSAFE_SLIDE +.\" @DA_SHRINK +.\" @DA_UNSAFE_SHRINK +.\" @DA_UNSLIDE +.\" @DA_UNSAFE_UNSLIDE .\" @DA_PUSH .\" @DA_POP .\" @DA_UNSHIFT @@ -59,16 +64,23 @@ darray \- dense, dynamically resizing arrays .BI "void DA_ENSURE(" atype " *" a ", size_t " n ); .BI "void DA_SHUNT(" atype " *" a ", size_t " n ); .BI "void DA_TIDY(" atype " *" a ); +.BI "void DA_RESET(" atype " *" a ); .IB type " *DA(" atype " *" a ); .BI "size_t DA_LEN(" atype " *" a ); .BI "size_t DA_SPARE(" atype " *" a ); .BI "size_t DA_OFFSET(" atype " *" a ); .BI "void DA_INCLUDE(" atype " *" a ", size_t " i ); + .BI "void DA_EXTEND(" atype " *" a ", long " n ); -.BI "void DA_UNSAFE_EXTEND(" atype " *" a ", long " n ); +.BI "void DA_SHRINK(" atype " *" a ", long " n ); .BI "void DA_SLIDE(" atype " *" a ", long " n ); +.BI "void DA_UNSLIDE(" atype " *" a ", long " n ); + +.BI "void DA_UNSAFE_EXTEND(" atype " *" a ", long " n ); +.BI "void DA_UNSAFE_SHRINK(" atype " *" a ", long " n ); .BI "void DA_UNSAFE_SLIDE(" atype " *" a ", long " n ); +.BI "void DA_UNSAFE_UNSLIDE(" atype " *" a ", long " n ); .BI "void DA_PUSH(" atype " *" a ", " type " " x ); .IB type " DA_POP(" atype " *" a ); @@ -140,6 +152,12 @@ The macro takes one argument: the address of a dynamic array. It minimizes the amount of memory used by the array. This is a useful function to call when the array's size has finally settled down. +.PP +The macro +.B DA_RESET +accepts the address of an array. It reduces the length of the array to +zero. No storage is deallocated. Resetting arrays might not be a good +idea if the objects in the array are dynamically allocated. .SS "Accessing array elements" If .I a @@ -242,6 +260,19 @@ is thrown if The macro .B DA_UNSAFE_SLIDE does the same job, only without the error checking. +.PP +The macros +.B DA_SHRINK +and +.B DA_UNSLIDE +do the same things as +.B DA_EXTEND +and +.B DA_SLIDE +respectively, except that they interpret the sign of their second +arguments in the opposite way. This is useful if the argument is +unsigned (e.g., if it's based on +.BR DA_LEN ). There are unsafed versions of both these macros too. .SS "Stack operations" Dynamic arrays support Perl-like stack operations. Given an array (pointer) -- [mdw]