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