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

   1 /* -*-c-*-
   2  *
   3  * $Id: darray.h,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.h,v $
  33  * Revision 1.1  1999/10/22 22:37:26  mdw
  34  * New dynamic array implementation replaces `dynarray.h'.
  35  *
  36  */
  37
  38 #ifndef DARRAY_H
  39 #define DARRAY_H
  40
  41 #ifdef __cplusplus
  42   extern "C" {
  43 #endif
  44
  45 /*----- Header files ------------------------------------------------------*/
  46
  47 #include <stdio.h>
  48 #include <stdlib.h>
  49 #include <string.h>
  50
  51 #ifndef ALLOC_H
  52 #  include "alloc.h"
  53 #endif
  54
  55 #ifndef EXC_H
  56 #  include "exc.h"
  57 #endif
  58
  59 /*----- Various important constants ---------------------------------------*/
  60
  61 /* --- @DAEXC_UFLOW@, @DAEXC_OFLOW@ --- *
  62  *
  63  * Underflow and overflow exceptions raised by @DA_SHIFT@, and by @DA_POP@
  64  * and @DA_SHIFT@.
  65  */
  66
  67 #define DAEXC_UFLOW EXC_ALLOCN(EXC_MLIB, 0)
  68 #define DAEXC_OFLOW EXC_ALLOCN(EXC_MLIB, 1)
  69
  70 /*----- Data structures ---------------------------------------------------*/
  71
  72 /* --- Base structure for dynamic arrays --- *
  73  *
  74  * An actual array has a `vector' @v@ in addition to this data (which is
  75  * tucked away in the @b@ member).  The vector contains the actual storage
  76  * for the array elements.
  77  *
  78  * The vector pointer @v@ potentially points somewhere in the middle of the
  79  * allocated storage.  The @off@ member explains how far into the storage the
  80  * vector points.  The allocated storage is sufficient for @sz + off@ items
  81  * to be stored.  Valid array indices are integers between 0 (inclusive) and
  82  * @len@ (exclusive).  Thus, from @v@ onwards, there is space for @sz@
  83  * elements, and of these, @sz - len@ are currently not considered to be
  84  * within the array's bounds.
  85  *
  86  * The @push@ and @unshift@ counts record how many times these operations
  87  * have been performed since the last extension of the array.  They are used
  88  * by the extension algorithm to decide how to position the data offset.
  89  *
  90  * Try to use the access macros rather than the structure members.
  91  */
  92
  93 typedef struct da_base {
  94   size_t sz;                            /* Size of allocated vector */
  95   size_t len;                           /* Length of useful portion */
  96   size_t off;                           /* Offset of @v@ into space */
  97   unsigned push, unshift;               /* Pushes/unshifts since growth */
  98 } da_base;
  99
 100 /* --- @DA_DECL@ --- *
 101  *
 102  * Arguments:   @atype@ = type name for the array
 103  *              @type@ = item type for the array
 104  *
 105  * Use:         Declares a structure for decribing a dynamic array.
 106  */
 107
 108 #define DA_DECL(atype, type)                                            \
 109   typedef struct atype { da_base b; type *v; } atype
 110
 111 /*----- Initialization, creation and destruction --------------------------*/
 112
 113 #define DA_INIT { { 0, 0, 0, 0, 0 }, 0 } /* Standard initializer */
 114
 115 /* --- @DA_CREATE@ --- *
 116  *
 117  * Arguments:   @a@ = pointer to an array block (multiply evaluated)
 118  *
 119  * Use:         Initializes an array block.
 120  */
 121
 122 #define DA_CREATE(a) do {                                               \
 123   (a)->b.sz = (a)->b.len = 0;                                           \
 124   (a)->b.off = 0;                                                       \
 125   (a)->b.push = (a)->b.unshift = 0;                                     \
 126   (a)->v = 0;                                                           \
 127 } while (0)
 128
 129 /* --- @DA_DESTROY@ --- *
 130  *
 131  * Arguments:   @a@ = pointer to an array block (multiply evaluated)
 132  *
 133  * Use:         Destroys an array.  The array is left valid but empty.
 134  */
 135
 136 #define DA_DESTROY(a) do {                                              \
 137   if ((a)->v)                                                           \
 138     free((a)->v - (a)->b.off);                                          \
 139   DA_CREATE(a);                                                         \
 140 } while (0)
 141
 142 /*----- Storage reservation -----------------------------------------------*/
 143
 144 /* --- @DA_ENSURE@ --- *
 145  *
 146  * Arguments:   @a@ = pointer to an array block (multiply evaluated)
 147  *              @n@ = required number of spare items in the array
 148  *
 149  * Use:         Ensures that there are at least @n@ spare slots at the end of
 150  *              the array.
 151  */
 152
 153 #define DA_ENSURE(a, n) do {                                            \
 154   size_t _n = (n);                                                      \
 155   if (_n > (a)->b.sz - (a)->b.len)                                      \
 156     (a)->v = da_ensure(&(a)->b, (a)->v, sizeof((a)->v[0]), _n);         \
 157   else                                                                  \
 158     (a)->b.push += _n;                                                  \
 159 } while (0)
 160
 161 /* --- @DA_SHUNT@ --- *
 162  *
 163  * Arguments:   @a@ = pointer to an array block (multiply evaluated)
 164  *              @n@ = required number of spare items in the array
 165  *
 166  * Use:         Ensures that there are at least @n@ spare slots at the start
 167  *              of the array.
 168  */
 169
 170 #define DA_SHUNT(a, n) do {                                             \
 171   size_t _n = (n);                                                      \
 172   if (_n > (a)->b.off)                                                  \
 173     (a)->v = da_shunt(&(a)->b, (a)->v, sizeof((a)->v[0]), _n);          \
 174   else                                                                  \
 175     (a)->b.unshift += _n;                                               \
 176 } while (0)
 177
 178 /* --- @DA_TIDY@ --- *
 179  *
 180  * Arguments:   @a@ = pointer to an array block (multiply evaluated)
 181  *
 182  * Use:         Reduces the amount of storage required by an array to its
 183  *              minimum possible.
 184  */
 185
 186 #define DA_TIDY(a) ((a)->v = da_tidy(&(a)->b, (a)->v, sizeof((a)->v[0])))
 187
 188 /*----- Access operations -------------------------------------------------*/
 189
 190 /* --- @DA@ --- *
 191  *
 192  * Arguments:   @a@ = pointer to array block
 193  *
 194  * Use:         Expands to a reference to the array proper.  Given an array
 195  *              @a@, item @i@ may be located using the expression @DA(a)[i]@.
 196  */
 197
 198 #define DA(a) ((a)->v + 0)
 199
 200 /* --- @DA_LEN@ --- *
 201  *
 202  * Arguments:   @a@ = pointer to array block
 203  *
 204  * Use:         Expands to the number of elements in the array.  Elements are
 205  *              assigned integer indices in the half-open interval
 206  *              [0, @DA_LEN(a)@).  Don't change the length directly; use
 207  *              @DA_EXTEND@ instead.
 208  */
 209
 210 #define DA_LEN(a) ((a)->b.len + 0)
 211
 212 /* --- @DA_SPARE@ --- *
 213  *
 214  * Arguments:   @a@ = pointer to array block (multiply evaluated)
 215  *
 216  * Use:         Evaluates to the number of spare array elements above the
 217  *              end of the array.
 218  */
 219
 220 #define DA_SPARE(a) ((a)->b.sz - (a)->b.len)
 221
 222 /* --- @DA_INCLUDE@ --- *
 223  *
 224  * Arguments:   @a@ = pointer to array block (multiply evaluated)
 225  *              @i@ = index into array
 226  *
 227  * Use:         Extends the array (if necessary) so that it includes the
 228  *              index @i@.
 229  */
 230
 231 #define DA_INCLUDE(a, i) do {                                           \
 232   size_t _i = (i);                                                      \
 233   size_t _len = DA_LEN(a);                                              \
 234   if (_i >= _len) {                                                     \
 235     size_t _nn = _i - _len + 1;                                         \
 236     DA_ENSURE(a, _nn);                                                  \
 237     DA_UNSAFE_EXTEND(a, _nn);                                           \
 238   }                                                                     \
 239 } while (0)
 240
 241 /* --- @DA_OFFSET@ --- *
 242  *
 243  * Arguments:   @a@ = pointer to array block
 244  *
 245  * Use:         Evaluates to the number of spare elements before the
 246  *              beginning of the array.  Don't modify the offset directly;
 247  *              use @DA_SLIDE@ instead.
 248  */
 249
 250 #define DA_OFFSET(a) ((a)->b.off + 0)
 251
 252 /* --- @DA_EXTEND@ --- *
 253  *
 254  * Arguments:   @a@ = pointer to array block (multiply evaluated)
 255  *              @n@ = number of slots to add (multiply evaluated)
 256  *
 257  * Use:         Extends the end of the array by @n@ elements.  The exception
 258  *              @DAEXC_OFLOW@ is thrown if there is not enough space for the
 259  *              new elements (i.e., @n > DA_SPARE(a)@) -- call @DA_ENSURE@ to
 260  *              prevent this from happening.  The integer @n@ may be
 261  *              negative; @DAEXC_UFLOW@ is called if @n < DA_LEN(a)@.
 262  */
 263
 264 #define DA_EXTEND(a, n) do {                                            \
 265   if ((n) > 0 && (n) > DA_SPARE(a))                                     \
 266     THROW(DAEXC_OFLOW);                                                 \
 267   else if ((n) < 0 && -(n) > DA_LEN(a))                                 \
 268     THROW(DAEXC_UFLOW);                                                 \
 269   DA_UNSAFE_EXTEND(a, n);                                               \
 270 } while (0)
 271
 272 /* --- @DA_EXTEND@ --- *
 273  *
 274  * Arguments:   @a@ = pointer to array block (multiply evaluated)
 275  *              @n@ = number of slots to add (multiply evaluated)
 276  *
 277  * Use:         As for @DA_EXTEND@, only it doesn't check for errors.
 278  */
 279
 280 #define DA_UNSAFE_EXTEND(a, n) do {                                     \
 281   (a)->b.len += (n);                                                    \
 282 } while (0)
 283
 284 /* --- @DA_SLIDE@ --- *
 285  *
 286  * Arguments:   @a@ = pointer to array block (multiply evaluated)
 287  *              @n@ = number of positions to slide the array (multiply
 288  *                      evaluated)
 289  *
 290  *
 291  * Use:         Slides the array elements by @n@ positions.  A positive @n@
 292  *              slides upwards, introducing new elements at the bottom; a
 293  *              negative @n@ slides downwards, removing low-numbered
 294  *              elements.  Formally, what was at index @i - n@ before the
 295  *              slide is moved to index @i@.  It is an error to slide by more
 296  *              than @DA_OFFSET(a)@ or less than @-DA_LEN(a)@.  The exception
 297  *              @DAEXC_OFLOW@ is raised in the former case, and @DAEXC_UFLOW@
 298  *              in the latter.
 299  */
 300
 301 #define DA_SLIDE(a, n) do {                                             \
 302   if ((n) > 0 && (n) > DA_OFFSET(a))                                    \
 303     THROW(DAEXC_OFLOW);                                                 \
 304   else if ((n) < 0 && -(n) > DA_LEN(a))                                 \
 305     THROW(DAEXC_UFLOW);                                                 \
 306   DA_UNSAFE_SLIDE((a), (n));                                            \
 307 } while (0)
 308
 309 /* --- @DA_UNSAFE_SLIDE@ --- *
 310  *
 311  * Arguments:   @a@ = pointer to array block (multiply evaluated)
 312  *              @n@ = number of positions to slide the array (multiply
 313  *                      evaluated)
 314  *
 315  * Use:         As for @DA_SLIDE@, only it doesn't check for errors.
 316  */
 317
 318 #define DA_UNSAFE_SLIDE(a, n) do {                                      \
 319   (a)->v -= (n);                                                        \
 320   (a)->b.len += (n);                                                    \
 321   (a)->b.sz += (n);                                                     \
 322   (a)->b.off -= (n);                                                    \
 323 } while (0)
 324
 325 /*----- Stack-like operations ---------------------------------------------*/
 326
 327 /* --- @DA_PUSH@ --- *
 328  *
 329  * Arguments:   @a@ = pointer to an array block (multiply evaluated)
 330  *              @x@ = item to append to the end
 331  *
 332  * Use:         Appends @x@ as the final element in the array @a@.
 333  */
 334
 335 #define DA_PUSH(a, x) do {                                              \
 336   DA_ENSURE(a, 1);                                                      \
 337   DA(a)[(a)->b.len++] = x;                                              \
 338 } while (0)
 339
 340 /* --- @DA_POP@ --- *
 341  *
 342  * Arguments:   @a@ = pointer to an array block (multiply evaluated)
 343  *
 344  * Use:         Evaluates to the final element in array @a@.  The element is
 345  *              removed.  An exception @DAEXC_UFLOW@ is raised if there is
 346  *              no item available to pop.
 347  */
 348
 349 #define DA_POP(a)                                                       \
 350   ((a)->b.len ? ((void)0) : THROW(DAEXC_UFLOW),                         \
 351    DA(a)[--(a)->b.len])
 352
 353 /* --- @DA_UNSHIFT@ --- *
 354  *
 355  * Arguments:   @a@ = pointer to an array block (multiply evaluated)
 356  *              @x@ = the new element to insert
 357  *
 358  * Use:         Inserts a new element at the beginning of an array.  This
 359  *              might take a while.
 360  */
 361
 362 #define DA_UNSHIFT(a, x) do {                                           \
 363   DA_SHUNT(a, 1);                                                       \
 364   DA_UNSAFE_SLIDE(a, 1);                                                \
 365   DA(a)[0] = x;                                                         \
 366 } while (0)
 367
 368 /* --- @DA_SHIFT@ --- *
 369  *
 370  * Arguments:   @a@ = pointer to an array block (multiply evaluated)
 371  *
 372  * Use:         Evaluates to the initial element in array @a@.  The element
 373  *              is removed, and all other elements are shifted down one
 374  *              place.  The exception @DAEXC_UFLOW@ is raised if there is no
 375  *              element to return.
 376  */
 377
 378 #define DA_SHIFT(a)                                                     \
 379   ((a)->b.len ? ((void)0) : THROW(DAEXC_UFLOW),                 \
 380    (a)->b.len--,                                                        \
 381    (a)->b.sz--,                                                         \
 382    (a)->b.off++,                                                        \
 383    *(a)->v++)
 384
 385 /*----- Functions provided ------------------------------------------------*/
 386
 387 /* --- @da_ensure@ --- *
 388  *
 389  * Arguments:   @da_base *b@ = pointer to array base structure
 390  *              @void *v@ = pointer to array vector
 391  *              @size_t sz@ = size of individual array elements
 392  *              @size_t n@ = number of items required at the end
 393  *
 394  * Returns:     Pointer to newly allocated or adjusted array vector.
 395  *
 396  * Use:         Extends a dynamic array to accommodate a number of new items
 397  *              at its end.  This function is a helper for the @DA_ENSURE@
 398  *              macro, which should be used by preference.
 399  */
 400
 401 extern void *da_ensure(da_base */*b*/, void */*v*/,
 402                        size_t /*sz*/, size_t /*n*/);
 403
 404 /* --- @da_shunt@ --- *
 405  *
 406  * Arguments:   @da_base *b@ = pointer to array base structure
 407  *              @void *v@ = pointer to array vector
 408  *              @size_t sz@ = size of the array elements
 409  *              @size_t n@ = number of items required at the start
 410  *
 411  * Returns:     Pointer to appropriately bodged vector.
 412  *
 413  * Use:         Extends an array to accommodate items inserted at its front.
 414  *              This function is a helper for the @DA_SHUNT@ macro, which
 415  *              should be used by preference.
 416  */
 417
 418 extern void *da_shunt(da_base */*b*/, void */*v*/,
 419                       size_t /*sz*/, size_t /*n*/);
 420
 421 /* --- @da_tidy@ --- *
 422  *
 423  * Arguments:   @da_base *b@ = pointer to array base structure
 424  *              @void *v@ = pointer to vector
 425  *              @size_t sz@ = size of the array elements
 426  *
 427  * Returns:     Newly allocated vector.
 428  *
 429  * Use:         Minimizes the space occupied by an array.  This function is a
 430  *              helper for the @DA_TIDY@ macro, which should be used by
 431  *              preference.
 432  */
 433
 434 extern void *da_tidy(da_base */*b*/, void */*v*/, size_t /*sz*/);
 435
 436 /*----- That's all, folks -------------------------------------------------*/
 437
 438 #ifdef __cplusplus
 439   }
 440 #endif
 441
 442 #endif