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