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