Wayne's Little Data Structures and Algorithms Library

Note: this page is also available in Romanian, Thanks to Maxim Petrenko. 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 C's 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 didn't 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 haven't 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, I'll 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 it's often the second-best," the implication being that it's 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: %s\n", 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. Here's 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 people's 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.

Some of the sub-libraries in libwayne

Discrete (integer) Algorithms

Floating Point Algorithms

I wrote these for my thesis research. If you have read this far and are interested in libwayne, then please contact me via e-mail. libwayne is availble for free. Originally, I wasn't going to release this code because I thought it wasn't "ready" for release. But, I've been using it and modifying it for years, and some of my friends have also used bits of it. I believe that David Neto is using my heap routines in his Travelling Saleman Problem research.

Dowload libwayne as a tar'd gzip'd archive, or as a ZIP archive

In any case, after reading The Cathedral and the Bazaar, I've decided to release it. If you'd just like to get it quickly, you can download a tar'd, gzip'd archive of the entire tree here. It's about 1.5MB. (Most of that is actually high-quality FORTRAN numerical stuff that I didn't write, but for which I've written C front-ends to.) If you find any bugs, or make any improvements, please contact me via e-mail.

libwayne is dual-licensed: the default is the Library GNU General Public License (LGPL), but you can contact me if you are interested in arranging another mutually agreeable licensing scheme.

If you came to this page looking for my quad precision routines, don't bother: I found a much better implementation.


Access count (updated once a day) since 1 Jan 1997: 78086