Ryan Boland

One of my recent assignments was to write an implementation of malloc using the best-fit algorithm. Inspired by one of Gary Bernhardt’s Destroy All Software screencasts, I decided to use TDD to flesh out the design. I’m not going to walk through the entire assignment, but I’ll go over the setup and some of the caveats so that you can consider trying something similar in one of your projects.

First, I will create a basic Makefile that compiles all of the files and executes the test runner, in this case, test_runner.c. For now, the only files that I’ll be compiling are the test runner itself and meta_list.c which will be my linked list implentation.

default: *.c *.h
  gcc -m32 -o test_runner test_runner.c meta_list.c
  ./test_runner

So lets get to writing the first test. To do this, I’ll include assert.h which gives us the assert macro, which will be the basis of our testing. As you can see below, I’ve borrowed Gary Bernhardt’s run_test macro, which simply prints out the name of the test function and executes it.

I know that I will use a doubly-linked list to represent meta data of malloc’d portions of memory (I’m calling this the “meta list”), so for the initial test I’ll jump to the conclusion that I need a meta_data_node struct.

#include <stdio.h>
#include <assert.h>
#include "meta_list.h"

#define run_test(function_name)\
  printf("Running: %s\n", #function_name);\
  function_name();

void head_changes_after_first_add() {  // Give a descriptive test name
  meta_data_node *node;                // Initialize a new node
  add_meta_list_node(node);            // Add the node to the linked-list

  void *head = get_meta_list_head();   // Fetch the list head
  assert(node == head);                // Verify the added node is now head
}

int main() {
  run_test(head_changes_after_first_add);  // call run_test for every
                                           //       test function we create
  return 0;
}

Running make at this point just results in errors due to the undefined struct and functions I’ve called in the above code. To remedy that, I’ll create meta_list.h and meta_list.c.

typedef struct meta_data_node {
  struct meta_data_node *next;
  struct meta_data_node *prev;
} meta_data_node;

meta_data_node *get_meta_list_head();
void add_meta_list_node(meta_data_node *);

#include "meta_list.h"
#include <stdio.h>

meta_data_node *list_head;
meta_data_node *list_end;

meta_data_node *get_meta_list_head() {
  return NULL; // TODO: return list head
}

void add_meta_list_node(meta_data_node *node) {
  // TODO: add parameter node to list
}

At this point, we have our first useful test output!

$ make
gcc -m32 -o test_runner test_runner.c meta_list.c
./test_runner

Running: head_changes_after_first_add
test_runner: test_runner.c:14: head_changes_after_first_add: Assertion 'node
== head' failed.
make: *** [default] Aborted (core dumped)

It doesn’t take much to get this test passing:

//...

meta_data_node *get_meta_list_head() {
  return list_head;
}

void add_meta_list_node(meta_data_node *node) {
  list_head = node;
}

And then the test output is:

$ make
gcc -m32 -o test_runner test_runner.c meta_list.c
./test_runner

Running: head_changes_after_first_add

Success!

Better Failure Messages

There is one aspect of our test macro that’s less than optimal, and that’s that the values of the compared variables are not shown. For example, running the following:

// ...
void two_ints_are_equal() {
  int i1 = 1;
  int i2 = 2;
  assert(i1 == i2);
}
// ...

Results in this output:

test_runner: test_runner.c:20: two_ints_are_equal: Assertion 'i1 ==
i2' failed.

Not very helpful. However, we can write a specific form of the assert macro that prints out the variables for us. One version that I’ve come up with is the following:

//...

#define assert_eq(a, b, type)\
  printf("--asserting " type " == " type "\n", a, b);\
  assert(a == b);

//...

void two_ints_are_equal() {
  int i1 = 1;
  int i2 = 2;
  assert_eq(i1, i2, "%i");
}

//...

In this implementation, the printf representation of the type of the variables being compared is passed in.

Final Thoughts

At the end of the day, if you’re going to do anything much more complicated than making a linked list, you’ll probably want to take a look at some existing C libraries created for TDD. This Stackoverflow question has some great suggestions, including a book that was written on the subject.

If you have any comments for have found this interesting feel free to tweet me @bolandrm! Thanks!