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

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