/* test_set.c - The test suite for set.h. A set is not a hash table here: it is a contiguous array with linear-scan uniqueness and swap-with-last removal. Most of what the header documents is about the consequences of that, so most of what is tested here is too - the tri-state return codes, the comparator identity rule, the index instability after a removal, and the ownership transfer of set_take()/set_take_at(). Cases named wb_* are white-box. They write to set_t fields directly to reach guards that are otherwise unreachable without gigabyte allocations, and they restore whatever they changed before the set is destroyed. @attention Every comparator lives in this one translation unit on purpose. set_is_compatible() decides compatibility by comparing function pointers, so a comparator that ended up with a distinct address per translation unit would make sets built in different files silently refuse to combine. Run with ctest. Pass/fail is the exit code; ctest -V shows every assertion. */ #include #include #include #include #include #include "../set.h" #include "dtest.h" #define DEFAULT_CAPACITY 10 // What set_create() gives you unless DLIBC_SET_INITIAL_CAPACITY says otherwise // Provided by set_altcap.c, which includes set.h with DLIBC_SET_INITIAL_CAPACITY set to 1 extern int set_altcap_growth_sequence(size_t* out, size_t count); extern size_t set_altcap_initial_capacity(void); // A four-byte element with no padding and no endianness, so that a byte-level // interior pointer into the set's data has an exactly predictable value typedef struct { char b[4]; } quad_t; // A struct with padding between its members, for the trap the header warns about typedef struct { char tag; int value; } tagged_t; // --------------------------------------------------------------------------- // Comparators // --------------------------------------------------------------------------- /* @brief Orders two ints. A conventional three-way comparator. */ static int cmp_int(const void* a, const void* b) { int x = *(const int*)a; int y = *(const int*)b; return (x > y) - (x < y); } /* @brief Reports two ints as equal or not, and never returns a negative value. @attention Only a result of 0 means equal, so a comparator that never goes negative is perfectly valid. This pins that the sign is never inspected. */ static int cmp_int_positive_only(const void* a, const void* b) { return (*(const int*)a == *(const int*)b) ? 0 : 7; } /* @brief A deliberately broken comparator that reports nothing as equal, not even an element and itself. @attention Used to reach the paths set_insert() keeps for exactly this case, where a bad comparator must still not be able to cause a use-after-free. */ static int cmp_never_equal(const void* a, const void* b) { (void)a; (void)b; return 1; } /* @brief Compares two char* elements by their contents rather than their addresses. */ static int cmp_str(const void* a, const void* b) { return strcmp(*(const char* const*)a, *(const char* const*)b); } /* @brief Compares two char* elements by their contents, ignoring case. @attention Hand-rolled rather than strcasecmp(), which is POSIX rather than ISO C and is not visible with compiler extensions turned off. */ static int cmp_str_ci(const void* a, const void* b) { const char* x = *(const char* const*)a; const char* y = *(const char* const*)b; while (*x && *y) { int cx = tolower((unsigned char)*x); int cy = tolower((unsigned char)*y); if (cx != cy) { return cx < cy ? -1 : 1; } ++x; ++y; } if (*x == *y) { return 0; } return *x ? 1 : -1; } /* @brief Compares two tagged_t elements by their members only, ignoring the padding between them. */ static int cmp_tagged(const void* a, const void* b) { const tagged_t* x = (const tagged_t*)a; const tagged_t* y = (const tagged_t*)b; return (x->tag == y->tag && x->value == y->value) ? 0 : 1; } static const void* recorded_lhs = NULL; // The first argument of the last cmp_recording() call static const void* recorded_rhs = NULL; // The second argument of the last cmp_recording() call /* @brief Compares two ints and remembers which pointers it was handed, so that the argument order can be asserted. */ static int cmp_recording(const void* a, const void* b) { recorded_lhs = a; recorded_rhs = b; return cmp_int(a, b); } // --------------------------------------------------------------------------- // Helpers // --------------------------------------------------------------------------- /* @brief Inserts the integers 0..count-1 into a set. @param set The set to fill. @param count How many integers to insert. @return 0 if every insert added a new element, -1 otherwise. */ static int fill_ints(set_t* set, int count) { for (int i = 0; i < count; ++i) { if (set_insert(set, &i) != 0) { return -1; } } return 0; } /* @brief Inserts each of the given integers into a set. @param set The set to fill. @param values The values to insert. @param count How many values there are. @return 0 if every insert added a new element, -1 otherwise. */ static int insert_all(set_t* set, const int* values, size_t count) { for (size_t i = 0; i < count; ++i) { if (set_insert(set, &values[i]) != 0) { return -1; } } return 0; } /* @brief Checks that a set holds exactly the given integers, in any order. @param set The set to check. @param values The values it should hold. @param count How many values there are. @param label A short description used in the assertion output. @attention Membership rather than index, because a set's indices are only stable until the next removal. */ static void check_holds_exactly(const set_t* set, const int* values, size_t count, const char* label) { int ok = (set_size(set) == count); for (size_t i = 0; ok && i < count; ++i) { ok = set_contains(set, &values[i]); } CHECK_TRUE(ok, label); } /* @brief Reports whether a set holds a given integer. @param set The set to search. @param value The value to look for. @return 1 if present, 0 otherwise. */ static int holds(const set_t* set, int value) { return set_contains(set, &value); } // --------------------------------------------------------------------------- // Lifecycle // --------------------------------------------------------------------------- static void set_create_basic(void) { set_t* set = set_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(set, "set_create returns a set"); CHECK_EQ_SIZE(set_size(set), 0, "a new set is empty"); CHECK_EQ_SIZE(set_capacity(set), DEFAULT_CAPACITY, "a new set has the default capacity"); CHECK_EQ_SIZE(set_element_size(set), sizeof(int), "element size is what was asked for"); CHECK_EQ_INT(set_is_empty(set), 1, "set_is_empty reports 1 on a new set"); CHECK_PTR_NULL(set_get_destructor(set), "a new set has no destructor"); CHECK_PTR_NULL(set_get_comparator(set), "a new set has no comparator, so equality falls back to memcmp"); CHECK_PTR_NOT_NULL(set_as_c_array(set), "an empty set still has a data array"); set_destroy(&set); } static void set_create_rejects_zero_element_size(void) { CHECK_PTR_NULL(set_create(0), "set_create(0) is refused"); } static void set_create_rejects_overflow(void) { CHECK_PTR_NULL(set_create(SIZE_MAX), "an element size of SIZE_MAX is refused"); CHECK_PTR_NULL(set_create(SIZE_MAX / 5), "an element size that cannot hold the initial capacity is refused"); } static void set_destroy_semantics(void) { CHECK_EQ_INT(set_destroy(NULL), -1, "destroying through a NULL pointer is an error"); set_t* already_null = NULL; CHECK_EQ_INT(set_destroy(&already_null), 0, "destroying an already-NULL set succeeds"); set_t* set = set_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(set, "set_create returns a set"); CHECK_EQ_INT(fill_ints(set, 4), 0, "the set fills"); CHECK_EQ_INT(set_destroy(&set), 0, "destroy succeeds"); CHECK_PTR_NULL(set, "destroy NULLs the caller's pointer"); CHECK_EQ_INT(set_destroy(&set), 0, "a second destroy is harmless"); } static void set_null_argument_matrix(void) { int value = 7; char out[sizeof(int)]; set_t* other = set_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(other, "set_create returns a set"); CHECK_EQ_INT(fill_ints(other, 3), 0, "the set fills"); // As with vector.h, the size_t getters conflate "invalid set" with "zero" // and set_is_empty() conflates it with "empty". Both are documented CHECK_EQ_SIZE(set_size(NULL), 0, "size of a NULL set is 0"); CHECK_EQ_SIZE(set_capacity(NULL), 0, "capacity of a NULL set is 0"); CHECK_EQ_SIZE(set_element_size(NULL), 0, "element size of a NULL set is 0"); CHECK_EQ_INT(set_is_empty(NULL), 1, "a NULL set reports as empty"); CHECK_PTR_NULL(set_get_const(NULL, 0), "get_const on a NULL set is NULL"); CHECK_PTR_NULL(set_as_c_array(NULL), "the array view of a NULL set is NULL"); CHECK_PTR_NULL(set_get_destructor(NULL), "the destructor of a NULL set is NULL"); CHECK_PTR_NULL(set_get_comparator(NULL), "the comparator of a NULL set is NULL"); CHECK_EQ_INT(set_insert(NULL, &value), -1, "insert on a NULL set fails"); CHECK_EQ_INT(set_insert(other, NULL), -1, "inserting a NULL element fails"); CHECK_EQ_SIZE(set_find(NULL, &value), SET_NPOS, "find on a NULL set is SET_NPOS"); CHECK_EQ_SIZE(set_find(other, NULL), SET_NPOS, "finding a NULL element is SET_NPOS"); // set_contains() folds every failure into 0 so that it is safe in an if CHECK_EQ_INT(set_contains(NULL, &value), 0, "contains on a NULL set is 0, not an error code"); CHECK_EQ_INT(set_contains(other, NULL), 0, "containing a NULL element is 0, not an error code"); CHECK_EQ_INT(set_remove(NULL, &value), -1, "remove on a NULL set fails"); CHECK_EQ_INT(set_remove(other, NULL), -1, "removing a NULL element fails"); CHECK_EQ_INT(set_remove_at(NULL, 0), -1, "remove_at on a NULL set fails"); CHECK_EQ_INT(set_take(NULL, &value, out), -1, "take on a NULL set fails"); CHECK_EQ_INT(set_take(other, NULL, out), -1, "taking a NULL element fails"); CHECK_EQ_INT(set_take(other, &value, NULL), -1, "taking into a NULL out fails"); CHECK_EQ_INT(set_take_at(NULL, 0, out), -1, "take_at on a NULL set fails"); CHECK_EQ_INT(set_take_at(other, 0, NULL), -1, "take_at into a NULL out fails"); CHECK_EQ_INT(set_dedupe(NULL), -1, "dedupe on a NULL set fails"); CHECK_EQ_INT(set_clear(NULL), -1, "clear on a NULL set fails"); CHECK_EQ_INT(set_reserve(NULL, 32), -1, "reserve on a NULL set fails"); CHECK_EQ_INT(set_grow(NULL), -1, "grow on a NULL set fails"); CHECK_EQ_INT(set_prune(NULL), -1, "prune on a NULL set fails"); CHECK_EQ_INT(set_set_destructor(NULL, dtest_count_destructor), -1, "set_destructor on a NULL set fails"); CHECK_EQ_INT(set_set_comparator(NULL, cmp_int), -1, "set_comparator on a NULL set fails"); CHECK_EQ_INT(set_is_aliased(NULL, &value), 0, "is_aliased on a NULL set is 0"); CHECK_EQ_INT(set_elements_equal(NULL, &value, &value), 0, "elements_equal on a NULL set is 0"); CHECK_EQ_INT(set_elements_equal(other, NULL, &value), 0, "elements_equal with a NULL left side is 0"); CHECK_EQ_INT(set_elements_equal(other, &value, NULL), 0, "elements_equal with a NULL right side is 0"); set_t* null_src = NULL; CHECK_EQ_INT(set_move(NULL, &null_src), -1, "move into a NULL destination fails"); CHECK_EQ_INT(set_move(other, NULL), -1, "move from a NULL source pointer fails"); CHECK_EQ_INT(set_move(other, &null_src), -1, "move from a NULL source set fails"); CHECK_PTR_NULL(set_deep_copy(NULL), "deep copying a NULL set is NULL"); CHECK_EQ_INT(set_is_compatible(NULL, other), 0, "a NULL set is compatible with nothing"); CHECK_EQ_INT(set_is_compatible(other, NULL), 0, "nothing is compatible with a NULL set"); CHECK_PTR_NULL(set_union(NULL, other), "the union with a NULL set is NULL"); CHECK_PTR_NULL(set_intersection(other, NULL), "the intersection with a NULL set is NULL"); CHECK_PTR_NULL(set_difference(NULL, NULL), "the difference of two NULL sets is NULL"); CHECK_EQ_INT(set_is_subset(NULL, other), 0, "is_subset with a NULL set is 0, never negative"); CHECK_EQ_INT(set_is_equal(other, NULL), 0, "is_equal with a NULL set is 0, never negative"); set_destroy(&other); } // --------------------------------------------------------------------------- // Capacity // --------------------------------------------------------------------------- static void set_reserve_grows_only(void) { set_t* set = set_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(set, "set_create returns a set"); CHECK_EQ_INT(set_reserve(set, 0), 0, "reserving zero succeeds"); CHECK_EQ_SIZE(set_capacity(set), DEFAULT_CAPACITY, "reserving zero does not shrink"); CHECK_EQ_INT(set_reserve(set, DEFAULT_CAPACITY - 1), 0, "reserving less than the capacity succeeds"); CHECK_EQ_SIZE(set_capacity(set), DEFAULT_CAPACITY, "reserving less does not shrink"); CHECK_EQ_INT(set_reserve(set, 128), 0, "reserving more succeeds"); CHECK_EQ_SIZE(set_capacity(set), 128, "reserving more raises the capacity exactly"); CHECK_EQ_SIZE(set_size(set), 0, "reserving does not change the size"); set_destroy(&set); } static void set_reserve_overflow_rejected(void) { set_t* set = set_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(set, "set_create returns a set"); CHECK_EQ_INT(fill_ints(set, 5), 0, "the set fills"); size_t capacity_before = set_capacity(set); CHECK_EQ_INT(set_reserve(set, SIZE_MAX), -1, "reserving SIZE_MAX is refused"); CHECK_EQ_SIZE(set_capacity(set), capacity_before, "a refused reserve leaves the capacity alone"); CHECK_EQ_SIZE(set_size(set), 5, "a refused reserve leaves the size alone"); int extra = 99; CHECK_EQ_INT(set_insert(set, &extra), 0, "the set is still usable afterwards"); CHECK_EQ_INT(holds(set, 99), 1, "the insert landed"); set_destroy(&set); } static void set_grow_doubling(void) { set_t* set = set_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(set, "set_create returns a set"); CHECK_EQ_INT(fill_ints(set, DEFAULT_CAPACITY), 0, "the set fills to capacity"); CHECK_EQ_SIZE(set_capacity(set), DEFAULT_CAPACITY, "filling to capacity does not grow"); int value = DEFAULT_CAPACITY; CHECK_EQ_INT(set_insert(set, &value), 0, "the insert past capacity succeeds"); CHECK_EQ_SIZE(set_capacity(set), DEFAULT_CAPACITY * 2, "capacity doubles"); CHECK_EQ_SIZE(set_size(set), (size_t)DEFAULT_CAPACITY + 1, "the insert landed"); // Everything must survive the reallocation, which for a set means membership int ok = 1; for (int i = 0; i <= DEFAULT_CAPACITY; ++i) { ok = ok && holds(set, i); } CHECK_TRUE(ok, "every element survives the reallocation"); set_destroy(&set); } static void set_prune_shrink_to_fit(void) { set_t* set = set_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(set, "set_create returns a set"); CHECK_EQ_INT(fill_ints(set, 3), 0, "the set fills"); CHECK_EQ_INT(set_prune(set), 0, "prune succeeds"); CHECK_EQ_SIZE(set_capacity(set), 3, "prune drops the capacity to the size"); CHECK_EQ_INT(holds(set, 0) && holds(set, 1) && holds(set, 2), 1, "prune preserves the contents"); CHECK_EQ_INT(set_prune(set), 0, "pruning an already-tight set succeeds"); CHECK_EQ_SIZE(set_capacity(set), 3, "pruning an already-tight set changes nothing"); CHECK_EQ_INT(set_clear(set), 0, "clear succeeds"); CHECK_EQ_INT(set_prune(set), 0, "pruning an empty set succeeds"); CHECK_EQ_SIZE(set_capacity(set), 1, "capacity never drops below 1"); int value = 42; CHECK_EQ_INT(set_insert(set, &value), 0, "a pruned set still accepts elements"); set_destroy(&set); } // --------------------------------------------------------------------------- // Insertion and uniqueness // --------------------------------------------------------------------------- static void set_insert_tristate(void) { set_t* set = set_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(set, "set_create returns a set"); int value = 5; CHECK_EQ_INT(set_insert(set, &value), 0, "inserting a new element returns 0"); CHECK_EQ_SIZE(set_size(set), 1, "the element was added"); // A return of 1 means the value was NOT stored, which matters when it owns memory CHECK_EQ_INT(set_insert(set, &value), 1, "inserting an equal element returns 1"); CHECK_EQ_SIZE(set_size(set), 1, "the duplicate did not change the size"); int other = 6; CHECK_EQ_INT(set_insert(set, &other), 0, "a different element is still accepted"); CHECK_EQ_SIZE(set_size(set), 2, "the second element was added"); CHECK_EQ_INT(set_insert(set, NULL), -1, "inserting NULL returns the error code, not 1"); set_destroy(&set); } static void set_insert_uniqueness_memcmp(void) { set_t* set = set_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(set, "set_create returns a set"); static const int values[] = { 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5 }; int added = 0; int rejected = 0; for (size_t i = 0; i < sizeof(values) / sizeof(values[0]); ++i) { int r = set_insert(set, &values[i]); if (r == 0) { ++added; } else if (r == 1) { ++rejected; } } CHECK_EQ_INT(added, 7, "the seven distinct values were added"); CHECK_EQ_INT(rejected, 4, "the four repeats were rejected"); CHECK_EQ_SIZE(set_size(set), 7, "the set holds only the distinct values"); static const int distinct[] = { 1, 2, 3, 4, 5, 6, 9 }; check_holds_exactly(set, distinct, sizeof(distinct) / sizeof(distinct[0]), "the set holds exactly the distinct values"); CHECK_EQ_INT(holds(set, 7), 0, "a value that was never inserted is absent"); set_destroy(&set); } static void set_insert_struct_padding_trap(void) { // Two structs with identical members but different padding bytes. Without a // comparator the set compares raw bytes, padding included, and sees two // different elements. This is exactly the trap the header warns about tagged_t zeroed; memset(&zeroed, 0x00, sizeof(zeroed)); zeroed.tag = 'x'; zeroed.value = 42; tagged_t dirty; memset(&dirty, 0xFF, sizeof(dirty)); dirty.tag = 'x'; dirty.value = 42; CHECK_EQ_INT(cmp_tagged(&zeroed, &dirty), 0, "the two structs have identical members"); int images_differ = (memcmp(&zeroed, &dirty, sizeof(tagged_t)) != 0); CHECK_TRUE(images_differ, "the padding bytes make the two byte images differ"); if (images_differ) { set_t* raw = set_create(sizeof(tagged_t)); REQUIRE_PTR_NOT_NULL(raw, "set_create returns a set"); CHECK_EQ_INT(set_insert(raw, &zeroed), 0, "the first struct is added"); CHECK_EQ_INT(set_insert(raw, &dirty), 0, "the byte-compared set treats the second as a new element"); CHECK_EQ_SIZE(set_size(raw), 2, "uniqueness was lost to the padding"); set_destroy(&raw); } // A comparator that looks at the members instead restores uniqueness set_t* compared = set_create(sizeof(tagged_t)); REQUIRE_PTR_NOT_NULL(compared, "set_create returns a set"); CHECK_EQ_INT(set_set_comparator(compared, cmp_tagged), 0, "the comparator is set"); CHECK_EQ_INT(set_insert(compared, &zeroed), 0, "the first struct is added"); CHECK_EQ_INT(set_insert(compared, &dirty), 1, "the comparator recognises the second as a duplicate"); CHECK_EQ_SIZE(set_size(compared), 1, "uniqueness holds with a comparator"); set_destroy(&compared); } static void set_insert_pointer_elements_compare_pointers(void) { char* first = dtest_dup("hello"); char* second = dtest_dup("hello"); REQUIRE_PTR_NOT_NULL(first, "the first string is duplicated"); REQUIRE_PTR_NOT_NULL(second, "the second string is duplicated"); CHECK_PTR_NE(first, second, "the two strings live at different addresses"); // Without a comparator, a set of char* compares the pointers themselves, so // two buffers holding the same text are two different elements set_t* by_pointer = set_create(sizeof(char*)); REQUIRE_PTR_NOT_NULL(by_pointer, "set_create returns a set"); CHECK_EQ_INT(set_insert(by_pointer, &first), 0, "the first pointer is added"); CHECK_EQ_INT(set_insert(by_pointer, &second), 0, "the second pointer is added as well"); CHECK_EQ_SIZE(set_size(by_pointer), 2, "the byte-compared set holds both pointers"); set_destroy(&by_pointer); set_t* by_content = set_create(sizeof(char*)); REQUIRE_PTR_NOT_NULL(by_content, "set_create returns a set"); CHECK_EQ_INT(set_set_comparator(by_content, cmp_str), 0, "the string comparator is set"); CHECK_EQ_INT(set_insert(by_content, &first), 0, "the first pointer is added"); CHECK_EQ_INT(set_insert(by_content, &second), 1, "the comparator recognises the same text as a duplicate"); CHECK_EQ_SIZE(set_size(by_content), 1, "the content-compared set holds one element"); set_destroy(&by_content); free(first); free(second); } static void set_insert_aliased_no_destructor(void) { set_t* set = set_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(set, "set_create returns a set"); CHECK_EQ_INT(fill_ints(set, 3), 0, "the set fills"); // An element-aligned pointer is by definition already in the set, so a // consistent comparator reports it as a duplicate without touching anything CHECK_EQ_INT(set_insert(set, set_get_const(set, 0)), 1, "inserting an element of the set itself reports a duplicate"); CHECK_EQ_SIZE(set_size(set), 3, "nothing was added"); set_destroy(&set); // A pointer partway into an element slips past the duplicate check and // reaches the copy. Four raw bytes per element keeps the result exact set_t* quads = set_create(sizeof(quad_t)); REQUIRE_PTR_NOT_NULL(quads, "set_create returns a set"); quad_t first = { { 'a', 'b', 'c', 'd' } }; quad_t second = { { 'e', 'f', 'g', 'h' } }; CHECK_EQ_INT(set_insert(quads, &first), 0, "the first quad is added"); CHECK_EQ_INT(set_insert(quads, &second), 0, "the second quad is added"); const char* interior = (const char*)set_as_c_array(quads) + 2; CHECK_EQ_INT(set_is_aliased(quads, interior), 1, "the interior pointer is recognised as aliased"); CHECK_EQ_INT(set_insert(quads, interior), 0, "an interior pointer is not seen as a duplicate and is copied in"); CHECK_EQ_SIZE(set_size(quads), 3, "the copy landed"); const quad_t* added = (const quad_t*)set_get_const(quads, 2); REQUIRE_PTR_NOT_NULL(added, "the new element is readable"); CHECK_MEM_EQ(added->b, "cdef", 4, "the copy holds the four bytes the interior pointer spanned"); set_destroy(&quads); } static void set_insert_aliased_with_broken_comparator(void) { // A comparator that reports nothing as equal makes every insert land, // including an element-aligned pointer into the set's own data. The value // has to be followed through the reallocation, which is the whole reason // set_insert() saves the byte offset before growing set_t* set = set_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(set, "set_create returns a set"); CHECK_EQ_INT(set_set_comparator(set, cmp_never_equal), 0, "the broken comparator is set"); int seed = 1234; CHECK_EQ_INT(set_insert(set, &seed), 0, "the seed element is added"); while (set_size(set) < set_capacity(set)) { CHECK_TRUE(set_insert(set, &seed) == 0, "the broken comparator lets duplicates in"); } CHECK_EQ_SIZE(set_size(set), set_capacity(set), "the set is full, so the next insert must grow"); CHECK_EQ_INT(set_insert(set, set_get_const(set, 0)), 0, "inserting an aliased element across a growth succeeds"); CHECK_EQ_SIZE(set_capacity(set), (size_t)DEFAULT_CAPACITY * 2, "the insert grew the set"); const int* copied = (const int*)set_get_const(set, set_size(set) - 1); REQUIRE_PTR_NOT_NULL(copied, "the new element is readable"); CHECK_EQ_INT(*copied, 1234, "the aliased value survived the reallocation"); set_destroy(&set); } static void set_insert_aliased_with_destructor_rejected(void) { set_t* set = set_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(set, "set_create returns a set"); CHECK_EQ_INT(set_set_destructor(set, dtest_count_destructor), 0, "the destructor is set"); CHECK_EQ_INT(fill_ints(set, 3), 0, "the set fills"); // The destructor-plus-aliased rejection sits above the duplicate check, so // this reports the error code rather than the 1 that the same pointer would // get on a set without a destructor. Pinned, as the docs list both outcomes // without saying which one wins dtest_reset_destructor_calls(); CHECK_EQ_INT(set_insert(set, set_get_const(set, 0)), -1, "an aliased element on a set with a destructor is refused"); CHECK_EQ_INT(dtest_destructor_calls, 0, "the refusal destroyed nothing"); CHECK_EQ_SIZE(set_size(set), 3, "the refusal changed nothing"); dtest_reset_destructor_calls(); set_destroy(&set); } // --------------------------------------------------------------------------- // Lookup // --------------------------------------------------------------------------- static void set_find_and_contains(void) { set_t* set = set_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(set, "set_create returns a set"); int needle = 5; CHECK_EQ_SIZE(set_find(set, &needle), SET_NPOS, "finding anything in an empty set is SET_NPOS"); CHECK_EQ_INT(set_contains(set, &needle), 0, "an empty set contains nothing"); CHECK_EQ_INT(fill_ints(set, 8), 0, "the set fills"); size_t index = set_find(set, &needle); CHECK_TRUE(index != SET_NPOS, "a present element is found"); CHECK_TRUE(index < set_size(set), "the returned index is in range"); const int* found = (const int*)set_get_const(set, index); REQUIRE_PTR_NOT_NULL(found, "the found index is readable"); CHECK_EQ_INT(*found, 5, "the index really points at the element that was looked for"); CHECK_EQ_INT(set_contains(set, &needle), 1, "contains agrees"); int absent = 99; CHECK_EQ_SIZE(set_find(set, &absent), SET_NPOS, "an absent element is SET_NPOS"); CHECK_EQ_INT(set_contains(set, &absent), 0, "contains agrees"); set_destroy(&set); } // --------------------------------------------------------------------------- // Removal // --------------------------------------------------------------------------- static void set_remove_tristate(void) { set_t* set = set_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(set, "set_create returns a set"); CHECK_EQ_INT(fill_ints(set, 5), 0, "the set fills"); int present = 2; CHECK_EQ_INT(set_remove(set, &present), 0, "removing a present element returns 0"); CHECK_EQ_SIZE(set_size(set), 4, "the element is gone"); CHECK_EQ_INT(holds(set, 2), 0, "the element really is gone"); CHECK_EQ_INT(set_remove(set, &present), 1, "removing it again reports that it was not there"); CHECK_EQ_SIZE(set_size(set), 4, "the second removal changed nothing"); int absent = 42; CHECK_EQ_INT(set_remove(set, &absent), 1, "removing something that was never there returns 1"); set_destroy(&set); } static void set_remove_at_swap_with_last(void) { set_t* set = set_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(set, "set_create returns a set"); CHECK_EQ_INT(fill_ints(set, 3), 0, "the set fills"); // Removal is O(1) because the last element is moved into the freed slot, // which is why an index is only good until the next removal int last_value = *(const int*)set_get_const(set, set_size(set) - 1); CHECK_EQ_INT(set_remove_at(set, 0), 0, "removing at index 0 succeeds"); CHECK_EQ_SIZE(set_size(set), 2, "the size dropped by one"); const int* now_at_zero = (const int*)set_get_const(set, 0); REQUIRE_PTR_NOT_NULL(now_at_zero, "index 0 is still readable"); CHECK_EQ_INT(*now_at_zero, last_value, "the last element was moved into the freed slot"); // Removing the last index needs no move at all int survivor = *(const int*)set_get_const(set, 0); CHECK_EQ_INT(set_remove_at(set, set_size(set) - 1), 0, "removing the last index succeeds"); CHECK_EQ_SIZE(set_size(set), 1, "the size dropped again"); CHECK_EQ_INT(*(const int*)set_get_const(set, 0), survivor, "removing the last index left index 0 alone"); CHECK_EQ_INT(set_remove_at(set, set_size(set)), -1, "remove_at index == size is refused"); set_destroy(&set); } static void set_remove_aliased_element(void) { set_t* set = set_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(set, "set_create returns a set"); CHECK_EQ_INT(fill_ints(set, 4), 0, "the set fills"); // set_remove() resolves the index before destroying anything, so a pointer // into the set's own data cannot be left dangling underneath it int doomed = *(const int*)set_get_const(set, 1); CHECK_EQ_INT(set_remove(set, set_get_const(set, 1)), 0, "removing via a pointer into the set's own data succeeds"); CHECK_EQ_SIZE(set_size(set), 3, "the element is gone"); CHECK_EQ_INT(holds(set, doomed), 0, "the right element was removed"); set_destroy(&set); } static void set_removal_during_iteration(void) { set_t* correct = set_create(sizeof(int)); set_t* naive = set_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(correct, "set_create returns a set"); REQUIRE_PTR_NOT_NULL(naive, "set_create returns a set"); CHECK_EQ_INT(fill_ints(correct, 10), 0, "the first set fills"); CHECK_EQ_INT(fill_ints(naive, 10), 0, "the second set fills"); // The documented pattern: do not advance the index after a removal, because // the element that was last has just been moved into the slot you are on size_t i = 0; while (i < set_size(correct)) { const int* value = (const int*)set_get_const(correct, i); if (value && *value % 2 == 0) { CHECK_TRUE(set_remove_at(correct, i) == 0, "the removal succeeds"); } else { ++i; } } CHECK_EQ_SIZE(set_size(correct), 5, "the correct loop removed all five even numbers"); int correct_kept_evens = 0; for (size_t j = 0; j < set_size(correct); ++j) { const int* value = (const int*)set_get_const(correct, j); if (value && *value % 2 == 0) { correct_kept_evens = 1; } } CHECK_EQ_INT(correct_kept_evens, 0, "no even number was missed"); CHECK_EQ_INT(holds(correct, 1) && holds(correct, 3) && holds(correct, 5) && holds(correct, 7) && holds(correct, 9), 1, "every odd number is still there"); // The naive loop advances after a removal and therefore steps over whatever // was swapped in. With ten elements it leaves six behind, one of them even for (size_t j = 0; j < set_size(naive); ++j) { const int* value = (const int*)set_get_const(naive, j); if (value && *value % 2 == 0) { CHECK_TRUE(set_remove_at(naive, j) == 0, "the removal succeeds"); } } CHECK_TRUE(set_size(naive) > 5, "the naive loop failed to remove everything it should have"); int naive_kept_evens = 0; for (size_t j = 0; j < set_size(naive); ++j) { const int* value = (const int*)set_get_const(naive, j); if (value && *value % 2 == 0) { naive_kept_evens = 1; } } CHECK_EQ_INT(naive_kept_evens, 1, "the naive loop skipped at least one even number"); set_destroy(&naive); set_destroy(&correct); } // --------------------------------------------------------------------------- // Taking elements out // --------------------------------------------------------------------------- static void set_take_at_basic(void) { set_t* set = set_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(set, "set_create returns a set"); CHECK_EQ_INT(fill_ints(set, 4), 0, "the set fills"); int expected = *(const int*)set_get_const(set, 1); int last_value = *(const int*)set_get_const(set, set_size(set) - 1); int taken = -1; CHECK_EQ_INT(set_take_at(set, 1, &taken), 0, "take_at succeeds"); CHECK_EQ_INT(taken, expected, "take_at hands over the element that was at the index"); CHECK_EQ_SIZE(set_size(set), 3, "take_at shrinks the size by one"); CHECK_EQ_INT(holds(set, expected), 0, "the taken element is no longer in the set"); // As with set_remove_at(), the last element fills the hole CHECK_EQ_INT(*(const int*)set_get_const(set, 1), last_value, "the last element was moved into the freed slot"); CHECK_EQ_INT(set_take_at(set, set_size(set), &taken), -1, "take_at index == size is refused"); CHECK_EQ_INT(set_take_at(set, 0, NULL), -1, "take_at with a NULL out is refused"); CHECK_EQ_SIZE(set_size(set), 3, "the refused takes changed nothing"); set_destroy(&set); } static void set_take_rejects_aliased_out(void) { set_t* set = set_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(set, "set_create returns a set"); CHECK_EQ_INT(fill_ints(set, 3), 0, "the set fills"); // A set has no mutable element access at all, so the illegal argument has to // be built by hand. That is the point: this is what the guard exists to catch void* inside = (void*)set_get_const(set, 1); CHECK_EQ_INT(set_take_at(set, 0, inside), -1, "take_at into the set's own data is refused"); CHECK_EQ_SIZE(set_size(set), 3, "the refused take changed nothing"); int present = 0; CHECK_EQ_INT(set_take(set, &present, inside), -1, "take into the set's own data is refused"); CHECK_EQ_INT(holds(set, 0), 1, "the element is still in the set"); // set_is_aliased() bounds on capacity, so the unused spare room counts too char* spare = (char*)(void*)((const char*)set_as_c_array(set) + (5 * set_element_size(set))); CHECK_EQ_INT(set_is_aliased(set, spare), 1, "the unused spare capacity counts as aliased"); CHECK_EQ_INT(set_take_at(set, 0, spare), -1, "take_at into the spare capacity is refused"); set_destroy(&set); } static void set_take_rejects_aliased_out_before_lookup(void) { set_t* set = set_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(set, "set_create returns a set"); CHECK_EQ_INT(fill_ints(set, 3), 0, "the set fills"); // set_take() validates out before it resolves the element, so an absent // element with an aliased out reports the error rather than the "not in the // set" 1. Pinned, because the ordering is what decides which one you get void* inside = (void*)set_get_const(set, 0); int absent = 99; CHECK_EQ_INT(set_take(set, &absent, inside), -1, "an aliased out is rejected even when the element is absent"); CHECK_EQ_SIZE(set_size(set), 3, "nothing changed"); int out = 0; CHECK_EQ_INT(set_take(set, &absent, &out), 1, "with a legal out the same absent element reports 1"); set_destroy(&set); } static void set_take_tristate(void) { set_t* set = set_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(set, "set_create returns a set"); CHECK_EQ_INT(fill_ints(set, 3), 0, "the set fills"); int out = -12345; int absent = 77; CHECK_EQ_INT(set_take(set, &absent, &out), 1, "taking an absent element returns 1"); CHECK_EQ_INT(out, -12345, "a failed take leaves the output buffer untouched"); CHECK_EQ_SIZE(set_size(set), 3, "a failed take changes nothing"); int present = 1; CHECK_EQ_INT(set_take(set, &present, &out), 0, "taking a present element returns 0"); CHECK_EQ_INT(out, 1, "the value was handed over"); CHECK_EQ_SIZE(set_size(set), 2, "the element is gone"); CHECK_EQ_INT(holds(set, 1), 0, "the element really is gone"); set_destroy(&set); } static void set_take_element_may_alias(void) { set_t* set = set_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(set, "set_create returns a set"); CHECK_EQ_INT(fill_ints(set, 4), 0, "the set fills"); // The element may point into the set's own data even though out may not. // The index is resolved before anything is copied, so it cannot dangle int expected = *(const int*)set_get_const(set, 2); int out = 0; CHECK_EQ_INT(set_take(set, set_get_const(set, 2), &out), 0, "taking via a pointer into the set's own data succeeds"); CHECK_EQ_INT(out, expected, "the right element was handed over"); CHECK_EQ_SIZE(set_size(set), 3, "the element is gone"); CHECK_EQ_INT(holds(set, expected), 0, "the element really is gone"); set_destroy(&set); } static void set_take_out_equals_key(void) { set_t* set = set_create(sizeof(char*)); REQUIRE_PTR_NOT_NULL(set, "set_create returns a set"); CHECK_EQ_INT(set_set_comparator(set, cmp_str_ci), 0, "the case-insensitive comparator is set"); char* stored = dtest_dup("ALPHA"); REQUIRE_PTR_NOT_NULL(stored, "the stored string is duplicated"); CHECK_EQ_INT(set_insert(set, &stored), 0, "the string is added"); // Passing the same buffer as both the search key and the output is legal, // as neither points into the set. The key is simply overwritten by the // stored element, which the caller then owns char* needle = dtest_dup("alpha"); REQUIRE_PTR_NOT_NULL(needle, "the search key is duplicated"); char* slot = needle; CHECK_EQ_INT(set_take(set, &slot, &slot), 0, "taking with out and the key at the same address succeeds"); CHECK_EQ_STR(slot, "ALPHA", "the slot now holds the stored element, not the key"); CHECK_PTR_EQ(slot, stored, "the caller received the very buffer the set was holding"); CHECK_EQ_SIZE(set_size(set), 0, "the set is empty"); free(slot); // The element the set handed over free(needle); // The key that was overwritten, still ours to free set_destroy(&set); } // --------------------------------------------------------------------------- // Comparators // --------------------------------------------------------------------------- static void set_comparator_get_set(void) { set_t* set = set_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(set, "set_create returns a set"); CHECK_PTR_NULL(set_get_comparator(set), "a fresh set has no comparator"); CHECK_EQ_INT(set_set_comparator(set, cmp_int), 0, "setting a comparator succeeds"); CHECK_TRUE(set_get_comparator(set) == cmp_int, "the comparator round-trips"); CHECK_EQ_INT(set_set_comparator(set, NULL), 0, "setting a NULL comparator succeeds"); CHECK_PTR_NULL(set_get_comparator(set), "a NULL comparator reverts to the memcmp fallback"); // With no comparator, equality is a raw byte comparison int value = 5; int same = 5; int different = 6; CHECK_EQ_INT(set_elements_equal(set, &value, &same), 1, "identical bytes compare equal"); CHECK_EQ_INT(set_elements_equal(set, &value, &different), 0, "different bytes compare unequal"); set_destroy(&set); } static void set_comparator_equality_used(void) { set_t* set = set_create(sizeof(char*)); REQUIRE_PTR_NOT_NULL(set, "set_create returns a set"); CHECK_EQ_INT(set_set_comparator(set, cmp_str_ci), 0, "the case-insensitive comparator is set"); char* upper = dtest_dup("Alpha"); char* lower = dtest_dup("ALPHA"); char* other = dtest_dup("bravo"); REQUIRE_PTR_NOT_NULL(upper, "the first string is duplicated"); REQUIRE_PTR_NOT_NULL(lower, "the second string is duplicated"); REQUIRE_PTR_NOT_NULL(other, "the third string is duplicated"); CHECK_EQ_INT(set_insert(set, &upper), 0, "the first spelling is added"); CHECK_EQ_INT(set_insert(set, &lower), 1, "a different spelling of the same word is a duplicate"); CHECK_EQ_INT(set_insert(set, &other), 0, "a genuinely different word is added"); CHECK_EQ_SIZE(set_size(set), 2, "the set holds two words"); CHECK_EQ_INT(set_contains(set, &lower), 1, "contains uses the same rule"); set_destroy(&set); free(upper); free(lower); free(other); } static void set_comparator_only_zero_matters(void) { set_t* set = set_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(set, "set_create returns a set"); // A comparator that never returns a negative value is still a valid one, // because only a result of 0 is ever consulted CHECK_EQ_INT(set_set_comparator(set, cmp_int_positive_only), 0, "the comparator is set"); CHECK_TRUE(cmp_int_positive_only(&(int){ 1 }, &(int){ 2 }) > 0, "the comparator never goes negative"); static const int values[] = { 4, 8, 15, 16, 23, 42 }; CHECK_EQ_INT(insert_all(set, values, sizeof(values) / sizeof(values[0])), 0, "the set fills"); int duplicate = 15; CHECK_EQ_INT(set_insert(set, &duplicate), 1, "a duplicate is still detected"); check_holds_exactly(set, values, sizeof(values) / sizeof(values[0]), "the set holds exactly the inserted values"); int absent = 99; CHECK_EQ_INT(set_contains(set, &absent), 0, "an absent value is still absent"); set_destroy(&set); } static void set_comparator_find_argument_order(void) { set_t* set = set_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(set, "set_create returns a set"); CHECK_EQ_INT(set_set_comparator(set, cmp_recording), 0, "the recording comparator is set"); CHECK_EQ_INT(fill_ints(set, 4), 0, "the set fills"); // Looking for something absent runs the comparator against every element, // so the last call is the one against the last slot. That pins the order as // (stored element, needle), which is what an asymmetric comparator needs recorded_lhs = NULL; recorded_rhs = NULL; int absent = 99; CHECK_EQ_SIZE(set_find(set, &absent), SET_NPOS, "the absent element is not found"); CHECK_PTR_EQ(recorded_lhs, set_get_const(set, set_size(set) - 1), "the first argument is the stored element"); CHECK_PTR_EQ(recorded_rhs, &absent, "the second argument is the element being looked for"); set_destroy(&set); } static void set_dedupe_after_loosening(void) { set_t* set = set_create(sizeof(char*)); REQUIRE_PTR_NOT_NULL(set, "set_create returns a set"); // Three distinct buffers. With no comparator the set compares the pointers, // so all three go in even though two of them spell the same word char* a_upper = dtest_dup("A"); char* a_lower = dtest_dup("a"); char* b_upper = dtest_dup("B"); REQUIRE_PTR_NOT_NULL(a_upper, "the first string is duplicated"); REQUIRE_PTR_NOT_NULL(a_lower, "the second string is duplicated"); REQUIRE_PTR_NOT_NULL(b_upper, "the third string is duplicated"); CHECK_EQ_INT(set_insert(set, &a_upper), 0, "\"A\" is added"); CHECK_EQ_INT(set_insert(set, &a_lower), 0, "\"a\" is added, as the pointers differ"); CHECK_EQ_INT(set_insert(set, &b_upper), 0, "\"B\" is added"); CHECK_EQ_SIZE(set_size(set), 3, "the byte-compared set holds all three"); // Loosening the rule on a populated set leaves duplicates behind until dedupe CHECK_EQ_INT(set_set_comparator(set, cmp_str_ci), 0, "the comparator is loosened"); CHECK_EQ_INT(set_set_destructor(set, dtest_string_destructor), 0, "a destructor is set, so dropped duplicates are freed"); CHECK_EQ_SIZE(set_size(set), 3, "loosening the comparator does not remove anything on its own"); dtest_reset_destructor_calls(); CHECK_EQ_INT(set_dedupe(set), 0, "dedupe succeeds"); CHECK_EQ_INT(dtest_destructor_calls, 1, "dedupe freed exactly the one dropped duplicate"); CHECK_EQ_SIZE(set_size(set), 2, "the set is unique again"); // Of any group of equal elements, the lowest index survives, so "A" is kept CHECK_EQ_INT(set_contains(set, &a_upper), 1, "a spelling of the first word is still there"); CHECK_EQ_STR(*(char* const*)set_get_const(set, 0), "A", "the lowest-index member of the group was kept"); CHECK_EQ_INT(set_contains(set, &b_upper), 1, "the unrelated word was left alone"); dtest_reset_destructor_calls(); CHECK_EQ_INT(set_destroy(&set), 0, "destroy succeeds"); CHECK_EQ_INT(dtest_destructor_calls, 2, "destroy freed the two survivors"); // Nothing is freed by hand here. Once the destructor was set, the set owned // all three buffers: dedupe freed a_lower and destroy freed the other two } static void set_dedupe_edge_cases(void) { set_t* empty = set_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(empty, "set_create returns a set"); CHECK_EQ_INT(set_dedupe(empty), 0, "deduping an empty set succeeds"); CHECK_EQ_SIZE(set_size(empty), 0, "it is still empty"); int value = 1; CHECK_EQ_INT(set_insert(empty, &value), 0, "one element is added"); CHECK_EQ_INT(set_dedupe(empty), 0, "deduping a single-element set succeeds"); CHECK_EQ_SIZE(set_size(empty), 1, "the element is still there"); set_destroy(&empty); // A set that only ever went through set_insert() is already unique, so // dedupe must be a no-op on it set_t* unique = set_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(unique, "set_create returns a set"); CHECK_EQ_INT(fill_ints(unique, 6), 0, "the set fills"); CHECK_EQ_INT(set_dedupe(unique), 0, "dedupe succeeds"); CHECK_EQ_SIZE(set_size(unique), 6, "an already-unique set is left alone"); set_destroy(&unique); // Five elements that a loosened comparator considers all equal collapse to one set_t* all_equal = set_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(all_equal, "set_create returns a set"); CHECK_EQ_INT(fill_ints(all_equal, 5), 0, "the set fills with five distinct values"); CHECK_EQ_INT(set_set_comparator(all_equal, cmp_int_positive_only), 0, "a comparator is set"); CHECK_EQ_INT(set_set_comparator(all_equal, NULL), 0, "and removed again, leaving the values distinct"); CHECK_EQ_INT(set_dedupe(all_equal), 0, "dedupe succeeds"); CHECK_EQ_SIZE(set_size(all_equal), 5, "distinct values are not collapsed"); // Now genuinely collapse them, with a comparator that calls everything equal CHECK_EQ_INT(set_set_comparator(all_equal, cmp_never_equal), 0, "a never-equal comparator is set"); CHECK_EQ_INT(set_dedupe(all_equal), 0, "dedupe succeeds"); CHECK_EQ_SIZE(set_size(all_equal), 5, "a comparator that finds nothing equal drops nothing"); set_destroy(&all_equal); } // --------------------------------------------------------------------------- // Clearing and reading // --------------------------------------------------------------------------- static void set_clear_keeps_capacity(void) { set_t* set = set_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(set, "set_create returns a set"); CHECK_EQ_INT(fill_ints(set, 25), 0, "the set fills past its initial capacity"); size_t capacity_before = set_capacity(set); const void* data_before = set_as_c_array(set); CHECK_EQ_INT(set_clear(set), 0, "clear succeeds"); CHECK_EQ_SIZE(set_size(set), 0, "clear empties the set"); CHECK_EQ_INT(set_is_empty(set), 1, "the cleared set reports empty"); CHECK_EQ_SIZE(set_capacity(set), capacity_before, "clear leaves the capacity alone"); CHECK_PTR_EQ(set_as_c_array(set), data_before, "clear does not reallocate"); CHECK_EQ_INT(fill_ints(set, 25), 0, "the cleared set refills"); CHECK_PTR_EQ(set_as_c_array(set), data_before, "refilling within the old capacity does not reallocate"); CHECK_EQ_SIZE(set_size(set), 25, "the refilled set holds everything again"); set_destroy(&set); } static void set_accessor_edge_cases(void) { set_t* set = set_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(set, "set_create returns a set"); CHECK_PTR_NULL(set_get_const(set, 0), "get_const on an empty set is NULL"); CHECK_PTR_NOT_NULL(set_as_c_array(set), "an empty set still has a data array"); CHECK_EQ_INT(fill_ints(set, 4), 0, "the set fills"); CHECK_PTR_NULL(set_get_const(set, set_size(set)), "get_const at index == size is NULL"); CHECK_PTR_NOT_NULL(set_get_const(set, set_size(set) - 1), "get_const at the last index is valid"); CHECK_PTR_EQ(set_get_const(set, 0), set_as_c_array(set), "index 0 sits at the start of the array view"); // Walking the whole set by index must reach every element exactly once const int* base = (const int*)set_as_c_array(set); REQUIRE_PTR_NOT_NULL(base, "the array view is valid"); int reachable = 1; for (size_t i = 0; i < set_size(set); ++i) { reachable = reachable && (set_get_const(set, i) == &base[i]); } CHECK_TRUE(reachable, "the indices walk the array view in order"); set_destroy(&set); } // --------------------------------------------------------------------------- // Destructors // --------------------------------------------------------------------------- static void set_destructor_get_set(void) { set_t* set = set_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(set, "set_create returns a set"); CHECK_PTR_NULL(set_get_destructor(set), "a fresh set has no destructor"); CHECK_EQ_INT(set_set_destructor(set, dtest_count_destructor), 0, "setting a destructor succeeds"); CHECK_TRUE(set_get_destructor(set) == dtest_count_destructor, "the destructor round-trips"); CHECK_EQ_INT(set_set_destructor(set, NULL), 0, "setting a NULL destructor succeeds"); CHECK_PTR_NULL(set_get_destructor(set), "a NULL destructor removes it"); set_destroy(&set); } static void set_destructor_call_counts(void) { set_t* set = set_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(set, "set_create returns a set"); CHECK_EQ_INT(set_set_destructor(set, dtest_count_destructor), 0, "the destructor is set"); CHECK_EQ_INT(fill_ints(set, 6), 0, "the set fills"); dtest_reset_destructor_calls(); CHECK_EQ_INT(set_remove_at(set, 0), 0, "remove_at succeeds"); CHECK_EQ_INT(dtest_destructor_calls, 1, "remove_at destroys exactly one element"); dtest_reset_destructor_calls(); int present = *(const int*)set_get_const(set, 0); CHECK_EQ_INT(set_remove(set, &present), 0, "remove succeeds"); CHECK_EQ_INT(dtest_destructor_calls, 1, "remove destroys exactly one element"); dtest_reset_destructor_calls(); int absent = 4242; CHECK_EQ_INT(set_remove(set, &absent), 1, "removing an absent element reports 1"); CHECK_EQ_INT(dtest_destructor_calls, 0, "a removal that found nothing destroys nothing"); // take and take_at hand ownership to the caller, so the destructor stays out dtest_reset_destructor_calls(); int taken = 0; CHECK_EQ_INT(set_take_at(set, 0, &taken), 0, "take_at succeeds"); CHECK_EQ_INT(dtest_destructor_calls, 0, "take_at never calls the destructor"); int next = *(const int*)set_get_const(set, 0); CHECK_EQ_INT(set_take(set, &next, &taken), 0, "take succeeds"); CHECK_EQ_INT(dtest_destructor_calls, 0, "take never calls the destructor"); CHECK_EQ_SIZE(set_size(set), 2, "two elements are left"); dtest_reset_destructor_calls(); CHECK_EQ_INT(set_clear(set), 0, "clear succeeds"); CHECK_EQ_INT(dtest_destructor_calls, 2, "clear destroys every remaining element"); CHECK_EQ_INT(fill_ints(set, 3), 0, "the set refills"); dtest_reset_destructor_calls(); CHECK_EQ_INT(set_destroy(&set), 0, "destroy succeeds"); CHECK_EQ_INT(dtest_destructor_calls, 3, "destroy destroys every element exactly once"); } static void set_owning_elements_end_to_end(void) { set_t* set = set_create(sizeof(char*)); REQUIRE_PTR_NOT_NULL(set, "set_create returns a set"); CHECK_EQ_INT(set_set_comparator(set, cmp_str), 0, "the string comparator is set"); CHECK_EQ_INT(set_set_destructor(set, dtest_string_destructor), 0, "the string destructor is set"); static const char* const words[] = { "alpha", "bravo", "charlie", "delta" }; 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(set_insert(set, ©), 0, "the string is added"); } CHECK_EQ_SIZE(set_size(set), 4, "all four strings are stored"); // A duplicate is not stored, so the caller still owns what they passed in. // Failing to free it here is exactly the leak the return value warns about char* duplicate = dtest_dup("bravo"); REQUIRE_PTR_NOT_NULL(duplicate, "the duplicate is created"); CHECK_EQ_INT(set_insert(set, &duplicate), 1, "the duplicate is rejected"); CHECK_EQ_SIZE(set_size(set), 4, "the set is unchanged"); free(duplicate); // remove frees what the element owned dtest_reset_destructor_calls(); char* key = dtest_dup("charlie"); REQUIRE_PTR_NOT_NULL(key, "the search key is created"); CHECK_EQ_INT(set_remove(set, &key), 0, "remove succeeds"); CHECK_EQ_INT(dtest_destructor_calls, 1, "remove freed the stored string"); free(key); // take hands the allocation over instead dtest_reset_destructor_calls(); char* wanted = dtest_dup("delta"); char* taken = NULL; REQUIRE_PTR_NOT_NULL(wanted, "the search key is created"); CHECK_EQ_INT(set_take(set, &wanted, &taken), 0, "take succeeds"); CHECK_EQ_INT(dtest_destructor_calls, 0, "take did not free the string"); CHECK_EQ_STR(taken, "delta", "the taken string is intact and owned by the caller"); free(taken); free(wanted); dtest_reset_destructor_calls(); CHECK_EQ_INT(set_destroy(&set), 0, "destroy succeeds"); CHECK_EQ_INT(dtest_destructor_calls, 2, "destroy freed the two remaining strings"); } // --------------------------------------------------------------------------- // Moving and copying // --------------------------------------------------------------------------- static void set_move_basic(void) { set_t* dest = set_create(sizeof(int)); set_t* src = set_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(dest, "the destination set is created"); REQUIRE_PTR_NOT_NULL(src, "the source set is created"); CHECK_EQ_INT(set_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(set_set_comparator(src, cmp_int), 0, "the source gets a comparator"); CHECK_EQ_INT(fill_ints(src, 5), 0, "the source fills"); CHECK_EQ_INT(set_reserve(src, 64), 0, "the source is given a distinctive capacity"); const void* src_data = set_as_c_array(src); dtest_reset_destructor_calls(); CHECK_EQ_INT(set_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(set_size(dest), 5, "the destination took the source's size"); CHECK_EQ_SIZE(set_capacity(dest), 64, "the destination took the source's capacity"); CHECK_EQ_SIZE(set_element_size(dest), sizeof(int), "the destination took the source's element size"); CHECK_PTR_EQ(set_as_c_array(dest), src_data, "the destination took the source's buffer, not a copy"); CHECK_PTR_NULL(set_get_destructor(dest), "the destination took the source's destructor, which was NULL"); CHECK_TRUE(set_get_comparator(dest) == cmp_int, "the comparator came across with the elements"); int ok = 1; for (int i = 0; i < 5; ++i) { ok = ok && holds(dest, i); } CHECK_TRUE(ok, "the moved contents are all there"); set_destroy(&dest); } static void set_move_self_is_noop(void) { set_t* set = set_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(set, "set_create returns a set"); CHECK_EQ_INT(fill_ints(set, 3), 0, "the set fills"); // Moving onto itself reports success and leaves everything alone, including // the caller's pointer, which is deliberately NOT NULLed here set_t* alias = set; CHECK_EQ_INT(set_move(set, &alias), 0, "a self-move reports success"); CHECK_PTR_EQ(alias, set, "a self-move leaves the source pointer alone"); CHECK_EQ_SIZE(set_size(set), 3, "a self-move leaves the size alone"); CHECK_EQ_INT(holds(set, 0) && holds(set, 1) && holds(set, 2), 1, "a self-move leaves the contents alone"); set_destroy(&set); } static void set_move_rejects_shallow_copy(void) { set_t* dest = set_create(sizeof(int)); set_t* src = set_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(dest, "the destination set is created"); REQUIRE_PTR_NOT_NULL(src, "the source set is created"); CHECK_EQ_INT(fill_ints(dest, 2), 0, "the destination fills"); // Two set_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(set_move(dest, &src), -1, "moving between sets that share a buffer is refused"); CHECK_PTR_NOT_NULL(src, "the refused move left the source pointer alone"); CHECK_EQ_SIZE(set_size(dest), 2, "the refused move left the destination alone"); src->data = src_data; set_destroy(&src); set_destroy(&dest); } static void set_deep_copy_basic(void) { set_t* set = set_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(set, "set_create returns a set"); CHECK_EQ_INT(fill_ints(set, 6), 0, "the set fills"); set_t* copy = set_deep_copy(set); REQUIRE_PTR_NOT_NULL(copy, "the deep copy is created"); CHECK_EQ_SIZE(set_size(copy), set_size(set), "the copy has the same size"); CHECK_EQ_SIZE(set_element_size(copy), set_element_size(set), "the copy has the same element size"); CHECK_PTR_NE(set_as_c_array(copy), set_as_c_array(set), "the copy has its own buffer"); CHECK_PTR_NULL(set_get_destructor(copy), "the copy has no destructor"); CHECK_EQ_INT(set_is_equal(copy, set), 1, "the copy holds the same elements"); // Fully independent in both directions int extra = 100; CHECK_EQ_INT(set_insert(copy, &extra), 0, "the copy can be modified"); CHECK_EQ_INT(holds(set, 100), 0, "modifying the copy does not touch the original"); int removed = 0; CHECK_EQ_INT(set_remove(set, &removed), 0, "the original can be modified"); CHECK_EQ_INT(holds(copy, 0), 1, "modifying the original does not touch the copy"); set_destroy(©); set_destroy(&set); } static void set_deep_copy_inherits_comparator(void) { set_t* set = set_create(sizeof(char*)); REQUIRE_PTR_NOT_NULL(set, "set_create returns a set"); CHECK_EQ_INT(set_set_comparator(set, cmp_str_ci), 0, "the case-insensitive comparator is set"); char* stored = dtest_dup("Alpha"); REQUIRE_PTR_NOT_NULL(stored, "the string is duplicated"); CHECK_EQ_INT(set_insert(set, &stored), 0, "the string is added"); set_t* copy = set_deep_copy(set); REQUIRE_PTR_NOT_NULL(copy, "the deep copy is created"); CHECK_TRUE(set_get_comparator(copy) == cmp_str_ci, "the copy inherits the comparator"); // Which means the copy enforces uniqueness by the same rule char* other_spelling = dtest_dup("ALPHA"); REQUIRE_PTR_NOT_NULL(other_spelling, "the second spelling is duplicated"); CHECK_EQ_INT(set_insert(copy, &other_spelling), 1, "the copy rejects a duplicate under the inherited rule"); // Inheriting the comparator is also what makes the copy compatible with its source CHECK_EQ_INT(set_is_compatible(copy, set), 1, "the copy is compatible with its source"); CHECK_EQ_INT(set_is_equal(copy, set), 1, "the copy is equal to its source"); set_destroy(©); set_destroy(&set); free(stored); free(other_spelling); } static void set_deep_copy_rejects_destructor(void) { set_t* set = set_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(set, "set_create returns a set"); CHECK_EQ_INT(set_set_destructor(set, dtest_count_destructor), 0, "the destructor is set"); CHECK_EQ_INT(fill_ints(set, 3), 0, "the set fills"); CHECK_PTR_NULL(set_deep_copy(set), "a set with a destructor cannot be deep copied"); CHECK_EQ_INT(set_set_destructor(set, NULL), 0, "the destructor is removed"); set_t* copy = set_deep_copy(set); CHECK_PTR_NOT_NULL(copy, "without the destructor the same set copies fine"); set_destroy(©); set_destroy(&set); } static void set_deep_copy_capacity_quirk(void) { set_t* set = set_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(set, "set_create returns a set"); int value = 1; CHECK_EQ_INT(set_insert(set, &value), 0, "one element is added"); CHECK_EQ_INT(set_prune(set), 0, "prune succeeds"); CHECK_EQ_SIZE(set_capacity(set), 1, "the source is pruned down to a capacity of 1"); // set_deep_copy() builds the copy with set_create(), which starts at the // default capacity, and then calls set_reserve() which never shrinks. A // source pruned below the default therefore copies to a roomier set. This is // pinned rather than worked around, so that any change to it is noticed set_t* copy = set_deep_copy(set); REQUIRE_PTR_NOT_NULL(copy, "the deep copy is created"); CHECK_EQ_SIZE(set_size(copy), 1, "the copy holds the one element"); CHECK_EQ_SIZE(set_capacity(copy), DEFAULT_CAPACITY, "the copy keeps the default capacity, not the source's"); CHECK_EQ_INT(holds(copy, 1), 1, "the value came across"); set_destroy(©); set_destroy(&set); } // --------------------------------------------------------------------------- // Compatibility and set algebra // --------------------------------------------------------------------------- static void set_is_compatible_matrix(void) { set_t* plain_a = set_create(sizeof(int)); set_t* plain_b = set_create(sizeof(int)); set_t* wider = set_create(sizeof(long)); set_t* compared = set_create(sizeof(int)); set_t* owning = set_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(plain_a, "the first set is created"); REQUIRE_PTR_NOT_NULL(plain_b, "the second set is created"); REQUIRE_PTR_NOT_NULL(wider, "the wide-element set is created"); REQUIRE_PTR_NOT_NULL(compared, "the comparator set is created"); REQUIRE_PTR_NOT_NULL(owning, "the owning set is created"); CHECK_EQ_INT(set_set_comparator(compared, cmp_int), 0, "the comparator is set"); CHECK_EQ_INT(set_set_destructor(owning, dtest_count_destructor), 0, "the destructor is set"); CHECK_EQ_INT(set_is_compatible(plain_a, plain_b), 1, "two plain sets of the same element type are compatible"); CHECK_EQ_INT(set_is_compatible(plain_a, plain_a), 1, "a set is compatible with itself"); CHECK_EQ_INT(set_is_compatible(plain_a, wider), 0, "different element sizes are incompatible"); CHECK_EQ_INT(set_is_compatible(plain_a, compared), 0, "a comparator on only one side is incompatible"); set_t* also_compared = set_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(also_compared, "the second comparator set is created"); CHECK_EQ_INT(set_set_comparator(also_compared, cmp_int), 0, "the same comparator is set"); CHECK_EQ_INT(set_is_compatible(compared, also_compared), 1, "the same comparator on both sides is compatible"); CHECK_EQ_INT(set_set_comparator(also_compared, cmp_int_positive_only), 0, "a different comparator is set"); CHECK_EQ_INT(set_is_compatible(compared, also_compared), 0, "different comparators are incompatible"); // A destructor on either side blocks compatibility, because the set // operations copy elements byte for byte CHECK_EQ_INT(set_is_compatible(owning, plain_a), 0, "a destructor on the left is incompatible"); CHECK_EQ_INT(set_is_compatible(plain_a, owning), 0, "a destructor on the right is incompatible"); CHECK_EQ_INT(set_is_compatible(owning, owning), 0, "a destructor on both sides is incompatible"); set_destroy(&also_compared); set_destroy(&owning); set_destroy(&compared); set_destroy(&wider); set_destroy(&plain_b); set_destroy(&plain_a); } static void set_union_basic(void) { static const int a_values[] = { 1, 2, 3 }; static const int b_values[] = { 3, 4, 5 }; static const int expected[] = { 1, 2, 3, 4, 5 }; set_t* a = set_create(sizeof(int)); set_t* b = set_create(sizeof(int)); set_t* empty = set_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(a, "the first set is created"); REQUIRE_PTR_NOT_NULL(b, "the second set is created"); REQUIRE_PTR_NOT_NULL(empty, "the empty set is created"); CHECK_EQ_INT(set_set_comparator(a, cmp_int), 0, "the first set gets a comparator"); CHECK_EQ_INT(set_set_comparator(b, cmp_int), 0, "the second set gets the same comparator"); CHECK_EQ_INT(set_set_comparator(empty, cmp_int), 0, "the empty set gets the same comparator"); CHECK_EQ_INT(insert_all(a, a_values, 3), 0, "the first set fills"); CHECK_EQ_INT(insert_all(b, b_values, 3), 0, "the second set fills"); set_t* result = set_union(a, b); REQUIRE_PTR_NOT_NULL(result, "the union is created"); check_holds_exactly(result, expected, 5, "the union holds every element of both, with the shared one only once"); CHECK_TRUE(set_get_comparator(result) == cmp_int, "the union inherits the comparator"); CHECK_PTR_NULL(set_get_destructor(result), "the union has no destructor"); set_destroy(&result); set_t* self = set_union(a, a); REQUIRE_PTR_NOT_NULL(self, "the union of a set with itself is created"); CHECK_EQ_INT(set_is_equal(self, a), 1, "a set unioned with itself equals itself"); set_destroy(&self); set_t* with_empty = set_union(a, empty); REQUIRE_PTR_NOT_NULL(with_empty, "the union with an empty set is created"); CHECK_EQ_INT(set_is_equal(with_empty, a), 1, "a union with the empty set equals the other set"); set_destroy(&with_empty); set_t* forwards = set_union(a, b); set_t* backwards = set_union(b, a); REQUIRE_PTR_NOT_NULL(forwards, "the forwards union is created"); REQUIRE_PTR_NOT_NULL(backwards, "the backwards union is created"); CHECK_EQ_INT(set_is_equal(forwards, backwards), 1, "the union is the same whichever way round it is taken"); set_destroy(&backwards); set_destroy(&forwards); set_destroy(&empty); set_destroy(&b); set_destroy(&a); } static void set_intersection_basic(void) { static const int a_values[] = { 1, 2, 3 }; static const int b_values[] = { 3, 4, 5 }; static const int disjoint_values[] = { 7, 8 }; static const int shared[] = { 3 }; set_t* a = set_create(sizeof(int)); set_t* b = set_create(sizeof(int)); set_t* disjoint = set_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(a, "the first set is created"); REQUIRE_PTR_NOT_NULL(b, "the second set is created"); REQUIRE_PTR_NOT_NULL(disjoint, "the disjoint set is created"); CHECK_EQ_INT(insert_all(a, a_values, 3), 0, "the first set fills"); CHECK_EQ_INT(insert_all(b, b_values, 3), 0, "the second set fills"); CHECK_EQ_INT(insert_all(disjoint, disjoint_values, 2), 0, "the disjoint set fills"); set_t* result = set_intersection(a, b); REQUIRE_PTR_NOT_NULL(result, "the intersection is created"); check_holds_exactly(result, shared, 1, "the intersection holds only the shared element"); set_destroy(&result); // Disjoint inputs give an empty set, not NULL. NULL means an error set_t* nothing = set_intersection(a, disjoint); REQUIRE_PTR_NOT_NULL(nothing, "the intersection of disjoint sets is still a set"); CHECK_EQ_SIZE(set_size(nothing), 0, "the intersection of disjoint sets is empty"); CHECK_EQ_INT(set_is_empty(nothing), 1, "and reports as empty"); set_destroy(¬hing); set_t* self = set_intersection(a, a); REQUIRE_PTR_NOT_NULL(self, "the intersection of a set with itself is created"); CHECK_EQ_INT(set_is_equal(self, a), 1, "a set intersected with itself equals itself"); set_destroy(&self); set_destroy(&disjoint); set_destroy(&b); set_destroy(&a); } static void set_difference_asymmetry(void) { static const int a_values[] = { 1, 2, 3 }; static const int b_values[] = { 3, 4, 5 }; static const int only_in_a[] = { 1, 2 }; static const int only_in_b[] = { 4, 5 }; set_t* a = set_create(sizeof(int)); set_t* b = set_create(sizeof(int)); set_t* empty = set_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(a, "the first set is created"); REQUIRE_PTR_NOT_NULL(b, "the second set is created"); REQUIRE_PTR_NOT_NULL(empty, "the empty set is created"); CHECK_EQ_INT(insert_all(a, a_values, 3), 0, "the first set fills"); CHECK_EQ_INT(insert_all(b, b_values, 3), 0, "the second set fills"); set_t* forwards = set_difference(a, b); set_t* backwards = set_difference(b, a); REQUIRE_PTR_NOT_NULL(forwards, "the forwards difference is created"); REQUIRE_PTR_NOT_NULL(backwards, "the backwards difference is created"); check_holds_exactly(forwards, only_in_a, 2, "a minus b holds what is only in a"); check_holds_exactly(backwards, only_in_b, 2, "b minus a holds what is only in b"); CHECK_EQ_INT(set_is_equal(forwards, backwards), 0, "the difference is not symmetric"); set_destroy(&backwards); set_destroy(&forwards); set_t* self = set_difference(a, a); REQUIRE_PTR_NOT_NULL(self, "a set minus itself is created"); CHECK_EQ_SIZE(set_size(self), 0, "a set minus itself is empty"); set_destroy(&self); set_t* minus_nothing = set_difference(a, empty); REQUIRE_PTR_NOT_NULL(minus_nothing, "a set minus the empty set is created"); CHECK_EQ_INT(set_is_equal(minus_nothing, a), 1, "a set minus the empty set equals itself"); set_destroy(&minus_nothing); set_t* nothing_minus = set_difference(empty, a); REQUIRE_PTR_NOT_NULL(nothing_minus, "the empty set minus a set is created"); CHECK_EQ_SIZE(set_size(nothing_minus), 0, "the empty set minus anything is empty"); set_destroy(¬hing_minus); set_destroy(&empty); set_destroy(&b); set_destroy(&a); } static void set_algebra_rejects_incompatible(void) { set_t* plain = set_create(sizeof(int)); set_t* wider = set_create(sizeof(long)); set_t* compared = set_create(sizeof(int)); set_t* owning = set_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(plain, "the plain set is created"); REQUIRE_PTR_NOT_NULL(wider, "the wide-element set is created"); REQUIRE_PTR_NOT_NULL(compared, "the comparator set is created"); REQUIRE_PTR_NOT_NULL(owning, "the owning set is created"); CHECK_EQ_INT(set_set_comparator(compared, cmp_int), 0, "the comparator is set"); CHECK_EQ_INT(set_set_destructor(owning, dtest_count_destructor), 0, "the destructor is set"); CHECK_EQ_INT(fill_ints(plain, 3), 0, "the plain set fills"); CHECK_PTR_NULL(set_union(plain, wider), "a union across different element sizes is refused"); CHECK_PTR_NULL(set_intersection(plain, wider), "an intersection across different element sizes is refused"); CHECK_PTR_NULL(set_difference(plain, wider), "a difference across different element sizes is refused"); CHECK_PTR_NULL(set_union(plain, compared), "a union across different comparators is refused"); CHECK_PTR_NULL(set_intersection(plain, compared), "an intersection across different comparators is refused"); CHECK_PTR_NULL(set_difference(plain, compared), "a difference across different comparators is refused"); // A destructor on either side blocks all three, because they copy bytes CHECK_PTR_NULL(set_union(plain, owning), "a union with an owning set is refused"); CHECK_PTR_NULL(set_union(owning, plain), "and in the other direction too"); CHECK_PTR_NULL(set_intersection(plain, owning), "an intersection with an owning set is refused"); CHECK_PTR_NULL(set_difference(plain, owning), "a difference with an owning set is refused"); set_destroy(&owning); set_destroy(&compared); set_destroy(&wider); set_destroy(&plain); } static void set_algebra_inputs_untouched(void) { static const int a_values[] = { 1, 2, 3 }; static const int b_values[] = { 3, 4, 5 }; set_t* a = set_create(sizeof(int)); set_t* b = set_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(a, "the first set is created"); REQUIRE_PTR_NOT_NULL(b, "the second set is created"); CHECK_EQ_INT(insert_all(a, a_values, 3), 0, "the first set fills"); CHECK_EQ_INT(insert_all(b, b_values, 3), 0, "the second set fills"); const void* a_data = set_as_c_array(a); const void* b_data = set_as_c_array(b); set_t* u = set_union(a, b); set_t* i = set_intersection(a, b); set_t* d = set_difference(a, b); CHECK_PTR_NOT_NULL(u, "the union is created"); CHECK_PTR_NOT_NULL(i, "the intersection is created"); CHECK_PTR_NOT_NULL(d, "the difference is created"); check_holds_exactly(a, a_values, 3, "the first input is untouched"); check_holds_exactly(b, b_values, 3, "the second input is untouched"); CHECK_PTR_EQ(set_as_c_array(a), a_data, "the first input was not reallocated"); CHECK_PTR_EQ(set_as_c_array(b), b_data, "the second input was not reallocated"); set_destroy(&d); set_destroy(&i); set_destroy(&u); set_destroy(&b); set_destroy(&a); } static void set_is_subset_semantics(void) { static const int big_values[] = { 1, 2, 3, 4 }; static const int small_values[] = { 2, 3 }; set_t* big = set_create(sizeof(int)); set_t* small = set_create(sizeof(int)); set_t* empty = set_create(sizeof(int)); set_t* wider = set_create(sizeof(long)); set_t* compared = set_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(big, "the large set is created"); REQUIRE_PTR_NOT_NULL(small, "the small set is created"); REQUIRE_PTR_NOT_NULL(empty, "the empty set is created"); REQUIRE_PTR_NOT_NULL(wider, "the wide-element set is created"); REQUIRE_PTR_NOT_NULL(compared, "the comparator set is created"); CHECK_EQ_INT(set_set_comparator(compared, cmp_int), 0, "the comparator is set"); CHECK_EQ_INT(insert_all(big, big_values, 4), 0, "the large set fills"); CHECK_EQ_INT(insert_all(small, small_values, 2), 0, "the small set fills"); CHECK_EQ_INT(set_is_subset(small, big), 1, "a proper subset reports 1"); CHECK_EQ_INT(set_is_subset(big, small), 0, "a superset is not a subset"); CHECK_EQ_INT(set_is_subset(big, big), 1, "a set is a subset of itself"); CHECK_EQ_INT(set_is_subset(empty, big), 1, "the empty set is a subset of everything compatible"); CHECK_EQ_INT(set_is_subset(empty, empty), 1, "the empty set is a subset of itself"); CHECK_EQ_INT(set_is_subset(big, empty), 0, "a non-empty set is not a subset of the empty set"); CHECK_EQ_INT(set_is_subset(small, wider), 0, "different element sizes report 0"); CHECK_EQ_INT(set_is_subset(small, compared), 0, "different comparators report 0"); // Unlike the operations that build a new set, is_subset accepts a destructor, // because nothing is copied. It must not call it either set_t* owning = set_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(owning, "the owning set is created"); CHECK_EQ_INT(set_set_destructor(owning, dtest_count_destructor), 0, "the destructor is set"); CHECK_EQ_INT(insert_all(owning, small_values, 2), 0, "the owning set fills"); CHECK_EQ_INT(set_is_compatible(owning, big), 0, "the two are not compatible for copying"); dtest_reset_destructor_calls(); CHECK_EQ_INT(set_is_subset(owning, big), 1, "is_subset works anyway, as it copies nothing"); CHECK_EQ_INT(set_is_subset(big, owning), 0, "and reports the other direction correctly"); CHECK_EQ_INT(dtest_destructor_calls, 0, "is_subset never destroys anything"); dtest_reset_destructor_calls(); set_destroy(&owning); set_destroy(&compared); set_destroy(&wider); set_destroy(&empty); set_destroy(&small); set_destroy(&big); } static void set_is_equal_semantics(void) { static const int forwards[] = { 1, 2, 3 }; static const int backwards[] = { 3, 2, 1 }; static const int shorter[] = { 1, 2 }; set_t* a = set_create(sizeof(int)); set_t* b = set_create(sizeof(int)); set_t* c = set_create(sizeof(int)); set_t* compared = set_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(a, "the first set is created"); REQUIRE_PTR_NOT_NULL(b, "the second set is created"); REQUIRE_PTR_NOT_NULL(c, "the third set is created"); REQUIRE_PTR_NOT_NULL(compared, "the comparator set is created"); CHECK_EQ_INT(set_set_comparator(compared, cmp_int), 0, "the comparator is set"); CHECK_EQ_INT(insert_all(a, forwards, 3), 0, "the first set fills"); CHECK_EQ_INT(insert_all(b, backwards, 3), 0, "the second set fills in the opposite order"); CHECK_EQ_INT(insert_all(c, shorter, 2), 0, "the third set fills with fewer elements"); CHECK_EQ_INT(insert_all(compared, forwards, 3), 0, "the comparator set fills with the same values"); CHECK_EQ_INT(set_is_equal(a, a), 1, "a set equals itself"); CHECK_EQ_INT(set_is_equal(a, b), 1, "insertion order does not affect equality"); CHECK_EQ_INT(set_is_equal(b, a), 1, "and it is symmetric"); CHECK_EQ_INT(set_is_equal(a, c), 0, "sets of different sizes are not equal"); CHECK_EQ_INT(set_is_equal(c, a), 0, "and that is symmetric too"); CHECK_EQ_INT(set_is_equal(a, compared), 0, "the same values under different comparators are not equal"); set_destroy(&compared); set_destroy(&c); set_destroy(&b); set_destroy(&a); } static void set_is_equal_duplicate_laden(void) { // The case the two-way containment check in set_is_equal() exists for. A // comparator loosened on a populated set leaves duplicates behind, so a set // holding "A" and "a" has the same size as one holding "A" and "B" and is // contained in it, but not the other way round char* a_upper = dtest_dup("A"); char* a_lower = dtest_dup("a"); char* b_upper = dtest_dup("B"); char* b_upper_copy = dtest_dup("B"); REQUIRE_PTR_NOT_NULL(a_upper, "the first string is duplicated"); REQUIRE_PTR_NOT_NULL(a_lower, "the second string is duplicated"); REQUIRE_PTR_NOT_NULL(b_upper, "the third string is duplicated"); REQUIRE_PTR_NOT_NULL(b_upper_copy, "the fourth string is duplicated"); set_t* laden = set_create(sizeof(char*)); REQUIRE_PTR_NOT_NULL(laden, "the duplicate-laden set is created"); CHECK_EQ_INT(set_insert(laden, &a_upper), 0, "\"A\" is added under the byte comparison"); CHECK_EQ_INT(set_insert(laden, &a_lower), 0, "\"a\" is added too, as the pointers differ"); CHECK_EQ_INT(set_set_comparator(laden, cmp_str_ci), 0, "the comparator is loosened afterwards"); CHECK_EQ_SIZE(set_size(laden), 2, "the set still holds two elements that are now equal to each other"); set_t* clean = set_create(sizeof(char*)); REQUIRE_PTR_NOT_NULL(clean, "the clean set is created"); CHECK_EQ_INT(set_set_comparator(clean, cmp_str_ci), 0, "the same comparator is set from the start"); CHECK_EQ_INT(set_insert(clean, &b_upper_copy), 0, "\"B\" is added"); CHECK_EQ_INT(set_insert(clean, &b_upper), 1, "the second \"B\" is a duplicate"); CHECK_EQ_INT(set_insert(clean, &a_upper), 0, "\"A\" is added"); CHECK_EQ_SIZE(set_size(clean), 2, "the clean set holds two genuinely distinct elements"); CHECK_EQ_INT(set_is_subset(laden, clean), 1, "every element of the laden set is in the clean one"); CHECK_EQ_INT(set_is_subset(clean, laden), 0, "but not the other way round"); CHECK_EQ_INT(set_is_equal(laden, clean), 0, "so the two sets are not equal, despite matching sizes"); // Deduping the laden set makes the asymmetry visible as a size difference CHECK_EQ_INT(set_dedupe(laden), 0, "dedupe succeeds"); CHECK_EQ_SIZE(set_size(laden), 1, "the laden set collapses to one element"); CHECK_EQ_INT(set_is_equal(laden, clean), 0, "and it is still not equal to the clean set"); set_destroy(&clean); set_destroy(&laden); free(a_upper); free(a_lower); free(b_upper); free(b_upper_copy); } // --------------------------------------------------------------------------- // White-box guards. These write set_t fields directly to reach branches that // are otherwise unreachable, and restore them before the set is destroyed // --------------------------------------------------------------------------- static void set_wb_grow_overflow_guard(void) { set_t* set = set_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(set, "set_create returns a set"); size_t real_capacity = set->capacity; set->capacity = SIZE_MAX / 2 + 1; CHECK_EQ_INT(set_grow(set), -1, "growing past half of SIZE_MAX is refused"); set->capacity = real_capacity; CHECK_EQ_SIZE(set_capacity(set), real_capacity, "the capacity was restored for cleanup"); set_destroy(&set); } static void set_wb_element_size_zero_guard(void) { set_t* set = set_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(set, "set_create returns a set"); size_t real_element_size = set->element_size; set->element_size = 0; CHECK_EQ_INT(set_reserve(set, 100), -1, "reserving on a zero element size is refused"); CHECK_EQ_INT(set_prune(set), -1, "pruning on a zero element size is refused"); set->element_size = real_element_size; CHECK_EQ_SIZE(set_element_size(set), sizeof(int), "the element size was restored for cleanup"); set_destroy(&set); } static void set_wb_reserve_multiply_overflow(void) { set_t* set = set_create(sizeof(int)); REQUIRE_PTR_NOT_NULL(set, "set_create returns a set"); size_t too_many = SIZE_MAX / sizeof(int) + 1; CHECK_EQ_INT(set_reserve(set, too_many), -1, "a reservation that would overflow the byte count is refused"); CHECK_EQ_SIZE(set_capacity(set), DEFAULT_CAPACITY, "the refused reservation changed nothing"); int value = 1; CHECK_EQ_INT(set_insert(set, &value), 0, "the set is still usable"); set_destroy(&set); } // --------------------------------------------------------------------------- // A non-default DLIBC_SET_INITIAL_CAPACITY, from set_altcap.c // --------------------------------------------------------------------------- static void set_altcap_initial_capacity_honoured(void) { CHECK_EQ_SIZE(set_altcap_initial_capacity(), 1, "DLIBC_SET_INITIAL_CAPACITY sets the starting capacity"); } static void set_altcap_growth_from_one(void) { size_t capacities[8]; REQUIRE_TRUE(set_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(set_create_basic), DTEST_CASE(set_create_rejects_zero_element_size), DTEST_CASE(set_create_rejects_overflow), DTEST_CASE(set_destroy_semantics), DTEST_CASE(set_null_argument_matrix), // Capacity DTEST_CASE(set_reserve_grows_only), DTEST_CASE(set_reserve_overflow_rejected), DTEST_CASE(set_grow_doubling), DTEST_CASE(set_prune_shrink_to_fit), // Insertion and uniqueness DTEST_CASE(set_insert_tristate), DTEST_CASE(set_insert_uniqueness_memcmp), DTEST_CASE(set_insert_struct_padding_trap), DTEST_CASE(set_insert_pointer_elements_compare_pointers), DTEST_CASE(set_insert_aliased_no_destructor), DTEST_CASE(set_insert_aliased_with_broken_comparator), DTEST_CASE(set_insert_aliased_with_destructor_rejected), // Lookup DTEST_CASE(set_find_and_contains), // Removal DTEST_CASE(set_remove_tristate), DTEST_CASE(set_remove_at_swap_with_last), DTEST_CASE(set_remove_aliased_element), DTEST_CASE(set_removal_during_iteration), // Taking elements out DTEST_CASE(set_take_at_basic), DTEST_CASE(set_take_rejects_aliased_out), DTEST_CASE(set_take_rejects_aliased_out_before_lookup), DTEST_CASE(set_take_tristate), DTEST_CASE(set_take_element_may_alias), DTEST_CASE(set_take_out_equals_key), // Comparators DTEST_CASE(set_comparator_get_set), DTEST_CASE(set_comparator_equality_used), DTEST_CASE(set_comparator_only_zero_matters), DTEST_CASE(set_comparator_find_argument_order), DTEST_CASE(set_dedupe_after_loosening), DTEST_CASE(set_dedupe_edge_cases), // Clearing and reading DTEST_CASE(set_clear_keeps_capacity), DTEST_CASE(set_accessor_edge_cases), // Destructors DTEST_CASE(set_destructor_get_set), DTEST_CASE(set_destructor_call_counts), DTEST_CASE(set_owning_elements_end_to_end), // Moving and copying DTEST_CASE(set_move_basic), DTEST_CASE(set_move_self_is_noop), DTEST_CASE(set_move_rejects_shallow_copy), DTEST_CASE(set_deep_copy_basic), DTEST_CASE(set_deep_copy_inherits_comparator), DTEST_CASE(set_deep_copy_rejects_destructor), DTEST_CASE(set_deep_copy_capacity_quirk), // Compatibility and set algebra DTEST_CASE(set_is_compatible_matrix), DTEST_CASE(set_union_basic), DTEST_CASE(set_intersection_basic), DTEST_CASE(set_difference_asymmetry), DTEST_CASE(set_algebra_rejects_incompatible), DTEST_CASE(set_algebra_inputs_untouched), DTEST_CASE(set_is_subset_semantics), DTEST_CASE(set_is_equal_semantics), DTEST_CASE(set_is_equal_duplicate_laden), // White-box guards DTEST_CASE(set_wb_grow_overflow_guard), DTEST_CASE(set_wb_element_size_zero_guard), DTEST_CASE(set_wb_reserve_multiply_overflow), // A non-default initial capacity DTEST_CASE(set_altcap_initial_capacity_honoured), DTEST_CASE(set_altcap_growth_from_one), }; return dtest_main(cases, sizeof(cases) / sizeof(cases[0]), "set"); }