chiark - git - mdw - mLib/blob - struct/darray.3.in

   1 .\" -*-nroff-*-
   2 .\"
   3 .\" Manual for dynamically growing arrays
   4 .\"
   5 .\" (c) 1999--2001, 2005, 2009, 2023, 2024 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 it under
  13 .\" the terms of the GNU Library General Public License as published by
  14 .\" the Free Software Foundation; either version 2 of the License, or (at
  15 .\" your option) any later version.
  16 .\"
  17 .\" mLib is distributed in the hope that it will be useful, but WITHOUT
  18 .\" ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  19 .\" FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Library General Public
  20 .\" 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 Software
  24 .\" Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307,
  25 .\" USA.
  26 .
  27 .\"--------------------------------------------------------------------------
  28 .so ../defs.man \" @@@PRE@@@
  29 .
  30 .\"--------------------------------------------------------------------------
  31 .TH darray 3mLib "21 October 1999" "Straylight/Edgeware" "mLib utilities library"
  32 .\" @DA_INIT
  33 .\" @DA_DECL
  34 .\" @DA_CREATE
  35 .\" @DA_DESTROY
  36 .\" @DA_ENSURE
  37 .\" @DA_SHUNT
  38 .\" @DA_TIDY
  39 .\" @DA_RESET
  40 .\" @DA
  41 .\" @DA_LEN
  42 .\" @DA_SPARE
  43 .\" @DA_OFFSET
  44 .\" @DA_INCLUDE
  45 .\" @DA_EXTEND
  46 .\" @DA_UNSAFE_EXTEND
  47 .\" @DA_SLIDE
  48 .\" @DA_UNSAFE_SLIDE
  49 .\" @DA_SHRINK
  50 .\" @DA_UNSAFE_SHRINK
  51 .\" @DA_UNSLIDE
  52 .\" @DA_UNSAFE_UNSLIDE
  53 .\" @DA_FIRST
  54 .\" @DA_LAST
  55 .\" @DA_PUSH
  56 .\" @DA_POP
  57 .\" @DA_UNSHIFT
  58 .\" @DA_SHIFT
  59 .\" @DAEXC_UFLOW
  60 .\" @DAEXC_OFLOW
  61 .\" @da_ensure
  62 .\" @da_shunt
  63 .\" @da_tidy
  64 .
  65 .\"--------------------------------------------------------------------------
  66 .SH "NAME"
  67 darray \- dense, dynamically resizing arrays
  68 .
  69 .\"--------------------------------------------------------------------------
  70 .SH "SYNOPSIS"
  71 .
  72 .nf
  73 .B "#include <mLib/darray.h>"
  74 .PP
  75 .ta 2n
  76 .B "typedef struct {"
  77 .B "    size_t sz, len, off;"
  78 .B "    unsigned push, unshift;"
  79 .B "    arena *a;"
  80 .B "} da_base;"
  81 .PP
  82 .B "#define DA_INIT ..."
  83 .PP
  84 .B "#define DAEXC_UFLOW EXC_ALLOCN(EXC_MLIB, ...)"
  85 .B "#define DAEXC_OFLOW EXC_ALLOCN(EXC_MLIB, ...)"
  86 .PP
  87 .BI DA_DECL( type_v ", " type );
  88 .BI "void DA_CREATE(" type_v " *" a );
  89 .BI "void DA_DESTROY(" type_v " *" a );
  90 .PP
  91 .BI "void DA_ENSURE(" type_v " *" a ", size_t " n );
  92 .BI "void DA_SHUNT(" type_v " *" a ", size_t " n );
  93 .BI "void DA_TIDY(" type_v " *" a );
  94 .BI "void DA_RESET(" type_v " *" a );
  95 .PP
  96 .IB type " *DA(" type_v " *" a );
  97 .BI "size_t DA_LEN(" type_v " *" a );
  98 .BI "size_t DA_SPARE(" type_v " *" a );
  99 .BI "size_t DA_OFFSET(" type_v " *" a );
 100 .BI "void DA_INCLUDE(" type_v " *" a ", size_t " i );
 101 .PP
 102 .BI "void DA_EXTEND(" type_v " *" a ", long " n );
 103 .BI "void DA_SHRINK(" type_v " *" a ", long " n );
 104 .BI "void DA_SLIDE(" type_v " *" a ", long " n );
 105 .BI "void DA_UNSLIDE(" type_v " *" a ", long " n );
 106 .PP
 107 .BI "void DA_UNSAFE_EXTEND(" type_v " *" a ", long " n );
 108 .BI "void DA_UNSAFE_SHRINK(" type_v " *" a ", long " n );
 109 .BI "void DA_UNSAFE_SLIDE(" type_v " *" a ", long " n );
 110 .BI "void DA_UNSAFE_UNSLIDE(" type_v " *" a ", long " n );
 111 .PP
 112 .IB type " DA_FIRST(" type_v " *" a );
 113 .IB type " DA_LAST(" type_v " *" a );
 114 .BI "void DA_PUSH(" type_v " *" a ", " type " " x );
 115 .IB type " DA_POP(" type_v " *" a );
 116 .BI "void DA_UNSHIFT(" type_v " *" a ", " type " " x );
 117 .IB type " DA_SHIFT(" type_v " *" a );
 118 .PP
 119 .BI "void *da_ensure(da_base *" b ", void *" v ", size_t " sz ", size_t " n );
 120 .BI "void *da_shunt(da_base *" b ", void *" v ", size_t " sz ", size_t " n );
 121 .BI "void *da_tidy(da_base *" b ", void *" v ", size_t " sz );
 122 .fi
 123 .
 124 .\"--------------------------------------------------------------------------
 125 .SH "DESCRIPTION"
 126 .
 127 The
 128 .B <mLib/darray.h>
 129 header file declares a collection of types, macros and functions which
 130 implement dynamically resizing arrays.
 131 .PP
 132 The macros described here may evaluate their arguments multiple times
 133 unless otherwise specified.
 134 .
 135 .SS "Creation and destruction"
 136 Each element type must have its own array
 137 type declared using the
 138 .B DA_DECL
 139 macro.  Calling
 140 .VS
 141 .BI DA_DECL( type_v ", " type );
 142 .VE
 143 Declares a new dynamic array type
 144 .I type_v
 145 whose elements have type
 146 .IR type .
 147 .PP
 148 It is conventional to form the name of an array type by appending
 149 .RB ` _v '
 150 to the base type name.  If the base type is a standard type, or is
 151 declared separately from the array, it's also conventional to declare a
 152 macro with the same name as the array type only in uppercase which may
 153 be used to prevent multiple declarations, e.g.,
 154 .VS
 155 .ta 2n
 156 #ifndef FOO_V
 157 #       define FOO_V
 158         DA_DECL(foo_v, foo);
 159 #endif
 160 .VE
 161 The macro
 162 .B DA_INIT
 163 is a valid static initializer for all types of dynamic arrays.  For
 164 cases where this isn't appropriate, a dynamic array may be initialized
 165 using the macro
 166 .BR DA_CREATE ,
 167 passing it the address of the array.
 168 .PP
 169 Arrays may be disposed of using the
 170 .B DA_DESTROY
 171 macro, which again takes the address of the array.
 172 .
 173 .SS "Storage allocation"
 174 .PP
 175 Space for new array elements may be reserved using the
 176 .B DA_ENSURE
 177 and
 178 .B DA_SHUNT
 179 macros, which reserve space at the end and beginning of the array
 180 respectively.  Both macros take two arguments: the address of an array
 181 object and the number of spare elements required.
 182 .PP
 183 Neither of these macros actually extends the array; both merely allocate
 184 memory for the array to extend itself into.  Use the macros
 185 .B DA_EXTEND
 186 and
 187 .B DA_SLIDE
 188 to actually increase the bounds of the array.
 189 .PP
 190 Note that when space is reserved, all the array elements might move.
 191 You should be careful not to depend on the addresses of array elements.
 192 If sufficient storage cannot be allocated, the exception
 193 .B EXC_NOMEM
 194 is thrown (see
 195 .BR exc (3)).
 196 .PP
 197 The macro
 198 .B DA_TIDY
 199 takes one argument: the address of a dynamic array.  It minimizes the
 200 amount of memory used by the array.  This is a useful function to call
 201 when the array's size has finally settled down.
 202 .PP
 203 The macro
 204 .B DA_RESET
 205 accepts the address of an array.  It reduces the length of the array to
 206 zero.  No storage is deallocated.  Resetting arrays might not be a good
 207 idea if the objects in the array are dynamically allocated.
 208 .
 209 .SS "Accessing array elements"
 210 If
 211 .I a
 212 is the address of a dynamic array object, then
 213 .BI DA( a )
 214 is the base address of the actual array.  The elements are stored
 215 contiguously starting at this address.  An element at index
 216 .I i
 217 may be referenced using the syntax
 218 .BI DA( a )[ i ]\fR.
 219 .PP
 220 The number of elements in the array
 221 .I a
 222 is given by
 223 .BI DA_LEN( a )\fR.
 224 An integer array index
 225 .I i
 226 is
 227 .I valid
 228 if 0 \(<=
 229 .I i
 230 <
 231 .BI DA_LEN( a )\fR.
 232 .PP
 233 There may be some spare slots at the end of the array.  In particular,
 234 after a call to
 235 .BI DA_ENSURE( a ", " n )
 236 there will be at least
 237 .I n
 238 spare slots.  The number of spare slots at the end of the array may be
 239 obtained as
 240 .BI DA_SPARE( a )\fR.
 241 .PP
 242 Similarly, there may be spare slots before the start of the array.  In
 243 particular, after a call to
 244 .BI DA_SHUNT( a ", " n )
 245 there will be at least
 246 .I n
 247 spare slots.  The number of spare slots before the start of the array
 248 may be obtained as
 249 .BI DA_OFFSET( a )\fR.
 250 .PP
 251 The call
 252 .BI DA_INCLUDE( a ", " i )
 253 ensures that the array's bounds include the index
 254 .I i
 255 by extending the array if necessary.  The exception
 256 .B EXC_NOMEM
 257 is thrown if there isn't enough memory to do this.
 258 .PP
 259 The array's bounds may be extended by
 260 .I n
 261 slots by calling
 262 .BI DA_EXTEND( a ", " n )\fR.
 263 The integer
 264 .I n
 265 must be less than
 266 .BI DA_SPARE( a )\fR;
 267 if this is not the case then the exception
 268 .B DAEXC_OFLOW
 269 is thrown.
 270 Note that
 271 .I n
 272 may be negative to reduce the bounds of the array: in this case it must
 273 be greater than
 274 .BI \-DA_LEN( a )
 275 or the exception
 276 .B DAEXC_UFLOW
 277 is thrown.  The macro
 278 .B DA_UNSAFE_EXTEND
 279 does the same job, but performs no error checking.
 280 .PP
 281 The macro
 282 .BI DA_SLIDE( a ", " n )
 283 offsets the array elements by
 284 .IR n .
 285 If
 286 .I n
 287 is positive, the array elements are slid upwards, to higher-numbered
 288 indices; if
 289 .I n
 290 is negative, the elements are slid downwards.  Precisely, what happens
 291 is that elements which used to have index
 292 .I i
 293 \-
 294 .I n
 295 now have index
 296 .IR i .
 297 The exception
 298 .B DAEXC_OFLOW
 299 is thrown if
 300 .I n
 301 >
 302 .BI DA_OFFSET( a )\fR;
 303 .B DAEXC_UFLOW
 304 is thrown if
 305 .I n
 306 <
 307 .BI \-DA_LEN( a )\fR.
 308 The macro
 309 .B DA_UNSAFE_SLIDE
 310 does the same job, only without the error checking.
 311 .PP
 312 The macros
 313 .B DA_SHRINK
 314 and
 315 .B DA_UNSLIDE
 316 do the same things as
 317 .B DA_EXTEND
 318 and
 319 .B DA_SLIDE
 320 respectively, except that they interpret the sign of their second
 321 arguments in the opposite way.  This is useful if the argument is
 322 unsigned (e.g., if it's based on
 323 .BR DA_LEN ).
 324 There are unsafe versions of both these macros too.
 325 .
 326 .SS "Stack operations"
 327 Dynamic arrays support Perl-like stack operations.  Given an array
 328 (pointer)
 329 .I a
 330 and an object of the array's element type
 331 .I x
 332 the following operations are provided:
 333 .TP
 334 .BI DA_PUSH( a ", " x )
 335 Add
 336 .I x
 337 to the end of the array, increasing the array size by one.
 338 .TP
 339 .IB x " = DA_POP(" a )
 340 Remove the final element of the array, assigning
 341 .I x
 342 its value and decreasing the array size by one.
 343 .TP
 344 .BI DA_UNSHIFT( a ", " x )
 345 Insert
 346 .I x
 347 at the beginning of the array, shifting all the elements up one place
 348 and increasing the array size by one.
 349 .TP
 350 .IB x " = DA_SHIFT(" a )
 351 Remove the first element of the array, assigning
 352 .I x
 353 its value, shifting all the subsequent array items down one place and
 354 decreasing the array size by one.
 355 .PP
 356 The operations
 357 .B DA_PUSH
 358 and
 359 .B DA_UNSHIFT
 360 can fail due to lack of memory, in which case
 361 .B EXC_NOMEM
 362 is thrown.  The operations
 363 .B DA_POP
 364 and
 365 .B DA_SHIFT
 366 can fail because the array is empty, in which case
 367 .B DAEXC_UFLOW
 368 is thrown.
 369 .PP
 370 The operations
 371 .B DA_FIRST
 372 and
 373 .B DA_LAST
 374 are lvalues referring to the first and last elements in the array
 375 respectively.  They are unsafe if the array is empty.
 376 .
 377 .SS "Low-level details"
 378 This section describes low-level details of the dynamic array
 379 implementation.  You should try to avoid making use of this information
 380 if you can, since the interface may change in later library versions.
 381 In particular, more subtleties may be added which low-level access will
 382 miss.
 383 .PP
 384 Dynamic arrays are structures with the format
 385 .VS
 386 .ta 2n
 387 .BI "typedef struct " type_v " {"
 388 .B "    da_base b;"
 389 .BI "   " type " *v;"
 390 .BI "} " type_v ";"
 391 .VE
 392 The pointer
 393 .B v
 394 indicates the current base of the array.  This will move in the
 395 allocated space as a result of
 396 .B DA_SHIFT
 397 and
 398 .B DA_UNSHIFT
 399 (and
 400 .BR DA_SLIDE )
 401 operations.
 402 .PP
 403 The
 404 .B da_base
 405 structure contains the following elements:
 406 .TP
 407 .B "size_t sz"
 408 The number of allocated slots from
 409 .B v
 410 onwards.
 411 .TP
 412 .B "size_t len"
 413 The number of items considered to be in the array.  The allocated space
 414 is usually larger than this.
 415 .TP
 416 .B "size_t off"
 417 The number of allocated slots preceding
 418 .BR v .
 419 The total number of allocated items is therefore
 420 .B sz
 421 +
 422 .BR off .
 423 .TP
 424 .B "unsigned push"
 425 The number of items pushed or ensured since the last array expansion.
 426 .TP
 427 .B "unsigned unshift"
 428 The number of items unshifted or shunted since the last array expansion.
 429 .PP
 430 The
 431 .B push
 432 and
 433 .B unshift
 434 members are used by the expansion routines to decide how to allocate
 435 free space before and after the array elements following a reallocation.
 436 The other members should be fairly self-explanatory.
 437 .PP
 438 The reallocation routines
 439 .BR da_ensure ,
 440 .B da_shunt
 441 and
 442 .B da_tidy
 443 have a regular interface.  They're a bit
 444 strange, though, because they have to deal with lots of different types
 445 of arrays.  The arguments they take are:
 446 .TP
 447 .BI "da_base *" b
 448 Pointer to the
 449 .B da_base
 450 member of the array block.
 451 .TP
 452 .BI "void *" v
 453 The array base pointer from the array block (i.e., the
 454 .B v
 455 member).
 456 .TP
 457 .BI "size_t " sz
 458 The element size for the array.
 459 .TP
 460 .BI "size_t " n
 461 (For
 462 .B da_ensure
 463 and
 464 .B da_shunt
 465 only.)  The number of spare slots required.
 466 .PP
 467 The functions may modify the base structure, and return a newly
 468 allocated (or at least repositioned) array base pointer, or throw
 469 .B EXC_NOMEM
 470 if there's not enough memory.
 471 .PP
 472 The three functions behave as follows:
 473 .TP
 474 .B da_ensure
 475 Ensure that there are at least
 476 .I n
 477 spare slots after the end of the array.
 478 .TP
 479 .B da_shunt
 480 Ensure that there are at least
 481 .I n
 482 spare slots preceding the start of the array.
 483 .TP
 484 .B da_tidy
 485 Reallocate the array to use the smallest amount of memory possible.
 486 .
 487 .\"--------------------------------------------------------------------------
 488 .SH "SEE ALSO"
 489 .
 490 .BR exc (3),
 491 .BR mLib (3).
 492 .
 493 .\"--------------------------------------------------------------------------
 494 .SH "AUTHOR"
 495 .
 496 Mark Wooding, <mdw@distorted.org.uk>
 497 .
 498 .\"----- That's all, folks --------------------------------------------------