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