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  /* ============================================================================================== */