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