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

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