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
