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

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