Goals for this homework

  • Practice with data representation, binary search trees.
  • Memory allocation

You are expected to complete this assignment individually. If you need help, you are invited to come to office hours and/or ask questions on piazza. Clarification questions about the assignments may be asked publicly. Once you have specific bugs related to your code, make the posts private.

Set Up

You should already have your set of files from the part 1. You will now implement a few more functions.

Overview

Now that you have a basic memory allocator working, you need to implement two optimizations that will improve the efficiency of your solution.

Problem 1: Compaction

Your implementation in part 1 is not optimal. Imagine this not unlikely scenario. A program requests many, many 36-byte chunks. Perhaps these are items that are being stored in a tree. Then, they are done with all of those chunks, so they have all been freed. Now the program requests a 48-byte chunk.

Unfortunately, there will be no chunks left that are 48 bytes, yet there's plenty of memory available total. In order to find memory, those separate 36-byte chunks need to be recombined (merged) into larger portions again.

This is going to be solved in two parts. You need a merge function that attempts to merge two items. Given two memory structs, check to see if the two can be merged. They can be merged if the two are next to each other in memory with no break in between. If they can be merged, return a memory struct pointer to a struct containing the information for a single memory chunk containing the old two chunks. Free any memory structs that are no longer being used. If they cannot be merged (there is space between them), then return NULL;

The other part of this is the code that goes through the entire set of available memory, attempting to merge memory structs that are near each other in memory. This is the crux of this problem.

You have a set of available memory structs stored in a bst. They are stored sorted by size. If you were to go through all of the available memory structs to attempt to merge them, what order would you want to go? How are you going to set this up so that you can go in that order? You are welcome to create an auxiliary data structure that holds pointers to the same memory structs but is sorted in a different order. Once you have figured out in what order you want to go through the available memory, and then set up the data stuctures and functions so that you can go in that order, then you need to write the code that will attempt to merge. If a merge occurs, then you need to think about how that will affect all of your data structures.

Problem 2: Delete

The goal of this section is to revisit your bst delete function to decide whether you have created a solution that significantly increases the height of the tree.

Removing a node should never increase the height of the tree. If you have a solution that increases the height of the tree, you need to reimplement your solution so that it does not do so.

Extra Credit: Self-Balancing

For extra credit, we can go ahead and implement our binary search trees as self-balancing. These are binary search trees that attempt to automatically keep their "height", or the number of levels (maximum number) below the root, as low as possible, and still responding properly to insertions and deletions.

In order to receive credit, additional functions may be added to the bst.h, bst.c file enabling this functionality. For additional information, see (https://en.wikipedia.org/wiki/Self-balancing_binary_search_tree)

Submit

At this point, you should have done the following:
  • Created the files specified in part 1 and any associated testing files you used, inside your hw8 directory on subversion. Don't forget to add and commit everything you worked on!
  • Implemented all of your functions. If not, you at least need skeletons of your functions so that our automated tests will compile for the functions you did write.
  • Compiled your executable manually and with the Makefile
  • Implemented your test cases
  • Executed your code
  • Debugged your code 
  • $ svn commit -m "hw8 complete"