Home | History | Annotate | Download | only in vector 
      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 "third_party/vector/vector.h"
     30 
     31 int aom_vector_setup(Vector *vector, size_t capacity, size_t element_size) {
     32   assert(vector != NULL);
     33 
     34   if (vector == NULL) return VECTOR_ERROR;
     35 
     36   vector->size = 0;
     37   vector->capacity = MAX(VECTOR_MINIMUM_CAPACITY, capacity);
     38   vector->element_size = element_size;
     39   vector->data = malloc(vector->capacity * element_size);
     40 
     41   return vector->data == NULL ? VECTOR_ERROR : VECTOR_SUCCESS;
     42 }
     43 
     44 int aom_vector_copy(Vector *destination, Vector *source) {
     45   assert(destination != NULL);
     46   assert(source != NULL);
     47   assert(aom_vector_is_initialized(source));
     48   assert(!aom_vector_is_initialized(destination));
     49 
     50   if (destination == NULL) return VECTOR_ERROR;
     51   if (source == NULL) return VECTOR_ERROR;
     52   if (aom_vector_is_initialized(destination)) return VECTOR_ERROR;
     53   if (!aom_vector_is_initialized(source)) return VECTOR_ERROR;
     54 
     55   /* Copy ALL the data */
     56   destination->size = source->size;
     57   destination->capacity = source->size * 2;
     58   destination->element_size = source->element_size;
     59 
     60   /* Note that we are not necessarily allocating the same capacity */
     61   destination->data = malloc(destination->capacity * source->element_size);
     62   if (destination->data == NULL) return VECTOR_ERROR;
     63 
     64   memcpy(destination->data, source->data, aom_vector_byte_size(source));
     65 
     66   return VECTOR_SUCCESS;
     67 }
     68 
     69 int aom_vector_copy_assign(Vector *destination, Vector *source) {
     70   assert(destination != NULL);
     71   assert(source != NULL);
     72   assert(aom_vector_is_initialized(source));
     73   assert(aom_vector_is_initialized(destination));
     74 
     75   if (destination == NULL) return VECTOR_ERROR;
     76   if (source == NULL) return VECTOR_ERROR;
     77   if (!aom_vector_is_initialized(destination)) return VECTOR_ERROR;
     78   if (!aom_vector_is_initialized(source)) return VECTOR_ERROR;
     79 
     80   aom_vector_destroy(destination);
     81 
     82   return aom_vector_copy(destination, source);
     83 }
     84 
     85 int aom_vector_move(Vector *destination, Vector *source) {
     86   assert(destination != NULL);
     87   assert(source != NULL);
     88 
     89   if (destination == NULL) return VECTOR_ERROR;
     90   if (source == NULL) return VECTOR_ERROR;
     91 
     92   *destination = *source;
     93   source->data = NULL;
     94 
     95   return VECTOR_SUCCESS;
     96 }
     97 
     98 int aom_vector_move_assign(Vector *destination, Vector *source) {
     99   aom_vector_swap(destination, source);
    100   return aom_vector_destroy(source);
    101 }
    102 
    103 int aom_vector_swap(Vector *destination, Vector *source) {
    104   void *temp;
    105 
    106   assert(destination != NULL);
    107   assert(source != NULL);
    108   assert(aom_vector_is_initialized(source));
    109   assert(aom_vector_is_initialized(destination));
    110 
    111   if (destination == NULL) return VECTOR_ERROR;
    112   if (source == NULL) return VECTOR_ERROR;
    113   if (!aom_vector_is_initialized(destination)) return VECTOR_ERROR;
    114   if (!aom_vector_is_initialized(source)) return VECTOR_ERROR;
    115 
    116   _vector_swap(&destination->size, &source->size);
    117   _vector_swap(&destination->capacity, &source->capacity);
    118   _vector_swap(&destination->element_size, &source->element_size);
    119 
    120   temp = destination->data;
    121   destination->data = source->data;
    122   source->data = temp;
    123 
    124   return VECTOR_SUCCESS;
    125 }
    126 
    127 int aom_vector_destroy(Vector *vector) {
    128   assert(vector != NULL);
    129 
    130   if (vector == NULL) return VECTOR_ERROR;
    131 
    132   free(vector->data);
    133   vector->data = NULL;
    134 
    135   return VECTOR_SUCCESS;
    136 }
    137 
    138 /* Insertion */
    139 int aom_vector_push_back(Vector *vector, void *element) {
    140   assert(vector != NULL);
    141   assert(element != NULL);
    142 
    143   if (_vector_should_grow(vector)) {
    144     if (_vector_adjust_capacity(vector) == VECTOR_ERROR) {
    145       return VECTOR_ERROR;
    146     }
    147   }
    148 
    149   _vector_assign(vector, vector->size, element);
    150 
    151   ++vector->size;
    152 
    153   return VECTOR_SUCCESS;
    154 }
    155 
    156 int aom_vector_push_front(Vector *vector, void *element) {
    157   return aom_vector_insert(vector, 0, element);
    158 }
    159 
    160 int aom_vector_insert(Vector *vector, size_t index, void *element) {
    161   void *offset;
    162 
    163   assert(vector != NULL);
    164   assert(element != NULL);
    165   assert(index <= vector->size);
    166 
    167   if (vector == NULL) return VECTOR_ERROR;
    168   if (element == NULL) return VECTOR_ERROR;
    169   if (vector->element_size == 0) return VECTOR_ERROR;
    170   if (index > vector->size) return VECTOR_ERROR;
    171 
    172   if (_vector_should_grow(vector)) {
    173     if (_vector_adjust_capacity(vector) == VECTOR_ERROR) {
    174       return VECTOR_ERROR;
    175     }
    176   }
    177 
    178   /* Move other elements to the right */
    179   if (_vector_move_right(vector, index) == VECTOR_ERROR) {
    180     return VECTOR_ERROR;
    181   }
    182 
    183   /* Insert the element */
    184   offset = _vector_offset(vector, index);
    185   memcpy(offset, element, vector->element_size);
    186   ++vector->size;
    187 
    188   return VECTOR_SUCCESS;
    189 }
    190 
    191 int aom_vector_assign(Vector *vector, size_t index, void *element) {
    192   assert(vector != NULL);
    193   assert(element != NULL);
    194   assert(index < vector->size);
    195 
    196   if (vector == NULL) return VECTOR_ERROR;
    197   if (element == NULL) return VECTOR_ERROR;
    198   if (vector->element_size == 0) return VECTOR_ERROR;
    199   if (index >= vector->size) return VECTOR_ERROR;
    200 
    201   _vector_assign(vector, index, element);
    202 
    203   return VECTOR_SUCCESS;
    204 }
    205 
    206 /* Deletion */
    207 int aom_vector_pop_back(Vector *vector) {
    208   assert(vector != NULL);
    209   assert(vector->size > 0);
    210 
    211   if (vector == NULL) return VECTOR_ERROR;
    212   if (vector->element_size == 0) return VECTOR_ERROR;
    213 
    214   --vector->size;
    215 
    216 #ifndef VECTOR_NO_SHRINK
    217   if (_vector_should_shrink(vector)) {
    218     _vector_adjust_capacity(vector);
    219   }
    220 #endif
    221 
    222   return VECTOR_SUCCESS;
    223 }
    224 
    225 int aom_vector_pop_front(Vector *vector) { return aom_vector_erase(vector, 0); }
    226 
    227 int aom_vector_erase(Vector *vector, size_t index) {
    228   assert(vector != NULL);
    229   assert(index < vector->size);
    230 
    231   if (vector == NULL) return VECTOR_ERROR;
    232   if (vector->element_size == 0) return VECTOR_ERROR;
    233   if (index >= vector->size) return VECTOR_ERROR;
    234 
    235   /* Just overwrite */
    236   _vector_move_left(vector, index);
    237 
    238 #ifndef VECTOR_NO_SHRINK
    239   if (--vector->size == vector->capacity / 4) {
    240     _vector_adjust_capacity(vector);
    241   }
    242 #endif
    243 
    244   return VECTOR_SUCCESS;
    245 }
    246 
    247 int aom_vector_clear(Vector *vector) { return aom_vector_resize(vector, 0); }
    248 
    249 /* Lookup */
    250 void *aom_vector_get(Vector *vector, size_t index) {
    251   assert(vector != NULL);
    252   assert(index < vector->size);
    253 
    254   if (vector == NULL) return NULL;
    255   if (vector->element_size == 0) return NULL;
    256   if (index >= vector->size) return NULL;
    257 
    258   return _vector_offset(vector, index);
    259 }
    260 
    261 const void *aom_vector_const_get(const Vector *vector, size_t index) {
    262   assert(vector != NULL);
    263   assert(index < vector->size);
    264 
    265   if (vector == NULL) return NULL;
    266   if (vector->element_size == 0) return NULL;
    267   if (index >= vector->size) return NULL;
    268 
    269   return _vector_const_offset(vector, index);
    270 }
    271 
    272 void *aom_vector_front(Vector *vector) { return aom_vector_get(vector, 0); }
    273 
    274 void *aom_vector_back(Vector *vector) {
    275   return aom_vector_get(vector, vector->size - 1);
    276 }
    277 
    278 /* Information */
    279 
    280 bool aom_vector_is_initialized(const Vector *vector) {
    281   return vector->data != NULL;
    282 }
    283 
    284 size_t aom_vector_byte_size(const Vector *vector) {
    285   return vector->size * vector->element_size;
    286 }
    287 
    288 size_t aom_vector_free_space(const Vector *vector) {
    289   return vector->capacity - vector->size;
    290 }
    291 
    292 bool aom_vector_is_empty(const Vector *vector) { return vector->size == 0; }
    293 
    294 /* Memory management */
    295 int aom_vector_resize(Vector *vector, size_t new_size) {
    296   if (new_size <= vector->capacity * VECTOR_SHRINK_THRESHOLD) {
    297     vector->size = new_size;
    298     if (_vector_reallocate(vector, new_size * VECTOR_GROWTH_FACTOR) == -1) {
    299       return VECTOR_ERROR;
    300     }
    301   } else if (new_size > vector->capacity) {
    302     if (_vector_reallocate(vector, new_size * VECTOR_GROWTH_FACTOR) == -1) {
    303       return VECTOR_ERROR;
    304     }
    305   }
    306 
    307   vector->size = new_size;
    308 
    309   return VECTOR_SUCCESS;
    310 }
    311 
    312 int aom_vector_reserve(Vector *vector, size_t minimum_capacity) {
    313   if (minimum_capacity > vector->capacity) {
    314     if (_vector_reallocate(vector, minimum_capacity) == VECTOR_ERROR) {
    315       return VECTOR_ERROR;
    316     }
    317   }
    318 
    319   return VECTOR_SUCCESS;
    320 }
    321 
    322 int aom_vector_shrink_to_fit(Vector *vector) {
    323   return _vector_reallocate(vector, vector->size);
    324 }
    325 
    326 /* Iterators */
    327 Iterator aom_vector_begin(Vector *vector) { return aom_vector_iterator(vector, 0); }
    328 
    329 Iterator aom_vector_end(Vector *vector) {
    330   return aom_vector_iterator(vector, vector->size);
    331 }
    332 
    333 Iterator aom_vector_iterator(Vector *vector, size_t index) {
    334   Iterator iterator = { NULL, 0 };
    335 
    336   assert(vector != NULL);
    337   assert(index <= vector->size);
    338 
    339   if (vector == NULL) return iterator;
    340   if (index > vector->size) return iterator;
    341   if (vector->element_size == 0) return iterator;
    342 
    343   iterator.pointer = _vector_offset(vector, index);
    344   iterator.element_size = vector->element_size;
    345 
    346   return iterator;
    347 }
    348 
    349 void *iterator_get(Iterator *iterator) { return iterator->pointer; }
    350 
    351 int iterator_erase(Vector *vector, Iterator *iterator) {
    352   size_t index = iterator_index(vector, iterator);
    353 
    354   if (aom_vector_erase(vector, index) == VECTOR_ERROR) {
    355     return VECTOR_ERROR;
    356   }
    357 
    358   *iterator = aom_vector_iterator(vector, index);
    359 
    360   return VECTOR_SUCCESS;
    361 }
    362 
    363 void iterator_increment(Iterator *iterator) {
    364   assert(iterator != NULL);
    365   // iterator->pointer += iterator->element_size;
    366   iterator->pointer =
    367       (unsigned char *)iterator->pointer + iterator->element_size;
    368 }
    369 
    370 void iterator_decrement(Iterator *iterator) {
    371   assert(iterator != NULL);
    372   // iterator->pointer -= iterator->element_size;
    373   iterator->pointer =
    374       (unsigned char *)iterator->pointer - iterator->element_size;
    375 }
    376 
    377 void *iterator_next(Iterator *iterator) {
    378   void *current = iterator->pointer;
    379   iterator_increment(iterator);
    380 
    381   return current;
    382 }
    383 
    384 void *iterator_previous(Iterator *iterator) {
    385   void *current = iterator->pointer;
    386   iterator_decrement(iterator);
    387 
    388   return current;
    389 }
    390 
    391 bool iterator_equals(Iterator *first, Iterator *second) {
    392   assert(first->element_size == second->element_size);
    393   return first->pointer == second->pointer;
    394 }
    395 
    396 bool iterator_is_before(Iterator *first, Iterator *second) {
    397   assert(first->element_size == second->element_size);
    398   return first->pointer < second->pointer;
    399 }
    400 
    401 bool iterator_is_after(Iterator *first, Iterator *second) {
    402   assert(first->element_size == second->element_size);
    403   return first->pointer > second->pointer;
    404 }
    405 
    406 size_t iterator_index(Vector *vector, Iterator *iterator) {
    407   assert(vector != NULL);
    408   assert(iterator != NULL);
    409   // return (iterator->pointer - vector->data) / vector->element_size;
    410   return ((unsigned char *)iterator->pointer - (unsigned char *)vector->data) /
    411          vector->element_size;
    412 }
    413 
    414 /***** PRIVATE *****/
    415 
    416 bool _vector_should_grow(Vector *vector) {
    417   assert(vector->size <= vector->capacity);
    418   return vector->size == vector->capacity;
    419 }
    420 
    421 bool _vector_should_shrink(Vector *vector) {
    422   assert(vector->size <= vector->capacity);
    423   return vector->size == vector->capacity * VECTOR_SHRINK_THRESHOLD;
    424 }
    425 
    426 size_t _vector_free_bytes(const Vector *vector) {
    427   return aom_vector_free_space(vector) * vector->element_size;
    428 }
    429 
    430 void *_vector_offset(Vector *vector, size_t index) {
    431   // return vector->data + (index * vector->element_size);
    432   return (unsigned char *)vector->data + (index * vector->element_size);
    433 }
    434 
    435 const void *_vector_const_offset(const Vector *vector, size_t index) {
    436   // return vector->data + (index * vector->element_size);
    437   return (unsigned char *)vector->data + (index * vector->element_size);
    438 }
    439 
    440 void _vector_assign(Vector *vector, size_t index, void *element) {
    441   /* Insert the element */
    442   void *offset = _vector_offset(vector, index);
    443   memcpy(offset, element, vector->element_size);
    444 }
    445 
    446 int _vector_move_right(Vector *vector, size_t index) {
    447   assert(vector->size < vector->capacity);
    448 
    449   /* The location where to start to move from. */
    450   void *offset = _vector_offset(vector, index);
    451 
    452   /* How many to move to the right. */
    453   size_t elements_in_bytes = (vector->size - index) * vector->element_size;
    454 
    455 #ifdef __STDC_LIB_EXT1__
    456   size_t right_capacity_in_bytes =
    457       (vector->capacity - (index + 1)) * vector->element_size;
    458 
    459   /* clang-format off */
    460     int return_code =  memmove_s(
    461         offset + vector->element_size,
    462         right_capacity_in_bytes,
    463         offset,
    464         elements_in_bytes);
    465 
    466   /* clang-format on */
    467 
    468   return return_code == 0 ? VECTOR_SUCCESS : VECTOR_ERROR;
    469 
    470 #else
    471   // memmove(offset + vector->element_size, offset, elements_in_bytes);
    472   memmove((unsigned char *)offset + vector->element_size, offset,
    473           elements_in_bytes);
    474   return VECTOR_SUCCESS;
    475 #endif
    476 }
    477 
    478 void _vector_move_left(Vector *vector, size_t index) {
    479   size_t right_elements_in_bytes;
    480   void *offset;
    481 
    482   /* The offset into the memory */
    483   offset = _vector_offset(vector, index);
    484 
    485   /* How many to move to the left */
    486   right_elements_in_bytes = (vector->size - index - 1) * vector->element_size;
    487 
    488   // memmove(offset, offset + vector->element_size, right_elements_in_bytes);
    489   memmove(offset, (unsigned char *)offset + vector->element_size,
    490           right_elements_in_bytes);
    491 }
    492 
    493 int _vector_adjust_capacity(Vector *vector) {
    494   return _vector_reallocate(vector,
    495                             MAX(1, vector->size * VECTOR_GROWTH_FACTOR));
    496 }
    497 
    498 int _vector_reallocate(Vector *vector, size_t new_capacity) {
    499   size_t new_capacity_in_bytes;
    500   void *old;
    501   assert(vector != NULL);
    502 
    503   if (new_capacity < VECTOR_MINIMUM_CAPACITY) {
    504     if (vector->capacity > VECTOR_MINIMUM_CAPACITY) {
    505       new_capacity = VECTOR_MINIMUM_CAPACITY;
    506     } else {
    507       /* NO-OP */
    508       return VECTOR_SUCCESS;
    509     }
    510   }
    511 
    512   new_capacity_in_bytes = new_capacity * vector->element_size;
    513   old = vector->data;
    514 
    515   if ((vector->data = malloc(new_capacity_in_bytes)) == NULL) {
    516     return VECTOR_ERROR;
    517   }
    518 
    519 #ifdef __STDC_LIB_EXT1__
    520   /* clang-format off */
    521     if (memcpy_s(vector->data,
    522                              new_capacity_in_bytes,
    523                              old,
    524                              aom_vector_byte_size(vector)) != 0) {
    525         return VECTOR_ERROR;
    526     }
    527 /* clang-format on */
    528 #else
    529   memcpy(vector->data, old, aom_vector_byte_size(vector));
    530 #endif
    531 
    532   vector->capacity = new_capacity;
    533 
    534   free(old);
    535 
    536   return VECTOR_SUCCESS;
    537 }
    538 
    539 void _vector_swap(size_t *first, size_t *second) {
    540   size_t temp = *first;
    541   *first = *second;
    542   *second = temp;
    543 }
    544