Goals for this Pre-lab

  • Practice binary search trees
  • Practice making a data structure generic using void pointers and function pointers

Remember to create a new directory in your repository for this lab. (Refer to previous labs for how if you have forgotten)

First answer the questions in lab7questions.html.

Second, read through the warmup exercises so you are ready to begin in class.

Valgrind

Valgrind is a memory mismanagement detector. It shows you memory leaks, deallocation errors, etc. Actually, Valgrind is a wrapper around a collection of tools that do many other things (e.g., cache profiling); however, here we focus on the default tool, memcheck. Memcheck can detect the following things that are useful to you right now:

  • Use of uninitialised memory
  • Reading/writing memory after it has been free'd
  • Reading/writing off the end of malloc'd blocks
  • Reading/writing inappropriate areas on the stack
  • Memory leaks -- where pointers to malloc'd blocks are lost forever
  • Mismatched use of malloc [] vs free []

Click here for a nice example with explanation for how to use valgrind and interpret its results.

You can use valgrind if you log into the main cs department computers: 

ssh cnetid@linux.cs.uchicago.edu
You can check out your repository there, compile it, and test it. You may use vim to edit your code there.

Setup

I am providing several files. For each file, create the file in vi and paste in the code I provided. The files are:

Exercises

During this week, you will create some code that will be used in your project in the next two weeks. These exercise structures, trees, and function pointers.

As you know, there are two sides to implementing data structures - the data structure itself and what is being held in the data structure.

Problem 1: memory struct and functions

You will first add code for the struct that will be held in the binary search tree. As you know, to use a binary search tree, the struct being stored needs to provide a compare function for insertion. The memory struct represents available memory blocks in the operating system. It contains two fields of unsigned int, representing memory address and size.

Look at memory.h for more information about the memory struct and the necessary functions to implement. You will be implementing them across the warmup and hw. We are having you finish the minimal set to test the BST - then, in the hw, you'll complete it.

You need to implement one compare function. For the warmup, complete memory_addr_cmp, which compares two memory structs by their addresses.

This function takes two arguments, const void* x and const void* y, you will need to cast both of them to type "memory*", and make comparisons. If x is less than y, return -1. If x is greater than y, return 1. If they are equal, return 0;

Problem 2: binary search tree

You are writing several binary search tree functions (bst). Look in bst.h for the overall design of the bst. Note, in particular, that there are two separate structus - the node struct that describes information for a single node in the tree, and a bst struct, that holds the root pointer and a function pointer to the comparison function being used for this tree. When you first create the tree, you pass in the comparison function, and this will be used for all functions that need it thereafter. Therefore, after that, you don't need to specify the comparison function to bst-level functions. The stored function pointer is then passed to the node-level functions.

Begin with allocation and initialization functions for both bst and node.
  • node* node_new(void* data); // create a new node with data provided as parameter
  • bst* bst_new(int (*cmp)(const void* x, const void* y)); // create a new bst with a given comparison function, initialize its root to be NULL
Then continue with insertions and traversals. Note that for every function, there are two versions - one for the bst and one for the node. The bst function is always called first, then the node functions are called from the bst function.
  • node* node_insert(node* root, void* data, int (*cmp)(const void* x, const void* y)); // insert a new node to the correct position of a subtree with a comparison function, and return the new root node.
  • void bst_insert(bst* b, void* data); //Insert a new node to the bst. Note that our bst has a field of comparison function, so you need to use that comparison function to insert a node.
  • void inorder_traversal(node* root, void(*func)(void* data)); //traverse a subtree in ascending order given a comparison function. Apply func to the data of each node.
  • void bst_inorder_traversal(bst* b, void(*func)(void* data)); //traverse a bst in ascending order. Apply func to the data of each node.
  • void bst_free(bst* b); // free the bst. Here you don't need to free the data field of he bst, but only free the node architectures. The field void* data should be freed in another separate function.

Think very carefully about the order in which you will implement these. Specifically, what is the minimum number of functions you need to implement in order to fill and print out a bst. You should be able to print the memories of the bst in ascending order with function memory_print and bst_inorder_traversal. Choose the simplest functions that will give you this functionality.

You are not expected to complete this in lab.

Testing

A program like this, that takes in a lot of data, is exceedingly annoying to test through command-line arguments or hard-coded tests within the code. Instead, what you would like is to have a file of words that can be opened and read.

For files that are not in a strict format, the paired functions fgets and strtok are functions that work every time. Once you learn to use them, you will be able to read in files of any format.

There are two steps to reading from a file. First, read in the file line by line. Second, split up each line into tokens or the different pieces to be dealt with separately.

In this assignment, we can create a file that stores free memory blocks. Each line has two fields, address and size. 

  1,200
  2,50
  3,80
  4,100
  5,150
When you test your code, just read in these memory blocks and see if your bst sorts the memory blocks correctly with the corresponding compare functions.

Here is code that reads in a file line by line, print out each line with its line number. 


#include <stdio.h >
#include <stdlib.h>

#define BUFSIZ 120

void display_file(char *filename)
{
  FILE *fp;
  char buf[BUFSIZ] = "Garbage";
  int i;

  // attempt to open the file, then check whether that worked.
  if ((fp = fopen(filename, "r")) == NULL)
  {
    fprintf(stderr,"Could not open file %s\n",filename);
    return (1);
  }

  // for each line of the file, read it in and then print it out
  i = 0;
  while (fgets(buf, sizeof(buf), fp) != NULL)
  {
    printf ("Line %4d: %s", i, buf);
    i++;
  }

  fclose(fp);
}

You can read more about reading files with fgets in this fgets tutorial.

The second step is to learn to use strtok to read the file. Strtok divides up a string into different parts, making separate strings. It does NOT allocate new memory - everything it does is within the original string. Therefore, if you want to use the strings later, you'll need to allocate space for them and copy them over.

To learn how to do this, read this tutorial on strtok.