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

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