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

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