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

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