Homework 5
ReadWrite Binary Tree
You have been tasked with implementing a read-write binary tree. Any add or remove function will
be a write operation while a get function will be considered a read operation.
You will need to arrange di�erent test cases that will look into di�erent read-write ratios. Your test cases should check that you can correctly add, remove, insert and retrieve elements from the binary tree and your functions are thread safe.
Afterwards, implement benchmarks with the following read-write ratios with your data structure and compare against your coarse grained implementation. Consider giving your data structure a set number of elements at the beginning.
10% Write, 90% Read 40% Write, 60% Read 50% Write, 50% Read 60% Write, 40% Read 90% Write, 10% Read
struct binarytree;
void binarytree_init(struct binarytree* map, void(*key_del)(void*),
void(*val_del)(void*), int(*cmp)(void*, void*), size_t keysize);
void binarytree_insert(struct binarytree*, void* key,
void* value);
void* binarytree_get(struct binarytree* map, void* key);
void* binarytree_remove(struct binarytree* map, void* key);
size_t binarytree_size(struct binarytree* map); void binarytree_destroy(struct binarytree* map);
Construct test cases with di�erent number of elements and workloads
Using the test cases, measure and record the execution time of the data structure
Record these results, graph and compare your data structure against a coarse grained version
You must produce a report that demonstrates the performance di�erence between the implementations and the di�erent workloads