+++ /dev/null
-/* -*-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 <stdio.h>
-#include <string.h>
-#include <stdlib.h>
-
-#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 -------------------------------------------------*/
~mdw / mLib / blobdiff