Debian Codegraph @

podofo/3rdparty/adobe/afdko/include/dynarr.h

raw
1 /* Copyright 2014 Adobe Systems Incorporated (http://www.adobe.com/). All Rights Reserved.
2 This software is licensed as OpenSource, under the Apache License, Version 2.0.
3 This license is available at: http://opensource.org/licenses/Apache-2.0. */
4
5 #ifndef DYNARR_H
6 #define DYNARR_H
7
8 #include "ctlshare.h"
9
10 #define DNA_VERSION CTL_MAKE_VERSION(2, 0, 4)
11
12 #ifdef __cplusplus
13 extern "C" {
14 #endif
15
16 /* Dynamic Array Library
17 =====================
18 The dynamic array library provides simple and flexible support for
19 homogeneous arrays that automatically grow to accommodate new elements.
20
21 Dynamic arrays or da's are particularly useful in situations where the size
22 of the array isn't known at compile or run time until the last element has
23 been stored, and no suitable default size can be determined. Such situations
24 occur, for example, when data is being read from a file and loaded into an
25 array. The traditional way of handling this situation has been to make
26 multiple passes over the data but this can be expensive, especially if
27 parsing is complicated. Dynamic arrays can provide a cheaper alternative.
28
29 da's are also useful in situations where the same array is used repeatedly
30 with different data sets. The traditional way of handling this situation has
31 been to allocate and deallocate memory for each data set but this can also
32 be expensive. Dynamic arrays can simply be reused with each data set and no
33 further allocation becomes necessary after the largest data set has been
34 encountered.
35
36 da's can also lead to a different programming style where programs no longer
37 have to handle unusually large data sets (normally by fatal error) but
38 rather "just work" irrespective of the data. This is particularly useful
39 when working with poorly specified data sets.
40
41 A da is implemented as a C structure that contains a pointer to a
42 dynamically allocated array plus a few fields to control (re)allocation, and
43 optional initialization, of elements of that array. da's are created by
44 declaring them with the dnaDCL() macro described below.
45
46 Once a da has been declared it must be initialized by the dnaINIT() or
47 dnaINIT_FIRST() macros. This process associates values chosen by the
48 client with the da that are used to control subsequent allocation.
49
50 After initialization the da is accessed using a number of macros described
51 below. These check if the desired index is within the array and, if not, the
52 array is grown (reallocated) to accommodate it. The possibility of
53 reallocation means that the array may be moved in memory outside of client
54 control and it is therefore NOT permitted to save element POINTERS during
55 the time that the da is growing. A client can, however, save element INDEXES
56 reliably since these aren't dependent on memory addresses.
57
58 After the da has been grown and loaded with data it may be accessed
59 without restriction.
60
61 Finally, when a client has finished with a da it is freed by a call to
62 dnaFREE().
63
64 The following describes the interface to the library. */
65
66 typedef struct dnaCtx_ *dnaCtx;
67
68 #define dnaDCL(type, da) \
69 struct \
70 { \
71 dnaCtx ctx; \
72 type *array; \
73 long cnt; \
74 long size; \
75 long incr; \
76 void (*func)(void *ctx, long cnt, type *base); \
77 } da
78
79 /* dnaDCL() declares a dynamic array object with elements of type "type". */
80
81 dnaCtx dnaNew(ctlMemoryCallbacks *mem_cb, CTL_CHECK_ARGS_DCL);
82
83 #define DNA_CHECK_ARGS CTL_CHECK_ARGS_CALL(DNA_VERSION)
84
85 /* dnaNew() initializes the library and returns an opaque context that is
86 subsequently passed to dnaINIT() or dnaINIT_FIRST(). It must be the first
87 function in the library to be called by the client. The client passes a set
88 memory callback functions (described in ctlshare.h) to the library via the
89 mem_cb parameters.
90
91 The DNA_CHECK_ARGS macro is passed as the last parameter to dnaNew() and is
92 concerned with checking client call compatibility with the library's version
93 and interface structure sizes. If a mismatch is found dnaNew() returns NULL
94 to indicate the initialization failed.
95
96 A client uses the dynamic array library almost exclusively through the
97 macros described below. Macros are necessary because the C language doesn't
98 permit types to be manipulated flexibly enough for this implementation.
99
100 The macro interface to the library doesn't handle memory allocation
101 failures, but since clients normally supply memory callback functions that
102 handle allocation errors by setjmp/longjmp, and therefore never return NULL,
103 this isn't a problem.
104
105 However, sometimes the overhead of setjmp is too high for the task being
106 performed. In such cases the client can choose to supply memory callback
107 functions that don't handle allocation errors and can return NULL. The
108 client must then use the dnaGrow() function to access the da (see below). */
109
110 void dnaInit(dnaCtx ctx, void *object, size_t init, size_t incr, int check);
111
112 #define dnaINIT(ctx, da, init, incr) \
113 dnaInit(ctx, (void *)(&(da)), init, incr, 0)
114
115 /* dnaINIT() initializes the dynamic array before its first use. The "init"
116 parameter specifies the initial number of elements to be allocated to the
117 array when first accessed. The "incr" parameter specifies the number of
118 additional elements allocated to the array on subsequent accesses. Note
119 that indexes that exceed the init or init+incr sizes are accommodated by
120 allocating to the next multiple of the incr size that accommodates the index.
121
122 Sometimes it is necessary to initialize the the newly created elements when
123 they are first allocated. This can be achieved by attaching an element
124 initializer function to the da by explicitly initializing the "func" field
125 of the da object with the address of the initializer function after the
126 calling dnaINIT() or dnaINIT_FIRST() and before first use of the da.
127
128 The initializer function's "cnt" parameter specifies the number of elements
129 to be initialized and the "base" parameter (whose type must match the da
130 declaration) specifies the address of the first element in the sub-array to
131 be initialized. The client context is also made available via the "ctx"
132 parameter and is simply a copy of the client context provided to the dna
133 library in ctlMemoryCallbacks.ctx field. */
134
135 #define dnaINIT_FIRST(ctx, da, init, incr) \
136 dnaInit(ctx, (void *)(&(da)), init, incr, 1)
137
138 /* dnaINIT_FIRST() is identical to dnaINIT() except that it will only
139 initialize the dynamic array on its first call. */
140
141 long dnaSetCnt(void *object, size_t elemsize, long cnt);
142 long dnaGrow(void *object, size_t elemsize, long index);
143 long dnaIndex(void *object, size_t elemsize, long index);
144 long dnaMax(void *object, size_t elemsize, long index);
145 long dnaNext(void *object, size_t elemsize);
146 long dnaExtend(void *object, size_t elemsize, long length);
147
148 /* These functions are used to grow a da according to different access schemes
149 that suit a wide variety of usages. In all functions the object parameter is
150 the address of the da to be accessed and the element parameter specifies the
151 size (in bytes) of an element in the da.
152
153 In normal operation these functions behave as follows.
154
155 function arg action normal return
156 --------------- ------ ------------------------------ -----------------
157 dnaSetCnt cnt da.cnt=cnt 0
158 dnaGrow index - 0
159 dnaIndex index - index
160 dnaMax index if(index>=da.cnt)da.cnt=index+1 index
161 dnaNext - da.cnt++ da.cnt
162 dnaExtend length da.cnt+=length da.cnt
163
164 The functions return -1 if memory allocation failure occurs, that is if
165 either the malloc or realloc functions return NULL.
166
167 These function are normally used indirectly through the macros described
168 below. Direct usage is only necessary when the memory callback functions can
169 return NULL to indicate failure rather than handling the failure within the
170 callback, for example by longjmp() or exit(). */
171
172 #define DNA_DA_ADDR_(da) \
173 ((void *)(&(da)))
174
175 #define DNA_ELEM_SIZE_(da) \
176 (sizeof((da).array[0]))
177
178 #define DNA_ELEM_ADDR_(da, i) \
179 (&(da).array[(i)])
180
181 #define dnaSET_CNT(da, n) \
182 (void)dnaSetCnt(DNA_DA_ADDR_(da), DNA_ELEM_SIZE_(da), (n))
183
184 /* dnaSET_CNT() grows the array to accommodate a total of "n" elements and
185 sets the da.cnt field to "n". */
186
187 #define dnaGROW(da, i) \
188 ((void)dnaGrow(DNA_DA_ADDR_(da), DNA_ELEM_SIZE_(da), (i)), (da).array)
189
190 /* dnaGROW() grows the array to accommodate the "i"th element and returns
191 the address of the first element of the array. The da.cnt field is
192 unaltered. */
193
194 #define dnaINDEX(da, i) \
195 ((void)dnaIndex(DNA_DA_ADDR_(da), DNA_ELEM_SIZE_(da), (i)), DNA_ELEM_ADDR_((da), (i)))
196
197 /* dnaINDEX() grow the array to accommodate the "i"th element and returns
198 its address. The da.cnt field is unaltered. */
199
200 #define dnaMAX(da, i) \
201 ((void)dnaMax(DNA_DA_ADDR_(da), DNA_ELEM_SIZE_(da), (i)), DNA_ELEM_ADDR_((da), (i)))
202
203 /* dnaMAX() is the same as dnaINDEX() except that the da.cnt field is set to
204 be one greater than the maximum index accommodated. */
205
206 #define dnaNEXT(da) \
207 ((void)dnaNext(DNA_DA_ADDR_(da), DNA_ELEM_SIZE_(da)), DNA_ELEM_ADDR_((da), (da).cnt - 1))
208
209 /* dnaNEXT() grows the array to accommodate the next element (da.cnt) and
210 returns its address. The da.cnt field is incremented by 1. */
211
212 #define dnaEXTEND(da, len) \
213 ((void)dnaExtend(DNA_DA_ADDR_(da), DNA_ELEM_SIZE_(da), (len)), DNA_ELEM_ADDR_((da), (da).cnt - (len)))
214
215 /* dnaEXTEND() extends the dynamic array by "len" elements and returns the
216 address of the first element of the extension. The da.cnt fields is
217 increment by "len". */
218
219 void dnaFreeObj(void *object);
220 #define dnaFREE(da) (dnaFreeObj)(DNA_DA_ADDR_(da))
221
222 /* dnaFREE() frees resources allocated to the dynamic array. It may be
223 safely applied to dynamic array objects that have been declared and
224 initialized but never used. */
225
226 void dnaSetDebug(dnaCtx h, int level);
227
228 void dnaFree(dnaCtx h);
229
230 /* dnaFree() destroys the library context and all the resources allocated to
231 it. */
232
233 void dnaGetVersion(ctlVersionCallbacks *cb);
234
235 /* dnaGetVersion() returns the library version number and name via the client
236 callbacks passed with the "cb" parameter (see ctlshare.h). This*/
237
238 /* ------------------------ Discussion and Examples ------------------------
239
240 Declaration
241 ===========
242 da's are declared with the dnaDCL() macro:
243
244 dnaDCL(int, integers);
245
246 Declares a da called "integers" with elements of type "int".
247
248 dnaDCL(char *, strings);
249
250 Declares a da called "strings" with elements of type "char *".
251
252 typedef struct
253 {
254 float x
255 float y
256 } Coord;
257 dnaDCL(Coord, coords);
258
259 Declares a da called "coords" with elements of type "Coord".
260
261 typedef dnaDCL(char, GrowBuf);
262 GrowBuf tmp;
263
264 Declares a type called "GrowBuf" that is a da with elements of type "char"
265 and defines an object called "tmp" of this type. This could be used as a
266 temporary char buffer for string manipulation, for example.
267
268 Initialization
269 ==============
270 Once they have been declared, da's must be initialized before being used by
271 calling the dnaINIT() or dnaINIT_FIRST() macros:
272
273 dnaINIT(dactx, coords, 1000, 500);
274
275 Initializes the "coords" da with an initial size of 1000 elements and an
276 increment size of 500 elements. The "dactx" parameter is the pointer
277 returned dnaNew() when the library was initialized.
278
279 If the code fragment is executed multiple times, for example with multiple
280 data sets, the initialization must only occur the first time otherwise the
281 previously allocated array will be leaked. First time initialization can be
282 conveniently handled by calling the dnaINIT_FIRST() macro in place of
283 dnaINIT():
284
285 dnaINIT_FIRST(dactx, coords, 1000, 500);
286
287 Sometimes it is necessary to initialize the the newly created elements when
288 they are first allocated. This can be achieved by attaching an element
289 initializer function (of matching type) to the da:
290
291 void initStrings(void *ctx, long cnt, char **base)
292 {
293 while (cnt--)
294 *base++ = NULL;
295 }
296 ...
297 dnaINIT(dactx, strings, 250, 50);
298 strings.func = initStrings;
299
300 Growing and Loading
301 ===================
302 Once a da has been declared and initialized it may be accessed so that
303 elements of the underlying array can be loaded. This is accomplished by a
304 number of macros that are tailored to particular types of access.
305
306 The simplest of these is dnaSET_CNT() which is used to grow the array to the
307 specified size and set the cnt field to that size. This would normally be
308 used for multiple data sets whose size was known in advance. The array is
309 then simply reused for each data set.
310
311 Next in complexity is dnaGROW() which simply grows the array to accommodate
312 an index and returns the address of the first element of the array. This can
313 be useful when inserting an element into the middle of a da, for example
314 when implementing an insertion sort.
315
316 Random elements in the da can be loaded using dnaINDEX(). This grows the
317 array to accommodate the index and returns a pointer to the indexed element.
318 This might be used when loading a sparse array, but in this case it is
319 imperative that an element initializer is specified so that elements may be
320 suitably initialized. If this isn't done there will be no reliable way of
321 determining which elements were loaded.
322
323 dnaMAX() is a variation on dnaINDEX() that records one greater than the
324 highest index in the da.cnt field which may be used to limit the subsequent
325 search for loaded elements.
326
327 A common requirement is to load the array sequentially, starting at index 0
328 and ending when the data is exhausted. This is easily achieved using
329 dnaNEXT() which returns a pointer to the next element and increments da.cnt
330 automatically. The client must initialize da.cnt to 0 (or any other suitable
331 starting index) before calling dnaNEXT(). The following example fills the
332 strings da with strings returned from the nextString() function which
333 returns NULL when its supply of strings is exhausted.
334
335 char *string;
336 strings.cnt = 0;
337 while ((string = nextString()) != NULL)
338 *dnaNEXT(strings) = string;
339
340 Finally, dnaEXTEND() is used to add a specified number of elements to the
341 end of the array and returns the address of the first element of this
342 extension. This function is useful for appending strings to a buffer
343 as shown in the example below:
344
345 char *string;
346 tmp.cnt = 0;
347 while ((string = nextString()) != NULL)
348 {
349 size_t len = strlen(string);
350 memmove(dnaEXTEND(tmp, len), string, len);
351 }
352
353 Note: strings have null termination removed in this example.
354
355 Access
356 ======
357 Once the da is loaded the elements in the array may be accessed using
358 conventional techniques and even the addresses of elements can be used
359 since the array will not be reallocated again. Generally, the da.cnt field
360 records the number of elements in the array so that the following code may
361 be used to find the maximum element in an array of integers. For brevity
362 this example assumes that there is at least 1 element in the array.
363
364 long i;
365 long max = integers.array[0];
366 for (i = 1; i < integers.cnt; i++)
367 if (integers.array[i] > max)
368 max = integers.array[i];
369
370 The following example sorts the string da after it is loaded.
371
372 int cmpStrings(const void *first, const void *second)
373 {
374 return strcmp(*(char**)first, *(char **)second);
375 }
376 ...
377 qsort(strings.array, strings.cnt, sizeof(char *), cmpStrings);
378
379 */
380
381 #ifdef __cplusplus
382 }
383 #endif
384
385 #endif /* DYNARR_H */