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