Home of Austin

Austin is a little data structure library written in C. It maintains ordered, keyed collections of objects. What makes it special is that the choice of container algorithm can be varied at run time, even over existing, populated containers.

So for instance a collection that starts out as a red-black tree can be later morphed into an AVL tree, or to a sorted list. The change is completely transparent; all of the abstract operations on the data structure continue to work, albeit using new implementations.

Moreover, the algorithm change operations do not reallocate memory at all. Each container node contains all of the link members, and other fields needed by every applicable algorithm. Of course, the space for these is overlaid to keep the nodes small. All that happens is that the nodes are linked differently under the structural discipline of the new algorithm, and their variant members are re-interpreted accordingly.

The algorithms that are supported in the latest version are: sorted list, plain binary search tree, AVL tree, red-black tree and splay tree.

What are the potential advantages of doing this?

Oh, and the name stands for the somewhat pompous sounding ``Astonishing Universal Search Tree Interface Novelty'', though there is hardly anything astonishing or novel in this project. The name was inspired by the name of a certain film character played by actor Mike Myers, because dynamically morphing a splay tree to a red-black tree tends to evoke cries of ``Yeah Baby!''. The name having been thus procured, I had to find a way to construe it as an acronym that is relevant to the project.

Download Austin source code here:

Keep in mind that this is somewhat experimental. If you want a stable, robust container without the frivolous flexibility of Austin, have a look at Kazlib.

Return to Home page.