For this homework assignment, you will design a templated binary search tree that stores lists of memory addresses for a given size of memory allocation. You will use this binary search tree to implement memory allocation and deallocation.
All of the files can be found on github in the hw4 folder.
A binary search tree is a data-structure that stores elements in a sorted order. The elements in the tree are stored in nodes. Each node has a left child and a right child, both of which are also nodes. These nodes can be chained together to form a tree structure.
In the diagram above, the tree has a root with value 8. As new values are inserted into the binary search tree, a comparison is done at each node to see if the value is the same, less than, or equal to the value of the current node. If the new value is less than the value of the current node, it is placed to the left of the current value. If the new value is greater than the value of the current node, it is placed to the right of the current value. For example, 3 is to the left of 8. On the other hand, 14 is to the right of 8. Pseudo-code for binary tree insert can be found below:
Insert (node, value):
if value == node.value:
Return
else if value < node.value:
if node.left == null:
node.left = new node(value)
else:
Insert(node.left,value)
else if value > node.value:
if node.right == null:
node.right = new node(value)
else:
Insert(node.right,value)
Finding a value in a binary tree is similar. At each node, a value can be found by traversing the left node if the value is less than the current value or traversing the right node if it is greater than the current value.
For this assignment, you will implement a binary search tree with a special structure. Each node will contain a list of values instead of a single value. The tree is structured this way because we want to be able to store multiple addresses that point to memory allocations of a given size. The structure of the node class is given below:
template <typename Key, typename Value>
class node{
public:
node<Key,Value> *_left;
node<Key,Value> *_right;
Key _key;
List<Value> _values;
};
Each node has a left child, a right child, a key, and a list of value. The key orders the binary search tree, and the values store some set of value for that key.
Your assignment is to implement insertion and retrieval for binary search tree that uses the node class given above. Your insertion algorithm should follow the pseudo-code given above. The only difference is that when a key matches the current node's key, the new value should be inserted into the list of values (instead of just returning). You must also implement a retrieval function that finds the node with a given key and returns the first value from that node's list.
The file tree.hpp contains some starter code and a few TODO comments that indicate which code you need to fill-in for the assignment. The file test_tree.cpp provides a few simple test cases for the tree to ensure that it works properly. You may also add more test cases to this file for your own use (not required for the assignment).
Using the ListTree template, you will implement a memory allocator that relies on ListTree to store addresses of a given allocation size. For this task, we have provided a few primitive operations for you.
// Returns a new memory block of the requested size void* get_memory_block(unsigned long size); // Frees a memory block void return_memory_block(void *p); // Finds the size of a memory block unsigned long get_block_size(void *block);
These functions are defined in primitives.cpp. You do not need to modify these functions, but it might be helpful to read through the code and understand how the function work. This memory allocator is designed to replace the standard malloc and free function in C and C++ code, so the primitive functions must use libdl to find and use the original malloc and free functions (since they have been replaced by our version). In most real memory allocators, memory allocation would rely on brk and mmap instead.
You must implement the memory::malloc and memory::free methods in memory.cpp. You will also need to define data-members in memory.hpp to store memory allocations (ListTree). memory::malloc should get an existing block of memory from the ListTree when possible and otherwise return a new block of memory from the primitive get_memory_block function. memory::free should place the free'd block in the ListTree structure for later use.
You can test your memory allocator using two different methods. First, the test_memory.cpp file provides a few tests to directly test the memory class. Second, the driver.cpp file can be used to indirectly test the memory class by overriding the malloc and free calls in the code using LD_PRELOAD. To run the code in driver.cpp with your memory allocator, you can run it with the following command:
LD_PRELOAD=/path/to/your/files/libcis190.so ./driver
/path/to/your/files/ is the path shown by typing pwd in the directory that your homework 4 files are contained.
std::allocator defines an interface for replacing the standard allocator in STL structures. The second template parameter of std::vector allows the user to change which allocator the vector's memory comes from.
std::vector<int> v1; // Uses std::allocatorstd::vector<int,my_allocator<int>>; // Uses my_allocator
You can create an allocator that can replace std::allocator by inheriting from std::allocator and overriding the allocate and deallocate methods as shown below.
T *allocate(size_t count, const T* hint = 0); void deallocate(T *p, size_t n);
For extra-credit, create a cisallocator class that can be used as the second template-argument for vector and calls memory::malloc and memory::free to allocate and deallocate memory. You should test this cisallocator using the std::vector class.