Coverage Report

Created: 2022-08-24 06:17

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