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

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