1 /*************************************************************************************************** 2 3 Zyan Core Library (Zycore-C) 4 5 Original Author : Florian Bernd 6 7 * Permission is hereby granted, free of charge, to any person obtaining a copy 8 * of this software and associated documentation files (the "Software"), to deal 9 * in the Software without restriction, including without limitation the rights 10 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell 11 * copies of the Software, and to permit persons to whom the Software is 12 * furnished to do so, subject to the following conditions: 13 * 14 * The above copyright notice and this permission notice shall be included in all 15 * copies or substantial portions of the Software. 16 * 17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 18 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 19 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 20 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 21 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 22 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE 23 * SOFTWARE. 24 25 ***************************************************************************************************/ 26 27 #include <Zycore/LibC.h> 28 #include <Zycore/Vector.h> 29 30 /* ============================================================================================== */ 31 /* Internal macros */ 32 /* ============================================================================================== */ 33 34 /** 35 * Checks, if the passed vector should grow. 36 * 37 * @param size The desired size of the vector. 38 * @param capacity The current capacity of the vector. 39 * 40 * @return `ZYAN_TRUE`, if the vector should grow or `ZYAN_FALSE`, if not. 41 */ 42 #define ZYCORE_VECTOR_SHOULD_GROW(size, capacity) \ 43 ((size) > (capacity)) 44 45 /** 46 * Checks, if the passed vector should shrink. 47 * 48 * @param size The desired size of the vector. 49 * @param capacity The current capacity of the vector. 50 * @param threshold The shrink threshold. 51 * 52 * @return `ZYAN_TRUE`, if the vector should shrink or `ZYAN_FALSE`, if not. 53 */ 54 #define ZYCORE_VECTOR_SHOULD_SHRINK(size, capacity, threshold) \ 55 (((threshold) != 0) && ((size) * (threshold) < (capacity))) 56 57 /** 58 * Returns the offset of the element at the given `index`. 59 * 60 * @param vector A pointer to the `ZyanVector` instance. 61 * @param index The element index. 62 * 63 * @return The offset of the element at the given `index`. 64 */ 65 #define ZYCORE_VECTOR_OFFSET(vector, index) \ 66 ((void*)((ZyanU8*)(vector)->data + ((index) * (vector)->element_size))) 67 68 /* ============================================================================================== */ 69 /* Internal functions */ 70 /* ============================================================================================== */ 71 72 /* ---------------------------------------------------------------------------------------------- */ 73 /* Helper functions */ 74 /* ---------------------------------------------------------------------------------------------- */ 75 76 /** 77 * Reallocates the internal buffer of the vector. 78 * 79 * @param vector A pointer to the `ZyanVector` instance. 80 * @param capacity The new capacity. 81 * 82 * @return A zyan status code. 83 */ 84 static ZyanStatus ZyanVectorReallocate(ZyanVector* vector, ZyanUSize capacity) 85 { 86 ZYAN_ASSERT(vector); 87 ZYAN_ASSERT(vector->capacity >= ZYAN_VECTOR_MIN_CAPACITY); 88 ZYAN_ASSERT(vector->element_size); 89 ZYAN_ASSERT(vector->data); 90 91 if (!vector->allocator) 92 { 93 if (vector->capacity < capacity) 94 { 95 return ZYAN_STATUS_INSUFFICIENT_BUFFER_SIZE; 96 } 97 return ZYAN_STATUS_SUCCESS; 98 } 99 100 ZYAN_ASSERT(vector->allocator); 101 ZYAN_ASSERT(vector->allocator->reallocate); 102 103 if (capacity < ZYAN_VECTOR_MIN_CAPACITY) 104 { 105 if (vector->capacity > ZYAN_VECTOR_MIN_CAPACITY) 106 { 107 capacity = ZYAN_VECTOR_MIN_CAPACITY; 108 } else 109 { 110 return ZYAN_STATUS_SUCCESS; 111 } 112 } 113 114 vector->capacity = capacity; 115 ZYAN_CHECK(vector->allocator->reallocate(vector->allocator, &vector->data, 116 vector->element_size, vector->capacity)); 117 118 return ZYAN_STATUS_SUCCESS; 119 } 120 121 /** 122 * Shifts all elements starting at the specified `index` by the amount of `count` to the left. 123 * 124 * @param vector A pointer to the `ZyanVector` instance. 125 * @param index The start index. 126 * @param count The amount of shift operations. 127 * 128 * @return A zyan status code. 129 */ 130 static ZyanStatus ZyanVectorShiftLeft(ZyanVector* vector, ZyanUSize index, ZyanUSize count) 131 { 132 ZYAN_ASSERT(vector); 133 ZYAN_ASSERT(vector->element_size); 134 ZYAN_ASSERT(vector->data); 135 ZYAN_ASSERT(count > 0); 136 //ZYAN_ASSERT((ZyanISize)count - (ZyanISize)index + 1 >= 0); 137 138 const void* const source = ZYCORE_VECTOR_OFFSET(vector, index + count); 139 void* const dest = ZYCORE_VECTOR_OFFSET(vector, index); 140 const ZyanUSize size = (vector->size - index - count) * vector->element_size; 141 ZYAN_MEMMOVE(dest, source, size); 142 143 return ZYAN_STATUS_SUCCESS; 144 } 145 146 /** 147 * Shifts all elements starting at the specified `index` by the amount of `count` to the right. 148 * 149 * @param vector A pointer to the `ZyanVector` instance. 150 * @param index The start index. 151 * @param count The amount of shift operations. 152 * 153 * @return A zyan status code. 154 */ 155 static ZyanStatus ZyanVectorShiftRight(ZyanVector* vector, ZyanUSize index, ZyanUSize count) 156 { 157 ZYAN_ASSERT(vector); 158 ZYAN_ASSERT(vector->element_size); 159 ZYAN_ASSERT(vector->data); 160 ZYAN_ASSERT(count > 0); 161 ZYAN_ASSERT(vector->size + count <= vector->capacity); 162 163 const void* const source = ZYCORE_VECTOR_OFFSET(vector, index); 164 void* const dest = ZYCORE_VECTOR_OFFSET(vector, index + count); 165 const ZyanUSize size = (vector->size - index) * vector->element_size; 166 ZYAN_MEMMOVE(dest, source, size); 167 168 return ZYAN_STATUS_SUCCESS; 169 } 170 171 /* ---------------------------------------------------------------------------------------------- */ 172 173 /* ============================================================================================== */ 174 /* Exported functions */ 175 /* ============================================================================================== */ 176 177 /* ---------------------------------------------------------------------------------------------- */ 178 /* Constructor and destructor */ 179 /* ---------------------------------------------------------------------------------------------- */ 180 181 #ifndef ZYAN_NO_LIBC 182 183 ZyanStatus ZyanVectorInit(ZyanVector* vector, ZyanUSize element_size, ZyanUSize capacity, 184 ZyanMemberProcedure destructor) 185 { 186 return ZyanVectorInitEx(vector, element_size, capacity, destructor, ZyanAllocatorDefault(), 187 ZYAN_VECTOR_DEFAULT_GROWTH_FACTOR, ZYAN_VECTOR_DEFAULT_SHRINK_THRESHOLD); 188 } 189 190 #endif // ZYAN_NO_LIBC 191 192 ZyanStatus ZyanVectorInitEx(ZyanVector* vector, ZyanUSize element_size, ZyanUSize capacity, 193 ZyanMemberProcedure destructor, ZyanAllocator* allocator, ZyanU8 growth_factor, 194 ZyanU8 shrink_threshold) 195 { 196 if (!vector || !element_size || !allocator || (growth_factor < 1)) 197 { 198 return ZYAN_STATUS_INVALID_ARGUMENT; 199 } 200 201 ZYAN_ASSERT(allocator->allocate); 202 203 vector->allocator = allocator; 204 vector->growth_factor = growth_factor; 205 vector->shrink_threshold = shrink_threshold; 206 vector->size = 0; 207 vector->capacity = ZYAN_MAX(ZYAN_VECTOR_MIN_CAPACITY, capacity); 208 vector->element_size = element_size; 209 vector->destructor = destructor; 210 vector->data = ZYAN_NULL; 211 212 return allocator->allocate(vector->allocator, &vector->data, vector->element_size, 213 vector->capacity); 214 } 215 216 ZyanStatus ZyanVectorInitCustomBuffer(ZyanVector* vector, ZyanUSize element_size, 217 void* buffer, ZyanUSize capacity, ZyanMemberProcedure destructor) 218 { 219 if (!vector || !element_size || !buffer || !capacity) 220 { 221 return ZYAN_STATUS_INVALID_ARGUMENT; 222 } 223 224 vector->allocator = ZYAN_NULL; 225 vector->growth_factor = 1; 226 vector->shrink_threshold = 0; 227 vector->size = 0; 228 vector->capacity = capacity; 229 vector->element_size = element_size; 230 vector->destructor = destructor; 231 vector->data = buffer; 232 233 return ZYAN_STATUS_SUCCESS; 234 } 235 236 ZyanStatus ZyanVectorDestroy(ZyanVector* vector) 237 { 238 if (!vector) 239 { 240 return ZYAN_STATUS_INVALID_ARGUMENT; 241 } 242 243 ZYAN_ASSERT(vector->element_size); 244 ZYAN_ASSERT(vector->data); 245 246 if (vector->destructor) 247 { 248 for (ZyanUSize i = 0; i < vector->size; ++i) 249 { 250 vector->destructor(ZYCORE_VECTOR_OFFSET(vector, i)); 251 } 252 } 253 254 if (vector->allocator && vector->capacity) 255 { 256 ZYAN_ASSERT(vector->allocator->deallocate); 257 ZYAN_CHECK(vector->allocator->deallocate(vector->allocator, vector->data, 258 vector->element_size, vector->capacity)); 259 } 260 261 vector->data = ZYAN_NULL; 262 return ZYAN_STATUS_SUCCESS; 263 } 264 265 /* ---------------------------------------------------------------------------------------------- */ 266 /* Duplication */ 267 /* ---------------------------------------------------------------------------------------------- */ 268 269 #ifndef ZYAN_NO_LIBC 270 271 ZyanStatus ZyanVectorDuplicate(ZyanVector* destination, const ZyanVector* source, 272 ZyanUSize capacity) 273 { 274 return ZyanVectorDuplicateEx(destination, source, capacity, ZyanAllocatorDefault(), 275 ZYAN_VECTOR_DEFAULT_GROWTH_FACTOR, ZYAN_VECTOR_DEFAULT_SHRINK_THRESHOLD); 276 } 277 278 #endif // ZYAN_NO_LIBC 279 280 ZyanStatus ZyanVectorDuplicateEx(ZyanVector* destination, const ZyanVector* source, 281 ZyanUSize capacity, ZyanAllocator* allocator, ZyanU8 growth_factor, ZyanU8 shrink_threshold) 282 { 283 if (!source) 284 { 285 return ZYAN_STATUS_INVALID_ARGUMENT; 286 } 287 288 const ZyanUSize len = source->size; 289 290 capacity = ZYAN_MAX(capacity, len); 291 ZYAN_CHECK(ZyanVectorInitEx(destination, source->element_size, capacity, source->destructor, 292 allocator, growth_factor, shrink_threshold)); 293 ZYAN_ASSERT(destination->capacity >= len); 294 295 ZYAN_MEMCPY(destination->data, source->data, len * source->element_size); 296 destination->size = len; 297 298 return ZYAN_STATUS_SUCCESS; 299 } 300 301 ZyanStatus ZyanVectorDuplicateCustomBuffer(ZyanVector* destination, const ZyanVector* source, 302 void* buffer, ZyanUSize capacity) 303 { 304 if (!source) 305 { 306 return ZYAN_STATUS_INVALID_ARGUMENT; 307 } 308 309 const ZyanUSize len = source->size; 310 311 if (capacity < len) 312 { 313 return ZYAN_STATUS_INSUFFICIENT_BUFFER_SIZE; 314 } 315 316 ZYAN_CHECK(ZyanVectorInitCustomBuffer(destination, source->element_size, buffer, capacity, 317 source->destructor)); 318 ZYAN_ASSERT(destination->capacity >= len); 319 320 ZYAN_MEMCPY(destination->data, source->data, len * source->element_size); 321 destination->size = len; 322 323 return ZYAN_STATUS_SUCCESS; 324 } 325 326 /* ---------------------------------------------------------------------------------------------- */ 327 /* Element access */ 328 /* ---------------------------------------------------------------------------------------------- */ 329 330 const void* ZyanVectorGet(const ZyanVector* vector, ZyanUSize index) 331 { 332 if (!vector || (index >= vector->size)) 333 { 334 return ZYAN_NULL; 335 } 336 337 ZYAN_ASSERT(vector->element_size); 338 ZYAN_ASSERT(vector->data); 339 340 return ZYCORE_VECTOR_OFFSET(vector, index); 341 } 342 343 void* ZyanVectorGetMutable(const ZyanVector* vector, ZyanUSize index) 344 { 345 if (!vector || (index >= vector->size)) 346 { 347 return ZYAN_NULL; 348 } 349 350 ZYAN_ASSERT(vector->element_size); 351 ZYAN_ASSERT(vector->data); 352 353 return ZYCORE_VECTOR_OFFSET(vector, index); 354 } 355 356 ZyanStatus ZyanVectorGetPointer(const ZyanVector* vector, ZyanUSize index, const void** value) 357 { 358 if (!vector || !value) 359 { 360 return ZYAN_STATUS_INVALID_ARGUMENT; 361 } 362 if (index >= vector->size) 363 { 364 return ZYAN_STATUS_OUT_OF_RANGE; 365 } 366 367 ZYAN_ASSERT(vector->element_size); 368 ZYAN_ASSERT(vector->data); 369 370 *value = (const void*)ZYCORE_VECTOR_OFFSET(vector, index); 371 372 return ZYAN_STATUS_SUCCESS; 373 } 374 375 ZyanStatus ZyanVectorGetPointerMutable(const ZyanVector* vector, ZyanUSize index, void** value) 376 { 377 if (!vector || !value) 378 { 379 return ZYAN_STATUS_INVALID_ARGUMENT; 380 } 381 if (index >= vector->size) 382 { 383 return ZYAN_STATUS_OUT_OF_RANGE; 384 } 385 386 ZYAN_ASSERT(vector->element_size); 387 ZYAN_ASSERT(vector->data); 388 389 *value = ZYCORE_VECTOR_OFFSET(vector, index); 390 391 return ZYAN_STATUS_SUCCESS; 392 } 393 394 ZyanStatus ZyanVectorSet(ZyanVector* vector, ZyanUSize index, const void* value) 395 { 396 if (!vector || !value) 397 { 398 return ZYAN_STATUS_INVALID_ARGUMENT; 399 } 400 if (index >= vector->size) 401 { 402 return ZYAN_STATUS_OUT_OF_RANGE; 403 } 404 405 ZYAN_ASSERT(vector->element_size); 406 ZYAN_ASSERT(vector->data); 407 408 void* const offset = ZYCORE_VECTOR_OFFSET(vector, index); 409 if (vector->destructor) 410 { 411 vector->destructor(offset); 412 } 413 ZYAN_MEMCPY(offset, value, vector->element_size); 414 415 return ZYAN_STATUS_SUCCESS; 416 } 417 418 /* ---------------------------------------------------------------------------------------------- */ 419 /* Insertion */ 420 /* ---------------------------------------------------------------------------------------------- */ 421 422 ZyanStatus ZyanVectorPushBack(ZyanVector* vector, const void* element) 423 { 424 if (!vector || !element) 425 { 426 return ZYAN_STATUS_INVALID_ARGUMENT; 427 } 428 429 ZYAN_ASSERT(vector->element_size); 430 ZYAN_ASSERT(vector->data); 431 432 if (ZYCORE_VECTOR_SHOULD_GROW(vector->size + 1, vector->capacity)) 433 { 434 ZYAN_CHECK(ZyanVectorReallocate(vector, 435 ZYAN_MAX(1, (ZyanUSize)((vector->size + 1) * vector->growth_factor)))); 436 } 437 438 void* const offset = ZYCORE_VECTOR_OFFSET(vector, vector->size); 439 ZYAN_MEMCPY(offset, element, vector->element_size); 440 441 ++vector->size; 442 443 return ZYAN_STATUS_SUCCESS; 444 } 445 446 ZyanStatus ZyanVectorInsert(ZyanVector* vector, ZyanUSize index, const void* element) 447 { 448 return ZyanVectorInsertRange(vector, index, element, 1); 449 } 450 451 ZyanStatus ZyanVectorInsertRange(ZyanVector* vector, ZyanUSize index, const void* elements, 452 ZyanUSize count) 453 { 454 if (!vector || !elements || !count) 455 { 456 return ZYAN_STATUS_INVALID_ARGUMENT; 457 } 458 if (index > vector->size) 459 { 460 return ZYAN_STATUS_OUT_OF_RANGE; 461 } 462 463 ZYAN_ASSERT(vector->element_size); 464 ZYAN_ASSERT(vector->data); 465 466 if (ZYCORE_VECTOR_SHOULD_GROW(vector->size + count, vector->capacity)) 467 { 468 ZYAN_CHECK(ZyanVectorReallocate(vector, 469 ZYAN_MAX(1, (ZyanUSize)((vector->size + count) * vector->growth_factor)))); 470 } 471 472 if (index < vector->size) 473 { 474 ZYAN_CHECK(ZyanVectorShiftRight(vector, index, count)); 475 } 476 477 void* const offset = ZYCORE_VECTOR_OFFSET(vector, index); 478 ZYAN_MEMCPY(offset, elements, count * vector->element_size); 479 vector->size += count; 480 481 return ZYAN_STATUS_SUCCESS; 482 } 483 484 ZyanStatus ZyanVectorEmplace(ZyanVector* vector, void** element, ZyanMemberFunction constructor) 485 { 486 if (!vector) 487 { 488 return ZYAN_STATUS_INVALID_ARGUMENT; 489 } 490 491 return ZyanVectorEmplaceEx(vector, vector->size, element, constructor); 492 } 493 494 ZyanStatus ZyanVectorEmplaceEx(ZyanVector* vector, ZyanUSize index, void** element, 495 ZyanMemberFunction constructor) 496 { 497 if (!vector) 498 { 499 return ZYAN_STATUS_INVALID_ARGUMENT; 500 } 501 if (index > vector->size) 502 { 503 return ZYAN_STATUS_OUT_OF_RANGE; 504 } 505 506 ZYAN_ASSERT(vector->element_size); 507 ZYAN_ASSERT(vector->data); 508 509 if (ZYCORE_VECTOR_SHOULD_GROW(vector->size + 1, vector->capacity)) 510 { 511 ZYAN_CHECK(ZyanVectorReallocate(vector, 512 ZYAN_MAX(1, (ZyanUSize)((vector->size + 1) * vector->growth_factor)))); 513 } 514 515 if (index < vector->size) 516 { 517 ZYAN_CHECK(ZyanVectorShiftRight(vector, index, 1)); 518 } 519 520 *element = ZYCORE_VECTOR_OFFSET(vector, index); 521 if (constructor) 522 { 523 ZYAN_CHECK(constructor(*element)); 524 } 525 526 ++vector->size; 527 528 return ZYAN_STATUS_SUCCESS; 529 } 530 531 /* ---------------------------------------------------------------------------------------------- */ 532 /* Utils */ 533 /* ---------------------------------------------------------------------------------------------- */ 534 535 ZyanStatus ZyanVectorSwapElements(ZyanVector* vector, ZyanUSize index_first, ZyanUSize index_second) 536 { 537 if (!vector) 538 { 539 return ZYAN_STATUS_INVALID_ARGUMENT; 540 } 541 if ((index_first >= vector->size) || (index_second >= vector->size)) 542 { 543 return ZYAN_STATUS_OUT_OF_RANGE; 544 } 545 546 if (vector->size == vector->capacity) 547 { 548 return ZYAN_STATUS_INSUFFICIENT_BUFFER_SIZE; 549 } 550 551 ZYAN_ASSERT(vector->element_size); 552 ZYAN_ASSERT(vector->data); 553 554 ZyanU64* const t = ZYCORE_VECTOR_OFFSET(vector, vector->size); 555 ZyanU64* const a = ZYCORE_VECTOR_OFFSET(vector, index_first); 556 ZyanU64* const b = ZYCORE_VECTOR_OFFSET(vector, index_second); 557 ZYAN_MEMCPY(t, a, vector->element_size); 558 ZYAN_MEMCPY(a, b, vector->element_size); 559 ZYAN_MEMCPY(b, t, vector->element_size); 560 561 return ZYAN_STATUS_SUCCESS; 562 } 563 564 /* ---------------------------------------------------------------------------------------------- */ 565 /* Deletion */ 566 /* ---------------------------------------------------------------------------------------------- */ 567 568 ZyanStatus ZyanVectorDelete(ZyanVector* vector, ZyanUSize index) 569 { 570 return ZyanVectorDeleteRange(vector, index, 1); 571 } 572 573 ZyanStatus ZyanVectorDeleteRange(ZyanVector* vector, ZyanUSize index, ZyanUSize count) 574 { 575 if (!vector || !count) 576 { 577 return ZYAN_STATUS_INVALID_ARGUMENT; 578 } 579 if (index + count > vector->size) 580 { 581 return ZYAN_STATUS_OUT_OF_RANGE; 582 } 583 584 if (vector->destructor) 585 { 586 for (ZyanUSize i = index; i < index + count; ++i) 587 { 588 vector->destructor(ZYCORE_VECTOR_OFFSET(vector, i)); 589 } 590 } 591 592 if (index + count < vector->size) 593 { 594 ZYAN_CHECK(ZyanVectorShiftLeft(vector, index, count)); 595 } 596 597 vector->size -= count; 598 if (ZYCORE_VECTOR_SHOULD_SHRINK(vector->size, vector->capacity, vector->shrink_threshold)) 599 { 600 return ZyanVectorReallocate(vector, 601 ZYAN_MAX(1, (ZyanUSize)(vector->size * vector->growth_factor))); 602 } 603 604 return ZYAN_STATUS_SUCCESS; 605 } 606 607 ZyanStatus ZyanVectorPopBack(ZyanVector* vector) 608 { 609 if (!vector) 610 { 611 return ZYAN_STATUS_INVALID_ARGUMENT; 612 } 613 if (vector->size == 0) 614 { 615 return ZYAN_STATUS_OUT_OF_RANGE; 616 } 617 618 if (vector->destructor) 619 { 620 vector->destructor(ZYCORE_VECTOR_OFFSET(vector, vector->size - 1)); 621 } 622 623 --vector->size; 624 if (ZYCORE_VECTOR_SHOULD_SHRINK(vector->size, vector->capacity, vector->shrink_threshold)) 625 { 626 return ZyanVectorReallocate(vector, 627 ZYAN_MAX(1, (ZyanUSize)(vector->size * vector->growth_factor))); 628 } 629 630 return ZYAN_STATUS_SUCCESS; 631 } 632 633 ZyanStatus ZyanVectorClear(ZyanVector* vector) 634 { 635 return ZyanVectorResizeEx(vector, 0, ZYAN_NULL); 636 } 637 638 /* ---------------------------------------------------------------------------------------------- */ 639 /* Searching */ 640 /* ---------------------------------------------------------------------------------------------- */ 641 642 ZyanStatus ZyanVectorFind(const ZyanVector* vector, const void* element, ZyanISize* found_index, 643 ZyanEqualityComparison comparison) 644 { 645 if (!vector) 646 { 647 return ZYAN_STATUS_INVALID_ARGUMENT; 648 } 649 650 return ZyanVectorFindEx(vector, element, found_index, comparison, 0, vector->size); 651 } 652 653 ZyanStatus ZyanVectorFindEx(const ZyanVector* vector, const void* element, ZyanISize* found_index, 654 ZyanEqualityComparison comparison, ZyanUSize index, ZyanUSize count) 655 { 656 if (!vector) 657 { 658 return ZYAN_STATUS_INVALID_ARGUMENT; 659 } 660 if ((index + count > vector->size) || (index == vector->size)) 661 { 662 return ZYAN_STATUS_OUT_OF_RANGE; 663 } 664 665 if (!count) 666 { 667 *found_index = -1; 668 return ZYAN_STATUS_FALSE; 669 } 670 671 ZYAN_ASSERT(vector->element_size); 672 ZYAN_ASSERT(vector->data); 673 674 for (ZyanUSize i = index; i < index + count; ++i) 675 { 676 if (comparison(ZYCORE_VECTOR_OFFSET(vector, i), element)) 677 { 678 *found_index = i; 679 return ZYAN_STATUS_TRUE; 680 } 681 } 682 683 *found_index = -1; 684 return ZYAN_STATUS_FALSE; 685 } 686 687 ZyanStatus ZyanVectorBinarySearch(const ZyanVector* vector, const void* element, 688 ZyanUSize* found_index, ZyanComparison comparison) 689 { 690 if (!vector) 691 { 692 return ZYAN_STATUS_INVALID_ARGUMENT; 693 } 694 695 return ZyanVectorBinarySearchEx(vector, element, found_index, comparison, 0, vector->size); 696 } 697 698 ZyanStatus ZyanVectorBinarySearchEx(const ZyanVector* vector, const void* element, 699 ZyanUSize* found_index, ZyanComparison comparison, ZyanUSize index, ZyanUSize count) 700 { 701 if (!vector) 702 { 703 return ZYAN_STATUS_INVALID_ARGUMENT; 704 } 705 if (((index >= vector->size) && (count > 0)) || (index + count > vector->size)) 706 { 707 return ZYAN_STATUS_OUT_OF_RANGE; 708 } 709 710 if (!count) 711 { 712 *found_index = index; 713 return ZYAN_STATUS_FALSE; 714 } 715 716 ZYAN_ASSERT(vector->element_size); 717 ZYAN_ASSERT(vector->data); 718 719 ZyanStatus status = ZYAN_STATUS_FALSE; 720 ZyanISize l = index; 721 ZyanISize h = index + count - 1; 722 while (l <= h) 723 { 724 const ZyanUSize mid = l + ((h - l) >> 1); 725 const ZyanI32 cmp = comparison(ZYCORE_VECTOR_OFFSET(vector, mid), element); 726 if (cmp < 0) 727 { 728 l = mid + 1; 729 } else 730 { 731 h = mid - 1; 732 if (cmp == 0) 733 { 734 status = ZYAN_STATUS_TRUE; 735 } 736 } 737 } 738 739 *found_index = l; 740 return status; 741 } 742 743 /* ---------------------------------------------------------------------------------------------- */ 744 /* Memory management */ 745 /* ---------------------------------------------------------------------------------------------- */ 746 747 ZyanStatus ZyanVectorResize(ZyanVector* vector, ZyanUSize size) 748 { 749 return ZyanVectorResizeEx(vector, size, ZYAN_NULL); 750 } 751 752 ZyanStatus ZyanVectorResizeEx(ZyanVector* vector, ZyanUSize size, const void* initializer) 753 { 754 if (!vector) 755 { 756 return ZYAN_STATUS_INVALID_ARGUMENT; 757 } 758 if (size == vector->size) 759 { 760 return ZYAN_STATUS_SUCCESS; 761 } 762 763 if (vector->destructor && (size < vector->size)) 764 { 765 for (ZyanUSize i = size; i < vector->size; ++i) 766 { 767 vector->destructor(ZYCORE_VECTOR_OFFSET(vector, i)); 768 } 769 } 770 771 if (ZYCORE_VECTOR_SHOULD_GROW(size, vector->capacity) || 772 ZYCORE_VECTOR_SHOULD_SHRINK(size, vector->capacity, vector->shrink_threshold)) 773 { 774 ZYAN_ASSERT(vector->growth_factor >= 1); 775 ZYAN_CHECK(ZyanVectorReallocate(vector, (ZyanUSize)(size * vector->growth_factor))); 776 } 777 778 if (initializer && (size > vector->size)) 779 { 780 for (ZyanUSize i = vector->size; i < size; ++i) 781 { 782 ZYAN_MEMCPY(ZYCORE_VECTOR_OFFSET(vector, i), initializer, vector->element_size); 783 } 784 } 785 786 vector->size = size; 787 788 return ZYAN_STATUS_SUCCESS; 789 } 790 791 ZyanStatus ZyanVectorReserve(ZyanVector* vector, ZyanUSize capacity) 792 { 793 if (!vector) 794 { 795 return ZYAN_STATUS_INVALID_ARGUMENT; 796 } 797 798 if (capacity > vector->capacity) 799 { 800 ZYAN_CHECK(ZyanVectorReallocate(vector, capacity)); 801 } 802 803 return ZYAN_STATUS_SUCCESS; 804 } 805 806 ZyanStatus ZyanVectorShrinkToFit(ZyanVector* vector) 807 { 808 if (!vector) 809 { 810 return ZYAN_STATUS_INVALID_ARGUMENT; 811 } 812 813 return ZyanVectorReallocate(vector, vector->size); 814 } 815 816 /* ---------------------------------------------------------------------------------------------- */ 817 /* Information */ 818 /* ---------------------------------------------------------------------------------------------- */ 819 820 ZyanStatus ZyanVectorGetCapacity(const ZyanVector* vector, ZyanUSize* capacity) 821 { 822 if (!vector) 823 { 824 return ZYAN_STATUS_INVALID_ARGUMENT; 825 } 826 827 *capacity = vector->capacity; 828 829 return ZYAN_STATUS_SUCCESS; 830 } 831 832 ZyanStatus ZyanVectorGetSize(const ZyanVector* vector, ZyanUSize* size) 833 { 834 if (!vector) 835 { 836 return ZYAN_STATUS_INVALID_ARGUMENT; 837 } 838 839 *size = vector->size; 840 841 return ZYAN_STATUS_SUCCESS; 842 } 843 844 /* ---------------------------------------------------------------------------------------------- */ 845 846 /* ============================================================================================== */ 847