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