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

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