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