Testing of the C Algorithms library

When writing a set of general purpose data structures, correctness of the implementation is particularly important. If the foundations on which a program is based are unsound, how can we have any confidence in its correctness or reliability? Edsger Dijkstra remarked that testing can never prove the absence of errors, only their presence. However, somewhat paradoxically, we can never have any confidence in a program unless it has been tested; as Donald Knuth once humorously commented: "beware of bugs in the above code; I have only proved it correct, not tested it".

A dual approach is used to gain confidence in the correctness of the C Algorithms library. Firstly, the code is structured to be as simple as possible in order to be obviously correct. Secondly, the library includes an extensive test suite.

Coverage analysis

For a test suite to be useful, it must test the entire program. If the test exercises some sections of the program but not others, we can only have a limited degree of confidence in the program as a whole. For this reason, code coverage analysis of the source code is performed, using GNU gcov. This provides a quantitative measure of the coverage providded by the test suite.

The aim is for 100% test coverage. The current version of the library comes very close to this; see here for the coverage report for the v1.2.0 release.

Code coverage is disabled by default, but can be enabled by passing the --enable-coverage parameter to the configure script.

Memory allocation testing

The C programming language uses manual memory management. As a large number of software bugs result from memory management errors, the test suite incorporates a framework for testing memory allocation. This consists of a header file that redirects all use of memory management functions test wrapper functions that track memory allocated during the test. As a result, it is possible to detect memory leaks, doubly freed memory blocks, and memory that is used without being properly initialised.

A secondary function of the memory testing framework is the ability to deliberately trigger memory allocation failures. It can therefore be confirmed that the library acts correctly in failure scenarios.


Valgrind is an award-winning program for detecting memory errors. The entire test suite can be run in Valgrind and it is used routinely during development.

Valgrind is disabled by default; to run the test suite in Valgrind, pass the --enable-valgrind command-line option to the configure script.

Send comments to Simon Howard.