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