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
  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
  68 .B "#define DA_INIT ..."
  69
  70 .B "#define DAEXC_UFLOW EXC_ALLOCN(EXC_MLIB, ...)"
  71 .B "#define DAEXC_OFLOW EXC_ALLOCN(EXC_MLIB, ...)"
  72
  73 .BI DA_DECL( type_v ", " type );
  74 .BI "void DA_CREATE(" type_v " *" a );
  75 .BI "void DA_DESTROY(" type_v " *" a );
  76
  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
  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
  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
  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
  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
 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 #ifndef FOO_V
 138 #  define FOO_V
 139    DA_DECL(foo_v, foo);
 140 #endif
 141 .VE
 142 The macro
 143 .B DA_INIT
 144 is a valid static initializer for all types of dynamic arrays.  For
 145 cases where this isn't appropriate, a dynamic array may be initialized
 146 using the macro
 147 .BR DA_CREATE ,
 148 passing it the address of the array.
 149 .PP
 150 Arrays may be disposed of using the
 151 .B DA_DESTROY
 152 macro, which again takes the address of the array.
 153 .SS "Storage allocation"
 154 .PP
 155 Space for new array elements may be reserved using the
 156 .B DA_ENSURE
 157 and
 158 .B DA_SHUNT
 159 macros, which reserve space at the end and beginning of the array
 160 respectively.  Both macros take two arguments: the address of an array
 161 object and the number of spare elements required.
 162 .PP
 163 Neither of these macros actually extends the array; both merely allocate
 164 memory for the array to extend itself into.  Use the macros
 165 .B DA_EXTEND
 166 and
 167 .B DA_SLIDE
 168 to actually increase the bounds of the array.
 169 .PP
 170 Note that when space is reserved, all the array elements might move.
 171 You should be careful not to depend on the addresses of array elements.
 172 If sufficient storage cannot be allocated, the exception
 173 .B EXC_NOMEM
 174 is thrown (see
 175 .BR exc (3)).
 176 .PP
 177 The macro
 178 .B DA_TIDY
 179 takes one argument: the address of a dynamic array.  It minimizes the
 180 amount of memory used by the array.  This is a useful function to call
 181 when the array's size has finally settled down.
 182 .PP
 183 The macro
 184 .B DA_RESET
 185 accepts the address of an array.  It reduces the length of the array to
 186 zero.  No storage is deallocated.  Resetting arrays might not be a good
 187 idea if the objects in the array are dynamically allocated.
 188 .SS "Accessing array elements"
 189 If
 190 .I a
 191 is the address of a dynamic array object, then
 192 .BI DA( a )
 193 is the base address of the actual array.  The elements are stored
 194 contiguously starting at this address.  An element at index
 195 .I i
 196 may be referenced using the syntax
 197 .BI DA( a )[ i ]\fR.
 198 .PP
 199 The number of elements in the array
 200 .I a
 201 is given by
 202 .BI DA_LEN( a )\fR.
 203 An integer array index
 204 .I i
 205 is
 206 .I valid
 207 if 0 \(<=
 208 .I i
 209 <
 210 .BI DA_LEN( a )\fR.
 211 .PP
 212 There may be some spare slots at the end of the array.  In particular,
 213 after a call to
 214 .BI DA_ENSURE( a ", " n )
 215 there will be at least
 216 .I n
 217 spare slots.  The number of spare slots at the end of the array may be
 218 obtained as
 219 .BI DA_SPARE( a )\fR.
 220 .PP
 221 Similarly, there may be spare slots before the start of the array.  In
 222 particular, after a call to
 223 .BI DA_SHUNT( a ", " n )
 224 there will be at least
 225 .I n
 226 spare slots.  The number of spare slots before the start of the array
 227 may be obtained as
 228 .BI DA_OFFSET( a )\fR.
 229 .PP
 230 The call
 231 .BI DA_INCLUDE( a ", " i )
 232 ensures that the array's bounds include the index
 233 .I i
 234 by extending the array if necessary.  The exception
 235 .B EXC_NOMEM
 236 is thrown if there isn't enough memory to do this.
 237 .PP
 238 The array's bounds may be extended by
 239 .I n
 240 slots by calling
 241 .BI DA_EXTEND( a ", " n )\fR.
 242 The integer
 243 .I n
 244 must be less than
 245 .BI DA_SPARE( a )\fR;
 246 if this is not the case then the exception
 247 .B DAEXC_OFLOW
 248 is thrown.
 249 Note that
 250 .I n
 251 may be negative to reduce the bounds of the array: in this case it must
 252 be greater than
 253 .BI \-DA_LEN( a )
 254 or the exception
 255 .B DAEXC_UFLOW
 256 is thrown.  The macro
 257 .B DA_UNSAFE_EXTEND
 258 does the same job, but performs no error checking.
 259 .PP
 260 The macro
 261 .BI DA_SLIDE( a ", " n )
 262 offsets the array elements by
 263 .IR n .
 264 If
 265 .I n
 266 is positive, the array elements are slid upwards, to higher-numbered
 267 indices; if
 268 .I n
 269 is negative, the elements are slid downwards.  Precisely, what happens
 270 is that elements which used to have index
 271 .I i
 272 \-
 273 .I n
 274 now have index
 275 .IR i .
 276 The exception
 277 .B DAEXC_OFLOW
 278 is thrown if
 279 .I n
 280 >
 281 .BI DA_OFFSET( a )\fR;
 282 .B DAEXC_UFLOW
 283 is thrown if
 284 .I n
 285 <
 286 .BI \-DA_LEN( a )\fR.
 287 The macro
 288 .B DA_UNSAFE_SLIDE
 289 does the same job, only without the error checking.
 290 .PP
 291 The macros
 292 .B DA_SHRINK
 293 and
 294 .B DA_UNSLIDE
 295 do the same things as
 296 .B DA_EXTEND
 297 and
 298 .B DA_SLIDE
 299 respectively, except that they interpret the sign of their second
 300 arguments in the opposite way.  This is useful if the argument is
 301 unsigned (e.g., if it's based on
 302 .BR DA_LEN ).
 303 There are unsafe versions of both these macros too.
 304 .SS "Stack operations"
 305 Dynamic arrays support Perl-like stack operations.  Given an array
 306 (pointer)
 307 .I a
 308 and an object of the array's element type
 309 .I x
 310 the following operations are provided:
 311 .TP
 312 .BI DA_PUSH( a ", " x )
 313 Add
 314 .I x
 315 to the end of the array, increasing the array size by one.
 316 .TP
 317 .IB x " = DA_POP(" a )
 318 Remove the final element of the array, assigning
 319 .I x
 320 its value and decreasing the array size by one.
 321 .TP
 322 .BI DA_UNSHIFT( a ", " x )
 323 Insert
 324 .I x
 325 at the beginning of the array, shifting all the elements up one place
 326 and increasing the array size by one.
 327 .TP
 328 .IB x " = DA_SHIFT(" a )
 329 Remove the first element of the array, assigning
 330 .I x
 331 its value, shifting all the subsequent array items down one place and
 332 decreasing the array size by one.
 333 .PP
 334 The operations
 335 .B DA_PUSH
 336 and
 337 .B DA_UNSHIFT
 338 can fail due to lack of memory, in which case
 339 .B EXC_NOMEM
 340 is thrown.  The operations
 341 .B DA_POP
 342 and
 343 .B DA_SHIFT
 344 can fail because the array is empty, in which case
 345 .B DAEXC_UFLOW
 346 is thrown.
 347 .PP
 348 The operations
 349 .B DA_FIRST
 350 and
 351 .B DA_LAST
 352 are lvalues referring to the first and last elements in the array
 353 respectively.  They are unsafe if the array is empty.
 354 .SS "Low-level details"
 355 This section describes low-level details of the dynamic array
 356 implementation.  You should try to avoid making use of this information
 357 if you can, since the interface may change in later library versions.
 358 In particular, more subtleties may be added which low-level access will
 359 miss.
 360 .PP
 361 Dynamic arrays are structures with the format
 362 .VS
 363 .BI "typedef struct " type_v " {"
 364 .B "  da_base b;"
 365 .BI "  " type " *v;"
 366 .BI "} " type_v ";"
 367 .VE
 368 The pointer
 369 .B v
 370 indicates the current base of the array.  This will move in the
 371 allocated space as a result of
 372 .B DA_SHIFT
 373 and
 374 .B DA_UNSHIFT
 375 (and
 376 .BR DA_SLIDE )
 377 operations.
 378 .PP
 379 The
 380 .B da_base
 381 structure contains the following elements:
 382 .TP
 383 .B "size_t sz"
 384 The number of allocated slots from
 385 .B v
 386 onwards.
 387 .TP
 388 .B "size_t len"
 389 The number of items considered to be in the array.  The allocated space
 390 is usually larger than this.
 391 .TP
 392 .B "size_t off"
 393 The number of allocated slots preceding
 394 .BR v .
 395 The total number of allocated items is therefore
 396 .B sz
 397 +
 398 .BR off .
 399 .TP
 400 .B "unsigned push"
 401 The number of items pushed or ensured since the last array expansion.
 402 .TP
 403 .B "unsigned unshift"
 404 The number of items unshifted or shunted since the last array expansion.
 405 .PP
 406 The
 407 .B push
 408 and
 409 .B unshift
 410 members are used by the expansion routines to decide how to allocate
 411 free space before and after the array elements following a reallocation.
 412 The other members should be fairly self-explanatory.
 413 .PP
 414 The reallocation routines
 415 .BR da_ensure ,
 416 .B da_shunt
 417 and
 418 .B da_tidy
 419 have a regular interface.  They're a bit
 420 strange, though, because they have to deal with lots of different types
 421 of arrays.  The arguments they take are:
 422 .TP
 423 .BI "da_base *" b
 424 Pointer to the
 425 .B da_base
 426 member of the array block.
 427 .TP
 428 .BI "void *" v
 429 The array base pointer from the array block (i.e., the
 430 .B v
 431 member).
 432 .TP
 433 .BI "size_t " sz
 434 The element size for the array.
 435 .TP
 436 .BI "size_t " n
 437 (For
 438 .B da_ensure
 439 and
 440 .B da_shunt
 441 only.)  The number of spare slots required.
 442 .PP
 443 The functions may modify the base structure, and return a newly
 444 allocated (or at least repositioned) array base pointer, or throw
 445 .B EXC_NOMEM
 446 if there's not enough memory.
 447 .PP
 448 The three functions behave as follows:
 449 .TP
 450 .B da_ensure
 451 Ensure that there are at least
 452 .I n
 453 spare slots after the end of the array.
 454 .TP
 455 .B da_shunt
 456 Ensure that there are at least
 457 .I n
 458 spare slots preceding the start of the array.
 459 .TP
 460 .B da_tidy
 461 Reallocate the array to use the smallest amount of memory possible.
 462 .SH "SEE ALSO"
 463 .BR exc (3),
 464 .BR mLib (3).
 465 .SH "AUTHOR"
 466 Mark Wooding, <mdw@distorted.org.uk>