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