From 5944051d2b324d3c3a1a47b2f93b9764015365c6 Mon Sep 17 00:00:00 2001 From: "Michael D. Lowis" Date: Sat, 23 May 2015 13:13:06 -0400 Subject: [PATCH] Finished implementing hashset using rbt and comparator objects --- Gemfile.lock | 6 +- source/cmp/cmp.c | 27 +++++++ source/cmp/cmp.h | 51 +++++++++++++ source/murmur3/murmur3.c | 78 +++++++++++++++++++ source/murmur3/murmur3.h | 28 +++++++ source/rbt/rbt.c | 15 +--- source/rbt/rbt.h | 18 ++--- source/set/set.c | 160 +++++++++++++-------------------------- source/set/set.h | 52 +++++++++++-- tests/main.c | 1 + tests/test_rbt.c | 145 +++++++++++++++++------------------ tests/test_set.c | 118 +++++++++++++++++++++++++++++ 12 files changed, 482 insertions(+), 217 deletions(-) create mode 100644 source/cmp/cmp.c create mode 100644 source/cmp/cmp.h create mode 100644 source/murmur3/murmur3.c create mode 100644 source/murmur3/murmur3.h create mode 100644 tests/test_set.c diff --git a/Gemfile.lock b/Gemfile.lock index 7b3953a..b3f4ea9 100644 --- a/Gemfile.lock +++ b/Gemfile.lock @@ -1,9 +1,9 @@ GEM remote: http://rubygems.org/ specs: - json (1.8.1) - rake (10.3.2) - rscons (1.6.0) + json (1.8.2) + rake (10.4.2) + rscons (1.9.0) json (~> 1.0) PLATFORMS diff --git a/source/cmp/cmp.c b/source/cmp/cmp.c new file mode 100644 index 0000000..d072358 --- /dev/null +++ b/source/cmp/cmp.c @@ -0,0 +1,27 @@ +/** + @file cmp.c + @brief See header for details + */ +#include "cmp.h" + +static void cmp_free(void* obj) +{ + cmp_t* cmp = (cmp_t*)obj; + if ((NULL != obj) && (NULL != cmp->env)) + mem_release(cmp->env); +} + +cmp_t* cmp_new(void* env, cmpfn_t fn) +{ + cmp_t* cmp = (cmp_t*)mem_allocate(sizeof(cmp_t), cmp_free); + cmp->env = env; + cmp->fn = fn; + return cmp; +} + +int cmp_compare(cmp_t* cmp, void* obja, void* objb) +{ + return cmp->fn(cmp->env, obja, objb); +} + + diff --git a/source/cmp/cmp.h b/source/cmp/cmp.h new file mode 100644 index 0000000..e554b50 --- /dev/null +++ b/source/cmp/cmp.h @@ -0,0 +1,51 @@ +/** + @file cmp.h + @brief TODO: Describe this file + */ +#ifndef CMP_H +#define CMP_H + +#ifdef __cplusplus +extern "C" { +#endif + +#include "rt.h" + +/** Function pointer representing a comparison function with an additional + * environment pointer */ +typedef int (*cmpfn_t)(void* env, void* obja, void* objb); + +/** Comparator object */ +typedef struct { + void* env; /**< The environment context associated with this comparator */ + cmpfn_t fn; /**< The comparison function for this comparator */ +} cmp_t; + +/** + * @brief Constructs a new comparator object. + * + * @param env The environment context associated with the comparator + * @param fn The comparison function associated with the comparator + * + * @return The newly constructed comparator. + */ +cmp_t* cmp_new(void* env, cmpfn_t fn); + +/** + * @brief Compares two objects using the comparator object. + * + * @param cmp The comparator to use. + * @param obja First object to compare. + * @param objb Second object to compare. + * + * @return 0 if objects are equal + * -1 if obja is less than objb + * 1 if obja is greater than objb + */ +int cmp_compare(cmp_t* cmp, void* obja, void* objb); + +#ifdef __cplusplus +} +#endif + +#endif /* CMP_H */ diff --git a/source/murmur3/murmur3.c b/source/murmur3/murmur3.c new file mode 100644 index 0000000..c10174e --- /dev/null +++ b/source/murmur3/murmur3.c @@ -0,0 +1,78 @@ +/** + @file murmur3.c + @brief See header for details +*/ +#include "murmur3.h" + +/** + * Get 32-bit Murmur3 hash. + * + * @param data source data + * @param nbytes size of data + * + * @return 32-bit unsigned hash value. + * + * @code + * uint32_t hashval = murmur3_32((void*)"hello", 5); + * @endcode + * + * @code + * MurmurHash3 was created by Austin Appleby in 2008. The initial + * implementation was published in C++ and placed in the public. + * https://sites.google.com/site/murmurhash/ + * Seungyoung Kim has ported its implementation into C language + * in 2012 and published it as a part of qLibc component. + * @endcode + */ +uint32_t murmur3_32(const uint8_t* data, size_t nbytes) +{ + /* Initial hash value */ + uint32_t hash = 0; + /* Magic numbers for the hash calculation */ + const uint32_t c1 = 0xcc9e2d51; + const uint32_t c2 = 0x1b873593; + /* Prepare to process the byte array as an array of uint32_ts */ + const int nblocks = nbytes / sizeof(uint32_t); + const uint32_t* blocks = (const uint32_t *) (data); + const uint8_t* tail = (const uint8_t *) (data + (nblocks * 4)); + /* Start processing the data if we have it */ + if (data != NULL || nbytes != 0) { + uint32_t blk; + /* Process all of the full uint32_ts in the data */ + for (int i = 0; i < nblocks; i++) { + blk = blocks[i]; + blk = blk * c1; + blk = (blk << 15) | (blk >> (32 - 15)); + blk = blk * c2; + /* Update the hash calculation */ + hash = hash ^ blk; + hash = (hash << 13) | (hash >> (32 - 13)); + hash = (hash * 5) + 0xe6546b64; + } + + /* Process the tail of the data */ + blk = 0; + switch (nbytes & 3) { + case 3: + blk ^= tail[2] << 16; + case 2: + blk ^= tail[1] << 8; + case 1: + blk ^= tail[0]; + blk *= c1; + blk = (blk << 15) | (blk >> (32 - 15)); + blk *= c2; + hash ^= blk; + }; + + /* Post process the hash */ + hash = hash ^ nbytes; + hash = hash ^ (hash >> 16); + hash = hash * (0x85ebca6b); + hash = hash ^ (hash >> 13); + hash = hash * (0xc2b2ae35); + hash = hash ^ (hash >> 16); + } + return hash; +} + diff --git a/source/murmur3/murmur3.h b/source/murmur3/murmur3.h new file mode 100644 index 0000000..d0b9cfc --- /dev/null +++ b/source/murmur3/murmur3.h @@ -0,0 +1,28 @@ +/** + @file murmur3.h + @brief Implementation of the murmur3 32-bit hash function. + */ +#ifndef MURMUR3_H +#define MURMUR3_H + +#include "rt.h" + +#ifdef __cplusplus +extern "C" { +#endif + +/** + * @brief Calculate the murmur3 32-bit hash of a region of memory. + * + * @param data Pointer to teh data to hash. + * @param nbytes The number of bytes of data to hash. + * + * @return The 32-bit hash value. + */ +uint32_t murmur3_32(const uint8_t* data, size_t nbytes); + +#ifdef __cplusplus +} +#endif + +#endif /* MURMUR3_H */ diff --git a/source/rbt/rbt.c b/source/rbt/rbt.c index 2abe719..bb1f112 100644 --- a/source/rbt/rbt.c +++ b/source/rbt/rbt.c @@ -12,13 +12,6 @@ static int rbt_default_compare(void* env, void* v_a, void* v_b){ return (a == b ? 0 : (aenv = NULL; - cmp->cmpfn = &rbt_default_compare; - return cmp; -} - /* -------------------------------- */ /* destructors / constructors */ /* -------------------------------- */ @@ -31,10 +24,10 @@ static void rbt_free(void* v_tree){ if(tree->comp) mem_release(tree->comp); } -rbt_t* rbt_new(comparator_t* comparator){ +rbt_t* rbt_new(cmp_t* cmp){ rbt_t* tree = mem_allocate(sizeof(rbt_t), &rbt_free); tree->root = NULL; - tree->comp = comparator ? comparator : rbt_default_comparator(); + tree->comp = cmp ? cmp : cmp_new(NULL, &rbt_default_compare); return tree; } @@ -75,7 +68,7 @@ rbt_color_t rbt_node_color(rbt_node_t* node){ static rbt_node_t* rbt_lookup_node(rbt_t* tree, rbt_node_t* node, void* value){ rbt_node_t* ret = NULL; if(node){ - int c = tree->comp->cmpfn(tree->comp->env, value, node->contents); + int c = cmp_compare(tree->comp, value, node->contents); if (c < 0) ret = rbt_lookup_node(tree, node->left, value); else if(c > 0) ret = rbt_lookup_node(tree, node->right, value); else ret = node; @@ -169,7 +162,7 @@ static void rbt_insert_node(rbt_t* tree, rbt_node_t* node, rbt_node_t* parent){ tree->root = node; rbt_ins_recolor(tree, node); }else{ - int c = tree->comp->cmpfn(tree->comp->env, node->contents, parent->contents); + int c = cmp_compare(tree->comp, node->contents, parent->contents); rbt_node_t** relevant_child = (c<0 ? &(parent->left) : &(parent->right)); if(*relevant_child){ rbt_insert_node(tree, node, *relevant_child); diff --git a/source/rbt/rbt.h b/source/rbt/rbt.h index ec1c08f..7f3a4a0 100644 --- a/source/rbt/rbt.h +++ b/source/rbt/rbt.h @@ -10,6 +10,7 @@ extern "C" { #endif #include "rt.h" +#include "cmp.h" /** node colors */ typedef enum { @@ -17,15 +18,6 @@ typedef enum { BLACK } rbt_color_t; -/** a function pointer for comparing node contents - should return -1, 0, or 1 if a is <, ==, or > b, respectively */ -//typedef int (*comparator_t)(void* env, void* p_a, void* p_b); - -typedef struct { - void* env; - int (*cmpfn)(void* env, void* p_a, void* p_b); -} comparator_t; - /** a red-black tree node */ typedef struct rbt_node_t { /** pointers to immediate relatives */ @@ -42,18 +34,18 @@ typedef struct rbt_node_t { typedef struct { /** pointer to the root of the tree */ rbt_node_t* root; - /** function pointer for comparing node contents */ - comparator_t* comp; + /** comparator object for comparing node contents */ + cmp_t* comp; } rbt_t; /** * @brief creates a new red-black tree * - * @param comparator pointer to the comparator function + * @param cmp pointer to the comparator object * * @return pointer to newly created tree */ -rbt_t* rbt_new(comparator_t* comparator); +rbt_t* rbt_new(cmp_t* cmp); /** * @brief find a value in a red-black tree diff --git a/source/set/set.c b/source/set/set.c index 5c641f6..a68c0bb 100644 --- a/source/set/set.c +++ b/source/set/set.c @@ -10,134 +10,76 @@ typedef struct { } set_pair_t; struct set_t { - hash_fn_t hash_func; - comparator_t* user_comp; - comparator_t* comp; + hashfn_t hash_func; rbt_t* tree; }; -//static void set_free(void* obj) -//{ -// mem_release(((set_t*)obj)->tree); -//} +static void set_pair_free(void* obj) +{ + mem_release(((set_pair_t*)obj)->value); +} + +static set_pair_t* set_pair_new(void* value, uint32_t hash) +{ + set_pair_t* pair = (set_pair_t*)mem_allocate(sizeof(set_pair_t), &set_pair_free); + pair->value = value; + pair->hash = hash; + return pair; +} -//static int set_compare_nodes(void* env, void* p_a, void* p_b) -//{ -// int cmp; -// set_t* set = (set_t*)env; -// set_pair_t* pair_a = (set_pair_t*)p_a; -// set_pair_t* pair_b = (set_pair_t*)p_b; -// if (pair_a->hash < pair_b->hash) { -// cmp = -1; -// } else if (pair_a->hash > pair_b->hash) { -// cmp = 1; -// } else { -// cmp = set->cmp_func(set, pair_a, pair_b); -// } -//} +static void set_free(void* obj) +{ + mem_release(((set_t*)obj)->tree); +} + +static int set_compare_nodes(void* env, void* p_a, void* p_b) +{ + int cmp; + cmp_t* user_comp = (cmp_t*)env; + set_pair_t* pair_a = (set_pair_t*)p_a; + set_pair_t* pair_b = (set_pair_t*)p_b; + if (pair_a->hash < pair_b->hash) { + cmp = -1; + } else if (pair_a->hash > pair_b->hash) { + cmp = 1; + } else { + cmp = cmp_compare(user_comp, pair_a->value, pair_b->value); + } + return cmp; +} -//set_t* set_new(hash_fn_t hash_fn, comparator_t* cmp_fn) -//{ -// set_t* set = (set_t*)mem_allocate(sizeof(set_t), set_free); -// set->hash_func = hash_fn; -// set->tree = rbt_new(set_compare_nodes); -// return set; -//} +set_t* set_new(cmp_t* cmp, hashfn_t hash_fn) +{ + set_t* set = (set_t*)mem_allocate(sizeof(set_t), &set_free); + cmp_t* comp = cmp_new(cmp, &set_compare_nodes); + set->hash_func = hash_fn; + set->tree = rbt_new(comp); + return set; +} bool set_contains(set_t* set, void* value) { - (void)set; - (void)value; - return false; + set_pair_t pair = { value, set->hash_func(value) }; + return (NULL != rbt_lookup(set->tree, &pair)); } size_t set_size(set_t* set) { - (void)set; - return 0; + return rbt_size(set->tree); } void set_insert(set_t* set, void* value) { - (void)set; - (void)value; + set_pair_t* pair = set_pair_new(value, set->hash_func(value)); + if (!rbt_lookup(set->tree, pair)) + rbt_insert(set->tree, pair); + else + mem_release(pair); } void set_delete(set_t* set, void* value) { - (void)set; - (void)value; + set_pair_t pair = { value, set->hash_func(value) }; + rbt_delete(set->tree, &pair); } - -/** - * Get 32-bit Murmur3 hash. - * - * @param data source data - * @param nbytes size of data - * - * @return 32-bit unsigned hash value. - * - * @code - * uint32_t hashval = qhashmurmur3_32((void*)"hello", 5); - * @endcode - * - * @code - * MurmurHash3 was created by Austin Appleby in 2008. The initial - * implementation was published in C++ and placed in the public. - * https://sites.google.com/site/murmurhash/ - * Seungyoung Kim has ported its implementation into C language - * in 2012 and published it as a part of qLibc component. - * @endcode - */ -uint32_t murmur3_32(const uint8_t* data, size_t nbytes) -{ - /* Initial hash value */ - uint32_t hash = 0; - /* Magic numbers for the hash calculation */ - const uint32_t c1 = 0xcc9e2d51; - const uint32_t c2 = 0x1b873593; - /* Prepare to process the byte array as an array of uint32_ts */ - const int nblocks = nbytes / sizeof(uint32_t); - const uint32_t* blocks = (const uint32_t *) (data); - const uint8_t* tail = (const uint8_t *) (data + (nblocks * 4)); - /* Start processing the data if we have it */ - if (data != NULL || nbytes != 0) { - uint32_t blk; - /* Process all of the full uint32_ts in the data */ - for (int i = 0; i < nblocks; i++) { - blk = blocks[i]; - blk = blk * c1; - blk = (blk << 15) | (blk >> (32 - 15)); - blk = blk * c2; - /* Update the hash calculation */ - hash = hash ^ blk; - hash = (hash << 13) | (hash >> (32 - 13)); - hash = (hash * 5) + 0xe6546b64; - } - - /* Process the tail of the data */ - blk = 0; - switch (nbytes & 3) { - case 3: - blk ^= tail[2] << 16; - case 2: - blk ^= tail[1] << 8; - case 1: - blk ^= tail[0]; - blk *= c1; - blk = (blk << 15) | (blk >> (32 - 15)); - blk *= c2; - hash ^= blk; - }; - - /* Post process the hash */ - hash = hash ^ nbytes; - hash = hash ^ (hash >> 16); - hash = hash * (0x85ebca6b); - hash = hash ^ (hash >> 13); - hash = hash * (0xc2b2ae35); - hash = hash ^ (hash >> 16); - } - return hash; -} diff --git a/source/set/set.h b/source/set/set.h index 6236b77..7a4cfa2 100644 --- a/source/set/set.h +++ b/source/set/set.h @@ -1,7 +1,7 @@ /** @file set.h - @brief TODO: Describe this file - */ + @brief Implementation of a HashSet data structure. +*/ #ifndef SET_H #define SET_H @@ -11,19 +11,61 @@ extern "C" { #include "rbt.h" -typedef uint32_t (*hashfn_t)(const void* obj); +/** Function pointer that returns the 32-bit hash of the given object. */ +typedef uint32_t (*hashfn_t)(void* obj); +/* Set data structure */ struct set_t; + +/* Set stat structure type alias */ typedef struct set_t set_t; -set_t* set_new(comparator_t comparator); +/** + * @brief Initializes a new set data structure. + * + * The initialized set will use the provided comparator and hash function for + * lookups and retrievals. + * + * @param cmp The comparator used to compare the object types stored in the set. + * @param hash_fn The function used to hash the objects in the set. + * + * @return the newly constructed set. + */ +set_t* set_new(cmp_t* cmp, hashfn_t hash_fn); -bool set_contains(set_t* p_set, void* value); +/** + * @brief Determines if the value is a member of the set. + * + * @param set The set. + * @param value The value to find. + * + * @return True if the value is a member, false otherwise. + */ +bool set_contains(set_t* set, void* value); +/** + * @brief Returns the number of members in the set. + * + * @param set The set. + * + * @return The number of members in the set. + */ size_t set_size(set_t* set); +/** + * @brief Insert a value into the set. + * + * @param set The set. + * @param value The value to insert. + */ void set_insert(set_t* set, void* value); +/** + * @brief Delete a value from the set. + * + * @param set The set. + * @param value The value to delete. + */ void set_delete(set_t* set, void* value); #ifdef __cplusplus diff --git a/tests/main.c b/tests/main.c index 50ed8ae..0e3c745 100644 --- a/tests/main.c +++ b/tests/main.c @@ -11,5 +11,6 @@ int main(int argc, char** argv) RUN_TEST_SUITE(RBT); RUN_TEST_SUITE(Exn); RUN_TEST_SUITE(Mem); + RUN_TEST_SUITE(Set); return PRINT_TEST_RESULTS(); } diff --git a/tests/test_rbt.c b/tests/test_rbt.c index e4be027..e1ebba1 100644 --- a/tests/test_rbt.c +++ b/tests/test_rbt.c @@ -17,13 +17,6 @@ static int test_compare(void* env, void* a, void* b){ return (ia == ib ? 0 : (iaenv = NULL; - cmp->cmpfn = &test_compare; - return cmp; -} - typedef enum { OK = 0, OUT_OF_ORDER, @@ -54,8 +47,8 @@ static rbt_status_t rbt_check_node(rbt_t* tree, rbt_node_t* node, void* min_val, if(node->color != RED && node->color != BLACK) ret = UNKNOWN_COLOR; else if(node->color == RED && (rbt_node_color(node->left) != BLACK && rbt_node_color(node->right) != BLACK)) ret = RED_WITH_RED_CHILD; - else if(min_val && tree->comp->cmpfn(tree->comp->env, node->contents, min_val) < 0) ret = OUT_OF_ORDER; - else if(max_val && tree->comp->cmpfn(tree->comp->env, node->contents, max_val) > 0) ret = OUT_OF_ORDER; + else if(min_val && cmp_compare(tree->comp, node->contents, min_val) < 0) ret = OUT_OF_ORDER; + else if(max_val && cmp_compare(tree->comp, node->contents, max_val) > 0) ret = OUT_OF_ORDER; else if(node->left == node || node->right == node) ret = SELF_REFERENCE; else if(node->left && node->left->parent != node) ret = BAD_PARENT_POINTER; else if(node->right && node->right->parent != node) ret = BAD_PARENT_POINTER; @@ -101,7 +94,7 @@ TEST_SUITE(RBT) { // Test the rbt_new function //------------------------------------------------------------------------- TEST(Verify_rbt_new_returns_an_empty_red_black_tree){ - rbt_t* tree = rbt_new(test_comparator()); + rbt_t* tree = rbt_new(cmp_new(NULL,&test_compare)); CHECK(NULL != tree); CHECK(NULL == tree->root); CHECK(OK == rbt_check_status(tree)); @@ -114,14 +107,14 @@ TEST_SUITE(RBT) { TEST(Verify_null_and_empty_trees_are_considered_valid){ rbt_t* tree = NULL; CHECK(OK == rbt_check_status(tree)); - tree = rbt_new(test_comparator()); + tree = rbt_new(cmp_new(NULL,&test_compare)); CHECK(OK == rbt_check_status(tree)); mem_release(tree); } TEST(Verify_tree_is_valid_checks_root_is_always_black_property){ void* box88 = mem_box(88); - rbt_t* tree = rbt_new(test_comparator()); + rbt_t* tree = rbt_new(cmp_new(NULL,&test_compare)); rbt_insert(tree, box88); CHECK(BLACK == tree->root->color); CHECK(OK == rbt_check_status(tree)); @@ -133,7 +126,7 @@ TEST_SUITE(RBT) { TEST(Verify_tree_is_valid_fails_when_nodes_not_sorted_two_nodes){ void* box42 = mem_box(42); void* box88 = mem_box(88); - rbt_t* tree = rbt_new(test_comparator()); + rbt_t* tree = rbt_new(cmp_new(NULL,&test_compare)); rbt_node_t* node1 = rbt_node_new(box42); rbt_node_t* node2 = rbt_node_new(box88); tree->root = node1; @@ -154,7 +147,7 @@ TEST_SUITE(RBT) { void* box88 = mem_box(88); void* box25 = mem_box(25); void* box99 = mem_box(99); - rbt_t* tree = rbt_new(test_comparator()); + rbt_t* tree = rbt_new(cmp_new(NULL,&test_compare)); rbt_node_t* node1 = rbt_node_new(box42); rbt_node_t* node2 = rbt_node_new(box88); rbt_node_t* node3 = rbt_node_new(box25); @@ -189,7 +182,7 @@ TEST_SUITE(RBT) { TEST(Verify_tree_is_valid_fails_when_black_nodes_are_unbalanced_two_nodes){ void* box42 = mem_box(42); void* box88 = mem_box(88); - rbt_t* tree = rbt_new(test_comparator()); + rbt_t* tree = rbt_new(cmp_new(NULL,&test_compare)); rbt_node_t* node1 = rbt_node_new(box42); rbt_node_t* node2 = rbt_node_new(box88); tree->root = node1; @@ -211,7 +204,7 @@ TEST_SUITE(RBT) { void* box42 = mem_box(42); void* box22 = mem_box(22); void* box88 = mem_box(88); - rbt_t* tree = rbt_new(test_comparator()); + rbt_t* tree = rbt_new(cmp_new(NULL,&test_compare)); rbt_node_t* node1 = rbt_node_new(box42); rbt_node_t* node2 = rbt_node_new(box22); rbt_node_t* node3 = rbt_node_new(box88); @@ -246,7 +239,7 @@ TEST_SUITE(RBT) { void* box22 = mem_box(22); void* box88 = mem_box(88); void* box33 = mem_box(33); - rbt_t* tree = rbt_new(test_comparator()); + rbt_t* tree = rbt_new(cmp_new(NULL,&test_compare)); rbt_node_t* node1 = rbt_node_new(box42); rbt_node_t* node2 = rbt_node_new(box22); rbt_node_t* node3 = rbt_node_new(box88); @@ -286,7 +279,7 @@ TEST_SUITE(RBT) { TEST(Verify_tree_is_valid_fails_when_node_is_unvalid_color){ void* box42 = mem_box(42); void* box88 = mem_box(88); - rbt_t* tree = rbt_new(test_comparator()); + rbt_t* tree = rbt_new(cmp_new(NULL,&test_compare)); rbt_node_t* node1 = rbt_node_new(box42); rbt_node_t* node2 = rbt_node_new(box88); tree->root = node1; @@ -307,7 +300,7 @@ TEST_SUITE(RBT) { TEST(Verify_tree_is_valid_fails_when_root_parent_pointer_is_not_null){ void* box42 = mem_box(42); void* box88 = mem_box(88); - rbt_t* tree = rbt_new(test_comparator()); + rbt_t* tree = rbt_new(cmp_new(NULL,&test_compare)); rbt_node_t* node1 = rbt_node_new(box42); rbt_node_t* node2 = rbt_node_new(box88); tree->root = node1; @@ -329,7 +322,7 @@ TEST_SUITE(RBT) { void* box42 = mem_box(42); void* box88 = mem_box(88); void* box99 = mem_box(99); - rbt_t* tree = rbt_new(test_comparator()); + rbt_t* tree = rbt_new(cmp_new(NULL,&test_compare)); rbt_node_t* node1 = rbt_node_new(box42); rbt_node_t* node2 = rbt_node_new(box88); rbt_node_t* node3 = rbt_node_new(box99); @@ -358,7 +351,7 @@ TEST_SUITE(RBT) { void* box22 = mem_box(22); void* box88 = mem_box(88); void* box33 = mem_box(33); - rbt_t* tree = rbt_new(test_comparator()); + rbt_t* tree = rbt_new(cmp_new(NULL,&test_compare)); rbt_node_t* node1 = rbt_node_new(box42); rbt_node_t* node2 = rbt_node_new(box22); rbt_node_t* node3 = rbt_node_new(box88); @@ -397,7 +390,7 @@ TEST_SUITE(RBT) { void* box22 = mem_box(22); void* box88 = mem_box(88); void* box33 = mem_box(33); - rbt_t* tree = rbt_new(test_comparator()); + rbt_t* tree = rbt_new(cmp_new(NULL,&test_compare)); rbt_node_t* node1 = rbt_node_new(box42); rbt_node_t* node2 = rbt_node_new(box22); rbt_node_t* node3 = rbt_node_new(box88); @@ -455,7 +448,7 @@ TEST_SUITE(RBT) { //------------------------------------------------------------------------- TEST(Verify_rbt_insert_to_an_empty_list_assigns_root){ void* box42 = mem_box(42); - rbt_t* tree = rbt_new(test_comparator()); + rbt_t* tree = rbt_new(cmp_new(NULL,&test_compare)); rbt_node_t* node = rbt_insert(tree, box42); CHECK(NULL != node); CHECK(tree->root == node); @@ -470,7 +463,7 @@ TEST_SUITE(RBT) { TEST(Verify_rbt_insert_node_to_root_left_works){ void* box42 = mem_box(42); void* box31 = mem_box(31); - rbt_t* tree = rbt_new(test_comparator()); + rbt_t* tree = rbt_new(cmp_new(NULL,&test_compare)); rbt_node_t* root = rbt_insert(tree, box42); rbt_node_t* node1 = rbt_insert(tree, box31); CHECK(NULL != root); @@ -488,7 +481,7 @@ TEST_SUITE(RBT) { TEST(Verify_rbt_insert_node_to_root_right_works){ void* box42 = mem_box(42); void* box64 = mem_box(64); - rbt_t* tree = rbt_new(test_comparator()); + rbt_t* tree = rbt_new(cmp_new(NULL,&test_compare)); rbt_node_t* root = rbt_insert(tree, box42); rbt_node_t* node2 = rbt_insert(tree, box64); CHECK(NULL != root); @@ -507,7 +500,7 @@ TEST_SUITE(RBT) { void* box42 = mem_box(42); void* box31 = mem_box(31); void* box64 = mem_box(64); - rbt_t* tree = rbt_new(test_comparator()); + rbt_t* tree = rbt_new(cmp_new(NULL,&test_compare)); rbt_node_t* root = rbt_insert(tree, box42); rbt_node_t* node1 = rbt_insert(tree, box31); rbt_node_t* node2 = rbt_insert(tree, box64); @@ -532,7 +525,7 @@ TEST_SUITE(RBT) { void* box31 = mem_box(31); void* box64 = mem_box(64); void* box15 = mem_box(15); - rbt_t* tree = rbt_new(test_comparator()); + rbt_t* tree = rbt_new(cmp_new(NULL,&test_compare)); rbt_node_t* root = rbt_insert(tree, box42); rbt_node_t* node1 = rbt_insert(tree, box31); rbt_node_t* node2 = rbt_insert(tree, box64); @@ -554,7 +547,7 @@ TEST_SUITE(RBT) { void* box42 = mem_box(42); void* box32 = mem_box(32); void* box15 = mem_box(15); - rbt_t* tree = rbt_new(test_comparator()); + rbt_t* tree = rbt_new(cmp_new(NULL,&test_compare)); rbt_node_t* node1 = rbt_insert(tree, box42); rbt_node_t* node2 = rbt_insert(tree, box32); CHECK(node1 == tree->root); @@ -591,7 +584,7 @@ TEST_SUITE(RBT) { void* box42 = mem_box(42); void* box53 = mem_box(53); void* box99 = mem_box(99); - rbt_t* tree = rbt_new(test_comparator()); + rbt_t* tree = rbt_new(cmp_new(NULL,&test_compare)); rbt_node_t* node1 = rbt_insert(tree, box42); rbt_node_t* node2 = rbt_insert(tree, box53); CHECK(node1 == tree->root); @@ -627,7 +620,7 @@ TEST_SUITE(RBT) { void* box42 = mem_box(42); void* box20 = mem_box(20); void* box33 = mem_box(33); - rbt_t* tree = rbt_new(test_comparator()); + rbt_t* tree = rbt_new(cmp_new(NULL,&test_compare)); rbt_node_t* node1 = rbt_insert(tree, box42); rbt_node_t* node2 = rbt_insert(tree, box20); CHECK(node1 == tree->root); @@ -663,7 +656,7 @@ TEST_SUITE(RBT) { void* box42 = mem_box(42); void* box99 = mem_box(99); void* box88 = mem_box(88); - rbt_t* tree = rbt_new(test_comparator()); + rbt_t* tree = rbt_new(cmp_new(NULL,&test_compare)); rbt_node_t* node1 = rbt_insert(tree, box42); rbt_node_t* node2 = rbt_insert(tree, box99); CHECK(node1 == tree->root); @@ -704,7 +697,7 @@ TEST_SUITE(RBT) { void* box88 = mem_box(88); void* box15 = mem_box(15); void* box78 = mem_box(78); - rbt_t* tree = rbt_new(test_comparator()); + rbt_t* tree = rbt_new(cmp_new(NULL,&test_compare)); rbt_insert(tree, box42); rbt_insert(tree, box33); rbt_insert(tree, box88); @@ -719,7 +712,7 @@ TEST_SUITE(RBT) { void* box33 = mem_box(33); void* box88 = mem_box(88); void* box15 = mem_box(15); - rbt_t* tree = rbt_new(test_comparator()); + rbt_t* tree = rbt_new(cmp_new(NULL,&test_compare)); rbt_node_t* node1 = rbt_insert(tree, box42); rbt_node_t* node2 = rbt_insert(tree, box33); rbt_node_t* node3 = rbt_insert(tree, box88); @@ -751,7 +744,7 @@ TEST_SUITE(RBT) { void* box33 = mem_box(33); void* box88 = mem_box(88); void* box15 = mem_box(15); - rbt_t* tree = rbt_new(test_comparator()); + rbt_t* tree = rbt_new(cmp_new(NULL,&test_compare)); rbt_node_t* node1 = rbt_insert(tree, box42); rbt_node_t* node2 = rbt_insert(tree, box33); rbt_node_t* node3 = rbt_insert(tree, box88); @@ -783,7 +776,7 @@ TEST_SUITE(RBT) { void* box33 = mem_box(33); void* box88 = mem_box(88); void* box15 = mem_box(15); - rbt_t* tree = rbt_new(test_comparator()); + rbt_t* tree = rbt_new(cmp_new(NULL,&test_compare)); rbt_node_t* node1 = rbt_insert(tree, box42); rbt_node_t* node2 = rbt_insert(tree, box33); rbt_node_t* node3 = rbt_insert(tree, box88); @@ -815,7 +808,7 @@ TEST_SUITE(RBT) { void* box33 = mem_box(33); void* box88 = mem_box(88); void* box38 = mem_box(38); - rbt_t* tree = rbt_new(test_comparator()); + rbt_t* tree = rbt_new(cmp_new(NULL,&test_compare)); rbt_node_t* node1 = rbt_insert(tree, box42); rbt_node_t* node2 = rbt_insert(tree, box33); rbt_node_t* node3 = rbt_insert(tree, box88); @@ -847,7 +840,7 @@ TEST_SUITE(RBT) { void* box33 = mem_box(33); void* box88 = mem_box(88); void* box98 = mem_box(98); - rbt_t* tree = rbt_new(test_comparator()); + rbt_t* tree = rbt_new(cmp_new(NULL,&test_compare)); rbt_node_t* node1 = rbt_insert(tree, box42); rbt_node_t* node2 = rbt_insert(tree, box33); rbt_node_t* node3 = rbt_insert(tree, box88); @@ -879,7 +872,7 @@ TEST_SUITE(RBT) { void* box33 = mem_box(33); void* box88 = mem_box(88); void* box68 = mem_box(68); - rbt_t* tree = rbt_new(test_comparator()); + rbt_t* tree = rbt_new(cmp_new(NULL,&test_compare)); rbt_node_t* node1 = rbt_insert(tree, box42); rbt_node_t* node2 = rbt_insert(tree, box33); rbt_node_t* node3 = rbt_insert(tree, box88); @@ -918,7 +911,7 @@ TEST_SUITE(RBT) { void* box22 = mem_box(22); void* box88 = mem_box(88); void* box77 = mem_box(77); - rbt_t* tree = rbt_new(test_comparator()); + rbt_t* tree = rbt_new(cmp_new(NULL,&test_compare)); rbt_node_t* node1 = rbt_insert(tree, box42); //root rbt_node_t* node2 = rbt_insert(tree, box22); //untouched rbt_node_t* node3 = rbt_insert(tree, box88); //parent @@ -960,7 +953,7 @@ TEST_SUITE(RBT) { void* box99 = mem_box(99); void* box42 = mem_box(42); void* box55 = mem_box(55); - rbt_t* tree = rbt_new(test_comparator()); + rbt_t* tree = rbt_new(cmp_new(NULL,&test_compare)); rbt_node_t* node1 = rbt_insert(tree, box88); //root rbt_node_t* node2 = rbt_insert(tree, box99); //untouched rbt_node_t* node3 = rbt_insert(tree, box42); //parent @@ -1004,7 +997,7 @@ TEST_SUITE(RBT) { void* box88 = mem_box(88); void* box77 = mem_box(77); void* box70 = mem_box(70); - rbt_t* tree = rbt_new(test_comparator()); + rbt_t* tree = rbt_new(cmp_new(NULL,&test_compare)); rbt_node_t* node1 = rbt_insert(tree, box42); //root rbt_node_t* node2 = rbt_insert(tree, box22); //untouched rbt_node_t* node3 = rbt_insert(tree, box88); //parent @@ -1050,7 +1043,7 @@ TEST_SUITE(RBT) { void* box42 = mem_box(42); void* box55 = mem_box(55); void* box64 = mem_box(64); - rbt_t* tree = rbt_new(test_comparator()); + rbt_t* tree = rbt_new(cmp_new(NULL,&test_compare)); rbt_node_t* node1 = rbt_insert(tree, box88); //root rbt_node_t* node2 = rbt_insert(tree, box99); //untouched rbt_node_t* node3 = rbt_insert(tree, box42); //parent @@ -1097,7 +1090,7 @@ TEST_SUITE(RBT) { void* box88 = mem_box(88); void* box70 = mem_box(70); void* box78 = mem_box(78); - rbt_t* tree = rbt_new(test_comparator()); + rbt_t* tree = rbt_new(cmp_new(NULL,&test_compare)); rbt_node_t* node1 = rbt_insert(tree, box42); //root rbt_node_t* node2 = rbt_insert(tree, box22); //untouched rbt_node_t* node3 = rbt_insert(tree, box88); //parent @@ -1143,7 +1136,7 @@ TEST_SUITE(RBT) { void* box42 = mem_box(42); void* box55 = mem_box(55); void* box48 = mem_box(48); - rbt_t* tree = rbt_new(test_comparator()); + rbt_t* tree = rbt_new(cmp_new(NULL,&test_compare)); rbt_node_t* node1 = rbt_insert(tree, box88); //root rbt_node_t* node2 = rbt_insert(tree, box99); //untouched rbt_node_t* node3 = rbt_insert(tree, box42); //parent @@ -1191,7 +1184,7 @@ TEST_SUITE(RBT) { void* box70 = mem_box(70); void* box78 = mem_box(78); void* box64 = mem_box(64); - rbt_t* tree = rbt_new(test_comparator()); + rbt_t* tree = rbt_new(cmp_new(NULL,&test_compare)); rbt_node_t* node1 = rbt_insert(tree, box42); //root rbt_node_t* node2 = rbt_insert(tree, box22); //untouched rbt_node_t* node3 = rbt_insert(tree, box88); //parent @@ -1241,7 +1234,7 @@ TEST_SUITE(RBT) { void* box55 = mem_box(55); void* box48 = mem_box(48); void* box64 = mem_box(64); - rbt_t* tree = rbt_new(test_comparator()); + rbt_t* tree = rbt_new(cmp_new(NULL,&test_compare)); rbt_node_t* node1 = rbt_insert(tree, box88); //root rbt_node_t* node2 = rbt_insert(tree, box99); //untouched rbt_node_t* node3 = rbt_insert(tree, box42); //parent @@ -1290,7 +1283,7 @@ TEST_SUITE(RBT) { //create tree w/ several nodes void* box88 = mem_box(88); void* box42 = mem_box(42); - rbt_t* tree = rbt_new(test_comparator()); + rbt_t* tree = rbt_new(cmp_new(NULL,&test_compare)); rbt_node_t* node1 = rbt_insert(tree, box88); //root rbt_node_t* node2 = rbt_insert(tree, target); //target rbt_node_t* node3 = rbt_insert(tree, box42); //sibbling @@ -1324,7 +1317,7 @@ TEST_SUITE(RBT) { //create tree w/ several nodes void* box42 = mem_box(42); void* box88 = mem_box(88); - rbt_t* tree = rbt_new(test_comparator()); + rbt_t* tree = rbt_new(cmp_new(NULL,&test_compare)); rbt_node_t* node1 = rbt_insert(tree, box42); //root rbt_node_t* node2 = rbt_insert(tree, target); //target rbt_node_t* node3 = rbt_insert(tree, box88); //sibbling @@ -1368,7 +1361,7 @@ TEST_SUITE(RBT) { void* box80 = mem_box(80); void* box60 = mem_box(60); void* box33 = mem_box(33); - rbt_t* tree = rbt_new(test_comparator()); + rbt_t* tree = rbt_new(cmp_new(NULL,&test_compare)); rbt_node_t* node01 = rbt_insert(tree, box42); rbt_node_t* node02 = rbt_insert(tree, box22); rbt_node_t* node03 = rbt_insert(tree, box70); @@ -1433,7 +1426,7 @@ TEST_SUITE(RBT) { void* box20 = mem_box(20); void* box16 = mem_box(16); void* box11 = mem_box(11); - rbt_t* tree = rbt_new(test_comparator()); + rbt_t* tree = rbt_new(cmp_new(NULL,&test_compare)); rbt_node_t* node01 = rbt_insert(tree, box42); rbt_node_t* node02 = rbt_insert(tree, box66); rbt_node_t* node03 = rbt_insert(tree, box22); @@ -1495,7 +1488,7 @@ TEST_SUITE(RBT) { void* box99 = mem_box(99); void* box75 = mem_box(75); void* box33 = mem_box(33); - rbt_t* tree = rbt_new(test_comparator()); + rbt_t* tree = rbt_new(cmp_new(NULL,&test_compare)); rbt_node_t* node1 = rbt_insert(tree, box42); rbt_node_t* node2 = rbt_insert(tree, box22); rbt_node_t* node3 = rbt_insert(tree, box88); @@ -1543,7 +1536,7 @@ TEST_SUITE(RBT) { void* box99 = mem_box(99); void* box33 = mem_box(33); void* box15 = mem_box(15); - rbt_t* tree = rbt_new(test_comparator()); + rbt_t* tree = rbt_new(cmp_new(NULL,&test_compare)); rbt_node_t* node1 = rbt_insert(tree, box42); rbt_node_t* node2 = rbt_insert(tree, box22); rbt_node_t* node3 = rbt_insert(tree, box88); @@ -1596,7 +1589,7 @@ TEST_SUITE(RBT) { void* box33 = mem_box(33); void* box20 = mem_box(20); void* box16 = mem_box(16); - rbt_t* tree = rbt_new(test_comparator()); + rbt_t* tree = rbt_new(cmp_new(NULL,&test_compare)); rbt_node_t* node01 = rbt_insert(tree, box42); rbt_node_t* node02 = rbt_insert(tree, box66); rbt_node_t* node03 = rbt_insert(tree, box22); @@ -1661,7 +1654,7 @@ TEST_SUITE(RBT) { void* box60 = mem_box(60); void* box33 = mem_box(33); void* box15 = mem_box(15); - rbt_t* tree = rbt_new(test_comparator()); + rbt_t* tree = rbt_new(cmp_new(NULL,&test_compare)); rbt_node_t* node01 = rbt_insert(tree, box42); rbt_node_t* node02 = rbt_insert(tree, box22); rbt_node_t* node03 = rbt_insert(tree, box70); @@ -1725,7 +1718,7 @@ TEST_SUITE(RBT) { void* box30 = mem_box(30); void* box89 = mem_box(89); void* box95 = mem_box(95); - rbt_t* tree = rbt_new(test_comparator()); + rbt_t* tree = rbt_new(cmp_new(NULL,&test_compare)); rbt_node_t* node01 = rbt_insert(tree, box42); rbt_node_t* node02 = rbt_insert(tree, box22); rbt_node_t* node03 = rbt_insert(tree, box55); @@ -1781,7 +1774,7 @@ TEST_SUITE(RBT) { void* box50 = mem_box(50); void* box17 = mem_box(17); void* box11 = mem_box(11); - rbt_t* tree = rbt_new(test_comparator()); + rbt_t* tree = rbt_new(cmp_new(NULL,&test_compare)); rbt_node_t* node01 = rbt_insert(tree, box42); rbt_node_t* node02 = rbt_insert(tree, box55); rbt_node_t* node03 = rbt_insert(tree, box33); @@ -1838,7 +1831,7 @@ TEST_SUITE(RBT) { void* box30 = mem_box(30); void* box50 = mem_box(50); void* box65 = mem_box(65); - rbt_t* tree = rbt_new(test_comparator()); + rbt_t* tree = rbt_new(cmp_new(NULL,&test_compare)); rbt_node_t* node01 = rbt_insert(tree, box42); rbt_node_t* node02 = rbt_insert(tree, box22); rbt_node_t* node03 = rbt_insert(tree, box55); @@ -1894,7 +1887,7 @@ TEST_SUITE(RBT) { void* box50 = mem_box(50); void* box37 = mem_box(37); void* box28 = mem_box(28); - rbt_t* tree = rbt_new(test_comparator()); + rbt_t* tree = rbt_new(cmp_new(NULL,&test_compare)); rbt_node_t* node01 = rbt_insert(tree, box42); rbt_node_t* node02 = rbt_insert(tree, box55); rbt_node_t* node03 = rbt_insert(tree, box33); @@ -1953,7 +1946,7 @@ TEST_SUITE(RBT) { void* box65 = mem_box(65); void* box89 = mem_box(89); void* box99 = mem_box(99); - rbt_t* tree = rbt_new(test_comparator()); + rbt_t* tree = rbt_new(cmp_new(NULL,&test_compare)); rbt_node_t* node01 = rbt_insert(tree, box42); rbt_node_t* node02 = rbt_insert(tree, box22); rbt_node_t* node03 = rbt_insert(tree, box55); @@ -2017,7 +2010,7 @@ TEST_SUITE(RBT) { void* box28 = mem_box(28); void* box17 = mem_box(17); void* box11 = mem_box(11); - rbt_t* tree = rbt_new(test_comparator()); + rbt_t* tree = rbt_new(cmp_new(NULL,&test_compare)); rbt_node_t* node01 = rbt_insert(tree, box42); rbt_node_t* node02 = rbt_insert(tree, box55); rbt_node_t* node03 = rbt_insert(tree, box33); @@ -2076,7 +2069,7 @@ TEST_SUITE(RBT) { void* box88 = mem_box(88); void* box42 = mem_box(42); void* box22 = mem_box(22); - rbt_t* tree = rbt_new(test_comparator()); + rbt_t* tree = rbt_new(cmp_new(NULL,&test_compare)); rbt_node_t* node1 = rbt_insert(tree, box88); //root rbt_node_t* node2 = rbt_insert(tree, target); //target rbt_node_t* node3 = rbt_insert(tree, box42); //sibbling @@ -2114,7 +2107,7 @@ TEST_SUITE(RBT) { void* box42 = mem_box(42); void* box88 = mem_box(88); void* box123 = mem_box(123); - rbt_t* tree = rbt_new(test_comparator()); + rbt_t* tree = rbt_new(cmp_new(NULL,&test_compare)); rbt_node_t* node1 = rbt_insert(tree, box42); //root rbt_node_t* node2 = rbt_insert(tree, target); //target rbt_node_t* node3 = rbt_insert(tree, box88); //sibbling @@ -2153,7 +2146,7 @@ TEST_SUITE(RBT) { void* box88 = mem_box(88); void* box42 = mem_box(42); void* box55 = mem_box(55); - rbt_t* tree = rbt_new(test_comparator()); + rbt_t* tree = rbt_new(cmp_new(NULL,&test_compare)); rbt_node_t* node1 = rbt_insert(tree, box88); //root rbt_node_t* node2 = rbt_insert(tree, target); //target rbt_node_t* node3 = rbt_insert(tree, box42); //sibbling @@ -2191,7 +2184,7 @@ TEST_SUITE(RBT) { void* box42 = mem_box(42); void* box88 = mem_box(88); void* box70 = mem_box(70); - rbt_t* tree = rbt_new(test_comparator()); + rbt_t* tree = rbt_new(cmp_new(NULL,&test_compare)); rbt_node_t* node1 = rbt_insert(tree, box42); //root rbt_node_t* node2 = rbt_insert(tree, target); //target rbt_node_t* node3 = rbt_insert(tree, box88); //sibbling @@ -2231,7 +2224,7 @@ TEST_SUITE(RBT) { void* box42 = mem_box(42); void* box22 = mem_box(22); void* box55 = mem_box(55); - rbt_t* tree = rbt_new(test_comparator()); + rbt_t* tree = rbt_new(cmp_new(NULL,&test_compare)); rbt_node_t* node1 = rbt_insert(tree, box88); //root rbt_node_t* node2 = rbt_insert(tree, target); //target rbt_node_t* node3 = rbt_insert(tree, box42); //sibbling @@ -2273,7 +2266,7 @@ TEST_SUITE(RBT) { void* box88 = mem_box(88); void* box70 = mem_box(70); void* box123 = mem_box(123); - rbt_t* tree = rbt_new(test_comparator()); + rbt_t* tree = rbt_new(cmp_new(NULL,&test_compare)); rbt_node_t* node1 = rbt_insert(tree, box42); //root rbt_node_t* node2 = rbt_insert(tree, target); //target rbt_node_t* node3 = rbt_insert(tree, box88); //sibbling @@ -2316,7 +2309,7 @@ TEST_SUITE(RBT) { void* box42 = mem_box(42); void* box22 = mem_box(22); void* box55 = mem_box(55); - rbt_t* tree = rbt_new(test_comparator()); + rbt_t* tree = rbt_new(cmp_new(NULL,&test_compare)); rbt_node_t* node1 = rbt_insert(tree, box88); //root rbt_node_t* node2 = rbt_insert(tree, target); //target rbt_node_t* node3 = rbt_insert(tree, box42); //sibbling @@ -2358,7 +2351,7 @@ TEST_SUITE(RBT) { void* box88 = mem_box(88); void* box70 = mem_box(70); void* box123 = mem_box(123); - rbt_t* tree = rbt_new(test_comparator()); + rbt_t* tree = rbt_new(cmp_new(NULL,&test_compare)); rbt_node_t* node1 = rbt_insert(tree, box42); //root rbt_node_t* node2 = rbt_insert(tree, target); //target rbt_node_t* node3 = rbt_insert(tree, box88); //sibbling @@ -2400,7 +2393,7 @@ TEST_SUITE(RBT) { void* box88 = mem_box(88); void* box33 = mem_box(33); void* box15 = mem_box(15); - rbt_t* tree = rbt_new(test_comparator()); + rbt_t* tree = rbt_new(cmp_new(NULL,&test_compare)); rbt_insert(tree, box42); rbt_insert(tree, box88); rbt_node_t* doomed = rbt_insert(tree, target); @@ -2436,7 +2429,7 @@ TEST_SUITE(RBT) { void* box25 = mem_box(25); void* box55 = mem_box(55); void* box99 = mem_box(99); - rbt_t* tree = rbt_new(test_comparator()); + rbt_t* tree = rbt_new(cmp_new(NULL,&test_compare)); rbt_node_t* doomed = rbt_insert(tree, target); rbt_insert(tree, box88); rbt_insert(tree, box22); @@ -2470,7 +2463,7 @@ TEST_SUITE(RBT) { TEST(Verify_rbt_delete_root_node_with_single_red_left_child){ void* box88 = mem_box(88); void* box42 = mem_box(42); - rbt_t* tree = rbt_new(test_comparator()); + rbt_t* tree = rbt_new(cmp_new(NULL,&test_compare)); rbt_node_t* node1 = rbt_insert(tree, box88); rbt_node_t* node2 = rbt_insert(tree, box42); mem_retain(node1); @@ -2492,7 +2485,7 @@ TEST_SUITE(RBT) { TEST(Verify_rbt_delete_root_node_with_single_red_right_child){ void* box42 = mem_box(42); void* box88 = mem_box(88); - rbt_t* tree = rbt_new(test_comparator()); + rbt_t* tree = rbt_new(cmp_new(NULL,&test_compare)); rbt_node_t* node1 = rbt_insert(tree, box42); rbt_node_t* node2 = rbt_insert(tree, box88); mem_retain(node1); @@ -2513,7 +2506,7 @@ TEST_SUITE(RBT) { TEST(Verify_rbt_delete_root_node_with_no_children){ void* box88 = mem_box(88); - rbt_t* tree = rbt_new(test_comparator()); + rbt_t* tree = rbt_new(cmp_new(NULL,&test_compare)); rbt_node_t* node1 = rbt_insert(tree, box88); mem_retain(node1); rbt_delete(tree, box88); @@ -2540,7 +2533,7 @@ TEST_SUITE(RBT) { void* box25 = mem_box(25); void* box55 = mem_box(55); void* box99 = mem_box(99); - rbt_t* tree = rbt_new(test_comparator()); + rbt_t* tree = rbt_new(cmp_new(NULL,&test_compare)); rbt_insert(tree, box42); rbt_insert(tree, box88); rbt_node_t* doomed = rbt_insert(tree, target); @@ -2575,7 +2568,7 @@ TEST_SUITE(RBT) { void* box88 = mem_box(88); void* box22 = mem_box(22); void* box33 = mem_box(33); - rbt_t* tree = rbt_new(test_comparator()); + rbt_t* tree = rbt_new(cmp_new(NULL,&test_compare)); rbt_node_t* doomed = rbt_insert(tree, target); rbt_insert(tree, box88); rbt_insert(tree, box22); @@ -2603,7 +2596,7 @@ TEST_SUITE(RBT) { void* box88 = mem_box(88); void* box36 = mem_box(36); void* box99 = mem_box(99); - rbt_t* tree = rbt_new(test_comparator()); + rbt_t* tree = rbt_new(cmp_new(NULL,&test_compare)); //rbt_t* tree = rbt_new(NULL); rbt_delete(tree, target); CHECK(OK == rbt_check_status(tree)); diff --git a/tests/test_set.c b/tests/test_set.c new file mode 100644 index 0000000..3ef6570 --- /dev/null +++ b/tests/test_set.c @@ -0,0 +1,118 @@ +// Unit Test Framework Includes +#include "test.h" + +// File To Test +#include "set.h" +#include "murmur3.h" + +static void test_setup(void) { } + +static uint32_t hash_int(void* obj) { + intptr_t val = mem_unbox(obj); + return murmur3_32((uint8_t*)&val, sizeof(intptr_t)); +} + +static int cmp_int(void* env, void* obja, void* objb) { + uintptr_t inta = mem_unbox(obja); + uintptr_t intb = mem_unbox(objb); + (void)env; + if (inta < intb) + return -1; + else if (intb < inta) + return 1; + else + return 0; +} + +//----------------------------------------------------------------------------- +// Begin Unit Tests +//----------------------------------------------------------------------------- +TEST_SUITE(Set) { + //------------------------------------------------------------------------- + // Test set_new function + //------------------------------------------------------------------------- + TEST(Verify_set_new) + { + set_t* set = set_new(cmp_new(NULL, cmp_int), hash_int); + mem_release(set); + } + + //------------------------------------------------------------------------- + // Test set_contains function + //------------------------------------------------------------------------- + TEST(Verify_set_contains_should_return_true_if_the_item_is_in_the_set) + { + set_t* set = set_new(cmp_new(NULL, cmp_int), hash_int); + void* boxed_val = mem_box(42); + set_insert(set, boxed_val); + CHECK(set_size(set) == 1); + CHECK(set_contains(set, boxed_val)); + mem_release(set); + } + + TEST(Verify_set_contains_should_return_false_if_the_item_is_not_in_the_set) + { + set_t* set = set_new(cmp_new(NULL, cmp_int), hash_int); + void* lup_val = mem_box(43); + set_insert(set, mem_box(42)); + CHECK(set_size(set) == 1); + CHECK(!set_contains(set, lup_val)); + mem_release(set); + mem_release(lup_val); + } + + //------------------------------------------------------------------------- + // Test set_insert function + //------------------------------------------------------------------------- + TEST(Verify_set_insert_multiple_times_with_the_same_value_only_inserts_once) + { + set_t* set = set_new(cmp_new(NULL, cmp_int), hash_int); + void* lup_val = mem_box(42); + set_insert(set, mem_box(42)); + set_insert(set, mem_box(42)); + CHECK(set_size(set) == 1); + CHECK(set_contains(set, lup_val)); + mem_release(set); + mem_release(lup_val); + } + + TEST(Verify_set_insert_a_value_less_than_an_existing_value) + { + set_t* set = set_new(cmp_new(NULL, cmp_int), hash_int); + void* lup_val = mem_box(41); + set_insert(set, mem_box(42)); + set_insert(set, mem_box(41)); + CHECK(set_size(set) == 2); + CHECK(set_contains(set, lup_val)); + mem_release(set); + mem_release(lup_val); + } + + TEST(Verify_set_insert_a_value_greater_than_an_existing_value) + { + set_t* set = set_new(cmp_new(NULL, cmp_int), hash_int); + void* lup_val = mem_box(42); + set_insert(set, mem_box(41)); + set_insert(set, mem_box(42)); + CHECK(set_size(set) == 2); + CHECK(set_contains(set, lup_val)); + mem_release(set); + mem_release(lup_val); + } + + //------------------------------------------------------------------------- + // Test set_delete function + //------------------------------------------------------------------------- + TEST(Verify_set_delete_deletes_the_item_from_the_set) + { + set_t* set = set_new(cmp_new(NULL, cmp_int), hash_int); + void* del_val = mem_box(42); + CHECK(set_size(set) == 0); + set_insert(set, mem_box(42)); + CHECK(set_size(set) == 1); + set_delete(set, del_val); + CHECK(set_size(set) == 0); + mem_release(set); + mem_release(del_val); + } +} -- 2.55.0