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 "zydis/Zycore/LibC.h"
28 #include "zydis/Zycore/Vector.h"
29
30 /* ============================================================================================== */
31 /* Internal macros */
32 /* ============================================================================================== */
33
34 /**
35 * @brief 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 * @brief 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 ((size) < (capacity) * (threshold))
56
57 /**
58 * @brief 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 * @brief 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 * @brief Shifts all elements starting at the specified `index` by the amount of `count` to the
123 * left.
124 *
125 * @param vector A pointer to the `ZyanVector` instance.
126 * @param index The start index.
127 * @param count The amount of shift operations.
128 *
129 * @return A zyan status code.
130 */
ZyanVectorShiftLeft(ZyanVector * vector,ZyanUSize index,ZyanUSize count)131 static ZyanStatus ZyanVectorShiftLeft(ZyanVector* vector, ZyanUSize index, ZyanUSize count)
132 {
133 ZYAN_ASSERT(vector);
134 ZYAN_ASSERT(vector->element_size);
135 ZYAN_ASSERT(vector->data);
136 ZYAN_ASSERT(count > 0);
137 //ZYAN_ASSERT((ZyanISize)count - (ZyanISize)index + 1 >= 0);
138
139 void* const source = ZYCORE_VECTOR_OFFSET(vector, index + count);
140 void* const dest = ZYCORE_VECTOR_OFFSET(vector, index);
141 const ZyanUSize size = (vector->size - index - count) * vector->element_size;
142 ZYAN_MEMMOVE(dest, source, size);
143
144 return ZYAN_STATUS_SUCCESS;
145 }
146
147 /**
148 * @brief Shifts all elements starting at the specified `index` by the amount of `count` to the
149 * right.
150 *
151 * @param vector A pointer to the `ZyanVector` instance.
152 * @param index The start index.
153 * @param count The amount of shift operations.
154 *
155 * @return A zyan status code.
156 */
ZyanVectorShiftRight(ZyanVector * vector,ZyanUSize index,ZyanUSize count)157 static ZyanStatus ZyanVectorShiftRight(ZyanVector* vector, ZyanUSize index, ZyanUSize count)
158 {
159 ZYAN_ASSERT(vector);
160 ZYAN_ASSERT(vector->element_size);
161 ZYAN_ASSERT(vector->data);
162 ZYAN_ASSERT(count > 0);
163 ZYAN_ASSERT(vector->size + count <= vector->capacity);
164
165 void* const source = ZYCORE_VECTOR_OFFSET(vector, index);
166 void* const dest = ZYCORE_VECTOR_OFFSET(vector, index + count);
167 const ZyanUSize size = (vector->size - index) * vector->element_size;
168 ZYAN_MEMMOVE(dest, source, size);
169
170 return ZYAN_STATUS_SUCCESS;
171 }
172
173 /* ---------------------------------------------------------------------------------------------- */
174
175 /* ============================================================================================== */
176 /* Exported functions */
177 /* ============================================================================================== */
178
179 /* ---------------------------------------------------------------------------------------------- */
180 /* Constructor and destructor */
181 /* ---------------------------------------------------------------------------------------------- */
182
183 #ifndef ZYAN_NO_LIBC
184
ZyanVectorInit(ZyanVector * vector,ZyanUSize element_size,ZyanUSize capacity,ZyanMemberProcedure destructor)185 ZyanStatus ZyanVectorInit(ZyanVector* vector, ZyanUSize element_size, ZyanUSize capacity,
186 ZyanMemberProcedure destructor)
187 {
188 return ZyanVectorInitEx(vector, element_size, capacity, destructor, ZyanAllocatorDefault(),
189 ZYAN_VECTOR_DEFAULT_GROWTH_FACTOR, ZYAN_VECTOR_DEFAULT_SHRINK_THRESHOLD);
190 }
191
192 #endif // ZYAN_NO_LIBC
193
ZyanVectorInitEx(ZyanVector * vector,ZyanUSize element_size,ZyanUSize capacity,ZyanMemberProcedure destructor,ZyanAllocator * allocator,float growth_factor,float shrink_threshold)194 ZyanStatus ZyanVectorInitEx(ZyanVector* vector, ZyanUSize element_size, ZyanUSize capacity,
195 ZyanMemberProcedure destructor, ZyanAllocator* allocator, float growth_factor,
196 float shrink_threshold)
197 {
198 if (!vector || !element_size || !allocator || (growth_factor < 1.0f) ||
199 (shrink_threshold < 0.0f) || (shrink_threshold > 1.0f))
200 {
201 return ZYAN_STATUS_INVALID_ARGUMENT;
202 }
203
204 ZYAN_ASSERT(allocator->allocate);
205
206 vector->allocator = allocator;
207 vector->growth_factor = growth_factor;
208 vector->shrink_threshold = shrink_threshold;
209 vector->size = 0;
210 vector->capacity = ZYAN_MAX(ZYAN_VECTOR_MIN_CAPACITY, capacity);
211 vector->element_size = element_size;
212 vector->destructor = destructor;
213 vector->data = ZYAN_NULL;
214
215 return allocator->allocate(vector->allocator, &vector->data, vector->element_size,
216 vector->capacity);
217 }
218
ZyanVectorInitCustomBuffer(ZyanVector * vector,ZyanUSize element_size,void * buffer,ZyanUSize capacity,ZyanMemberProcedure destructor)219 ZyanStatus ZyanVectorInitCustomBuffer(ZyanVector* vector, ZyanUSize element_size,
220 void* buffer, ZyanUSize capacity, ZyanMemberProcedure destructor)
221 {
222 if (!vector || !element_size || !buffer || !capacity)
223 {
224 return ZYAN_STATUS_INVALID_ARGUMENT;
225 }
226
227 vector->allocator = ZYAN_NULL;
228 vector->growth_factor = 1.0f;
229 vector->shrink_threshold = 0.0f;
230 vector->size = 0;
231 vector->capacity = capacity;
232 vector->element_size = element_size;
233 vector->destructor = destructor;
234 vector->data = buffer;
235
236 return ZYAN_STATUS_SUCCESS;
237 }
238
ZyanVectorDestroy(ZyanVector * vector)239 ZyanStatus ZyanVectorDestroy(ZyanVector* vector)
240 {
241 if (!vector)
242 {
243 return ZYAN_STATUS_INVALID_ARGUMENT;
244 }
245
246 ZYAN_ASSERT(vector->element_size);
247 ZYAN_ASSERT(vector->data);
248
249 if (vector->destructor)
250 {
251 for (ZyanUSize i = 0; i < vector->size; ++i)
252 {
253 vector->destructor(ZYCORE_VECTOR_OFFSET(vector, i));
254 }
255 }
256
257 if (vector->allocator && vector->capacity)
258 {
259 ZYAN_ASSERT(vector->allocator->deallocate);
260 ZYAN_CHECK(vector->allocator->deallocate(vector->allocator, vector->data,
261 vector->element_size, vector->capacity));
262 }
263
264 vector->data = ZYAN_NULL;
265 return ZYAN_STATUS_SUCCESS;
266 }
267
268 /* ---------------------------------------------------------------------------------------------- */
269 /* Duplication */
270 /* ---------------------------------------------------------------------------------------------- */
271
272 #ifndef ZYAN_NO_LIBC
273
ZyanVectorDuplicate(ZyanVector * destination,const ZyanVector * source,ZyanUSize capacity)274 ZyanStatus ZyanVectorDuplicate(ZyanVector* destination, const ZyanVector* source,
275 ZyanUSize capacity)
276 {
277 return ZyanVectorDuplicateEx(destination, source, capacity, ZyanAllocatorDefault(),
278 ZYAN_VECTOR_DEFAULT_GROWTH_FACTOR, ZYAN_VECTOR_DEFAULT_SHRINK_THRESHOLD);
279 }
280
281 #endif // ZYAN_NO_LIBC
282
ZyanVectorDuplicateEx(ZyanVector * destination,const ZyanVector * source,ZyanUSize capacity,ZyanAllocator * allocator,float growth_factor,float shrink_threshold)283 ZyanStatus ZyanVectorDuplicateEx(ZyanVector* destination, const ZyanVector* source,
284 ZyanUSize capacity, ZyanAllocator* allocator, float growth_factor, float shrink_threshold)
285 {
286 if (!source)
287 {
288 return ZYAN_STATUS_INVALID_ARGUMENT;
289 }
290
291 const ZyanUSize len = source->size;
292
293 capacity = ZYAN_MAX(capacity, len);
294 ZYAN_CHECK(ZyanVectorInitEx(destination, source->element_size, capacity, source->destructor,
295 allocator, growth_factor, shrink_threshold));
296 ZYAN_ASSERT(destination->capacity >= len);
297
298 ZYAN_MEMCPY(destination->data, source->data, len * source->element_size);
299 destination->size = len;
300
301 return ZYAN_STATUS_SUCCESS;
302 }
303
ZyanVectorDuplicateCustomBuffer(ZyanVector * destination,const ZyanVector * source,void * buffer,ZyanUSize capacity)304 ZyanStatus ZyanVectorDuplicateCustomBuffer(ZyanVector* destination, const ZyanVector* source,
305 void* buffer, ZyanUSize capacity)
306 {
307 if (!source)
308 {
309 return ZYAN_STATUS_INVALID_ARGUMENT;
310 }
311
312 const ZyanUSize len = source->size;
313
314 if (capacity < len)
315 {
316 return ZYAN_STATUS_INSUFFICIENT_BUFFER_SIZE;
317 }
318
319 ZYAN_CHECK(ZyanVectorInitCustomBuffer(destination, source->element_size, buffer, capacity,
320 source->destructor));
321 ZYAN_ASSERT(destination->capacity >= len);
322
323 ZYAN_MEMCPY(destination->data, source->data, len * source->element_size);
324 destination->size = len;
325
326 return ZYAN_STATUS_SUCCESS;
327 }
328
329 /* ---------------------------------------------------------------------------------------------- */
330 /* Element access */
331 /* ---------------------------------------------------------------------------------------------- */
332
ZyanVectorGet(const ZyanVector * vector,ZyanUSize index)333 const void* ZyanVectorGet(const ZyanVector* vector, ZyanUSize index)
334 {
335 if (!vector || (index >= vector->size))
336 {
337 return ZYAN_NULL;
338 }
339
340 ZYAN_ASSERT(vector->element_size);
341 ZYAN_ASSERT(vector->data);
342
343 return ZYCORE_VECTOR_OFFSET(vector, index);
344 }
345
ZyanVectorGetMutable(const ZyanVector * vector,ZyanUSize index)346 void* ZyanVectorGetMutable(const ZyanVector* vector, ZyanUSize index)
347 {
348 if (!vector || (index >= vector->size))
349 {
350 return ZYAN_NULL;
351 }
352
353 ZYAN_ASSERT(vector->element_size);
354 ZYAN_ASSERT(vector->data);
355
356 return ZYCORE_VECTOR_OFFSET(vector, index);
357 }
358
ZyanVectorGetPointer(const ZyanVector * vector,ZyanUSize index,const void ** value)359 ZyanStatus ZyanVectorGetPointer(const ZyanVector* vector, ZyanUSize index, const void** value)
360 {
361 if (!vector || !value)
362 {
363 return ZYAN_STATUS_INVALID_ARGUMENT;
364 }
365 if (index >= vector->size)
366 {
367 return ZYAN_STATUS_OUT_OF_RANGE;
368 }
369
370 ZYAN_ASSERT(vector->element_size);
371 ZYAN_ASSERT(vector->data);
372
373 *value = (const void*)ZYCORE_VECTOR_OFFSET(vector, index);
374
375 return ZYAN_STATUS_SUCCESS;
376 }
377
ZyanVectorGetPointerMutable(const ZyanVector * vector,ZyanUSize index,void ** value)378 ZyanStatus ZyanVectorGetPointerMutable(const ZyanVector* vector, ZyanUSize index, void** value)
379 {
380 if (!vector || !value)
381 {
382 return ZYAN_STATUS_INVALID_ARGUMENT;
383 }
384 if (index >= vector->size)
385 {
386 return ZYAN_STATUS_OUT_OF_RANGE;
387 }
388
389 ZYAN_ASSERT(vector->element_size);
390 ZYAN_ASSERT(vector->data);
391
392 *value = ZYCORE_VECTOR_OFFSET(vector, index);
393
394 return ZYAN_STATUS_SUCCESS;
395 }
396
ZyanVectorSet(ZyanVector * vector,ZyanUSize index,const void * value)397 ZyanStatus ZyanVectorSet(ZyanVector* vector, ZyanUSize index, const void* value)
398 {
399 if (!vector || !value)
400 {
401 return ZYAN_STATUS_INVALID_ARGUMENT;
402 }
403 if (index >= vector->size)
404 {
405 return ZYAN_STATUS_OUT_OF_RANGE;
406 }
407
408 ZYAN_ASSERT(vector->element_size);
409 ZYAN_ASSERT(vector->data);
410
411 void* const offset = ZYCORE_VECTOR_OFFSET(vector, index);
412 if (vector->destructor)
413 {
414 vector->destructor(offset);
415 }
416 ZYAN_MEMCPY(offset, value, vector->element_size);
417
418 return ZYAN_STATUS_SUCCESS;
419 }
420
421 /* ---------------------------------------------------------------------------------------------- */
422 /* Insertion */
423 /* ---------------------------------------------------------------------------------------------- */
424
ZyanVectorPushBack(ZyanVector * vector,const void * element)425 ZyanStatus ZyanVectorPushBack(ZyanVector* vector, const void* element)
426 {
427 if (!vector || !element)
428 {
429 return ZYAN_STATUS_INVALID_ARGUMENT;
430 }
431
432 ZYAN_ASSERT(vector->element_size);
433 ZYAN_ASSERT(vector->data);
434
435 if (ZYCORE_VECTOR_SHOULD_GROW(vector->size + 1, vector->capacity))
436 {
437 ZYAN_CHECK(ZyanVectorReallocate(vector,
438 ZYAN_MAX(1, (ZyanUSize)((vector->size + 1) * vector->growth_factor))));
439 }
440
441 void* const offset = ZYCORE_VECTOR_OFFSET(vector, vector->size);
442 ZYAN_MEMCPY(offset, element, vector->element_size);
443
444 ++vector->size;
445
446 return ZYAN_STATUS_SUCCESS;
447 }
448
ZyanVectorInsert(ZyanVector * vector,ZyanUSize index,const void * element)449 ZyanStatus ZyanVectorInsert(ZyanVector* vector, ZyanUSize index, const void* element)
450 {
451 return ZyanVectorInsertRange(vector, index, element, 1);
452 }
453
ZyanVectorInsertRange(ZyanVector * vector,ZyanUSize index,const void * elements,ZyanUSize count)454 ZyanStatus ZyanVectorInsertRange(ZyanVector* vector, ZyanUSize index, const void* elements,
455 ZyanUSize count)
456 {
457 if (!vector || !elements || !count)
458 {
459 return ZYAN_STATUS_INVALID_ARGUMENT;
460 }
461 if (index > vector->size)
462 {
463 return ZYAN_STATUS_OUT_OF_RANGE;
464 }
465
466 ZYAN_ASSERT(vector->element_size);
467 ZYAN_ASSERT(vector->data);
468
469 if (ZYCORE_VECTOR_SHOULD_GROW(vector->size + count, vector->capacity))
470 {
471 ZYAN_CHECK(ZyanVectorReallocate(vector,
472 ZYAN_MAX(1, (ZyanUSize)((vector->size + count) * vector->growth_factor))));
473 }
474
475 if (index < vector->size)
476 {
477 ZYAN_CHECK(ZyanVectorShiftRight(vector, index, count));
478 }
479
480 void* const offset = ZYCORE_VECTOR_OFFSET(vector, index);
481 ZYAN_MEMCPY(offset, elements, count * vector->element_size);
482 vector->size += count;
483
484 return ZYAN_STATUS_SUCCESS;
485 }
486
ZyanVectorEmplace(ZyanVector * vector,void ** element,ZyanMemberFunction constructor)487 ZyanStatus ZyanVectorEmplace(ZyanVector* vector, void** element, ZyanMemberFunction constructor)
488 {
489 if (!vector)
490 {
491 return ZYAN_STATUS_INVALID_ARGUMENT;
492 }
493
494 return ZyanVectorEmplaceEx(vector, vector->size, element, constructor);
495 }
496
ZyanVectorEmplaceEx(ZyanVector * vector,ZyanUSize index,void ** element,ZyanMemberFunction constructor)497 ZyanStatus ZyanVectorEmplaceEx(ZyanVector* vector, ZyanUSize index, void** element,
498 ZyanMemberFunction constructor)
499 {
500 if (!vector)
501 {
502 return ZYAN_STATUS_INVALID_ARGUMENT;
503 }
504 if (index > vector->size)
505 {
506 return ZYAN_STATUS_OUT_OF_RANGE;
507 }
508
509 ZYAN_ASSERT(vector->element_size);
510 ZYAN_ASSERT(vector->data);
511
512 if (ZYCORE_VECTOR_SHOULD_GROW(vector->size + 1, vector->capacity))
513 {
514 ZYAN_CHECK(ZyanVectorReallocate(vector,
515 ZYAN_MAX(1, (ZyanUSize)((vector->size + 1) * vector->growth_factor))));
516 }
517
518 if (index < vector->size)
519 {
520 ZYAN_CHECK(ZyanVectorShiftRight(vector, index, 1));
521 }
522
523 *element = ZYCORE_VECTOR_OFFSET(vector, index);
524 if (constructor)
525 {
526 ZYAN_CHECK(constructor(*element));
527 }
528
529 ++vector->size;
530
531 return ZYAN_STATUS_SUCCESS;
532 }
533
534 /* ---------------------------------------------------------------------------------------------- */
535 /* Utils */
536 /* ---------------------------------------------------------------------------------------------- */
537
ZyanVectorSwapElements(ZyanVector * vector,ZyanUSize index_first,ZyanUSize index_second)538 ZyanStatus ZyanVectorSwapElements(ZyanVector* vector, ZyanUSize index_first, ZyanUSize index_second)
539 {
540 if (!vector)
541 {
542 return ZYAN_STATUS_INVALID_ARGUMENT;
543 }
544 if ((index_first >= vector->size) || (index_second >= vector->size))
545 {
546 return ZYAN_STATUS_OUT_OF_RANGE;
547 }
548
549 if (vector->size == vector->capacity)
550 {
551 return ZYAN_STATUS_INSUFFICIENT_BUFFER_SIZE;
552 }
553
554 ZYAN_ASSERT(vector->element_size);
555 ZYAN_ASSERT(vector->data);
556
557 ZyanU64* const t = ZYCORE_VECTOR_OFFSET(vector, vector->size);
558 ZyanU64* const a = ZYCORE_VECTOR_OFFSET(vector, index_first);
559 ZyanU64* const b = ZYCORE_VECTOR_OFFSET(vector, index_second);
560 ZYAN_MEMCPY(t, a, vector->element_size);
561 ZYAN_MEMCPY(a, b, vector->element_size);
562 ZYAN_MEMCPY(b, t, vector->element_size);
563
564 return ZYAN_STATUS_SUCCESS;
565 }
566
567 /* ---------------------------------------------------------------------------------------------- */
568 /* Deletion */
569 /* ---------------------------------------------------------------------------------------------- */
570
ZyanVectorDelete(ZyanVector * vector,ZyanUSize index)571 ZyanStatus ZyanVectorDelete(ZyanVector* vector, ZyanUSize index)
572 {
573 return ZyanVectorDeleteRange(vector, index, 1);
574 }
575
ZyanVectorDeleteRange(ZyanVector * vector,ZyanUSize index,ZyanUSize count)576 ZyanStatus ZyanVectorDeleteRange(ZyanVector* vector, ZyanUSize index, ZyanUSize count)
577 {
578 if (!vector || !count)
579 {
580 return ZYAN_STATUS_INVALID_ARGUMENT;
581 }
582 if (index + count > vector->size)
583 {
584 return ZYAN_STATUS_OUT_OF_RANGE;
585 }
586
587 if (vector->destructor)
588 {
589 for (ZyanUSize i = index; i < index + count; ++i)
590 {
591 vector->destructor(ZYCORE_VECTOR_OFFSET(vector, i));
592 }
593 }
594
595 if (index + count < vector->size)
596 {
597 ZYAN_CHECK(ZyanVectorShiftLeft(vector, index, count));
598 }
599
600 vector->size -= count;
601 if (ZYCORE_VECTOR_SHOULD_SHRINK(vector->size, vector->capacity, vector->shrink_threshold))
602 {
603 return ZyanVectorReallocate(vector,
604 ZYAN_MAX(1, (ZyanUSize)(vector->size * vector->growth_factor)));
605 }
606
607 return ZYAN_STATUS_SUCCESS;
608 }
609
ZyanVectorPopBack(ZyanVector * vector)610 ZyanStatus ZyanVectorPopBack(ZyanVector* vector)
611 {
612 if (!vector)
613 {
614 return ZYAN_STATUS_INVALID_ARGUMENT;
615 }
616 if (vector->size == 0)
617 {
618 return ZYAN_STATUS_OUT_OF_RANGE;
619 }
620
621 if (vector->destructor)
622 {
623 vector->destructor(ZYCORE_VECTOR_OFFSET(vector, vector->size - 1));
624 }
625
626 --vector->size;
627 if (ZYCORE_VECTOR_SHOULD_SHRINK(vector->size, vector->capacity, vector->shrink_threshold))
628 {
629 return ZyanVectorReallocate(vector,
630 ZYAN_MAX(1, (ZyanUSize)(vector->size * vector->growth_factor)));
631 }
632
633 return ZYAN_STATUS_SUCCESS;
634 }
635
ZyanVectorClear(ZyanVector * vector)636 ZyanStatus ZyanVectorClear(ZyanVector* vector)
637 {
638 return ZyanVectorResizeEx(vector, 0, ZYAN_NULL);
639 }
640
641 /* ---------------------------------------------------------------------------------------------- */
642 /* Searching */
643 /* ---------------------------------------------------------------------------------------------- */
644
ZyanVectorFind(const ZyanVector * vector,const void * element,ZyanISize * found_index,ZyanEqualityComparison comparison)645 ZyanStatus ZyanVectorFind(const ZyanVector* vector, const void* element, ZyanISize* found_index,
646 ZyanEqualityComparison comparison)
647 {
648 if (!vector)
649 {
650 return ZYAN_STATUS_INVALID_ARGUMENT;
651 }
652
653 return ZyanVectorFindEx(vector, element, found_index, comparison, 0, vector->size);
654 }
655
ZyanVectorFindEx(const ZyanVector * vector,const void * element,ZyanISize * found_index,ZyanEqualityComparison comparison,ZyanUSize index,ZyanUSize count)656 ZyanStatus ZyanVectorFindEx(const ZyanVector* vector, const void* element, ZyanISize* found_index,
657 ZyanEqualityComparison comparison, ZyanUSize index, ZyanUSize count)
658 {
659 if (!vector)
660 {
661 return ZYAN_STATUS_INVALID_ARGUMENT;
662 }
663 if ((index + count > vector->size) || (index == vector->size))
664 {
665 return ZYAN_STATUS_OUT_OF_RANGE;
666 }
667
668 if (!count)
669 {
670 *found_index = -1;
671 return ZYAN_STATUS_FALSE;
672 }
673
674 ZYAN_ASSERT(vector->element_size);
675 ZYAN_ASSERT(vector->data);
676
677 for (ZyanUSize i = index; i < index + count; ++i)
678 {
679 if (comparison(ZYCORE_VECTOR_OFFSET(vector, i), element))
680 {
681 *found_index = i;
682 return ZYAN_STATUS_TRUE;
683 }
684 }
685
686 *found_index = -1;
687 return ZYAN_STATUS_FALSE;
688 }
689
ZyanVectorBinarySearch(const ZyanVector * vector,const void * element,ZyanUSize * found_index,ZyanComparison comparison)690 ZyanStatus ZyanVectorBinarySearch(const ZyanVector* vector, const void* element,
691 ZyanUSize* found_index, ZyanComparison comparison)
692 {
693 if (!vector)
694 {
695 return ZYAN_STATUS_INVALID_ARGUMENT;
696 }
697
698 return ZyanVectorBinarySearchEx(vector, element, found_index, comparison, 0, vector->size);
699 }
700
ZyanVectorBinarySearchEx(const ZyanVector * vector,const void * element,ZyanUSize * found_index,ZyanComparison comparison,ZyanUSize index,ZyanUSize count)701 ZyanStatus ZyanVectorBinarySearchEx(const ZyanVector* vector, const void* element,
702 ZyanUSize* found_index, ZyanComparison comparison, ZyanUSize index, ZyanUSize count)
703 {
704 if (!vector)
705 {
706 return ZYAN_STATUS_INVALID_ARGUMENT;
707 }
708 if (((index >= vector->size) && (count > 0)) || (index + count > vector->size))
709 {
710 return ZYAN_STATUS_OUT_OF_RANGE;
711 }
712
713 if (!count)
714 {
715 *found_index = index;
716 return ZYAN_STATUS_FALSE;
717 }
718
719 ZYAN_ASSERT(vector->element_size);
720 ZYAN_ASSERT(vector->data);
721
722 ZyanStatus status = ZYAN_STATUS_FALSE;
723 ZyanISize l = index;
724 ZyanISize h = index + count - 1;
725 while (l <= h)
726 {
727 const ZyanUSize mid = l + ((h - l) >> 1);
728 const ZyanI32 cmp = comparison(ZYCORE_VECTOR_OFFSET(vector, mid), element);
729 if (cmp < 0)
730 {
731 l = mid + 1;
732 } else
733 {
734 h = mid - 1;
735 if (cmp == 0)
736 {
737 status = ZYAN_STATUS_TRUE;
738 }
739 }
740 }
741
742 *found_index = l;
743 return status;
744 }
745
746 /* ---------------------------------------------------------------------------------------------- */
747 /* Memory management */
748 /* ---------------------------------------------------------------------------------------------- */
749
ZyanVectorResize(ZyanVector * vector,ZyanUSize size)750 ZyanStatus ZyanVectorResize(ZyanVector* vector, ZyanUSize size)
751 {
752 return ZyanVectorResizeEx(vector, size, ZYAN_NULL);
753 }
754
ZyanVectorResizeEx(ZyanVector * vector,ZyanUSize size,const void * initializer)755 ZyanStatus ZyanVectorResizeEx(ZyanVector* vector, ZyanUSize size, const void* initializer)
756 {
757 if (!vector)
758 {
759 return ZYAN_STATUS_INVALID_ARGUMENT;
760 }
761 if (size == vector->size)
762 {
763 return ZYAN_STATUS_SUCCESS;
764 }
765
766 if (vector->destructor && (size < vector->size))
767 {
768 for (ZyanUSize i = size; i < vector->size; ++i)
769 {
770 vector->destructor(ZYCORE_VECTOR_OFFSET(vector, i));
771 }
772 }
773
774 if (ZYCORE_VECTOR_SHOULD_GROW(size, vector->capacity) ||
775 ZYCORE_VECTOR_SHOULD_SHRINK(size, vector->capacity, vector->shrink_threshold))
776 {
777 ZYAN_CHECK(ZyanVectorReallocate(vector, (ZyanUSize)(size * vector->growth_factor)));
778 };
779
780 if (initializer && (size > vector->size))
781 {
782 for (ZyanUSize i = vector->size; i < size; ++i)
783 {
784 ZYAN_MEMCPY(ZYCORE_VECTOR_OFFSET(vector, i), initializer, vector->element_size);
785 }
786 }
787
788 vector->size = size;
789
790 return ZYAN_STATUS_SUCCESS;
791 }
792
ZyanVectorReserve(ZyanVector * vector,ZyanUSize capacity)793 ZyanStatus ZyanVectorReserve(ZyanVector* vector, ZyanUSize capacity)
794 {
795 if (!vector)
796 {
797 return ZYAN_STATUS_INVALID_ARGUMENT;
798 }
799
800 if (capacity > vector->capacity)
801 {
802 ZYAN_CHECK(ZyanVectorReallocate(vector, capacity));
803 }
804
805 return ZYAN_STATUS_SUCCESS;
806 }
807
ZyanVectorShrinkToFit(ZyanVector * vector)808 ZyanStatus ZyanVectorShrinkToFit(ZyanVector* vector)
809 {
810 if (!vector)
811 {
812 return ZYAN_STATUS_INVALID_ARGUMENT;
813 }
814
815 return ZyanVectorReallocate(vector, vector->size);
816 }
817
818 /* ---------------------------------------------------------------------------------------------- */
819 /* Information */
820 /* ---------------------------------------------------------------------------------------------- */
821
ZyanVectorGetCapacity(const ZyanVector * vector,ZyanUSize * capacity)822 ZyanStatus ZyanVectorGetCapacity(const ZyanVector* vector, ZyanUSize* capacity)
823 {
824 if (!vector)
825 {
826 return ZYAN_STATUS_INVALID_ARGUMENT;
827 }
828
829 *capacity = vector->capacity;
830
831 return ZYAN_STATUS_SUCCESS;
832 }
833
ZyanVectorGetSize(const ZyanVector * vector,ZyanUSize * size)834 ZyanStatus ZyanVectorGetSize(const ZyanVector* vector, ZyanUSize* size)
835 {
836 if (!vector)
837 {
838 return ZYAN_STATUS_INVALID_ARGUMENT;
839 }
840
841 *size = vector->size;
842
843 return ZYAN_STATUS_SUCCESS;
844 }
845
846 /* ---------------------------------------------------------------------------------------------- */
847
848 /* ============================================================================================== */
849