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