X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~mdw/git/mLib/blobdiff_plain/dd3c57bc8cac59e0d657ee665ce462988d27d714..18c831dcd0ae4d660c70ccac69d27ed2a97851be:/darray.c diff --git a/darray.c b/darray.c deleted file mode 100644 index aa7e4a2..0000000 --- a/darray.c +++ /dev/null @@ -1,297 +0,0 @@ -/* -*-c-*- - * - * 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. - */ - -/*----- Header files ------------------------------------------------------*/ - -#include -#include -#include - -#include "alloc.h" -#include "arena.h" -#include "darray.h" - -/*----- Magic numbers -----------------------------------------------------*/ - -#define DA_INITSZ 16 /* 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. It's not worth - * bothering if there's not actually double the amount of space I need. - */ - - if (rq * 2 < 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); - } - - /* --- 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 >> 1); - do nsz <<= 1; while (nsz < rq); - - /* --- 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; - 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. Again, if there's - * not actually twice the space needed, reallocate the array. - */ - - if (rq * 2 < 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 --- * - * - * 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 >> 1); - do nsz <<= 1; while (nsz < rq); - - /* --- 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; - 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; - 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) { - xfree(p - b->off * sz); - return (0); - } - - q = x_alloc(b->a, b->len * sz); - memcpy(q, p, b->len * sz); - x_free(b->a, 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 -------------------------------------------------*/