/* test_vector.c - The test suite for vector.h. Every documented behavior in vector.h gets a case here, including the ones the header spends most of its words on: the aliasing rules, the destructor ownership transfer of vector_take_at()/vector_take_back(), the overflow guards, and the exact return code of every failure path. Cases named wb_* are white-box. They write to vector_t fields directly to reach guards that are otherwise unreachable without gigabyte allocations, and they restore whatever they changed before the vector is destroyed. Run with ctest. Pass/fail is the exit code; ctest -V shows every assertion. */ #include #include #include #include #include "../vector.h" #include "dtest.h" #define DEFAULT_CAPACITY 10 // What vector_create() gives you unless DLIBC_VECTOR_INITIAL_CAPACITY says otherwise // Provided by vector_altcap.c, which includes vector.h with DLIBC_VECTOR_INITIAL_CAPACITY set to 1 extern int vector_altcap_growth_sequence(size_t* out, size_t count); extern size_t vector_altcap_initial_capacity(void); // A four-byte element with no padding and no endianness, so that byte-level // overlap in vector_set() can be asserted exactly typedef struct { char b[4]; } quad_t; /* @brief Pushes the integers 0..count-1 onto a vector. @param vec The vector to fill. @param count How many integers to push. @return 0 if every push succeeded, -1 otherwise. */ static int fill_ints(vector_t* vec, int count) { for (int i = 0; i < count; ++i) { if (vector_push_back(vec, &i) != 0) { return -1; } } return 0; } /* @brief Reads the int at an index, or a sentinel if the index is not readable. @param vec The vector to read from. @param index The index to read. @return The stored value, or INT_MIN-ish sentinel -999999 if vector_get() returned NULL. */ static int int_at(const vector_t* vec, size_t index) { const int* value = (const int*)vector_get_const(vec, index); return value ? *value : -999999; } /* @brief Checks that a vector holds exactly the integers 0..count-1 in order. @param vec The vector to check. @param count The expected size. @param label A short description used in the assertion output. */ static void check_ints_in_order(const vector_t* vec, int count, const char* label) { int ok = (vector_size(vec) == (size_t)count); for (int i = 0; ok && i < count; ++i) { ok = (int_at(vec, (size_t)i) == i); } CHECK_TRUE(ok, label); } /* @brief Checks that the first count elements of a vector are the integers 0..count-1, ignoring whatever follows them. @param vec The vector to check. @param count How many leading elements to check. @param label A short description used in the assertion output. */ static void check_int_prefix(const vector_t* vec, int count, const char* label) { int ok = (vector_size(vec) >= (size_t)count); for (int i = 0; ok && i < count; ++i) { ok = (int_at(vec, (size_t)i) == i); } CHECK_TRUE(ok, label); } // --------------------------------------------------------------------------- // Lifecycle // --------------------------------------------------------------------------- static void vector_create_basic(void) { vector_t* vec = vector_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(vec, "vector_create returns a vector"); CHECK_EQ_SIZE(vector_size(vec), 0, "a new vector is empty"); CHECK_EQ_SIZE(vector_capacity(vec), DEFAULT_CAPACITY, "a new vector has the default capacity"); CHECK_EQ_SIZE(vector_element_size(vec), sizeof(int), "element size is what was asked for"); CHECK_EQ_INT(vector_is_empty(vec), 1, "vector_is_empty reports 1 on a new vector"); CHECK_PTR_NULL(vector_get_destructor(vec), "a new vector has no destructor"); // The data array is allocated up front, so the C array view is valid even // though there is nothing in it yet CHECK_PTR_NOT_NULL(vector_as_c_array(vec), "an empty vector still has a data array"); CHECK_PTR_NOT_NULL(vector_as_c_array_mutable(vec), "the mutable array view is valid too"); vector_destroy(&vec); } static void vector_create_rejects_zero_element_size(void) { CHECK_PTR_NULL(vector_create(0), "vector_create(0) is refused"); } static void vector_create_rejects_overflow(void) { // SIZE_MAX / element_size lands below the initial capacity, so the data // array could never be allocated and creation is refused before trying CHECK_PTR_NULL(vector_create(SIZE_MAX), "an element size of SIZE_MAX is refused"); CHECK_PTR_NULL(vector_create(SIZE_MAX / 5), "an element size that cannot hold the initial capacity is refused"); } static void vector_destroy_semantics(void) { CHECK_EQ_INT(vector_destroy(NULL), -1, "destroying through a NULL pointer is an error"); vector_t* already_null = NULL; CHECK_EQ_INT(vector_destroy(&already_null), 0, "destroying an already-NULL vector succeeds"); vector_t* vec = vector_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(vec, "vector_create returns a vector"); CHECK_EQ_INT(fill_ints(vec, 4), 0, "the vector fills"); CHECK_EQ_INT(vector_destroy(&vec), 0, "destroy succeeds"); CHECK_PTR_NULL(vec, "destroy NULLs the caller's pointer"); CHECK_EQ_INT(vector_destroy(&vec), 0, "a second destroy is harmless"); } static void vector_null_argument_matrix(void) { int value = 7; char out[sizeof(int)]; vector_t* other = vector_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(other, "vector_create returns a vector"); // The size_t getters conflate "invalid vector" with "zero", and // vector_is_empty() conflates it with "empty". Both are documented CHECK_EQ_SIZE(vector_size(NULL), 0, "size of a NULL vector is 0"); CHECK_EQ_SIZE(vector_capacity(NULL), 0, "capacity of a NULL vector is 0"); CHECK_EQ_SIZE(vector_element_size(NULL), 0, "element size of a NULL vector is 0"); CHECK_EQ_INT(vector_is_empty(NULL), 1, "a NULL vector reports as empty"); CHECK_PTR_NULL(vector_get(NULL, 0), "get on a NULL vector is NULL"); CHECK_PTR_NULL(vector_get_const(NULL, 0), "get_const on a NULL vector is NULL"); CHECK_PTR_NULL(vector_front(NULL), "front on a NULL vector is NULL"); CHECK_PTR_NULL(vector_front_const(NULL), "front_const on a NULL vector is NULL"); CHECK_PTR_NULL(vector_back(NULL), "back on a NULL vector is NULL"); CHECK_PTR_NULL(vector_back_const(NULL), "back_const on a NULL vector is NULL"); CHECK_PTR_NULL(vector_as_c_array(NULL), "the array view of a NULL vector is NULL"); CHECK_PTR_NULL(vector_as_c_array_mutable(NULL), "the mutable array view of a NULL vector is NULL"); CHECK_PTR_NULL(vector_get_destructor(NULL), "the destructor of a NULL vector is NULL"); CHECK_EQ_INT(vector_push_back(NULL, &value), -1, "push_back on a NULL vector fails"); CHECK_EQ_INT(vector_insert(NULL, 0, &value), -1, "insert on a NULL vector fails"); CHECK_EQ_INT(vector_set(NULL, 0, &value), -1, "set on a NULL vector fails"); CHECK_EQ_INT(vector_pop_back(NULL), -1, "pop_back on a NULL vector fails"); CHECK_EQ_INT(vector_pop_at(NULL, 0), -1, "pop_at on a NULL vector fails"); CHECK_EQ_INT(vector_take_at(NULL, 0, out), -1, "take_at on a NULL vector fails"); CHECK_EQ_INT(vector_take_back(NULL, out), -1, "take_back on a NULL vector fails"); CHECK_EQ_INT(vector_clear(NULL), -1, "clear on a NULL vector fails"); CHECK_EQ_INT(vector_reserve(NULL, 32), -1, "reserve on a NULL vector fails"); CHECK_EQ_INT(vector_grow(NULL), -1, "grow on a NULL vector fails"); CHECK_EQ_INT(vector_prune(NULL), -1, "prune on a NULL vector fails"); CHECK_EQ_INT(vector_set_destructor(NULL, dtest_count_destructor), -1, "set_destructor on a NULL vector fails"); CHECK_EQ_INT(vector_is_aliased(NULL, &value), 0, "is_aliased on a NULL vector is 0"); vector_t* null_src = NULL; CHECK_EQ_INT(vector_move(NULL, &null_src), -1, "move into a NULL destination fails"); CHECK_EQ_INT(vector_move(other, NULL), -1, "move from a NULL source pointer fails"); CHECK_EQ_INT(vector_move(other, &null_src), -1, "move from a NULL source vector fails"); CHECK_PTR_NULL(vector_deep_copy(NULL), "deep copying a NULL vector is NULL"); vector_destroy(&other); } // --------------------------------------------------------------------------- // Capacity // --------------------------------------------------------------------------- static void vector_reserve_grows_only(void) { vector_t* vec = vector_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(vec, "vector_create returns a vector"); CHECK_EQ_INT(vector_reserve(vec, 0), 0, "reserving zero succeeds"); CHECK_EQ_SIZE(vector_capacity(vec), DEFAULT_CAPACITY, "reserving zero does not shrink"); CHECK_EQ_INT(vector_reserve(vec, DEFAULT_CAPACITY - 1), 0, "reserving less than the capacity succeeds"); CHECK_EQ_SIZE(vector_capacity(vec), DEFAULT_CAPACITY, "reserving less does not shrink"); CHECK_EQ_INT(vector_reserve(vec, DEFAULT_CAPACITY), 0, "reserving exactly the capacity succeeds"); CHECK_EQ_SIZE(vector_capacity(vec), DEFAULT_CAPACITY, "reserving the same is a no-op"); CHECK_EQ_INT(vector_reserve(vec, 128), 0, "reserving more succeeds"); CHECK_EQ_SIZE(vector_capacity(vec), 128, "reserving more raises the capacity exactly"); CHECK_EQ_SIZE(vector_size(vec), 0, "reserving does not change the size"); vector_destroy(&vec); } static void vector_reserve_overflow_rejected(void) { vector_t* vec = vector_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(vec, "vector_create returns a vector"); CHECK_EQ_INT(fill_ints(vec, 5), 0, "the vector fills"); size_t capacity_before = vector_capacity(vec); CHECK_EQ_INT(vector_reserve(vec, SIZE_MAX), -1, "reserving SIZE_MAX is refused"); // A failed reservation must leave the vector exactly as it was CHECK_EQ_SIZE(vector_capacity(vec), capacity_before, "a refused reserve leaves the capacity alone"); check_ints_in_order(vec, 5, "a refused reserve leaves the contents alone"); int extra = 5; CHECK_EQ_INT(vector_push_back(vec, &extra), 0, "the vector is still usable afterwards"); check_ints_in_order(vec, 6, "the push landed correctly"); vector_destroy(&vec); } static void vector_grow_doubling(void) { vector_t* vec = vector_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(vec, "vector_create returns a vector"); CHECK_EQ_INT(fill_ints(vec, DEFAULT_CAPACITY), 0, "the vector fills to capacity"); CHECK_EQ_SIZE(vector_capacity(vec), DEFAULT_CAPACITY, "filling to capacity does not grow"); int value = DEFAULT_CAPACITY; CHECK_EQ_INT(vector_push_back(vec, &value), 0, "the push past capacity succeeds"); CHECK_EQ_SIZE(vector_capacity(vec), DEFAULT_CAPACITY * 2, "capacity doubles"); check_ints_in_order(vec, DEFAULT_CAPACITY + 1, "the contents survive the reallocation in order"); for (int i = DEFAULT_CAPACITY + 1; i < DEFAULT_CAPACITY * 2; ++i) { CHECK_EQ_INT(vector_push_back(vec, &i), 0, "filling to the doubled capacity succeeds"); } CHECK_EQ_SIZE(vector_size(vec), (size_t)DEFAULT_CAPACITY * 2, "the vector is full again"); CHECK_EQ_SIZE(vector_capacity(vec), DEFAULT_CAPACITY * 2, "filling to the new capacity does not grow again"); value = DEFAULT_CAPACITY * 2 + 1; CHECK_EQ_INT(vector_push_back(vec, &value), 0, "the next push succeeds"); CHECK_EQ_SIZE(vector_capacity(vec), DEFAULT_CAPACITY * 4, "capacity doubles a second time"); vector_destroy(&vec); } static void vector_prune_shrink_to_fit(void) { vector_t* vec = vector_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(vec, "vector_create returns a vector"); CHECK_EQ_INT(fill_ints(vec, 3), 0, "the vector fills"); CHECK_EQ_INT(vector_prune(vec), 0, "prune succeeds"); CHECK_EQ_SIZE(vector_capacity(vec), 3, "prune drops the capacity to the size"); check_ints_in_order(vec, 3, "prune preserves the contents"); CHECK_EQ_INT(vector_prune(vec), 0, "pruning an already-tight vector succeeds"); CHECK_EQ_SIZE(vector_capacity(vec), 3, "pruning an already-tight vector changes nothing"); CHECK_EQ_INT(vector_clear(vec), 0, "clear succeeds"); CHECK_EQ_INT(vector_prune(vec), 0, "pruning an empty vector succeeds"); CHECK_EQ_SIZE(vector_capacity(vec), 1, "capacity never drops below 1"); // A pruned-to-nothing vector must still be usable int value = 42; CHECK_EQ_INT(vector_push_back(vec, &value), 0, "a pruned vector still accepts elements"); CHECK_EQ_INT(int_at(vec, 0), 42, "the element landed"); vector_destroy(&vec); } // --------------------------------------------------------------------------- // Adding elements // --------------------------------------------------------------------------- static void vector_push_back_basic(void) { vector_t* vec = vector_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(vec, "vector_create returns a vector"); CHECK_EQ_INT(vector_push_back(vec, NULL), -1, "pushing a NULL element is refused"); CHECK_EQ_SIZE(vector_size(vec), 0, "the refused push changed nothing"); CHECK_EQ_INT(fill_ints(vec, 100), 0, "100 pushes all succeed"); CHECK_EQ_SIZE(vector_size(vec), 100, "the size matches the number of pushes"); CHECK_EQ_INT(vector_is_empty(vec), 0, "a filled vector is not empty"); check_ints_in_order(vec, 100, "order is preserved across every reallocation"); CHECK_EQ_INT(*(const int*)vector_front_const(vec), 0, "front is the first element pushed"); CHECK_EQ_INT(*(const int*)vector_back_const(vec), 99, "back is the last element pushed"); CHECK_PTR_EQ(vector_front(vec), vector_get(vec, 0), "front and get(0) are the same slot"); CHECK_PTR_EQ(vector_back(vec), vector_get(vec, 99), "back and get(size-1) are the same slot"); vector_destroy(&vec); } static void vector_insert_positions(void) { vector_t* vec = vector_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(vec, "vector_create returns a vector"); int value = 10; CHECK_EQ_INT(vector_insert(vec, 0, &value), 0, "inserting at 0 into an empty vector succeeds"); CHECK_EQ_SIZE(vector_size(vec), 1, "the size grew"); CHECK_EQ_INT(int_at(vec, 0), 10, "the element landed at 0"); value = 30; CHECK_EQ_INT(vector_insert(vec, 1, &value), 0, "inserting at index == size appends"); value = 20; CHECK_EQ_INT(vector_insert(vec, 1, &value), 0, "inserting in the middle succeeds"); value = 5; CHECK_EQ_INT(vector_insert(vec, 0, &value), 0, "inserting at the front succeeds"); CHECK_EQ_SIZE(vector_size(vec), 4, "all four inserts landed"); CHECK_EQ_INT(int_at(vec, 0), 5, "front insert shifted everything right"); CHECK_EQ_INT(int_at(vec, 1), 10, "the original front moved to 1"); CHECK_EQ_INT(int_at(vec, 2), 20, "the middle insert is in the middle"); CHECK_EQ_INT(int_at(vec, 3), 30, "the append is still last"); value = 99; CHECK_EQ_INT(vector_insert(vec, vector_size(vec) + 1, &value), -1, "inserting past size is refused"); CHECK_EQ_INT(vector_insert(vec, 0, NULL), -1, "inserting a NULL element is refused"); CHECK_EQ_SIZE(vector_size(vec), 4, "the refused inserts changed nothing"); // Insert across a growth boundary, so the shift and the reallocation happen together vector_t* tight = vector_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(tight, "vector_create returns a vector"); CHECK_EQ_INT(fill_ints(tight, DEFAULT_CAPACITY), 0, "the vector fills to capacity"); value = -1; CHECK_EQ_INT(vector_insert(tight, 0, &value), 0, "inserting at capacity grows and shifts"); CHECK_EQ_SIZE(vector_capacity(tight), DEFAULT_CAPACITY * 2, "the insert grew the vector"); CHECK_EQ_INT(int_at(tight, 0), -1, "the inserted element is at the front"); CHECK_EQ_INT(int_at(tight, DEFAULT_CAPACITY), DEFAULT_CAPACITY - 1, "the old contents shifted right intact"); vector_destroy(&tight); vector_destroy(&vec); } static void vector_set_basic(void) { vector_t* vec = vector_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(vec, "vector_create returns a vector"); int value = 99; CHECK_EQ_INT(vector_set(vec, 0, &value), -1, "setting on an empty vector is refused"); CHECK_EQ_INT(fill_ints(vec, 3), 0, "the vector fills"); CHECK_EQ_INT(vector_set(vec, 1, &value), 0, "setting in range succeeds"); CHECK_EQ_INT(int_at(vec, 1), 99, "the new value is stored"); CHECK_EQ_INT(int_at(vec, 0), 0, "the neighbours are untouched"); CHECK_EQ_INT(int_at(vec, 2), 2, "the neighbours are untouched"); CHECK_EQ_SIZE(vector_size(vec), 3, "set never changes the size"); CHECK_EQ_INT(vector_set(vec, 3, &value), -1, "setting at index == size is refused"); CHECK_EQ_INT(vector_set(vec, 0, NULL), -1, "setting a NULL element is refused"); vector_destroy(&vec); } static void vector_set_self_assignment(void) { vector_t* vec = vector_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(vec, "vector_create returns a vector"); CHECK_EQ_INT(fill_ints(vec, 3), 0, "the vector fills"); CHECK_EQ_INT(vector_set(vec, 1, vector_get(vec, 1)), 0, "setting an element to itself reports success"); CHECK_EQ_INT(int_at(vec, 1), 1, "setting an element to itself leaves the value alone"); check_ints_in_order(vec, 3, "nothing else moved"); vector_destroy(&vec); } // --------------------------------------------------------------------------- // Removing elements // --------------------------------------------------------------------------- static void vector_pop_back_and_at(void) { vector_t* vec = vector_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(vec, "vector_create returns a vector"); CHECK_EQ_INT(vector_pop_back(vec), -1, "popping an empty vector is refused"); CHECK_EQ_INT(vector_pop_at(vec, 0), -1, "popping at 0 on an empty vector is refused"); CHECK_EQ_INT(fill_ints(vec, 5), 0, "the vector fills"); size_t capacity_before = vector_capacity(vec); CHECK_EQ_INT(vector_pop_back(vec), 0, "pop_back succeeds"); CHECK_EQ_SIZE(vector_size(vec), 4, "pop_back shrinks the size by one"); CHECK_EQ_SIZE(vector_capacity(vec), capacity_before, "pop_back leaves the capacity alone"); check_ints_in_order(vec, 4, "pop_back removed only the last element"); CHECK_EQ_INT(vector_pop_at(vec, 0), 0, "pop_at the front succeeds"); CHECK_EQ_SIZE(vector_size(vec), 3, "pop_at shrinks the size by one"); CHECK_EQ_INT(int_at(vec, 0), 1, "pop_at shifted the remainder left, preserving order"); CHECK_EQ_INT(int_at(vec, 1), 2, "pop_at shifted the remainder left, preserving order"); CHECK_EQ_INT(int_at(vec, 2), 3, "pop_at shifted the remainder left, preserving order"); CHECK_EQ_INT(vector_pop_at(vec, vector_size(vec) - 1), 0, "pop_at the last index succeeds"); CHECK_EQ_SIZE(vector_size(vec), 2, "the size dropped again"); CHECK_EQ_INT(vector_pop_at(vec, vector_size(vec)), -1, "pop_at index == size is refused"); vector_destroy(&vec); } static void vector_take_at_basic(void) { vector_t* vec = vector_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(vec, "vector_create returns a vector"); CHECK_EQ_INT(fill_ints(vec, 5), 0, "the vector fills"); int taken = -1; CHECK_EQ_INT(vector_take_at(vec, 1, &taken), 0, "take_at succeeds"); CHECK_EQ_INT(taken, 1, "take_at hands over the stored value"); CHECK_EQ_SIZE(vector_size(vec), 4, "take_at shrinks the size by one"); // Unlike a set, a vector preserves order, so the remainder shifts left CHECK_EQ_INT(int_at(vec, 0), 0, "take_at preserves order"); CHECK_EQ_INT(int_at(vec, 1), 2, "take_at preserves order"); CHECK_EQ_INT(int_at(vec, 2), 3, "take_at preserves order"); CHECK_EQ_INT(int_at(vec, 3), 4, "take_at preserves order"); CHECK_EQ_INT(vector_take_at(vec, vector_size(vec), &taken), -1, "take_at index == size is refused"); CHECK_EQ_INT(vector_take_at(vec, 0, NULL), -1, "take_at with a NULL out is refused"); CHECK_EQ_SIZE(vector_size(vec), 4, "the refused takes changed nothing"); vector_destroy(&vec); } static void vector_take_back_basic(void) { vector_t* vec = vector_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(vec, "vector_create returns a vector"); int taken = -1; CHECK_EQ_INT(vector_take_back(vec, &taken), -1, "take_back on an empty vector is refused"); CHECK_EQ_INT(fill_ints(vec, 3), 0, "the vector fills"); CHECK_EQ_INT(vector_take_back(vec, NULL), -1, "take_back with a NULL out is refused"); CHECK_EQ_INT(vector_take_back(vec, &taken), 0, "take_back succeeds"); CHECK_EQ_INT(taken, 2, "take_back hands over the last element"); CHECK_EQ_SIZE(vector_size(vec), 2, "take_back shrinks the size by one"); check_ints_in_order(vec, 2, "the remainder is untouched"); CHECK_EQ_INT(vector_take_back(vec, &taken), 0, "take_back again succeeds"); CHECK_EQ_INT(taken, 1, "take_back walks backwards"); CHECK_EQ_INT(vector_take_back(vec, &taken), 0, "take_back drains the vector"); CHECK_EQ_INT(vector_take_back(vec, &taken), -1, "take_back on the now-empty vector is refused"); vector_destroy(&vec); } static void vector_take_rejects_aliased_out(void) { vector_t* vec = vector_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(vec, "vector_create returns a vector"); CHECK_EQ_INT(fill_ints(vec, 3), 0, "the vector fills"); void* inside = vector_get(vec, 1); CHECK_EQ_INT(vector_take_at(vec, 0, inside), -1, "take_at into the vector's own data is refused"); CHECK_EQ_INT(vector_take_back(vec, inside), -1, "take_back into the vector's own data is refused"); CHECK_EQ_SIZE(vector_size(vec), 3, "the refused takes changed nothing"); check_ints_in_order(vec, 3, "the refused takes left the contents intact"); // vector_is_aliased() bounds on capacity rather than size, so even the unused // spare room at the end of the buffer counts as inside the vector char* spare = (char*)vector_as_c_array_mutable(vec) + (5 * vector_element_size(vec)); CHECK_EQ_INT(vector_is_aliased(vec, spare), 1, "the unused spare capacity counts as aliased"); CHECK_EQ_INT(vector_take_at(vec, 0, spare), -1, "take_at into the spare capacity is refused"); vector_destroy(&vec); } static void vector_clear_keeps_capacity(void) { vector_t* vec = vector_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(vec, "vector_create returns a vector"); CHECK_EQ_INT(fill_ints(vec, 25), 0, "the vector fills past its initial capacity"); size_t capacity_before = vector_capacity(vec); const void* data_before = vector_as_c_array(vec); CHECK_EQ_INT(vector_clear(vec), 0, "clear succeeds"); CHECK_EQ_SIZE(vector_size(vec), 0, "clear empties the vector"); CHECK_EQ_INT(vector_is_empty(vec), 1, "the cleared vector reports empty"); CHECK_EQ_SIZE(vector_capacity(vec), capacity_before, "clear leaves the capacity alone"); CHECK_PTR_EQ(vector_as_c_array(vec), data_before, "clear does not reallocate"); CHECK_EQ_INT(fill_ints(vec, 25), 0, "the cleared vector refills"); CHECK_PTR_EQ(vector_as_c_array(vec), data_before, "refilling within the old capacity does not reallocate"); check_ints_in_order(vec, 25, "the refilled contents are correct"); vector_destroy(&vec); } // --------------------------------------------------------------------------- // Aliasing, on a vector without a destructor // --------------------------------------------------------------------------- static void vector_alias_push_back_no_grow(void) { vector_t* vec = vector_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(vec, "vector_create returns a vector"); CHECK_EQ_INT(fill_ints(vec, 3), 0, "the vector fills without reaching capacity"); CHECK_TRUE(vector_size(vec) < vector_capacity(vec), "there is spare room, so no growth is needed"); CHECK_EQ_INT(vector_push_back(vec, vector_get(vec, 0)), 0, "pushing an element of the vector itself succeeds"); CHECK_EQ_SIZE(vector_size(vec), 4, "the push landed"); CHECK_EQ_INT(int_at(vec, 3), 0, "the pushed copy holds the aliased element's value"); CHECK_EQ_INT(int_at(vec, 0), 0, "the source element is unchanged"); vector_destroy(&vec); } static void vector_alias_push_back_triggers_grow(void) { vector_t* vec = vector_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(vec, "vector_create returns a vector"); CHECK_EQ_INT(fill_ints(vec, DEFAULT_CAPACITY), 0, "the vector fills to exactly its capacity"); CHECK_EQ_SIZE(vector_size(vec), vector_capacity(vec), "size and capacity are equal, so the next push must grow"); // This is the path where the element's byte offset has to be remembered // before the reallocation and re-resolved afterwards CHECK_EQ_INT(vector_push_back(vec, vector_get(vec, 0)), 0, "pushing an aliased element across a growth succeeds"); CHECK_EQ_SIZE(vector_capacity(vec), DEFAULT_CAPACITY * 2, "the push grew the vector"); CHECK_EQ_SIZE(vector_size(vec), (size_t)DEFAULT_CAPACITY + 1, "the push landed"); CHECK_EQ_INT(int_at(vec, DEFAULT_CAPACITY), 0, "the pushed copy survived the reallocation"); check_int_prefix(vec, DEFAULT_CAPACITY, "the original contents survived too"); // The same again from the last element, where the offset sits at the far end // of the buffer. The filler values are distinctive so that the assertion // below cannot pass by coincidence int filler = 1000; while (vector_size(vec) < vector_capacity(vec)) { CHECK_TRUE(vector_push_back(vec, &filler) == 0, "topping the vector back up to capacity"); ++filler; } size_t last = vector_size(vec) - 1; int last_value = int_at(vec, last); CHECK_EQ_INT(vector_push_back(vec, vector_get(vec, last)), 0, "pushing the last element across a growth succeeds"); CHECK_EQ_INT(int_at(vec, vector_size(vec) - 1), last_value, "the pushed copy holds the last element's value"); CHECK_EQ_INT(int_at(vec, last), last_value, "the source element is unchanged"); vector_destroy(&vec); } static void vector_alias_insert(void) { vector_t* vec = vector_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(vec, "vector_create returns a vector"); CHECK_EQ_INT(fill_ints(vec, 5), 0, "the vector fills"); // insert() copies an aliased element aside into a temporary, because both // the reallocation and the shift would otherwise clobber it CHECK_EQ_INT(vector_insert(vec, 0, vector_back(vec)), 0, "inserting an element of the vector itself succeeds"); CHECK_EQ_SIZE(vector_size(vec), 6, "the insert landed"); CHECK_EQ_INT(int_at(vec, 0), 4, "the inserted copy holds the aliased element's value"); CHECK_EQ_INT(int_at(vec, 1), 0, "the old contents shifted right"); CHECK_EQ_INT(int_at(vec, 5), 4, "the source element is still there, one place later"); // And again where the insert also has to grow vector_t* tight = vector_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(tight, "vector_create returns a vector"); CHECK_EQ_INT(fill_ints(tight, DEFAULT_CAPACITY), 0, "the vector fills to capacity"); CHECK_EQ_INT(vector_insert(tight, 2, vector_get(tight, DEFAULT_CAPACITY - 1)), 0, "inserting an aliased element across a growth succeeds"); CHECK_EQ_SIZE(vector_capacity(tight), DEFAULT_CAPACITY * 2, "the insert grew the vector"); CHECK_EQ_INT(int_at(tight, 2), DEFAULT_CAPACITY - 1, "the inserted copy survived the reallocation"); CHECK_EQ_INT(int_at(tight, 1), 1, "the elements before the index did not move"); CHECK_EQ_INT(int_at(tight, 3), 2, "the elements from the index shifted right"); vector_destroy(&tight); vector_destroy(&vec); } static void vector_alias_set(void) { vector_t* vec = vector_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(vec, "vector_create returns a vector"); CHECK_EQ_INT(fill_ints(vec, 5), 0, "the vector fills"); CHECK_EQ_INT(vector_set(vec, 0, vector_get(vec, 1)), 0, "setting from another slot succeeds"); CHECK_EQ_INT(int_at(vec, 0), 1, "the value was copied across"); CHECK_EQ_INT(int_at(vec, 1), 1, "the source slot is unchanged"); // A source that is not element-aligned overlaps the destination slot, which // is exactly why set() copies with memmove(). Four raw bytes per element // keeps the expected result free of any endianness question vector_t* quads = vector_create(sizeof(quad_t)); REQUIRE_PTR_NOT_NULL(quads, "vector_create returns a vector"); quad_t first = { { 'a', 'b', 'c', 'd' } }; quad_t second = { { 'e', 'f', 'g', 'h' } }; CHECK_EQ_INT(vector_push_back(quads, &first), 0, "the first quad is pushed"); CHECK_EQ_INT(vector_push_back(quads, &second), 0, "the second quad is pushed"); const char* interior = (const char*)vector_as_c_array(quads) + 2; CHECK_EQ_INT(vector_is_aliased(quads, interior), 1, "the interior pointer is recognised as aliased"); CHECK_EQ_INT(vector_set(quads, 0, interior), 0, "setting from an overlapping interior pointer succeeds"); const quad_t* result = (const quad_t*)vector_get_const(quads, 0); REQUIRE_PTR_NOT_NULL(result, "the element is readable"); CHECK_MEM_EQ(result->b, "cdef", 4, "the overlapping copy produced the right four bytes"); vector_destroy(&quads); vector_destroy(&vec); } static void vector_is_aliased_semantics(void) { vector_t* vec = vector_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(vec, "vector_create returns a vector"); CHECK_EQ_INT(fill_ints(vec, 3), 0, "the vector fills"); char* base = (char*)vector_as_c_array_mutable(vec); size_t span = vector_capacity(vec) * vector_element_size(vec); CHECK_EQ_INT(vector_is_aliased(vec, base), 1, "the first byte of the buffer is aliased"); CHECK_EQ_INT(vector_is_aliased(vec, base + span - 1), 1, "the last byte of the capacity is aliased"); CHECK_EQ_INT(vector_is_aliased(vec, base + span), 0, "one past the end of the capacity is not aliased"); CHECK_EQ_INT(vector_is_aliased(vec, NULL), 0, "a NULL pointer is not aliased"); CHECK_EQ_INT(vector_is_aliased(NULL, base), 0, "nothing is aliased in a NULL vector"); int on_the_stack = 0; CHECK_EQ_INT(vector_is_aliased(vec, &on_the_stack), 0, "an unrelated address is not aliased"); vector_destroy(&vec); } // --------------------------------------------------------------------------- // Destructors // --------------------------------------------------------------------------- static void vector_destructor_get_set(void) { vector_t* vec = vector_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(vec, "vector_create returns a vector"); // A vector with no destructor and a NULL vector both report NULL, which is // the documented ambiguity CHECK_PTR_NULL(vector_get_destructor(vec), "a fresh vector has no destructor"); CHECK_EQ_INT(vector_set_destructor(vec, dtest_count_destructor), 0, "setting a destructor succeeds"); CHECK_TRUE(vector_get_destructor(vec) == dtest_count_destructor, "the destructor round-trips"); CHECK_EQ_INT(vector_set_destructor(vec, NULL), 0, "setting a NULL destructor succeeds"); CHECK_PTR_NULL(vector_get_destructor(vec), "a NULL destructor removes it"); vector_destroy(&vec); } static void vector_destructor_call_counts(void) { vector_t* vec = vector_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(vec, "vector_create returns a vector"); CHECK_EQ_INT(vector_set_destructor(vec, dtest_count_destructor), 0, "the destructor is set"); CHECK_EQ_INT(fill_ints(vec, 5), 0, "the vector fills"); dtest_reset_destructor_calls(); CHECK_EQ_INT(vector_pop_back(vec), 0, "pop_back succeeds"); CHECK_EQ_INT(dtest_destructor_calls, 1, "pop_back destroys exactly one element"); dtest_reset_destructor_calls(); CHECK_EQ_INT(vector_pop_at(vec, 0), 0, "pop_at succeeds"); CHECK_EQ_INT(dtest_destructor_calls, 1, "pop_at destroys exactly one element"); dtest_reset_destructor_calls(); int replacement = 77; CHECK_EQ_INT(vector_set(vec, 0, &replacement), 0, "set succeeds"); CHECK_EQ_INT(dtest_destructor_calls, 1, "set destroys exactly the element it overwrites"); // take_at and take_back hand ownership to the caller, so the destructor must // stay out of the way entirely dtest_reset_destructor_calls(); int taken = 0; CHECK_EQ_INT(vector_take_at(vec, 0, &taken), 0, "take_at succeeds"); CHECK_EQ_INT(dtest_destructor_calls, 0, "take_at never calls the destructor"); CHECK_EQ_INT(vector_take_back(vec, &taken), 0, "take_back succeeds"); CHECK_EQ_INT(dtest_destructor_calls, 0, "take_back never calls the destructor"); CHECK_EQ_SIZE(vector_size(vec), 1, "one element is left"); dtest_reset_destructor_calls(); CHECK_EQ_INT(vector_clear(vec), 0, "clear succeeds"); CHECK_EQ_INT(dtest_destructor_calls, 1, "clear destroys every remaining element"); CHECK_EQ_INT(fill_ints(vec, 4), 0, "the vector refills"); dtest_reset_destructor_calls(); CHECK_EQ_INT(vector_destroy(&vec), 0, "destroy succeeds"); CHECK_EQ_INT(dtest_destructor_calls, 4, "destroy destroys every element exactly once"); } static void vector_destructor_set_self_assign_no_call(void) { vector_t* vec = vector_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(vec, "vector_create returns a vector"); CHECK_EQ_INT(vector_set_destructor(vec, dtest_count_destructor), 0, "the destructor is set"); CHECK_EQ_INT(fill_ints(vec, 3), 0, "the vector fills"); // The slot == element early-out sits above both the aliasing rejection and // the destructor call, so setting an element to itself touches nothing dtest_reset_destructor_calls(); CHECK_EQ_INT(vector_set(vec, 1, vector_get(vec, 1)), 0, "self-assignment reports success even with a destructor"); CHECK_EQ_INT(dtest_destructor_calls, 0, "self-assignment does not destroy the element"); CHECK_EQ_INT(int_at(vec, 1), 1, "the value is intact"); dtest_reset_destructor_calls(); vector_destroy(&vec); } static void vector_destructor_rejects_aliased_writes(void) { vector_t* vec = vector_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(vec, "vector_create returns a vector"); CHECK_EQ_INT(vector_set_destructor(vec, dtest_count_destructor), 0, "the destructor is set"); CHECK_EQ_INT(fill_ints(vec, 3), 0, "the vector fills"); dtest_reset_destructor_calls(); CHECK_EQ_INT(vector_push_back(vec, vector_get(vec, 0)), -1, "pushing an aliased element is refused"); CHECK_EQ_INT(vector_insert(vec, 0, vector_get(vec, 1)), -1, "inserting an aliased element is refused"); CHECK_EQ_INT(vector_set(vec, 0, vector_get(vec, 2)), -1, "setting from another slot is refused"); // A refusal must be inert: nothing added, nothing shifted, nothing freed CHECK_EQ_INT(dtest_destructor_calls, 0, "no element was destroyed by the refusals"); CHECK_EQ_SIZE(vector_size(vec), 3, "the size is unchanged"); check_ints_in_order(vec, 3, "the contents are unchanged"); dtest_reset_destructor_calls(); vector_destroy(&vec); } static void vector_owning_elements_end_to_end(void) { vector_t* vec = vector_create(sizeof(char*)); REQUIRE_PTR_NOT_NULL(vec, "vector_create returns a vector"); CHECK_EQ_INT(vector_set_destructor(vec, dtest_string_destructor), 0, "the string destructor is set"); static const char* const words[] = { "alpha", "bravo", "charlie", "delta", "echo" }; for (size_t i = 0; i < sizeof(words) / sizeof(words[0]); ++i) { char* copy = dtest_dup(words[i]); REQUIRE_PTR_NOT_NULL(copy, "the string is duplicated"); CHECK_EQ_INT(vector_push_back(vec, ©), 0, "the string pointer is pushed"); } CHECK_EQ_SIZE(vector_size(vec), 5, "all five strings are stored"); CHECK_EQ_STR(*(char* const*)vector_front_const(vec), "alpha", "the first string reads back"); CHECK_EQ_STR(*(char* const*)vector_back_const(vec), "echo", "the last string reads back"); // pop_back frees what the element owned dtest_reset_destructor_calls(); CHECK_EQ_INT(vector_pop_back(vec), 0, "pop_back succeeds"); CHECK_EQ_INT(dtest_destructor_calls, 1, "pop_back freed the popped string"); // take_back hands the allocation over instead, so the caller frees it dtest_reset_destructor_calls(); char* taken = NULL; CHECK_EQ_INT(vector_take_back(vec, &taken), 0, "take_back succeeds"); CHECK_EQ_INT(dtest_destructor_calls, 0, "take_back did not free the string"); CHECK_EQ_STR(taken, "delta", "the taken string is intact and owned by the caller"); free(taken); dtest_reset_destructor_calls(); CHECK_EQ_INT(vector_clear(vec), 0, "clear succeeds"); CHECK_EQ_INT(dtest_destructor_calls, 3, "clear freed the three remaining strings"); char* last = dtest_dup("foxtrot"); REQUIRE_PTR_NOT_NULL(last, "the string is duplicated"); CHECK_EQ_INT(vector_push_back(vec, &last), 0, "the cleared vector still accepts strings"); dtest_reset_destructor_calls(); CHECK_EQ_INT(vector_destroy(&vec), 0, "destroy succeeds"); CHECK_EQ_INT(dtest_destructor_calls, 1, "destroy freed the last string"); } // --------------------------------------------------------------------------- // Moving and copying // --------------------------------------------------------------------------- static void vector_move_basic(void) { vector_t* dest = vector_create(sizeof(int)); vector_t* src = vector_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(dest, "the destination vector is created"); REQUIRE_PTR_NOT_NULL(src, "the source vector is created"); CHECK_EQ_INT(vector_set_destructor(dest, dtest_count_destructor), 0, "the destination gets a destructor"); CHECK_EQ_INT(fill_ints(dest, 3), 0, "the destination fills"); CHECK_EQ_INT(fill_ints(src, 5), 0, "the source fills"); CHECK_EQ_INT(vector_reserve(src, 64), 0, "the source is given a distinctive capacity"); const void* src_data = vector_as_c_array(src); dtest_reset_destructor_calls(); CHECK_EQ_INT(vector_move(dest, &src), 0, "the move succeeds"); CHECK_EQ_INT(dtest_destructor_calls, 3, "the destination's own destructor ran on its old elements"); CHECK_PTR_NULL(src, "the move NULLs the source pointer"); CHECK_EQ_SIZE(vector_size(dest), 5, "the destination took the source's size"); CHECK_EQ_SIZE(vector_capacity(dest), 64, "the destination took the source's capacity"); CHECK_EQ_SIZE(vector_element_size(dest), sizeof(int), "the destination took the source's element size"); CHECK_PTR_EQ(vector_as_c_array(dest), src_data, "the destination took the source's buffer, not a copy"); CHECK_PTR_NULL(vector_get_destructor(dest), "the destination took the source's destructor, which was NULL"); check_ints_in_order(dest, 5, "the moved contents are correct"); vector_destroy(&dest); // The other direction: a source that carries a destructor hands it over vector_t* plain_dest = vector_create(sizeof(int)); vector_t* owning_src = vector_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(plain_dest, "the destination vector is created"); REQUIRE_PTR_NOT_NULL(owning_src, "the source vector is created"); CHECK_EQ_INT(vector_set_destructor(owning_src, dtest_count_destructor), 0, "the source gets a destructor"); CHECK_EQ_INT(fill_ints(owning_src, 2), 0, "the source fills"); dtest_reset_destructor_calls(); CHECK_EQ_INT(vector_move(plain_dest, &owning_src), 0, "the move succeeds"); CHECK_EQ_INT(dtest_destructor_calls, 0, "an empty destination has nothing to destroy"); CHECK_TRUE(vector_get_destructor(plain_dest) == dtest_count_destructor, "the destructor came across with the elements"); dtest_reset_destructor_calls(); vector_destroy(&plain_dest); CHECK_EQ_INT(dtest_destructor_calls, 2, "the transferred destructor cleans up the transferred elements"); } static void vector_move_self_is_noop(void) { vector_t* vec = vector_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(vec, "vector_create returns a vector"); CHECK_EQ_INT(fill_ints(vec, 3), 0, "the vector fills"); // Moving onto itself reports success and leaves everything alone, including // the caller's pointer, which is deliberately NOT NULLed here vector_t* alias = vec; CHECK_EQ_INT(vector_move(vec, &alias), 0, "a self-move reports success"); CHECK_PTR_EQ(alias, vec, "a self-move leaves the source pointer alone"); CHECK_EQ_SIZE(vector_size(vec), 3, "a self-move leaves the size alone"); check_ints_in_order(vec, 3, "a self-move leaves the contents alone"); vector_destroy(&vec); } static void vector_move_rejects_shallow_copy(void) { vector_t* dest = vector_create(sizeof(int)); vector_t* src = vector_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(dest, "the destination vector is created"); REQUIRE_PTR_NOT_NULL(src, "the source vector is created"); CHECK_EQ_INT(fill_ints(dest, 2), 0, "the destination fills"); // Two vector_t sharing a data pointer can only come from copying the struct, // which is never valid. Fabricate it here, check the guard, then unfabricate // it so that nothing is freed twice void* src_data = src->data; src->data = dest->data; CHECK_EQ_INT(vector_move(dest, &src), -1, "moving between vectors that share a buffer is refused"); CHECK_PTR_NOT_NULL(src, "the refused move left the source pointer alone"); CHECK_EQ_SIZE(vector_size(dest), 2, "the refused move left the destination alone"); src->data = src_data; vector_destroy(&src); vector_destroy(&dest); } static void vector_deep_copy_basic(void) { vector_t* vec = vector_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(vec, "vector_create returns a vector"); CHECK_EQ_INT(fill_ints(vec, 6), 0, "the vector fills"); vector_t* copy = vector_deep_copy(vec); REQUIRE_PTR_NOT_NULL(copy, "the deep copy is created"); CHECK_EQ_SIZE(vector_size(copy), vector_size(vec), "the copy has the same size"); CHECK_EQ_SIZE(vector_element_size(copy), vector_element_size(vec), "the copy has the same element size"); CHECK_PTR_NE(vector_as_c_array(copy), vector_as_c_array(vec), "the copy has its own buffer"); CHECK_PTR_NULL(vector_get_destructor(copy), "the copy has no destructor"); check_ints_in_order(copy, 6, "the copy holds the same values in the same order"); // The two must be fully independent in both directions int changed = 999; CHECK_EQ_INT(vector_set(copy, 0, &changed), 0, "the copy can be modified"); CHECK_EQ_INT(int_at(vec, 0), 0, "modifying the copy does not touch the original"); changed = 888; CHECK_EQ_INT(vector_set(vec, 1, &changed), 0, "the original can be modified"); CHECK_EQ_INT(int_at(copy, 1), 1, "modifying the original does not touch the copy"); CHECK_EQ_INT(vector_push_back(copy, &changed), 0, "the copy can grow independently"); CHECK_EQ_SIZE(vector_size(vec), 6, "growing the copy does not change the original's size"); vector_destroy(©); vector_destroy(&vec); } static void vector_deep_copy_empty(void) { vector_t* vec = vector_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(vec, "vector_create returns a vector"); vector_t* copy = vector_deep_copy(vec); REQUIRE_PTR_NOT_NULL(copy, "an empty vector can be deep copied"); CHECK_EQ_SIZE(vector_size(copy), 0, "the copy is empty"); CHECK_EQ_INT(vector_is_empty(copy), 1, "the copy reports empty"); CHECK_PTR_NOT_NULL(vector_as_c_array(copy), "the empty copy still has a buffer"); int value = 1; CHECK_EQ_INT(vector_push_back(copy, &value), 0, "the empty copy is usable"); vector_destroy(©); vector_destroy(&vec); } static void vector_deep_copy_rejects_destructor(void) { vector_t* vec = vector_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(vec, "vector_create returns a vector"); CHECK_EQ_INT(vector_set_destructor(vec, dtest_count_destructor), 0, "the destructor is set"); CHECK_EQ_INT(fill_ints(vec, 3), 0, "the vector fills"); // Copying byte for byte would leave both vectors owning the same memory CHECK_PTR_NULL(vector_deep_copy(vec), "a vector with a destructor cannot be deep copied"); CHECK_EQ_INT(vector_set_destructor(vec, NULL), 0, "the destructor is removed"); vector_t* copy = vector_deep_copy(vec); CHECK_PTR_NOT_NULL(copy, "without the destructor the same vector copies fine"); vector_destroy(©); vector_destroy(&vec); } static void vector_deep_copy_capacity_quirk(void) { vector_t* vec = vector_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(vec, "vector_create returns a vector"); int value = 1; CHECK_EQ_INT(vector_push_back(vec, &value), 0, "one element is pushed"); CHECK_EQ_INT(vector_prune(vec), 0, "prune succeeds"); CHECK_EQ_SIZE(vector_capacity(vec), 1, "the source is pruned down to a capacity of 1"); // vector_deep_copy() builds the copy with vector_create(), which starts at the // default capacity, and then calls vector_reserve() which never shrinks. A // source pruned below the default therefore copies to a roomier vector. This // is pinned rather than worked around, so that any change to it is noticed vector_t* copy = vector_deep_copy(vec); REQUIRE_PTR_NOT_NULL(copy, "the deep copy is created"); CHECK_EQ_SIZE(vector_size(copy), 1, "the copy holds the one element"); CHECK_EQ_SIZE(vector_capacity(copy), DEFAULT_CAPACITY, "the copy keeps the default capacity, not the source's"); CHECK_EQ_INT(int_at(copy, 0), 1, "the value came across"); vector_destroy(©); vector_destroy(&vec); } // --------------------------------------------------------------------------- // Accessors // --------------------------------------------------------------------------- static void vector_accessor_edge_cases(void) { vector_t* vec = vector_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(vec, "vector_create returns a vector"); CHECK_PTR_NULL(vector_front(vec), "front of an empty vector is NULL"); CHECK_PTR_NULL(vector_front_const(vec), "front_const of an empty vector is NULL"); CHECK_PTR_NULL(vector_back(vec), "back of an empty vector is NULL"); CHECK_PTR_NULL(vector_back_const(vec), "back_const of an empty vector is NULL"); CHECK_PTR_NULL(vector_get(vec, 0), "get on an empty vector is NULL"); CHECK_EQ_INT(fill_ints(vec, 4), 0, "the vector fills"); CHECK_PTR_NULL(vector_get(vec, vector_size(vec)), "get at index == size is NULL"); CHECK_PTR_NULL(vector_get_const(vec, vector_size(vec)), "get_const at index == size is NULL"); CHECK_PTR_NOT_NULL(vector_get(vec, vector_size(vec) - 1), "get at the last index is valid"); // The mutable array view really is the vector's own storage int* raw = (int*)vector_as_c_array_mutable(vec); REQUIRE_PTR_NOT_NULL(raw, "the mutable array view is valid"); raw[2] = 555; CHECK_EQ_INT(int_at(vec, 2), 555, "a write through the array view is visible through get"); CHECK_PTR_EQ(vector_as_c_array(vec), raw, "both array views point at the same storage"); vector_destroy(&vec); } // --------------------------------------------------------------------------- // White-box guards. These write vector_t fields directly to reach branches that // are otherwise unreachable, and restore them before the vector is destroyed // --------------------------------------------------------------------------- static void vector_wb_grow_overflow_guard(void) { vector_t* vec = vector_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(vec, "vector_create returns a vector"); size_t real_capacity = vec->capacity; vec->capacity = SIZE_MAX / 2 + 1; CHECK_EQ_INT(vector_grow(vec), -1, "growing past half of SIZE_MAX is refused"); vec->capacity = real_capacity; CHECK_EQ_SIZE(vector_capacity(vec), real_capacity, "the capacity was restored for cleanup"); vector_destroy(&vec); } static void vector_wb_element_size_zero_guard(void) { vector_t* vec = vector_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(vec, "vector_create returns a vector"); // An element size of zero cannot come from vector_create(), but it would make // the capacity arithmetic divide by zero, so reserve and prune both guard it size_t real_element_size = vec->element_size; vec->element_size = 0; CHECK_EQ_INT(vector_reserve(vec, 100), -1, "reserving on a zero element size is refused"); CHECK_EQ_INT(vector_prune(vec), -1, "pruning on a zero element size is refused"); vec->element_size = real_element_size; CHECK_EQ_SIZE(vector_element_size(vec), sizeof(int), "the element size was restored for cleanup"); vector_destroy(&vec); } static void vector_wb_reserve_multiply_overflow(void) { vector_t* vec = vector_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(vec, "vector_create returns a vector"); // One element more than the address space could hold at this element size size_t too_many = SIZE_MAX / sizeof(int) + 1; CHECK_EQ_INT(vector_reserve(vec, too_many), -1, "a reservation that would overflow the byte count is refused"); CHECK_EQ_SIZE(vector_capacity(vec), DEFAULT_CAPACITY, "the refused reservation changed nothing"); int value = 1; CHECK_EQ_INT(vector_push_back(vec, &value), 0, "the vector is still usable"); vector_destroy(&vec); } // --------------------------------------------------------------------------- // A non-default DLIBC_VECTOR_INITIAL_CAPACITY, from vector_altcap.c // --------------------------------------------------------------------------- static void vector_altcap_initial_capacity_honoured(void) { CHECK_EQ_SIZE(vector_altcap_initial_capacity(), 1, "DLIBC_VECTOR_INITIAL_CAPACITY sets the starting capacity"); } static void vector_altcap_growth_from_one(void) { size_t capacities[8]; REQUIRE_TRUE(vector_altcap_growth_sequence(capacities, 8) == 0, "the growth probe runs"); static const size_t expected[8] = { 1, 2, 4, 4, 8, 8, 8, 8 }; for (size_t i = 0; i < 8; ++i) { CHECK_EQ_SIZE(capacities[i], expected[i], "capacity doubles on demand from an initial capacity of 1"); } } // --------------------------------------------------------------------------- int main(void) { static const dtest_case_t cases[] = { // Lifecycle DTEST_CASE(vector_create_basic), DTEST_CASE(vector_create_rejects_zero_element_size), DTEST_CASE(vector_create_rejects_overflow), DTEST_CASE(vector_destroy_semantics), DTEST_CASE(vector_null_argument_matrix), // Capacity DTEST_CASE(vector_reserve_grows_only), DTEST_CASE(vector_reserve_overflow_rejected), DTEST_CASE(vector_grow_doubling), DTEST_CASE(vector_prune_shrink_to_fit), // Adding elements DTEST_CASE(vector_push_back_basic), DTEST_CASE(vector_insert_positions), DTEST_CASE(vector_set_basic), DTEST_CASE(vector_set_self_assignment), // Removing elements DTEST_CASE(vector_pop_back_and_at), DTEST_CASE(vector_take_at_basic), DTEST_CASE(vector_take_back_basic), DTEST_CASE(vector_take_rejects_aliased_out), DTEST_CASE(vector_clear_keeps_capacity), // Aliasing DTEST_CASE(vector_alias_push_back_no_grow), DTEST_CASE(vector_alias_push_back_triggers_grow), DTEST_CASE(vector_alias_insert), DTEST_CASE(vector_alias_set), DTEST_CASE(vector_is_aliased_semantics), // Destructors DTEST_CASE(vector_destructor_get_set), DTEST_CASE(vector_destructor_call_counts), DTEST_CASE(vector_destructor_set_self_assign_no_call), DTEST_CASE(vector_destructor_rejects_aliased_writes), DTEST_CASE(vector_owning_elements_end_to_end), // Moving and copying DTEST_CASE(vector_move_basic), DTEST_CASE(vector_move_self_is_noop), DTEST_CASE(vector_move_rejects_shallow_copy), DTEST_CASE(vector_deep_copy_basic), DTEST_CASE(vector_deep_copy_empty), DTEST_CASE(vector_deep_copy_rejects_destructor), DTEST_CASE(vector_deep_copy_capacity_quirk), // Accessors DTEST_CASE(vector_accessor_edge_cases), // White-box guards DTEST_CASE(vector_wb_grow_overflow_guard), DTEST_CASE(vector_wb_element_size_zero_guard), DTEST_CASE(vector_wb_reserve_multiply_overflow), // A non-default initial capacity DTEST_CASE(vector_altcap_initial_capacity_honoured), DTEST_CASE(vector_altcap_growth_from_one), }; return dtest_main(cases, sizeof(cases) / sizeof(cases[0]), "vector"); }