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
aom_vector_setup(Vector * vector,size_t capacity,size_t element_size)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
aom_vector_copy(Vector * destination,Vector * source)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
aom_vector_copy_assign(Vector * destination,Vector * source)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
aom_vector_move(Vector * destination,Vector * source)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
aom_vector_move_assign(Vector * destination,Vector * source)98 int aom_vector_move_assign(Vector *destination, Vector *source) {
99 aom_vector_swap(destination, source);
100 return aom_vector_destroy(source);
101 }
102
aom_vector_swap(Vector * destination,Vector * source)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
aom_vector_destroy(Vector * vector)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 */
aom_vector_push_back(Vector * vector,void * element)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
aom_vector_push_front(Vector * vector,void * element)156 int aom_vector_push_front(Vector *vector, void *element) {
157 return aom_vector_insert(vector, 0, element);
158 }
159
aom_vector_insert(Vector * vector,size_t index,void * element)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
aom_vector_assign(Vector * vector,size_t index,void * element)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 */
aom_vector_pop_back(Vector * vector)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
aom_vector_pop_front(Vector * vector)225 int aom_vector_pop_front(Vector *vector) { return aom_vector_erase(vector, 0); }
226
aom_vector_erase(Vector * vector,size_t index)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
aom_vector_clear(Vector * vector)247 int aom_vector_clear(Vector *vector) { return aom_vector_resize(vector, 0); }
248
249 /* Lookup */
aom_vector_get(Vector * vector,size_t index)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
aom_vector_const_get(const Vector * vector,size_t index)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
aom_vector_front(Vector * vector)272 void *aom_vector_front(Vector *vector) { return aom_vector_get(vector, 0); }
273
aom_vector_back(Vector * vector)274 void *aom_vector_back(Vector *vector) {
275 return aom_vector_get(vector, vector->size - 1);
276 }
277
278 /* Information */
279
aom_vector_is_initialized(const Vector * vector)280 bool aom_vector_is_initialized(const Vector *vector) {
281 return vector->data != NULL;
282 }
283
aom_vector_byte_size(const Vector * vector)284 size_t aom_vector_byte_size(const Vector *vector) {
285 return vector->size * vector->element_size;
286 }
287
aom_vector_free_space(const Vector * vector)288 size_t aom_vector_free_space(const Vector *vector) {
289 return vector->capacity - vector->size;
290 }
291
aom_vector_is_empty(const Vector * vector)292 bool aom_vector_is_empty(const Vector *vector) { return vector->size == 0; }
293
294 /* Memory management */
aom_vector_resize(Vector * vector,size_t new_size)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
aom_vector_reserve(Vector * vector,size_t minimum_capacity)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
aom_vector_shrink_to_fit(Vector * vector)322 int aom_vector_shrink_to_fit(Vector *vector) {
323 return _vector_reallocate(vector, vector->size);
324 }
325
326 /* Iterators */
aom_vector_begin(Vector * vector)327 Iterator aom_vector_begin(Vector *vector) { return aom_vector_iterator(vector, 0); }
328
aom_vector_end(Vector * vector)329 Iterator aom_vector_end(Vector *vector) {
330 return aom_vector_iterator(vector, vector->size);
331 }
332
aom_vector_iterator(Vector * vector,size_t index)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
iterator_get(Iterator * iterator)349 void *iterator_get(Iterator *iterator) { return iterator->pointer; }
350
iterator_erase(Vector * vector,Iterator * iterator)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
iterator_increment(Iterator * iterator)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
iterator_decrement(Iterator * iterator)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
iterator_next(Iterator * iterator)377 void *iterator_next(Iterator *iterator) {
378 void *current = iterator->pointer;
379 iterator_increment(iterator);
380
381 return current;
382 }
383
iterator_previous(Iterator * iterator)384 void *iterator_previous(Iterator *iterator) {
385 void *current = iterator->pointer;
386 iterator_decrement(iterator);
387
388 return current;
389 }
390
iterator_equals(Iterator * first,Iterator * second)391 bool iterator_equals(Iterator *first, Iterator *second) {
392 assert(first->element_size == second->element_size);
393 return first->pointer == second->pointer;
394 }
395
iterator_is_before(Iterator * first,Iterator * second)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
iterator_is_after(Iterator * first,Iterator * second)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
iterator_index(Vector * vector,Iterator * iterator)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
_vector_should_grow(Vector * vector)416 bool _vector_should_grow(Vector *vector) {
417 assert(vector->size <= vector->capacity);
418 return vector->size == vector->capacity;
419 }
420
_vector_should_shrink(Vector * vector)421 bool _vector_should_shrink(Vector *vector) {
422 assert(vector->size <= vector->capacity);
423 return vector->size == vector->capacity * VECTOR_SHRINK_THRESHOLD;
424 }
425
_vector_free_bytes(const Vector * vector)426 size_t _vector_free_bytes(const Vector *vector) {
427 return aom_vector_free_space(vector) * vector->element_size;
428 }
429
_vector_offset(Vector * vector,size_t index)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
_vector_const_offset(const Vector * vector,size_t index)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
_vector_assign(Vector * vector,size_t index,void * element)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
_vector_move_right(Vector * vector,size_t index)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
_vector_move_left(Vector * vector,size_t index)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
_vector_adjust_capacity(Vector * vector)493 int _vector_adjust_capacity(Vector *vector) {
494 return _vector_reallocate(vector,
495 MAX(1, vector->size * VECTOR_GROWTH_FACTOR));
496 }
497
_vector_reallocate(Vector * vector,size_t new_capacity)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
_vector_swap(size_t * first,size_t * second)539 void _vector_swap(size_t *first, size_t *second) {
540 size_t temp = *first;
541 *first = *second;
542 *second = temp;
543 }
544