Goals for this homework

  • Practice implementing with trees
  • Exercise algorithm development using trees
  • Practice making a generic tree and using it on specific data

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.

This homework has a similar set of problems to what you did in the warmup. These will be used in next week's two-week project.

Set Up

There is no additional setup - you should have your files from the warm-up.

Exercises

Problem 1: memory struct and functions

You will implement the second comparison function for memory: memory_size_cmp

Problem 2: binary search tree

You are writing several binary search tree functions (bst) to add to what you implemented in the warm-up:

  • void* node_search(node* root, void* data, int (*cmp)(const void* x, const void* y)); // search for the data in a subtree using the given comparison function. Only return the first node if multiple nodes have data fields equal to the data we are searching with.
  • void* bst_search(bst* b, void* data); // search for node with data in a bst.
  • node* node_delete(node* root, void* data, int (*cmp)(const void* x, const void* y)); // delete a node with certain data you only need to delete the first occurence of node which has a data field equal to the data we want to delete. Use cmp as the comparison function. When deleting a node, only free the node but not the data field contained in the node.
  • void bst_delete(bst* b, void* data); //delete a node containing data from the bst

Problem 3: read memory blocks

You will write a function with the following interface: 

bst* read_memory_blocks(char *filename, 
  int (*cmp)(const void* x, const void* y));

This function takes in a filename. It reads in the file and splits the file into memory blocks. Create files hw7.h and hw7.c, and put function read_memory_blocks into these files. Each line in this file corresponds to a block of memory, i.e., an integer of memory address and another integer of memory size, separated by a comma. I suggest using fgets to read in the lines and strtok to divide the line into words.

Note that this function has a lot going on within it - and it will be hard to get partial credit if it doesn't work. Partial credit is from implementing the other functions in the warm-up and hw. However, to get credit for this problem, you need to finish it.

Submit

At this point, you should have done the following:
  • Created and filled in several files associated with this project: bst.h bst.c memory.h memory.c hw7.c hw7.h hw7_main.c Created test files with memory addresses and sizes in them 
  • $ svn add *.c *.h Makefile testmemory1.txt testmemory2.txt
  • Compiled your executable manually and with the Makefile
  • Implemented your test cases
  • Executed your code
  • Debugged your code 
  • $ svn commit -m "hw7 complete"