From 7f108a303106f460615c8ba3462d09869980d900 Mon Sep 17 00:00:00 2001 From: "Mike D. Lowis" Date: Fri, 22 May 2015 17:54:09 -0400 Subject: [PATCH] Start implementation of set module --- source/rbt/rbt.c | 19 ++++-- source/rbt/rbt.h | 15 ++--- source/set/set.c | 143 +++++++++++++++++++++++++++++++++++++++++++++ source/set/set.h | 33 +++++++++++ tests/test_rbt.c | 148 +++++++++++++++++++++++++---------------------- 5 files changed, 276 insertions(+), 82 deletions(-) create mode 100644 source/set/set.c diff --git a/source/rbt/rbt.c b/source/rbt/rbt.c index 843d456..2abe719 100644 --- a/source/rbt/rbt.c +++ b/source/rbt/rbt.c @@ -5,12 +5,20 @@ #include "rbt.h" //nodes are compared by memory address by default -static int rbt_default_comparator(void* v_a, void* v_b){ +static int rbt_default_compare(void* env, void* v_a, void* v_b){ uintptr_t a = (intptr_t)v_a; uintptr_t b = (intptr_t)v_b; + (void)env; return (a == b ? 0 : (aenv = NULL; + cmp->cmpfn = &rbt_default_compare; + return cmp; +} + /* -------------------------------- */ /* destructors / constructors */ /* -------------------------------- */ @@ -20,12 +28,13 @@ static void rbt_free(void* v_tree){ rbt_t* tree = (rbt_t*) v_tree; assert(NULL != tree); if(tree->root) mem_release(tree->root); + if(tree->comp) mem_release(tree->comp); } -rbt_t* rbt_new(comparator_t comparator){ +rbt_t* rbt_new(comparator_t* comparator){ rbt_t* tree = mem_allocate(sizeof(rbt_t), &rbt_free); tree->root = NULL; - tree->comp = comparator ? comparator : rbt_default_comparator; + tree->comp = comparator ? comparator : rbt_default_comparator(); return tree; } @@ -66,7 +75,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(value, node->contents); + int c = tree->comp->cmpfn(tree->comp->env, 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; @@ -160,7 +169,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(node->contents, parent->contents); + int c = tree->comp->cmpfn(tree->comp->env, 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 b47755d..ec1c08f 100644 --- a/source/rbt/rbt.h +++ b/source/rbt/rbt.h @@ -19,7 +19,12 @@ typedef enum { /** a function pointer for comparing node contents should return -1, 0, or 1 if a is <, ==, or > b, respectively */ -typedef int (*comparator_t)(void* p_a, void* p_b); +//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 { @@ -38,10 +43,9 @@ typedef struct { /** pointer to the root of the tree */ rbt_node_t* root; /** function pointer for comparing node contents */ - comparator_t comp; + comparator_t* comp; } rbt_t; - /** * @brief creates a new red-black tree * @@ -49,8 +53,7 @@ typedef struct { * * @return pointer to newly created tree */ -rbt_t* rbt_new(comparator_t comparator); - +rbt_t* rbt_new(comparator_t* comparator); /** * @brief find a value in a red-black tree @@ -63,7 +66,6 @@ rbt_t* rbt_new(comparator_t comparator); */ rbt_node_t* rbt_lookup(rbt_t* tree, void* value); - /** * @brief count the number of nodes in a red-black tree * @@ -83,7 +85,6 @@ int rbt_size(rbt_t* tree); */ rbt_node_t* rbt_insert(rbt_t* tree, void* value); - /** * @brief removes a value from a red-black tree * diff --git a/source/set/set.c b/source/set/set.c new file mode 100644 index 0000000..5c641f6 --- /dev/null +++ b/source/set/set.c @@ -0,0 +1,143 @@ +/** + @file set.c + @brief See header for details + */ +#include "set.h" + +typedef struct { + void* value; + uint32_t hash; +} set_pair_t; + +struct set_t { + hash_fn_t hash_func; + comparator_t* user_comp; + comparator_t* comp; + rbt_t* tree; +}; + +//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; +// 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); +// } +//} + +//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; +//} + +bool set_contains(set_t* set, void* value) +{ + (void)set; + (void)value; + return false; +} + +size_t set_size(set_t* set) +{ + (void)set; + return 0; +} + +void set_insert(set_t* set, void* value) +{ + (void)set; + (void)value; +} + +void set_delete(set_t* set, void* value) +{ + (void)set; + (void)value; +} + + +/** + * 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 e69de29..6236b77 100644 --- a/source/set/set.h +++ b/source/set/set.h @@ -0,0 +1,33 @@ +/** + @file set.h + @brief TODO: Describe this file + */ +#ifndef SET_H +#define SET_H + +#ifdef __cplusplus +extern "C" { +#endif + +#include "rbt.h" + +typedef uint32_t (*hashfn_t)(const void* obj); + +struct set_t; +typedef struct set_t set_t; + +set_t* set_new(comparator_t comparator); + +bool set_contains(set_t* p_set, void* value); + +size_t set_size(set_t* set); + +void set_insert(set_t* set, void* value); + +void set_delete(set_t* set, void* value); + +#ifdef __cplusplus +} +#endif + +#endif /* SET_H */ diff --git a/tests/test_rbt.c b/tests/test_rbt.c index ebfa26c..e4be027 100644 --- a/tests/test_rbt.c +++ b/tests/test_rbt.c @@ -10,12 +10,20 @@ extern rbt_color_t rbt_node_color(rbt_node_t* node); extern rbt_node_t* rbt_node_new(void* contents); -static int test_compare(void* a, void* b){ +static int test_compare(void* env, void* a, void* b){ int ia = (int)(mem_unbox(a)); int ib = (int)(mem_unbox(b)); + (void)env; return (ia == ib ? 0 : (iaenv = NULL; + cmp->cmpfn = &test_compare; + return cmp; +} + typedef enum { OK = 0, OUT_OF_ORDER, @@ -46,8 +54,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(node->contents, min_val) < 0) ret = OUT_OF_ORDER; - else if(max_val && tree->comp(node->contents, max_val) > 0) ret = OUT_OF_ORDER; + 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(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; @@ -93,7 +101,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_compare); + rbt_t* tree = rbt_new(test_comparator()); CHECK(NULL != tree); CHECK(NULL == tree->root); CHECK(OK == rbt_check_status(tree)); @@ -106,14 +114,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_compare); + tree = rbt_new(test_comparator()); 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_compare); + rbt_t* tree = rbt_new(test_comparator()); rbt_insert(tree, box88); CHECK(BLACK == tree->root->color); CHECK(OK == rbt_check_status(tree)); @@ -125,7 +133,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_compare); + rbt_t* tree = rbt_new(test_comparator()); rbt_node_t* node1 = rbt_node_new(box42); rbt_node_t* node2 = rbt_node_new(box88); tree->root = node1; @@ -146,7 +154,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_compare); + rbt_t* tree = rbt_new(test_comparator()); rbt_node_t* node1 = rbt_node_new(box42); rbt_node_t* node2 = rbt_node_new(box88); rbt_node_t* node3 = rbt_node_new(box25); @@ -181,7 +189,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_compare); + rbt_t* tree = rbt_new(test_comparator()); rbt_node_t* node1 = rbt_node_new(box42); rbt_node_t* node2 = rbt_node_new(box88); tree->root = node1; @@ -203,7 +211,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_compare); + rbt_t* tree = rbt_new(test_comparator()); rbt_node_t* node1 = rbt_node_new(box42); rbt_node_t* node2 = rbt_node_new(box22); rbt_node_t* node3 = rbt_node_new(box88); @@ -238,7 +246,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_compare); + rbt_t* tree = rbt_new(test_comparator()); rbt_node_t* node1 = rbt_node_new(box42); rbt_node_t* node2 = rbt_node_new(box22); rbt_node_t* node3 = rbt_node_new(box88); @@ -278,7 +286,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_compare); + rbt_t* tree = rbt_new(test_comparator()); rbt_node_t* node1 = rbt_node_new(box42); rbt_node_t* node2 = rbt_node_new(box88); tree->root = node1; @@ -299,7 +307,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_compare); + rbt_t* tree = rbt_new(test_comparator()); rbt_node_t* node1 = rbt_node_new(box42); rbt_node_t* node2 = rbt_node_new(box88); tree->root = node1; @@ -321,7 +329,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_compare); + rbt_t* tree = rbt_new(test_comparator()); rbt_node_t* node1 = rbt_node_new(box42); rbt_node_t* node2 = rbt_node_new(box88); rbt_node_t* node3 = rbt_node_new(box99); @@ -350,7 +358,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_compare); + rbt_t* tree = rbt_new(test_comparator()); rbt_node_t* node1 = rbt_node_new(box42); rbt_node_t* node2 = rbt_node_new(box22); rbt_node_t* node3 = rbt_node_new(box88); @@ -389,7 +397,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_compare); + rbt_t* tree = rbt_new(test_comparator()); rbt_node_t* node1 = rbt_node_new(box42); rbt_node_t* node2 = rbt_node_new(box22); rbt_node_t* node3 = rbt_node_new(box88); @@ -447,7 +455,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_compare); + rbt_t* tree = rbt_new(test_comparator()); rbt_node_t* node = rbt_insert(tree, box42); CHECK(NULL != node); CHECK(tree->root == node); @@ -462,7 +470,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_compare); + rbt_t* tree = rbt_new(test_comparator()); rbt_node_t* root = rbt_insert(tree, box42); rbt_node_t* node1 = rbt_insert(tree, box31); CHECK(NULL != root); @@ -480,7 +488,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_compare); + rbt_t* tree = rbt_new(test_comparator()); rbt_node_t* root = rbt_insert(tree, box42); rbt_node_t* node2 = rbt_insert(tree, box64); CHECK(NULL != root); @@ -499,7 +507,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_compare); + rbt_t* tree = rbt_new(test_comparator()); rbt_node_t* root = rbt_insert(tree, box42); rbt_node_t* node1 = rbt_insert(tree, box31); rbt_node_t* node2 = rbt_insert(tree, box64); @@ -524,7 +532,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_compare); + rbt_t* tree = rbt_new(test_comparator()); rbt_node_t* root = rbt_insert(tree, box42); rbt_node_t* node1 = rbt_insert(tree, box31); rbt_node_t* node2 = rbt_insert(tree, box64); @@ -546,7 +554,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_compare); + rbt_t* tree = rbt_new(test_comparator()); rbt_node_t* node1 = rbt_insert(tree, box42); rbt_node_t* node2 = rbt_insert(tree, box32); CHECK(node1 == tree->root); @@ -583,7 +591,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_compare); + rbt_t* tree = rbt_new(test_comparator()); rbt_node_t* node1 = rbt_insert(tree, box42); rbt_node_t* node2 = rbt_insert(tree, box53); CHECK(node1 == tree->root); @@ -619,7 +627,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_compare); + rbt_t* tree = rbt_new(test_comparator()); rbt_node_t* node1 = rbt_insert(tree, box42); rbt_node_t* node2 = rbt_insert(tree, box20); CHECK(node1 == tree->root); @@ -655,7 +663,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_compare); + rbt_t* tree = rbt_new(test_comparator()); rbt_node_t* node1 = rbt_insert(tree, box42); rbt_node_t* node2 = rbt_insert(tree, box99); CHECK(node1 == tree->root); @@ -696,7 +704,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_compare); + rbt_t* tree = rbt_new(test_comparator()); rbt_insert(tree, box42); rbt_insert(tree, box33); rbt_insert(tree, box88); @@ -711,7 +719,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_compare); + rbt_t* tree = rbt_new(test_comparator()); rbt_node_t* node1 = rbt_insert(tree, box42); rbt_node_t* node2 = rbt_insert(tree, box33); rbt_node_t* node3 = rbt_insert(tree, box88); @@ -743,7 +751,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_compare); + rbt_t* tree = rbt_new(test_comparator()); rbt_node_t* node1 = rbt_insert(tree, box42); rbt_node_t* node2 = rbt_insert(tree, box33); rbt_node_t* node3 = rbt_insert(tree, box88); @@ -775,7 +783,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_compare); + rbt_t* tree = rbt_new(test_comparator()); rbt_node_t* node1 = rbt_insert(tree, box42); rbt_node_t* node2 = rbt_insert(tree, box33); rbt_node_t* node3 = rbt_insert(tree, box88); @@ -807,7 +815,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_compare); + rbt_t* tree = rbt_new(test_comparator()); rbt_node_t* node1 = rbt_insert(tree, box42); rbt_node_t* node2 = rbt_insert(tree, box33); rbt_node_t* node3 = rbt_insert(tree, box88); @@ -839,7 +847,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_compare); + rbt_t* tree = rbt_new(test_comparator()); rbt_node_t* node1 = rbt_insert(tree, box42); rbt_node_t* node2 = rbt_insert(tree, box33); rbt_node_t* node3 = rbt_insert(tree, box88); @@ -871,7 +879,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_compare); + rbt_t* tree = rbt_new(test_comparator()); rbt_node_t* node1 = rbt_insert(tree, box42); rbt_node_t* node2 = rbt_insert(tree, box33); rbt_node_t* node3 = rbt_insert(tree, box88); @@ -910,7 +918,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_compare); + rbt_t* tree = rbt_new(test_comparator()); 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 @@ -952,7 +960,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_compare); + rbt_t* tree = rbt_new(test_comparator()); 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 @@ -996,7 +1004,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_compare); + rbt_t* tree = rbt_new(test_comparator()); 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 @@ -1042,7 +1050,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_compare); + rbt_t* tree = rbt_new(test_comparator()); 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 @@ -1089,7 +1097,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_compare); + rbt_t* tree = rbt_new(test_comparator()); 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 @@ -1135,7 +1143,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_compare); + rbt_t* tree = rbt_new(test_comparator()); 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 @@ -1183,7 +1191,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_compare); + rbt_t* tree = rbt_new(test_comparator()); 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 @@ -1233,7 +1241,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_compare); + rbt_t* tree = rbt_new(test_comparator()); 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 @@ -1282,7 +1290,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_compare); + rbt_t* tree = rbt_new(test_comparator()); 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 @@ -1316,7 +1324,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_compare); + rbt_t* tree = rbt_new(test_comparator()); 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 @@ -1360,7 +1368,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_compare); + rbt_t* tree = rbt_new(test_comparator()); rbt_node_t* node01 = rbt_insert(tree, box42); rbt_node_t* node02 = rbt_insert(tree, box22); rbt_node_t* node03 = rbt_insert(tree, box70); @@ -1425,7 +1433,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_compare); + rbt_t* tree = rbt_new(test_comparator()); rbt_node_t* node01 = rbt_insert(tree, box42); rbt_node_t* node02 = rbt_insert(tree, box66); rbt_node_t* node03 = rbt_insert(tree, box22); @@ -1487,7 +1495,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_compare); + rbt_t* tree = rbt_new(test_comparator()); rbt_node_t* node1 = rbt_insert(tree, box42); rbt_node_t* node2 = rbt_insert(tree, box22); rbt_node_t* node3 = rbt_insert(tree, box88); @@ -1535,7 +1543,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_compare); + rbt_t* tree = rbt_new(test_comparator()); rbt_node_t* node1 = rbt_insert(tree, box42); rbt_node_t* node2 = rbt_insert(tree, box22); rbt_node_t* node3 = rbt_insert(tree, box88); @@ -1588,7 +1596,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_compare); + rbt_t* tree = rbt_new(test_comparator()); rbt_node_t* node01 = rbt_insert(tree, box42); rbt_node_t* node02 = rbt_insert(tree, box66); rbt_node_t* node03 = rbt_insert(tree, box22); @@ -1653,7 +1661,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_compare); + rbt_t* tree = rbt_new(test_comparator()); rbt_node_t* node01 = rbt_insert(tree, box42); rbt_node_t* node02 = rbt_insert(tree, box22); rbt_node_t* node03 = rbt_insert(tree, box70); @@ -1717,7 +1725,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_compare); + rbt_t* tree = rbt_new(test_comparator()); rbt_node_t* node01 = rbt_insert(tree, box42); rbt_node_t* node02 = rbt_insert(tree, box22); rbt_node_t* node03 = rbt_insert(tree, box55); @@ -1773,7 +1781,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_compare); + rbt_t* tree = rbt_new(test_comparator()); rbt_node_t* node01 = rbt_insert(tree, box42); rbt_node_t* node02 = rbt_insert(tree, box55); rbt_node_t* node03 = rbt_insert(tree, box33); @@ -1830,7 +1838,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_compare); + rbt_t* tree = rbt_new(test_comparator()); rbt_node_t* node01 = rbt_insert(tree, box42); rbt_node_t* node02 = rbt_insert(tree, box22); rbt_node_t* node03 = rbt_insert(tree, box55); @@ -1886,7 +1894,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_compare); + rbt_t* tree = rbt_new(test_comparator()); rbt_node_t* node01 = rbt_insert(tree, box42); rbt_node_t* node02 = rbt_insert(tree, box55); rbt_node_t* node03 = rbt_insert(tree, box33); @@ -1945,7 +1953,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_compare); + rbt_t* tree = rbt_new(test_comparator()); rbt_node_t* node01 = rbt_insert(tree, box42); rbt_node_t* node02 = rbt_insert(tree, box22); rbt_node_t* node03 = rbt_insert(tree, box55); @@ -2009,7 +2017,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_compare); + rbt_t* tree = rbt_new(test_comparator()); rbt_node_t* node01 = rbt_insert(tree, box42); rbt_node_t* node02 = rbt_insert(tree, box55); rbt_node_t* node03 = rbt_insert(tree, box33); @@ -2068,7 +2076,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_compare); + rbt_t* tree = rbt_new(test_comparator()); 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 @@ -2106,7 +2114,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_compare); + rbt_t* tree = rbt_new(test_comparator()); 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 @@ -2145,7 +2153,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_compare); + rbt_t* tree = rbt_new(test_comparator()); 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 @@ -2183,7 +2191,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_compare); + rbt_t* tree = rbt_new(test_comparator()); 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 @@ -2223,7 +2231,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_compare); + rbt_t* tree = rbt_new(test_comparator()); 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 @@ -2265,7 +2273,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_compare); + rbt_t* tree = rbt_new(test_comparator()); 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 @@ -2308,7 +2316,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_compare); + rbt_t* tree = rbt_new(test_comparator()); 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 @@ -2350,7 +2358,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_compare); + rbt_t* tree = rbt_new(test_comparator()); 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 @@ -2392,7 +2400,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_compare); + rbt_t* tree = rbt_new(test_comparator()); rbt_insert(tree, box42); rbt_insert(tree, box88); rbt_node_t* doomed = rbt_insert(tree, target); @@ -2428,7 +2436,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_compare); + rbt_t* tree = rbt_new(test_comparator()); rbt_node_t* doomed = rbt_insert(tree, target); rbt_insert(tree, box88); rbt_insert(tree, box22); @@ -2462,7 +2470,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_compare); + rbt_t* tree = rbt_new(test_comparator()); rbt_node_t* node1 = rbt_insert(tree, box88); rbt_node_t* node2 = rbt_insert(tree, box42); mem_retain(node1); @@ -2484,7 +2492,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_compare); + rbt_t* tree = rbt_new(test_comparator()); rbt_node_t* node1 = rbt_insert(tree, box42); rbt_node_t* node2 = rbt_insert(tree, box88); mem_retain(node1); @@ -2505,7 +2513,7 @@ TEST_SUITE(RBT) { TEST(Verify_rbt_delete_root_node_with_no_children){ void* box88 = mem_box(88); - rbt_t* tree = rbt_new(test_compare); + rbt_t* tree = rbt_new(test_comparator()); rbt_node_t* node1 = rbt_insert(tree, box88); mem_retain(node1); rbt_delete(tree, box88); @@ -2532,7 +2540,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_compare); + rbt_t* tree = rbt_new(test_comparator()); rbt_insert(tree, box42); rbt_insert(tree, box88); rbt_node_t* doomed = rbt_insert(tree, target); @@ -2567,7 +2575,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_compare); + rbt_t* tree = rbt_new(test_comparator()); rbt_node_t* doomed = rbt_insert(tree, target); rbt_insert(tree, box88); rbt_insert(tree, box22); @@ -2595,7 +2603,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_compare); + rbt_t* tree = rbt_new(test_comparator()); //rbt_t* tree = rbt_new(NULL); rbt_delete(tree, target); CHECK(OK == rbt_check_status(tree)); -- 2.55.0