X-Git-Url: https://www.chiark.greenend.org.uk/ucgi/~mdw/git/mLib/blobdiff_plain/3745e24b5b5526174fda7f83999a0ca301c4c146..dd3c57bc8cac59e0d657ee665ce462988d27d714:/darray.c diff --git a/darray.c b/darray.c index 0825bca..aa7e4a2 100644 --- a/darray.c +++ b/darray.c @@ -1,13 +1,11 @@ /* -*-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 --------------------------------------------------* +/*----- Licensing notice --------------------------------------------------* * * This file is part of the mLib utilities library. * @@ -15,26 +13,18 @@ * 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 @@ -42,11 +32,12 @@ #include #include "alloc.h" +#include "arena.h" #include "darray.h" /*----- Magic numbers -----------------------------------------------------*/ -#define DA_INITSZ 64 /* Default size for new array */ +#define DA_INITSZ 16 /* Default size for new array */ #define DA_SLOTS 8 /* Number of preshifted slots */ /*----- Main code ---------------------------------------------------------*/ @@ -100,10 +91,11 @@ void *da_ensure(da_base *b, void *v, size_t sz, size_t n) /* --- 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. + * moving the objects about in their existing storage. It's not worth + * bothering if there's not actually double the amount of space I need. */ - if (rq < b->sz + b->off) { + if (rq * 2 < b->sz + b->off) { q = p - (b->off - slots) * sz; memmove(q, p, b->len * sz); b->sz += b->off - slots; @@ -112,15 +104,37 @@ void *da_ensure(da_base *b, void *v, size_t sz, size_t n) return (q); } - /* --- Reallocate the array --- */ + /* --- Decide on a new size --- * + * + * There's a minimum possible size for the array which is used if it's + * currently completely empty. Otherwise I choose the smallest power of + * two which is big enough, starting at double the current size. + */ - nsz = v ? b->sz + b->off : DA_INITSZ; + 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); + + /* --- Reallocate the block --- * + * + * If I'm not changing the base offset then it's worth using @realloc@; + * otherwise there'll probably be two calls to @memcpy@ to shunt the data + * around so it's not worth bothering. + */ + + if (p && slots == b->off) { + q = x_realloc(b->a, p - b->off * sz, nsz * sz, b->sz + b->off); + q += slots * sz; + } else { + q = x_alloc(b->a, nsz * sz); + q += slots * sz; + if (p) { + memcpy(q, p, b->len * sz); + x_free(b->a, p - b->off * sz); + } + } + + /* --- Fill in the other parts of the base structure --- */ + b->off = slots; b->sz = nsz - slots; b->unshift = b->push = 0; @@ -179,10 +193,11 @@ void *da_shunt(da_base *b, void *v, size_t sz, size_t n) /* --- 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. + * moving the objects about in their existing storage. Again, if there's + * not actually twice the space needed, reallocate the array. */ - if (rq < b->sz + b->off) { + if (rq * 2 < b->sz + b->off) { q = p + (b->sz - slots) * sz; memmove(q, p, b->len * sz); b->off += b->sz - slots; @@ -191,15 +206,37 @@ 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! + */ + + /* --- Decide on a new size --- * + * + * There's a minimum possible size for the array which is used if it's + * currently completely empty. Otherwise I choose the smallest power of + * two which is big enough, starting at double the current size. + */ - nsz = v ? b->sz + b->off : DA_INITSZ; + nsz = v ? b->sz + b->off : (DA_INITSZ >> 1); do nsz <<= 1; while (nsz < rq); - q = xmalloc(nsz * sz); + + /* --- Reallocate the block --- * + * + * 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! + */ + + q = x_alloc(b->a, nsz * sz); q += (nsz - slots) * sz; - memcpy(q, p, b->len * sz); - if (p) - free(p - b->off * sz); + if (p) { + memcpy(q, p, b->len * sz); + x_free(b->a, p - b->off * sz); + } + + /* --- Fill in the other parts of the base structure --- */ + b->off = nsz - slots; b->sz = slots; b->unshift = b->push = 0; @@ -231,13 +268,13 @@ void *da_tidy(da_base *b, void *v, size_t sz) return (p); if (!b->len) { - free(p - b->off * sz); + xfree(p - b->off * sz); return (0); } - q = xmalloc(b->len * sz); + q = x_alloc(b->a, b->len * sz); memcpy(q, p, b->len * sz); - free(p - b->off * sz); + x_free(b->a, p - b->off * sz); b->sz = b->len; b->off = 0; return (q);