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

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