Mercurial > repos > rliterman > csp2

comparison CSP2/CSP2_env/env-d9b9114564458d9d-741b3de822f2aaca6c6caa4325c4afce/include/tkArray.h @ 69:33d812a61356

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
planemo upload commit 2e9511a184a1ca667c7be0c6321a36dc4e3d116d
author jpayne
date Tue, 18 Mar 2025 17:55:14 -0400
parents
children
comparison
equal deleted inserted replaced
67:0e9998148a16 69:33d812a61356
1 /*
2 * tkArray.h --
3 *
4 * An array is a sequence of items, stored in a contiguous memory region.
5 * Random access to any item is very fast. New items can be either appended
6 * or prepended. An array may be traversed in the forward or backward direction.
7 *
8 * Copyright (c) 2018-2019 by Gregor Cramer.
9 *
10 * See the file "license.terms" for information on usage and redistribution of
11 * this file, and for a DISCLAIMER OF ALL WARRANTIES.
12 */
13
14 /*
15 * Note that this file will not be included in header files, it is the purpose
16 * of this file to be included in source files only. Thus we are not using the
17 * prefix "Tk_" here for functions, because all the functions have private scope.
18 */
19
20 /*
21 * -------------------------------------------------------------------------------
22 * Use the array in the following way:
23 * -------------------------------------------------------------------------------
24 * typedef struct { int key, value; } Pair;
25 * TK_PTR_ARRAY_DEFINE(MyArray, Pair);
26 * MyArray *arr = NULL;
27 * if (MyArray_IsEmpty(arr)) {
28 * MyArray_Append(&arr, MakePair(1, 2));
29 * MyArray_Append(&arr, MakePair(2, 3));
30 * for (i = 0; i < MyArray_Size(arr); ++i) {
31 * Pair *p = MyArray_Get(arr, i);
32 * printf("%d -> %d\n", p->key, p->value);
33 * ckfree(p);
34 * }
35 * MyArray_Free(&arr);
36 * assert(arr == NULL);
37 * }
38 * -------------------------------------------------------------------------------
39 * Or with aggregated elements:
40 * -------------------------------------------------------------------------------
41 * typedef struct { int key, value; } Pair;
42 * TK_ARRAY_DEFINE(MyArray, Pair);
43 * Pair p1 = { 1, 2 };
44 * Pair p2 = { 2, 3 };
45 * MyArray *arr = NULL;
46 * if (MyArray_IsEmpty(arr)) {
47 * MyArray_Append(&arr, p1);
48 * MyArray_Append(&arr, p2);
49 * for (i = 0; i < MyArray_Size(arr); ++i) {
50 * const Pair *p = MyArray_Get(arr, i);
51 * printf("%d -> %d\n", p->key, p->value);
52 * }
53 * MyArray_Free(&arr);
54 * assert(arr == NULL);
55 * }
56 * -------------------------------------------------------------------------------
57 */
58
59 /*************************************************************************/
60 /*
61 * Two array types will be provided:
62 * Use TK_ARRAY_DEFINE if your array is aggregating the elements. Use
63 * TK_PTR_ARRAY_DEFINE if your array contains pointers to elements. But
64 * in latter case the array is not responsible for the lifetime of the
65 * elements.
66 */
67 /*************************************************************************/
68 /*
69 * Array_ElemSize: Returns the memory size for one array element.
70 */
71 /*************************************************************************/
72 /*
73 * Array_BufferSize: Returns the memory size for given number of elements.
74 */
75 /*************************************************************************/
76 /*
77 * Array_IsEmpty: Array is empty?
78 */
79 /*************************************************************************/
80 /*
81 * Array_Size: Number of elements in array.
82 */
83 /*************************************************************************/
84 /*
85 * Array_Capacity: Capacity of given array. This is the maximal number of
86 * elements fitting into current array memory without resizing the buffer.
87 */
88 /*************************************************************************/
89 /*
90 * Array_SetSize: Set array size, new size must not exceed the capacity of
91 * the array. This function has to be used with care when increasing the
92 * array size.
93 */
94 /*************************************************************************/
95 /*
96 * Array_First: Returns position of first element in array. Given array
97 * may be NULL.
98 */
99 /*************************************************************************/
100 /*
101 * Array_Last: Returns position after last element in array. Given array
102 * may be empty.
103 */
104 /*************************************************************************/
105 /*
106 * Array_Front: Returns first element in array. Given array must not be
107 * empty.
108 */
109 /*************************************************************************/
110 /*
111 * Array_Back: Returns last element in array. Given array must not be
112 * empty.
113 */
114 /*************************************************************************/
115 /*
116 * Array_Resize: Resize buffer of array for given number of elements. The
117 * array may grow or shrink. Note that this function is not initializing
118 * the increased buffer.
119 */
120 /*************************************************************************/
121 /*
122 * Array_ResizeAndClear: Resize buffer of array for given number of
123 * elements. The array may grow or shrink. The increased memory will be
124 * filled with zeroes.
125 */
126 /*************************************************************************/
127 /*
128 * Array_Clear: Fill specified range with zeroes.
129 */
130 /*************************************************************************/
131 /*
132 * Array_Free: Resize array to size zero. This function will release the
133 * array buffer.
134 */
135 /*************************************************************************/
136 /*
137 * Array_Append: Insert given element after end of array.
138 */
139 /*************************************************************************/
140 /*
141 * Array_PopBack: Shrink array by one element. Given array must not be
142 * empty.
143 */
144 /*************************************************************************/
145 /*
146 * Array_Get: Random access to array element at given position. The given
147 * index must not exceed current array size.
148 */
149 /*************************************************************************/
150 /*
151 * Array_Set: Replace array element at given position with new value. The
152 * given index must not exceed current array size.
153 */
154 /*************************************************************************/
155 /*
156 * Array_Find: Return index position of element which matches given
157 * argument. If not found then -1 will be returned.
158 */
159 /*************************************************************************/
160
161 #ifndef TK_ARRAY_DEFINED
162 #define TK_ARRAY_DEFINED
163
164 #include "tkInt.h"
165
166 #if defined(__GNUC__) || defined(__clang__)
167 # define __TK_ARRAY_UNUSED __attribute__((unused))
168 #else
169 # define __TK_ARRAY_UNUSED
170 #endif
171
172 #define TK_ARRAY_DEFINE(AT, ElemType) /* AT = type of array */ \
173 /* ------------------------------------------------------------------------- */ \
174 typedef struct AT { \
175 size_t size; \
176 size_t capacity; \
177 ElemType buf[1]; \
178 } AT; \
179 \
180 __TK_ARRAY_UNUSED \
181 static void \
182 AT##_Init(AT *arr) \
183 { \
184 assert(arr); \
185 arr->size = 0; \
186 arr->capacity = 0; \
187 } \
188 \
189 __TK_ARRAY_UNUSED \
190 static size_t \
191 AT##_ElemSize() \
192 { \
193 return sizeof(ElemType); \
194 } \
195 \
196 __TK_ARRAY_UNUSED \
197 static size_t \
198 AT##_BufferSize(size_t numElems) \
199 { \
200 return numElems*sizeof(ElemType); \
201 } \
202 \
203 __TK_ARRAY_UNUSED \
204 static int \
205 AT##_IsEmpty(const AT *arr) \
206 { \
207 assert(!arr || arr->size != 0xdeadbeef); \
208 return !arr || arr->size == 0u; \
209 } \
210 \
211 __TK_ARRAY_UNUSED \
212 static size_t \
213 AT##_Size(const AT *arr) \
214 { \
215 assert(!arr || arr->size != 0xdeadbeef); \
216 return arr ? arr->size : 0u; \
217 } \
218 \
219 __TK_ARRAY_UNUSED \
220 static size_t \
221 AT##_Capacity(const AT *arr) \
222 { \
223 assert(!arr || arr->size != 0xdeadbeef); \
224 return arr ? arr->capacity : 0u; \
225 } \
226 \
227 __TK_ARRAY_UNUSED \
228 static ElemType * \
229 AT##_First(AT *arr) \
230 { \
231 assert(!arr || arr->size != 0xdeadbeef); \
232 return arr ? arr->buf : NULL; \
233 } \
234 \
235 __TK_ARRAY_UNUSED \
236 static ElemType * \
237 AT##_Last(AT *arr) \
238 { \
239 assert(!arr || arr->size != 0xdeadbeef); \
240 return arr ? arr->buf + arr->size : NULL; \
241 } \
242 \
243 __TK_ARRAY_UNUSED \
244 static ElemType * \
245 AT##_Front(AT *arr) \
246 { \
247 assert(arr); \
248 assert(arr->size != 0xdeadbeef); \
249 assert(!AT##_IsEmpty(arr)); \
250 return &arr->buf[0]; \
251 } \
252 \
253 __TK_ARRAY_UNUSED \
254 static ElemType * \
255 AT##_Back(AT *arr) \
256 { \
257 assert(arr); \
258 assert(arr->size != 0xdeadbeef); \
259 assert(!AT##_IsEmpty(arr)); \
260 return &arr->buf[arr->size - 1]; \
261 } \
262 \
263 __TK_ARRAY_UNUSED \
264 static void \
265 AT##_Resize(AT **arrp, size_t newSize) \
266 { \
267 assert(arrp); \
268 assert(!*arrp || (*arrp)->size != 0xdeadbeef); \
269 if (newSize == 0) { \
270 assert(!*arrp || ((*arrp)->size = 0xdeadbeef)); \
271 ckfree(*arrp); \
272 *arrp = NULL; \
273 } else { \
274 int init = *arrp == NULL; \
275 size_t memSize = AT##_BufferSize(newSize - 1) + sizeof(AT); \
276 *arrp = ckrealloc(*arrp, memSize); \
277 if (init) { \
278 (*arrp)->size = 0; \
279 } else if (newSize < (*arrp)->size) { \
280 (*arrp)->size = newSize; \
281 } \
282 (*arrp)->capacity = newSize; \
283 } \
284 } \
285 \
286 __TK_ARRAY_UNUSED \
287 static void \
288 AT##_Clear(AT *arr, size_t from, size_t to) \
289 { \
290 assert(arr); \
291 assert(arr->size != 0xdeadbeef); \
292 assert(to <= AT##_Capacity(arr)); \
293 assert(from <= to); \
294 memset(arr->buf + from, 0, AT##_BufferSize(to - from)); \
295 } \
296 \
297 __TK_ARRAY_UNUSED \
298 static void \
299 AT##_ResizeAndClear(AT **arrp, size_t newSize) \
300 { \
301 size_t oldCapacity; \
302 assert(arrp); \
303 oldCapacity = *arrp ? (*arrp)->capacity : 0; \
304 AT##_Resize(arrp, newSize); \
305 if (newSize > oldCapacity) { \
306 AT##_Clear(*arrp, oldCapacity, newSize); \
307 } \
308 } \
309 \
310 __TK_ARRAY_UNUSED \
311 static void \
312 AT##_SetSize(AT *arr, size_t newSize) \
313 { \
314 assert(newSize <= AT##_Capacity(arr)); \
315 assert(!arr || arr->size != 0xdeadbeef); \
316 if (arr) { \
317 arr->size = newSize; \
318 } \
319 } \
320 \
321 __TK_ARRAY_UNUSED \
322 static void \
323 AT##_Append(AT **arrp, ElemType *elem) \
324 { \
325 assert(arrp); \
326 if (!*arrp) { \
327 AT##_Resize(arrp, 1); \
328 } else if ((*arrp)->size == (*arrp)->capacity) { \
329 AT##_Resize(arrp, (*arrp)->capacity + ((*arrp)->capacity + 1)/2); \
330 } \
331 (*arrp)->buf[(*arrp)->size++] = *elem; \
332 } \
333 \
334 __TK_ARRAY_UNUSED \
335 static size_t \
336 AT##_PopBack(AT *arr) \
337 { \
338 assert(!AT##_IsEmpty(arr)); \
339 return arr->size -= 1; \
340 } \
341 \
342 __TK_ARRAY_UNUSED \
343 static ElemType * \
344 AT##_Get(const AT *arr, size_t at) \
345 { \
346 assert(arr); \
347 assert(at < AT##_Size(arr)); \
348 return (ElemType *) &arr->buf[at]; \
349 } \
350 \
351 __TK_ARRAY_UNUSED \
352 static void \
353 AT##_Set(AT *arr, size_t at, ElemType *elem) \
354 { \
355 assert(arr); \
356 assert(at < AT##_Size(arr)); \
357 arr->buf[at] = *elem; \
358 } \
359 \
360 __TK_ARRAY_UNUSED \
361 static void \
362 AT##_Free(AT **arrp) \
363 { \
364 AT##_Resize(arrp, 0); \
365 } \
366 \
367 __TK_ARRAY_UNUSED \
368 static int \
369 AT##_Find(const AT *arr, const ElemType *elem) \
370 { \
371 assert(!arr || arr->size != 0xdeadbeef); \
372 if (arr) { \
373 const ElemType *buf = arr->buf; \
374 size_t i; \
375 for (i = 0; i < arr->size; ++i) { \
376 if (memcmp(&buf[i], elem, sizeof(ElemType)) == 0) { \
377 return (int) i; \
378 } \
379 } \
380 } \
381 return -1; \
382 } \
383 \
384 __TK_ARRAY_UNUSED \
385 static int \
386 AT##_Contains(const AT *arr, const ElemType *elem) \
387 { \
388 return AT##_Find(arr, elem) != -1; \
389 } \
390 /* ------------------------------------------------------------------------- */
391
392 #define TK_PTR_ARRAY_DEFINE(AT, ElemType) /* AT = type of array */ \
393 /* ------------------------------------------------------------------------- */ \
394 typedef struct AT { \
395 size_t size; \
396 size_t capacity; \
397 ElemType *buf[1]; \
398 } AT; \
399 \
400 __TK_ARRAY_UNUSED \
401 static size_t \
402 AT##_ElemSize() \
403 { \
404 return sizeof(ElemType); \
405 } \
406 \
407 __TK_ARRAY_UNUSED \
408 static size_t \
409 AT##_BufferSize(size_t numElems) \
410 { \
411 return numElems*sizeof(ElemType *); \
412 } \
413 \
414 __TK_ARRAY_UNUSED \
415 static int \
416 AT##_IsEmpty(const AT *arr) \
417 { \
418 assert(!arr || arr->size != 0xdeadbeef); \
419 return !arr || arr->size == 0; \
420 } \
421 \
422 __TK_ARRAY_UNUSED \
423 static ElemType ** \
424 AT##_First(AT *arr) \
425 { \
426 assert(!arr || arr->size != 0xdeadbeef); \
427 return arr ? arr->buf : NULL; \
428 } \
429 \
430 __TK_ARRAY_UNUSED \
431 static ElemType ** \
432 AT##_Last(AT *arr) \
433 { \
434 assert(!arr || arr->size != 0xdeadbeef); \
435 return arr ? arr->buf + arr->size : NULL; \
436 } \
437 \
438 __TK_ARRAY_UNUSED \
439 static ElemType * \
440 AT##_Front(AT *arr) \
441 { \
442 assert(arr); \
443 assert(arr->size != 0xdeadbeef); \
444 assert(!AT##_IsEmpty(arr)); \
445 return arr->buf[0]; \
446 } \
447 \
448 __TK_ARRAY_UNUSED \
449 static ElemType * \
450 AT##_Back(AT *arr) \
451 { \
452 assert(arr); \
453 assert(arr->size != 0xdeadbeef); \
454 assert(!AT##_IsEmpty(arr)); \
455 return arr->buf[arr->size - 1]; \
456 } \
457 \
458 __TK_ARRAY_UNUSED \
459 static size_t \
460 AT##_Size(const AT *arr) \
461 { \
462 assert(!arr || arr->size != 0xdeadbeef); \
463 return arr ? arr->size : 0; \
464 } \
465 \
466 __TK_ARRAY_UNUSED \
467 static size_t \
468 AT##_Capacity(const AT *arr) \
469 { \
470 assert(!arr || arr->size != 0xdeadbeef); \
471 return arr ? arr->capacity : 0; \
472 } \
473 \
474 __TK_ARRAY_UNUSED \
475 static void \
476 AT##_Resize(AT **arrp, size_t newCapacity) \
477 { \
478 assert(arrp); \
479 assert(!*arrp || (*arrp)->size != 0xdeadbeef); \
480 if (newCapacity == 0) { \
481 assert(!*arrp || ((*arrp)->size = 0xdeadbeef)); \
482 ckfree(*arrp); \
483 *arrp = NULL; \
484 } else { \
485 int init = *arrp == NULL; \
486 size_t memSize = AT##_BufferSize(newCapacity - 1) + sizeof(AT); \
487 *arrp = ckrealloc(*arrp, memSize); \
488 if (init) { \
489 (*arrp)->size = 0; \
490 } else if (newCapacity < (*arrp)->size) { \
491 (*arrp)->size = newCapacity; \
492 } \
493 (*arrp)->capacity = newCapacity; \
494 } \
495 } \
496 \
497 __TK_ARRAY_UNUSED \
498 static void \
499 AT##_Clear(AT *arr, size_t from, size_t to) \
500 { \
501 assert(arr); \
502 assert(arr->size != 0xdeadbeef); \
503 assert(to <= AT##_Capacity(arr)); \
504 assert(from <= to); \
505 memset(arr->buf + from, 0, AT##_BufferSize(to - from)); \
506 } \
507 \
508 __TK_ARRAY_UNUSED \
509 static void \
510 AT##_ResizeAndClear(AT **arrp, size_t newCapacity) \
511 { \
512 size_t oldCapacity; \
513 assert(arrp); \
514 oldCapacity = *arrp ? (*arrp)->capacity : 0; \
515 AT##_Resize(arrp, newCapacity); \
516 if (newCapacity > oldCapacity) { \
517 AT##_Clear(*arrp, oldCapacity, newCapacity); \
518 } \
519 } \
520 \
521 __TK_ARRAY_UNUSED \
522 static void \
523 AT##_SetSize(AT *arr, size_t newSize) \
524 { \
525 assert(arr); \
526 assert(newSize <= AT##_Capacity(arr)); \
527 arr->size = newSize; \
528 } \
529 \
530 __TK_ARRAY_UNUSED \
531 static void \
532 AT##_Append(AT **arrp, ElemType *elem) \
533 { \
534 assert(arrp); \
535 if (!*arrp) { \
536 AT##_Resize(arrp, 1); \
537 } else if ((*arrp)->size == (*arrp)->capacity) { \
538 AT##_Resize(arrp, (*arrp)->capacity + ((*arrp)->capacity + 1)/2); \
539 } \
540 (*arrp)->buf[(*arrp)->size++] = elem; \
541 } \
542 \
543 __TK_ARRAY_UNUSED \
544 static size_t \
545 AT##_PopBack(AT *arr) \
546 { \
547 assert(!AT##_IsEmpty(arr)); \
548 return arr->size -= 1; \
549 } \
550 \
551 __TK_ARRAY_UNUSED \
552 static ElemType * \
553 AT##_Get(const AT *arr, size_t at) \
554 { \
555 assert(arr); \
556 assert(at < AT##_Size(arr)); \
557 return arr->buf[at]; \
558 } \
559 \
560 __TK_ARRAY_UNUSED \
561 static void \
562 AT##_Set(AT *arr, size_t at, ElemType *elem) \
563 { \
564 assert(arr); \
565 assert(at < AT##_Size(arr)); \
566 arr->buf[at] = elem; \
567 } \
568 \
569 __TK_ARRAY_UNUSED \
570 static void \
571 AT##_Free(AT **arrp) \
572 { \
573 AT##_Resize(arrp, 0); \
574 } \
575 \
576 __TK_ARRAY_UNUSED \
577 static int \
578 AT##_Find(const AT *arr, const ElemType *elem) \
579 { \
580 assert(!arr || arr->size != 0xdeadbeef); \
581 if (arr) { \
582 ElemType *const *buf = arr->buf; \
583 size_t i; \
584 for (i = 0; i < arr->size; ++i) { \
585 if (buf[i] == elem) { \
586 return (int) i; \
587 } \
588 } \
589 } \
590 return -1; \
591 } \
592 \
593 __TK_ARRAY_UNUSED \
594 static int \
595 AT##_Contains(const AT *arr, const ElemType *elem) \
596 { \
597 return AT##_Find(arr, elem) != -1; \
598 } \
599 /* ------------------------------------------------------------------------- */
600
601 #endif /* TK_ARRAY_DEFINED */
602
603 /*
604 * Local Variables:
605 * mode: c
606 * c-basic-offset: 4
607 * fill-column: 105
608 * End:
609 * vi:set ts=8 sw=4:
610 */