| 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 |