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