Mercurial > repos > rliterman > csp2

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