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 */
ZyanVectorReallocate(ZyanVector * vector,ZyanUSize capacity)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 */
ZyanVectorShiftLeft(ZyanVector * vector,ZyanUSize index,ZyanUSize count)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 */
ZyanVectorShiftRight(ZyanVector * vector,ZyanUSize index,ZyanUSize count)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
ZyanVectorInit(ZyanVector * vector,ZyanUSize element_size,ZyanUSize capacity,ZyanMemberProcedure destructor)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
ZyanVectorInitEx(ZyanVector * vector,ZyanUSize element_size,ZyanUSize capacity,ZyanMemberProcedure destructor,ZyanAllocator * allocator,ZyanU8 growth_factor,ZyanU8 shrink_threshold)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
ZyanVectorInitCustomBuffer(ZyanVector * vector,ZyanUSize element_size,void * buffer,ZyanUSize capacity,ZyanMemberProcedure destructor)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
ZyanVectorDestroy(ZyanVector * vector)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
ZyanVectorDuplicate(ZyanVector * destination,const ZyanVector * source,ZyanUSize capacity)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
ZyanVectorDuplicateEx(ZyanVector * destination,const ZyanVector * source,ZyanUSize capacity,ZyanAllocator * allocator,ZyanU8 growth_factor,ZyanU8 shrink_threshold)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
ZyanVectorDuplicateCustomBuffer(ZyanVector * destination,const ZyanVector * source,void * buffer,ZyanUSize capacity)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
ZyanVectorGet(const ZyanVector * vector,ZyanUSize index)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
ZyanVectorGetMutable(const ZyanVector * vector,ZyanUSize index)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
ZyanVectorGetPointer(const ZyanVector * vector,ZyanUSize index,const void ** value)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
ZyanVectorGetPointerMutable(const ZyanVector * vector,ZyanUSize index,void ** value)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
ZyanVectorSet(ZyanVector * vector,ZyanUSize index,const void * value)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
ZyanVectorPushBack(ZyanVector * vector,const void * element)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
ZyanVectorInsert(ZyanVector * vector,ZyanUSize index,const void * element)446 ZyanStatus ZyanVectorInsert(ZyanVector* vector, ZyanUSize index, const void* element)
447 {
448 return ZyanVectorInsertRange(vector, index, element, 1);
449 }
450
ZyanVectorInsertRange(ZyanVector * vector,ZyanUSize index,const void * elements,ZyanUSize count)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
ZyanVectorEmplace(ZyanVector * vector,void ** element,ZyanMemberFunction constructor)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
ZyanVectorEmplaceEx(ZyanVector * vector,ZyanUSize index,void ** element,ZyanMemberFunction constructor)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
ZyanVectorSwapElements(ZyanVector * vector,ZyanUSize index_first,ZyanUSize index_second)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
ZyanVectorDelete(ZyanVector * vector,ZyanUSize index)568 ZyanStatus ZyanVectorDelete(ZyanVector* vector, ZyanUSize index)
569 {
570 return ZyanVectorDeleteRange(vector, index, 1);
571 }
572
ZyanVectorDeleteRange(ZyanVector * vector,ZyanUSize index,ZyanUSize count)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
ZyanVectorPopBack(ZyanVector * vector)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
ZyanVectorClear(ZyanVector * vector)633 ZyanStatus ZyanVectorClear(ZyanVector* vector)
634 {
635 return ZyanVectorResizeEx(vector, 0, ZYAN_NULL);
636 }
637
638 /* ---------------------------------------------------------------------------------------------- */
639 /* Searching */
640 /* ---------------------------------------------------------------------------------------------- */
641
ZyanVectorFind(const ZyanVector * vector,const void * element,ZyanISize * found_index,ZyanEqualityComparison comparison)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
ZyanVectorFindEx(const ZyanVector * vector,const void * element,ZyanISize * found_index,ZyanEqualityComparison comparison,ZyanUSize index,ZyanUSize count)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
ZyanVectorBinarySearch(const ZyanVector * vector,const void * element,ZyanUSize * found_index,ZyanComparison comparison)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
ZyanVectorBinarySearchEx(const ZyanVector * vector,const void * element,ZyanUSize * found_index,ZyanComparison comparison,ZyanUSize index,ZyanUSize count)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
ZyanVectorResize(ZyanVector * vector,ZyanUSize size)747 ZyanStatus ZyanVectorResize(ZyanVector* vector, ZyanUSize size)
748 {
749 return ZyanVectorResizeEx(vector, size, ZYAN_NULL);
750 }
751
ZyanVectorResizeEx(ZyanVector * vector,ZyanUSize size,const void * initializer)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
ZyanVectorReserve(ZyanVector * vector,ZyanUSize capacity)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
ZyanVectorShrinkToFit(ZyanVector * vector)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
ZyanVectorGetCapacity(const ZyanVector * vector,ZyanUSize * capacity)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
ZyanVectorGetSize(const ZyanVector * vector,ZyanUSize * size)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