Line data    Source code

       1             : /*
       2             : The MIT License(MIT)
       3             : Copyright(c) 2016 Peter Goldsborough
       4             : 
       5             : Permission is hereby granted, free of charge, to any person obtaining a copy of
       6             : this software and associated documentation files(the "Software"), to deal in
       7             : the Software without restriction, including without limitation the rights to
       8             : use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
       9             : the Software, and to permit persons to whom the Software is furnished to do so,
      10             : subject to the following conditions :
      11             : 
      12             : The above copyright notice and this permission notice shall be included in all
      13             : copies or substantial portions of the Software.
      14             : 
      15             : THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
      16             : IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS
      17             : FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.IN NO EVENT SHALL THE AUTHORS OR
      18             : COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER
      19             : IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
      20             : CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
      21             : */
      22             : 
      23             : #define __STDC_WANT_LIB_EXT1__ 1
      24             : 
      25             : #include <assert.h>
      26             : #include <stdlib.h>
      27             : #include <string.h>
      28             : 
      29             : #include "vector.h"
      30             : #define MAX(a, b) ((a) > (b) ? (a) : (b))
      31           0 : int eb_aom_vector_setup(Vector *vector, size_t capacity, size_t element_size) {
      32           0 :   assert(vector != NULL);
      33             : 
      34           0 :   if (vector == NULL) return VECTOR_ERROR;
      35             : 
      36           0 :   vector->size = 0;
      37           0 :   vector->capacity = MAX(VECTOR_MINIMUM_CAPACITY, capacity);
      38           0 :   vector->element_size = element_size;
      39           0 :   vector->data = malloc(vector->capacity * element_size);
      40             : 
      41           0 :   return vector->data == NULL ? VECTOR_ERROR : VECTOR_SUCCESS;
      42             : }
      43             : 
      44           0 : int eb_aom_vector_copy(Vector *destination, Vector *source) {
      45           0 :   assert(destination != NULL);
      46           0 :   assert(source != NULL);
      47           0 :   assert(eb_aom_vector_is_initialized(source));
      48           0 :   assert(!eb_aom_vector_is_initialized(destination));
      49             : 
      50           0 :   if (destination == NULL) return VECTOR_ERROR;
      51           0 :   if (source == NULL) return VECTOR_ERROR;
      52           0 :   if (eb_aom_vector_is_initialized(destination)) return VECTOR_ERROR;
      53           0 :   if (!eb_aom_vector_is_initialized(source)) return VECTOR_ERROR;
      54             : 
      55             :   /* Copy ALL the data */
      56           0 :   destination->size = source->size;
      57           0 :   destination->capacity = source->size * 2;
      58           0 :   destination->element_size = source->element_size;
      59             : 
      60             :   /* Note that we are not necessarily allocating the same capacity */
      61           0 :   destination->data = malloc(destination->capacity * source->element_size);
      62           0 :   if (destination->data == NULL) return VECTOR_ERROR;
      63             : 
      64           0 :   memcpy(destination->data, source->data, eb_aom_vector_byte_size(source));
      65             : 
      66           0 :   return VECTOR_SUCCESS;
      67             : }
      68             : 
      69           0 : int eb_aom_vector_copy_assign(Vector *destination, Vector *source) {
      70           0 :   assert(destination != NULL);
      71           0 :   assert(source != NULL);
      72           0 :   assert(eb_aom_vector_is_initialized(source));
      73           0 :   assert(eb_aom_vector_is_initialized(destination));
      74             : 
      75           0 :   if (destination == NULL) return VECTOR_ERROR;
      76           0 :   if (source == NULL) return VECTOR_ERROR;
      77           0 :   if (!eb_aom_vector_is_initialized(destination)) return VECTOR_ERROR;
      78           0 :   if (!eb_aom_vector_is_initialized(source)) return VECTOR_ERROR;
      79             : 
      80           0 :   eb_aom_vector_destroy(destination);
      81             : 
      82           0 :   return eb_aom_vector_copy(destination, source);
      83             : }
      84             : 
      85           0 : int eb_aom_vector_move(Vector *destination, Vector *source) {
      86           0 :   assert(destination != NULL);
      87           0 :   assert(source != NULL);
      88             : 
      89           0 :   if (destination == NULL) return VECTOR_ERROR;
      90           0 :   if (source == NULL) return VECTOR_ERROR;
      91             : 
      92           0 :   *destination = *source;
      93           0 :   source->data = NULL;
      94             : 
      95           0 :   return VECTOR_SUCCESS;
      96             : }
      97             : 
      98           0 : int eb_aom_vector_move_assign(Vector *destination, Vector *source) {
      99           0 :   eb_aom_vector_swap(destination, source);
     100           0 :   return eb_aom_vector_destroy(source);
     101             : }
     102             : 
     103           0 : int eb_aom_vector_swap(Vector *destination, Vector *source) {
     104             :   void *temp;
     105             : 
     106           0 :   assert(destination != NULL);
     107           0 :   assert(source != NULL);
     108           0 :   assert(eb_aom_vector_is_initialized(source));
     109           0 :   assert(eb_aom_vector_is_initialized(destination));
     110             : 
     111           0 :   if (destination == NULL) return VECTOR_ERROR;
     112           0 :   if (source == NULL) return VECTOR_ERROR;
     113           0 :   if (!eb_aom_vector_is_initialized(destination)) return VECTOR_ERROR;
     114           0 :   if (!eb_aom_vector_is_initialized(source)) return VECTOR_ERROR;
     115             : 
     116           0 :   _vector_swap(&destination->size, &source->size);
     117           0 :   _vector_swap(&destination->capacity, &source->capacity);
     118           0 :   _vector_swap(&destination->element_size, &source->element_size);
     119             : 
     120           0 :   temp = destination->data;
     121           0 :   destination->data = source->data;
     122           0 :   source->data = temp;
     123             : 
     124           0 :   return VECTOR_SUCCESS;
     125             : }
     126             : 
     127           0 : int eb_aom_vector_destroy(Vector *vector) {
     128           0 :   assert(vector != NULL);
     129             : 
     130           0 :   if (vector == NULL) return VECTOR_ERROR;
     131             : 
     132           0 :   free(vector->data);
     133           0 :   vector->data = NULL;
     134             : 
     135           0 :   return VECTOR_SUCCESS;
     136             : }
     137             : 
     138             : /* Insertion */
     139           0 : int eb_aom_vector_push_back(Vector *vector, void *element) {
     140           0 :   assert(vector != NULL);
     141           0 :   assert(element != NULL);
     142             : 
     143           0 :   if (_vector_should_grow(vector)) {
     144           0 :     if (_vector_adjust_capacity(vector) == VECTOR_ERROR)
     145           0 :       return VECTOR_ERROR;
     146             :   }
     147             : 
     148           0 :   _vector_assign(vector, vector->size, element);
     149             : 
     150           0 :   ++vector->size;
     151             : 
     152           0 :   return VECTOR_SUCCESS;
     153             : }
     154             : 
     155           0 : int eb_aom_vector_push_front(Vector *vector, void *element) {
     156           0 :   return eb_aom_vector_insert(vector, 0, element);
     157             : }
     158             : 
     159           0 : int eb_aom_vector_insert(Vector *vector, size_t index, void *element) {
     160             :   void *offset;
     161             : 
     162           0 :   assert(vector != NULL);
     163           0 :   assert(element != NULL);
     164           0 :   assert(index <= vector->size);
     165             : 
     166           0 :   if (vector == NULL) return VECTOR_ERROR;
     167           0 :   if (element == NULL) return VECTOR_ERROR;
     168           0 :   if (vector->element_size == 0) return VECTOR_ERROR;
     169           0 :   if (index > vector->size) return VECTOR_ERROR;
     170             : 
     171           0 :   if (_vector_should_grow(vector)) {
     172           0 :     if (_vector_adjust_capacity(vector) == VECTOR_ERROR)
     173           0 :       return VECTOR_ERROR;
     174             :   }
     175             : 
     176             :   /* Move other elements to the right */
     177           0 :   if (_vector_move_right(vector, index) == VECTOR_ERROR)
     178           0 :     return VECTOR_ERROR;
     179             :   /* Insert the element */
     180           0 :   offset = _vector_offset(vector, index);
     181           0 :   memcpy(offset, element, vector->element_size);
     182           0 :   ++vector->size;
     183             : 
     184           0 :   return VECTOR_SUCCESS;
     185             : }
     186             : 
     187           0 : int eb_aom_vector_assign(Vector *vector, size_t index, void *element) {
     188           0 :   assert(vector != NULL);
     189           0 :   assert(element != NULL);
     190           0 :   assert(index < vector->size);
     191             : 
     192           0 :   if (vector == NULL) return VECTOR_ERROR;
     193           0 :   if (element == NULL) return VECTOR_ERROR;
     194           0 :   if (vector->element_size == 0) return VECTOR_ERROR;
     195           0 :   if (index >= vector->size) return VECTOR_ERROR;
     196             : 
     197           0 :   _vector_assign(vector, index, element);
     198             : 
     199           0 :   return VECTOR_SUCCESS;
     200             : }
     201             : 
     202             : /* Deletion */
     203           0 : int eb_aom_vector_pop_back(Vector *vector) {
     204           0 :   assert(vector != NULL);
     205           0 :   assert(vector->size > 0);
     206             : 
     207           0 :   if (vector == NULL) return VECTOR_ERROR;
     208           0 :   if (vector->element_size == 0) return VECTOR_ERROR;
     209             : 
     210           0 :   --vector->size;
     211             : 
     212             : #ifndef VECTOR_NO_SHRINK
     213           0 :   if (_vector_should_shrink(vector))
     214           0 :     _vector_adjust_capacity(vector);
     215             : #endif
     216             : 
     217           0 :   return VECTOR_SUCCESS;
     218             : }
     219             : 
     220           0 : int eb_aom_vector_pop_front(Vector *vector) { return eb_aom_vector_erase(vector, 0); }
     221             : 
     222           0 : int eb_aom_vector_erase(Vector *vector, size_t index) {
     223           0 :   assert(vector != NULL);
     224           0 :   assert(index < vector->size);
     225             : 
     226           0 :   if (vector == NULL) return VECTOR_ERROR;
     227           0 :   if (vector->element_size == 0) return VECTOR_ERROR;
     228           0 :   if (index >= vector->size) return VECTOR_ERROR;
     229             : 
     230             :   /* Just overwrite */
     231           0 :   _vector_move_left(vector, index);
     232             : 
     233             : #ifndef VECTOR_NO_SHRINK
     234           0 :   if (--vector->size == vector->capacity / 4)
     235           0 :     _vector_adjust_capacity(vector);
     236             : #endif
     237             : 
     238           0 :   return VECTOR_SUCCESS;
     239             : }
     240             : 
     241           0 : int eb_aom_vector_clear(Vector *vector) { return eb_aom_vector_resize(vector, 0); }
     242             : 
     243             : /* Lookup */
     244           0 : void *eb_aom_vector_get(Vector *vector, size_t index) {
     245           0 :   assert(vector != NULL);
     246           0 :   assert(index < vector->size);
     247             : 
     248           0 :   if (vector == NULL) return NULL;
     249           0 :   if (vector->element_size == 0) return NULL;
     250           0 :   if (index >= vector->size) return NULL;
     251             : 
     252           0 :   return _vector_offset(vector, index);
     253             : }
     254             : 
     255           0 : const void *eb_aom_vector_const_get(const Vector *vector, size_t index) {
     256           0 :   assert(vector != NULL);
     257           0 :   assert(index < vector->size);
     258             : 
     259           0 :   if (vector == NULL) return NULL;
     260           0 :   if (vector->element_size == 0) return NULL;
     261           0 :   if (index >= vector->size) return NULL;
     262             : 
     263           0 :   return _vector_const_offset(vector, index);
     264             : }
     265             : 
     266           0 : void *eb_aom_vector_front(Vector *vector) { return eb_aom_vector_get(vector, 0); }
     267             : 
     268           0 : void *eb_aom_vector_back(Vector *vector) {
     269           0 :   return eb_aom_vector_get(vector, vector->size - 1);
     270             : }
     271             : 
     272             : /* Information */
     273             : 
     274           0 : bool eb_aom_vector_is_initialized(const Vector *vector) {
     275           0 :   return vector->data != NULL;
     276             : }
     277             : 
     278           0 : size_t eb_aom_vector_byte_size(const Vector *vector) {
     279           0 :   return vector->size * vector->element_size;
     280             : }
     281             : 
     282           0 : size_t eb_aom_vector_free_space(const Vector *vector) {
     283           0 :   return vector->capacity - vector->size;
     284             : }
     285             : 
     286           0 : bool eb_aom_vector_is_empty(const Vector *vector) { return vector->size == 0; }
     287             : 
     288             : /* Memory management */
     289           0 : int eb_aom_vector_resize(Vector *vector, size_t new_size) {
     290           0 :   if (new_size <= vector->capacity * VECTOR_SHRINK_THRESHOLD) {
     291           0 :     vector->size = new_size;
     292           0 :     if (_vector_reallocate(vector, new_size * VECTOR_GROWTH_FACTOR) == -1)
     293           0 :       return VECTOR_ERROR;
     294           0 :   } else if (new_size > vector->capacity) {
     295           0 :     if (_vector_reallocate(vector, new_size * VECTOR_GROWTH_FACTOR) == -1)
     296           0 :       return VECTOR_ERROR;
     297             :   }
     298             : 
     299           0 :   vector->size = new_size;
     300             : 
     301           0 :   return VECTOR_SUCCESS;
     302             : }
     303             : 
     304           0 : int eb_aom_vector_reserve(Vector *vector, size_t minimum_capacity) {
     305           0 :   if (minimum_capacity > vector->capacity) {
     306           0 :     if (_vector_reallocate(vector, minimum_capacity) == VECTOR_ERROR)
     307           0 :       return VECTOR_ERROR;
     308             :   }
     309             : 
     310           0 :   return VECTOR_SUCCESS;
     311             : }
     312             : 
     313           0 : int eb_aom_vector_shrink_to_fit(Vector *vector) {
     314           0 :   return _vector_reallocate(vector, vector->size);
     315             : }
     316             : 
     317             : /* Iterators */
     318           0 : Iterator eb_aom_vector_begin(Vector *vector) { return eb_aom_vector_iterator(vector, 0); }
     319             : 
     320           0 : Iterator eb_aom_vector_end(Vector *vector) {
     321           0 :   return eb_aom_vector_iterator(vector, vector->size);
     322             : }
     323             : 
     324           0 : Iterator eb_aom_vector_iterator(Vector *vector, size_t index) {
     325           0 :   Iterator iterator = { NULL, 0 };
     326             : 
     327           0 :   assert(vector != NULL);
     328           0 :   assert(index <= vector->size);
     329             : 
     330           0 :   if (vector == NULL) return iterator;
     331           0 :   if (index > vector->size) return iterator;
     332           0 :   if (vector->element_size == 0) return iterator;
     333             : 
     334           0 :   iterator.pointer = _vector_offset(vector, index);
     335           0 :   iterator.element_size = vector->element_size;
     336             : 
     337           0 :   return iterator;
     338             : }
     339             : 
     340           0 : void *iterator_get(Iterator *iterator) { return iterator->pointer; }
     341             : 
     342           0 : int iterator_erase(Vector *vector, Iterator *iterator) {
     343           0 :   size_t index = iterator_index(vector, iterator);
     344             : 
     345           0 :   if (eb_aom_vector_erase(vector, index) == VECTOR_ERROR)
     346           0 :     return VECTOR_ERROR;
     347           0 :   *iterator = eb_aom_vector_iterator(vector, index);
     348             : 
     349           0 :   return VECTOR_SUCCESS;
     350             : }
     351             : 
     352           0 : void iterator_increment(Iterator *iterator) {
     353           0 :   assert(iterator != NULL);
     354             :   // iterator->pointer += iterator->element_size;
     355           0 :   iterator->pointer =
     356           0 :       (unsigned char *)iterator->pointer + iterator->element_size;
     357           0 : }
     358             : 
     359           0 : void iterator_decrement(Iterator *iterator) {
     360           0 :   assert(iterator != NULL);
     361             :   // iterator->pointer -= iterator->element_size;
     362           0 :   iterator->pointer =
     363           0 :       (unsigned char *)iterator->pointer - iterator->element_size;
     364           0 : }
     365             : 
     366           0 : void *iterator_next(Iterator *iterator) {
     367           0 :   void *current = iterator->pointer;
     368           0 :   iterator_increment(iterator);
     369             : 
     370           0 :   return current;
     371             : }
     372             : 
     373           0 : void *iterator_previous(Iterator *iterator) {
     374           0 :   void *current = iterator->pointer;
     375           0 :   iterator_decrement(iterator);
     376             : 
     377           0 :   return current;
     378             : }
     379             : 
     380           0 : bool iterator_equals(Iterator *first, Iterator *second) {
     381           0 :   assert(first->element_size == second->element_size);
     382           0 :   return first->pointer == second->pointer;
     383             : }
     384             : 
     385           0 : bool iterator_is_before(Iterator *first, Iterator *second) {
     386           0 :   assert(first->element_size == second->element_size);
     387           0 :   return first->pointer < second->pointer;
     388             : }
     389             : 
     390           0 : bool iterator_is_after(Iterator *first, Iterator *second) {
     391           0 :   assert(first->element_size == second->element_size);
     392           0 :   return first->pointer > second->pointer;
     393             : }
     394             : 
     395           0 : size_t iterator_index(Vector *vector, Iterator *iterator) {
     396           0 :   assert(vector != NULL);
     397           0 :   assert(iterator != NULL);
     398             :   // return (iterator->pointer - vector->data) / vector->element_size;
     399           0 :   return ((unsigned char *)iterator->pointer - (unsigned char *)vector->data) /
     400           0 :          vector->element_size;
     401             : }
     402             : 
     403             : /***** PRIVATE *****/
     404             : 
     405           0 : bool _vector_should_grow(Vector *vector) {
     406           0 :   assert(vector->size <= vector->capacity);
     407           0 :   return vector->size == vector->capacity;
     408             : }
     409             : 
     410           0 : bool _vector_should_shrink(Vector *vector) {
     411           0 :   assert(vector->size <= vector->capacity);
     412           0 :   return vector->size == vector->capacity * VECTOR_SHRINK_THRESHOLD;
     413             : }
     414             : 
     415           0 : size_t _vector_free_bytes(const Vector *vector) {
     416           0 :   return eb_aom_vector_free_space(vector) * vector->element_size;
     417             : }
     418             : 
     419           0 : void *_vector_offset(Vector *vector, size_t index) {
     420             :   // return vector->data + (index * vector->element_size);
     421           0 :   return (unsigned char *)vector->data + (index * vector->element_size);
     422             : }
     423             : 
     424           0 : const void *_vector_const_offset(const Vector *vector, size_t index) {
     425             :   // return vector->data + (index * vector->element_size);
     426           0 :   return (unsigned char *)vector->data + (index * vector->element_size);
     427             : }
     428             : 
     429           0 : void _vector_assign(Vector *vector, size_t index, void *element) {
     430             :   /* Insert the element */
     431           0 :   void *offset = _vector_offset(vector, index);
     432           0 :   memcpy(offset, element, vector->element_size);
     433           0 : }
     434             : 
     435           0 : int _vector_move_right(Vector *vector, size_t index) {
     436           0 :   assert(vector->size < vector->capacity);
     437             : 
     438             :   /* The location where to start to move from. */
     439           0 :   void *offset = _vector_offset(vector, index);
     440             : 
     441             :   /* How many to move to the right. */
     442           0 :   size_t elements_in_bytes = (vector->size - index) * vector->element_size;
     443             : 
     444             : #ifdef __STDC_LIB_EXT1__
     445             :   size_t right_capacity_in_bytes =
     446             :       (vector->capacity - (index + 1)) * vector->element_size;
     447             : 
     448             :   /* clang-format off */
     449             :     int return_code =  memmove_s(
     450             :         offset + vector->element_size,
     451             :         right_capacity_in_bytes,
     452             :         offset,
     453             :         elements_in_bytes);
     454             : 
     455             :   /* clang-format on */
     456             : 
     457             :   return return_code == 0 ? VECTOR_SUCCESS : VECTOR_ERROR;
     458             : 
     459             : #else
     460             :   // memmove(offset + vector->element_size, offset, elements_in_bytes);
     461           0 :   memmove((unsigned char *)offset + vector->element_size, offset,
     462             :           elements_in_bytes);
     463           0 :   return VECTOR_SUCCESS;
     464             : #endif
     465             : }
     466             : 
     467           0 : void _vector_move_left(Vector *vector, size_t index) {
     468             :   size_t right_elements_in_bytes;
     469             :   void *offset;
     470             : 
     471             :   /* The offset into the memory */
     472           0 :   offset = _vector_offset(vector, index);
     473             : 
     474             :   /* How many to move to the left */
     475           0 :   right_elements_in_bytes = (vector->size - index - 1) * vector->element_size;
     476             : 
     477             :   // memmove(offset, offset + vector->element_size, right_elements_in_bytes);
     478           0 :   memmove(offset, (unsigned char *)offset + vector->element_size,
     479             :           right_elements_in_bytes);
     480           0 : }
     481             : 
     482           0 : int _vector_adjust_capacity(Vector *vector) {
     483           0 :   return _vector_reallocate(vector,
     484           0 :                             MAX(1, vector->size * VECTOR_GROWTH_FACTOR));
     485             : }
     486             : 
     487           0 : int _vector_reallocate(Vector *vector, size_t new_capacity) {
     488             :   size_t new_capacity_in_bytes;
     489             :   void *old;
     490           0 :   assert(vector != NULL);
     491             : 
     492           0 :   if (new_capacity < VECTOR_MINIMUM_CAPACITY) {
     493           0 :     if (vector->capacity > VECTOR_MINIMUM_CAPACITY) {
     494           0 :       new_capacity = VECTOR_MINIMUM_CAPACITY;
     495             :     } else {
     496             :       /* NO-OP */
     497           0 :       return VECTOR_SUCCESS;
     498             :     }
     499             :   }
     500             : 
     501           0 :   new_capacity_in_bytes = new_capacity * vector->element_size;
     502           0 :   old = vector->data;
     503             : 
     504           0 :   if ((vector->data = malloc(new_capacity_in_bytes)) == NULL)
     505           0 :     return VECTOR_ERROR;
     506             : #ifdef __STDC_LIB_EXT1__
     507             :   /* clang-format off */
     508             :     if (memcpy_s(vector->data,
     509             :                              new_capacity_in_bytes,
     510             :                              old,
     511             :                              eb_aom_vector_byte_size(vector)) != 0) {
     512             :         return VECTOR_ERROR;
     513             :     }
     514             : /* clang-format on */
     515             : #else
     516           0 :   memcpy(vector->data, old, eb_aom_vector_byte_size(vector));
     517             : #endif
     518             : 
     519           0 :   vector->capacity = new_capacity;
     520             : 
     521           0 :   free(old);
     522             : 
     523           0 :   return VECTOR_SUCCESS;
     524             : }
     525             : 
     526           0 : void _vector_swap(size_t *first, size_t *second) {
     527           0 :   size_t temp = *first;
     528           0 :   *first = *second;
     529           0 :   *second = temp;
     530           0 : }