chiark - git - mdw - mLib/blob - darray.c

   1 /* -*-c-*-
   2  *
   3  * $Id: darray.c,v 1.7 2004/04/08 01:36:11 mdw Exp $
   4  *
   5  * Dynamically growing dense arrays
   6  *
   7  * (c) 1999 Straylight/Edgeware
   8  */
   9
  10 /*----- Licensing notice --------------------------------------------------*
  11  *
  12  * This file is part of the mLib utilities library.
  13  *
  14  * mLib is free software; you can redistribute it and/or modify
  15  * it under the terms of the GNU Library General Public License as
  16  * published by the Free Software Foundation; either version 2 of the
  17  * License, or (at your option) any later version.
  18  *
  19  * mLib is distributed in the hope that it will be useful,
  20  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  21  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  22  * GNU Library General Public License for more details.
  23  *
  24  * You should have received a copy of the GNU Library General Public
  25  * License along with mLib; if not, write to the Free
  26  * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  27  * MA 02111-1307, USA.
  28  */
  29
  30 /*----- Header files ------------------------------------------------------*/
  31
  32 #include <stdio.h>
  33 #include <string.h>
  34 #include <stdlib.h>
  35
  36 #include "alloc.h"
  37 #include "arena.h"
  38 #include "darray.h"
  39
  40 /*----- Magic numbers -----------------------------------------------------*/
  41
  42 #define DA_INITSZ 16                    /* Default size for new array */
  43 #define DA_SLOTS 8                      /* Number of preshifted slots */
  44
  45 /*----- Main code ---------------------------------------------------------*/
  46
  47 /* --- @da_ensure@ --- *
  48  *
  49  * Arguments:   @da_base *b@ = pointer to array base structure
  50  *              @void *v@ = pointer to array vector
  51  *              @size_t sz@ = size of individual array elements
  52  *              @size_t n@ = number of items required at the end
  53  *
  54  * Returns:     Pointer to newly allocated or adjusted array vector.
  55  *
  56  * Use:         Extends a dynamic array to accommodate a number of new items
  57  *              at its end.  This function is a helper for the @DA_ENSURE@
  58  *              macro, which should be used by preference.
  59  */
  60
  61 void *da_ensure(da_base *b, void *v, size_t sz, size_t n)
  62 {
  63   size_t rq = n + b->len;
  64   char *p = v, *q;
  65   size_t nsz;
  66   size_t slots;
  67
  68   /* --- Make sure there's something which needs doing --- *
  69    *
  70    * If there's enough space already then return immediately.
  71    */
  72
  73   if (rq < b->sz)
  74     return (p);
  75
  76   /* --- Compute a number of `unshift' slots --- *
  77    *
  78    * When returning from this function, the offset will be set to @slots@.
  79    * If @unshift@ is zero, there's no point in reserving slots.  Otherwise
  80    * choose a power of two greater than @unshift@, with a minimum of
  81    * @DA_SLOTS@.  Then add the number of slots to the requirement.
  82    */
  83
  84   if (!b->unshift)
  85     slots = 0;
  86   else {
  87     slots = DA_SLOTS;
  88     while (slots < b->unshift)
  89       slots <<= 1;
  90   }
  91   rq += slots;
  92
  93   /* --- Maybe just shunt data around a bit --- *
  94    *
  95    * If the vector is large enough, then theoretically we could cope by
  96    * moving the objects about in their existing storage.  It's not worth
  97    * bothering if there's not actually double the amount of space I need.
  98    */
  99
 100   if (rq * 2 < b->sz + b->off) {
 101     q = p - (b->off - slots) * sz;
 102     memmove(q, p, b->len * sz);
 103     b->sz += b->off - slots;
 104     b->off = slots;
 105     b->unshift = b->push = 0;
 106     return (q);
 107   }
 108
 109   /* --- Decide on a new size --- *
 110    *
 111    * There's a minimum possible size for the array which is used if it's
 112    * currently completely empty.  Otherwise I choose the smallest power of
 113    * two which is big enough, starting at double the current size.
 114    */
 115
 116   nsz = v ? b->sz + b->off : (DA_INITSZ >> 1);
 117   do nsz <<= 1; while (nsz < rq);
 118
 119   /* --- Reallocate the block --- *
 120    *
 121    * If I'm not changing the base offset then it's worth using @realloc@;
 122    * otherwise there'll probably be two calls to @memcpy@ to shunt the data
 123    * around so it's not worth bothering.
 124    */
 125
 126   if (p && slots == b->off) {
 127     q = x_realloc(b->a, p - b->off * sz, nsz * sz, b->sz + b->off);
 128     q += slots * sz;
 129   } else {
 130     q = x_alloc(b->a, nsz * sz);
 131     q += slots * sz;
 132     if (p) {
 133       memcpy(q, p, b->len * sz);
 134       x_free(b->a, p - b->off * sz);
 135     }
 136   }
 137
 138   /* --- Fill in the other parts of the base structure --- */
 139
 140   b->off = slots;
 141   b->sz = nsz - slots;
 142   b->unshift = b->push = 0;
 143   return (q);
 144 }
 145
 146 /* --- @da_shunt@ --- *
 147  *
 148  * Arguments:   @da_base *b@ = pointer to array base structure
 149  *              @void *v@ = pointer to array vector
 150  *              @size_t sz@ = size of the array elements
 151  *              @size_t n@ = number of items required at the start
 152  *
 153  * Returns:     Pointer to appropriately bodged vector.
 154  *
 155  * Use:         Extends an array to accommodate items inserted at its front.
 156  *              This function is a helper for the @DA_SHUNT@ macro, which
 157  *              should be used by preference.
 158  */
 159
 160 void *da_shunt(da_base *b, void *v, size_t sz, size_t n)
 161 {
 162   size_t rq;
 163   char *p = v, *q;
 164   size_t nsz;
 165   size_t slots;
 166
 167   /* --- Make sure there's something which needs doing --- *
 168    *
 169    * If there's enough space already then return immediately.
 170    */
 171
 172   if (n < b->off)
 173     return (p);
 174
 175   /* --- Compute a number of `push' slots --- *
 176    *
 177    * When returning from this function, there will be @slots@ free spaces at
 178    * the end of the array.  If @push@ is zero, there's no point in reserving
 179    * slots.  Otherwise choose a power of two greater than @push@, with a
 180    * minimum of @DA_SLOTS@.  To simplify matters, add the number of items
 181    * already in the array to @slots@, and then add the number of slots to the
 182    * requirement.
 183    */
 184
 185   if (!b->push)
 186     slots = 0;
 187   else {
 188     slots = DA_SLOTS;
 189     while (slots < b->push)
 190       slots <<= 1;
 191   }
 192   slots += b->len;
 193   rq = n + slots;
 194
 195   /* --- Maybe just shunt data around a bit --- *
 196    *
 197    * If the vector is large enough, then theoretically we could cope by
 198    * moving the objects about in their existing storage.  Again, if there's
 199    * not actually twice the space needed, reallocate the array.
 200    */
 201
 202   if (rq * 2 < b->sz + b->off) {
 203     q = p + (b->sz - slots) * sz;
 204     memmove(q, p, b->len * sz);
 205     b->off += b->sz - slots;
 206     b->sz = slots;
 207     b->unshift = b->push = 0;
 208     return (q);
 209   }
 210
 211   /* --- Reallocate the array --- *
 212    *
 213    * The neat @realloc@ code doesn't need to be here: the offset changes
 214    * almost all the time -- that's the whole point of this routine!
 215    */
 216
 217   /* --- Decide on a new size --- *
 218    *
 219    * There's a minimum possible size for the array which is used if it's
 220    * currently completely empty.  Otherwise I choose the smallest power of
 221    * two which is big enough, starting at double the current size.
 222    */
 223
 224   nsz = v ? b->sz + b->off : (DA_INITSZ >> 1);
 225   do nsz <<= 1; while (nsz < rq);
 226
 227   /* --- Reallocate the block --- *
 228    *
 229    * The neat @realloc@ code doesn't need to be here: the offset changes
 230    * almost all the time -- that's the whole point of this routine!
 231    */
 232
 233   q = x_alloc(b->a, nsz * sz);
 234   q += (nsz - slots) * sz;
 235   if (p) {
 236     memcpy(q, p, b->len * sz);
 237     x_free(b->a, p - b->off * sz);
 238   }
 239
 240   /* --- Fill in the other parts of the base structure --- */
 241
 242   b->off = nsz - slots;
 243   b->sz = slots;
 244   b->unshift = b->push = 0;
 245   return (q);
 246 }
 247
 248 /* --- @da_tidy@ --- *
 249  *
 250  * Arguments:   @da_base *b@ = pointer to array base structure
 251  *              @void *v@ = pointer to vector
 252  *              @size_t sz@ = size of the array elements
 253  *
 254  * Returns:     Newly allocated vector.
 255  *
 256  * Use:         Minimizes the space occupied by an array.  This function is a
 257  *              helper for the @DA_TIDY@ macro, which should be used by
 258  *              preference.
 259  */
 260
 261 void *da_tidy(da_base *b, void *v, size_t sz)
 262 {
 263   char *p = v, *q;
 264
 265   b->unshift = b->push = 0;
 266
 267   if (!p)
 268     return (0);
 269   if (b->sz == b->len && b->off == 0)
 270     return (p);
 271
 272   if (!b->len) {
 273     xfree(p - b->off * sz);
 274     return (0);
 275   }
 276
 277   q = x_alloc(b->a, b->len * sz);
 278   memcpy(q, p, b->len * sz);
 279   x_free(b->a, p - b->off * sz);
 280   b->sz = b->len;
 281   b->off = 0;
 282   return (q);
 283 }
 284
 285 /* --- Note about testing --- *
 286  *
 287  * The test rig for this code is split into three parts.  There's `da-gtest',
 288  * which is a Perl script which generates a list of commands.  The `da-ref'
 289  * Perl script interprets these commands as operations on a Perl array.  It's
 290  * relatively conservatively written and believed to be reliable.  The
 291  * `da-test.c' file implements a command reader for the same syntax and
 292  * performs the operations on an integer darray, producing output in the same
 293  * format.  To test darray, generate a command script with `da-gtest', pass
 294  * it through both `da-ref' and `da-test' (the result of compiling
 295  * da-test.c'), and compare the results.  If they're not byte-for-byte
 296  * identical, there's something wrong.
 297  */
 298
 299 /*----- That's all, folks -------------------------------------------------*/