| 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> |