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