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