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

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