libwayne

libwayne is a library of reasonably abstract datatypes and algorithms written in C.

The algorithms in libwayne are by no means original. Many of them are taken verbatim from textbooks on data structures and algorithms, and I simply translated them into C. They include efficient and correct routines for priority queues, event-driven simulations, queues, stacks, binary trees, sets of integers, graphs (the node-edge kind), some combinatorics routines, ODE integration routines, a simple statistics package, and a matrix-vector library.

Many of the routines (heap, stack, queue, bintree) can work with arbitrary objects, not just integers. Comparisons are done with pointers to comparison functions, similar to ANSI Cs standard qsort. This library is not meant to be complete; I write the routines as I need them, but only high-quality code goes into libwayne.

One thing that many people ask me is ``why didnt you use C++? Without going into a long tirade, suffice it to say that, although I am not a C++ expert (actually, the only stuff I havent learned in intimate detail is templates), I know enough C++ to realize that it is not the be-all, end-all of programming languages. In fact, after several years of C++ being around, it is already beginning a slow fading into history, with Java being its successor --- and not a very good one, at that.

At the risk of sounding like the 40-50 year olds out there who still insist that FORTRAN is a good enough language for everything, Ill be a 30-something who insists that, until something better comes along, C is still a good all-purpose language in which to write heavy, data-structure intensive programs. I believe it was Dennis Ritchie who said something like, "C is rarely the best language for a given task, but its often the second-best," the implication being that its better to learn one language that is second-best for everything, than to learn a new language for every programming task. (One could say the same of English.)

I started libwayne when I realized that I was constantly re-writing little bits of code that did important things that should be in the C standard, but are not. For example, how many times have you written code like this:
if((p = malloc(n)) == NULL) /* or some other fatal error condition */
{
fprintf(stderr, "error: %sn", err_msg);
exit(1);
}

I got sick of it. Furthermore, I often wanted to know more about why my program failed. So I wrote Fatal. Heres its prototype:
void Fatal(char *fmt, ...); /* generates an assertion failure */

It uses varargs so you can pass it an arbitrary list of output arguments just like printf, but it generates an assertion failure so that if you run it under a debugger, you can look at the program nicely as it dies. It turned out to be only the first function I wrote for libwayne, and it was put into a file called "misc.c" which I started including in most of the code I wrote. Another early member of the library was Malloc, which calls Fatal if the standard malloc fails.

Eventually "misc.c" started getting pretty big, with macros for MIN, MAX, ABS, SQR, etc, so I created misc.h and compiled misc.c into an object module. That was about 1993.

About that time I started to realize that, at least in C, we need a way to pass "objects" around in a reasonably transparent way, but sometimes we want to treat pointers as integers. This makes some peoples teeth sweat (my own included), so I invented the voint datatype, which is (you guessed it) a union of (void*) and (int).

Then I started adding more complex algorithms to libwayne, whenever I needed them. Each and every piece of libwayne was written because I needed it, but only things that I took careful time to do well went into libwayne. Any algorithm that needs to compare objects needs a comparison function like the one used by the ANSI standard qsort routine.