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

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