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

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