Testing linked lists

I’m just finishing up the CS 136 class here at the University of Waterloo, which also goes by the name of “Elementary Algorithm Design and Data Abstraction.” In other words, we make the transition from introductory Scheme to introductory C while learning about topics such as braun trees, hash tables, and more. We’re also expected to use test driven design, or at least write tests and run them frequently, to ensure that our assignment programs are working correctly. While most of the programs are rather elementary, the procedure to test data structures such as linked lists is rather annoying, because it ends up looking something like this:

int i;
int testNum[] = {0, 1, 2, 3}; List *l = list;
for(i = 0; i < sizeof(testNum)/sizeof(testNum[0]); i++)
   assert(list->val == testNum[i]);

No imagine writing that over and over, especially if you have multiple fields that need testing. Being unsatisfied with this setup, I took it upon myself to write a linked list field asserter, which can be used like so:

int cmp_num(void *a, void *b)
{
    return (int)a – (int)b;
}

int testNum[] = {0, 1, 2, 3};
assertListFieldEqual(list, offsetof(List, val), cmp_num, testNum, sizeof(int), offsetof(List, next));

As you can guess, it’s about as generic as you can get in straight C without the benefit of C++ templates. If you have a structure that is traversed via a pointer to the next structure, it can be asserted with this system. assertListFieldEqual takes

  • a pointer to the head element
  • offsetof(list type, field to compare)
  • a pointer to a comparison function
  • a pointer to a list of expected values
  • the size of a value
  • offsetof(list type, traversal field)

The function itself is not particularly difficult, but it does abuse pointers in very unethical ways:

typedef int (*cmp_func)(void *, void *);

void assertListFieldEqual(void *list, ptrdiff_t field, cmp_func cmp, void *cmp_to, size_t cmp_size, ptrdiff_t next)
{
    ptrdiff_t count = 0;
    while(1)
    {
        assert(!cmp((void *)(*(ptrdiff_t *)(cmp_to + count * cmp_size)), (void *)(*(ptrdiff_t *)(list + field))));
        if((void *)*((ptrdiff_t *)(list + next)) == NULL)
            break;
        list = (void *)(*(ptrdiff_t *)(list + next));
        count++;
    }
}

I’m pretty sure all of my pointer abuse is fully sanctioned by the standard, so it should be portable to my knowledge. Therefore, go forth and multiply, and test your lists well! And if you’re in any doubt that this is not generic enough, behold, I give you string comparison!

const char *testName[] = {"1", "2", "3", "4"};
assertListFieldEqual(list, offsetof(List, name), (cmp_func)strcmp, testName, sizeof(char *), offsetof(List, next));

One Response to “Testing linked lists”

  1. Its like you read my mind! You seem to know so much about this, like you wrote the book in it or something. I think that you could do with some pics to drive the message home a bit, but other than that, this is wonderful blog. A fantastic read. I will certainly be back.

Leave a Reply