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

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