Richard Harter’s World
Site map
Mathematics and Computer Science
February 2011

Source code released for public use

Table of contents

Stand alone packages
   An implementation of the dominance tree sort
   Histogram sort for integers (fast)
   An implementation of unordered radix trees
   The moving window median using two heaps
   The minimum on a sliding window algorithm
   The minimal longest ascending subsequence algorithm
   Array rotation revisited
   Are two vertices connected in a graph?
   Choosing k random lines from a file
   McCarthy’s mergesort algorithm
   Heap structured search trees
   Optimizing the merging of sorted arrays
   The error managment utility
   The read lines from a file utility
   The instrumented storage allocation utility
   A small linked list management utility
   An object management utility for C programs
   A command line option processing package
   A storage pool package
   The stack of calls reporting package
   An unordered radix tree data storage facility


This is the master page for source code that I have created and released for public use. All code is under a under a modified BSD style license. All C code is Ansi C89 unless otherwise noted. Currently there are no zip or tar files for the packages; there may be in the future.

The list is divided into three categories. The first category lists stand alone packages, typically containing one or more C files, an include file, and documentation and support files. These files will be in a single directory and should be complete and self contained.

The second categories lists articles that contain illustrative code for algorithms. The code may be C code or it may be pseudocode.

The third category is a group of utilities. The source files are in one directory and the include files are in another. Utility programs may include other utility programs and may include any of the include files in the include directory. There is a makefile for the utilities package that compiles object files in an obj directory.

Stand alone packages

An implementation of the dominance tree sort contains the C source code for a dominance tree sort. The theory of dominance tree sorts is in the article Dominance Tree Sorts. This sorting algorithm is near optimal in the number of comparisons required.

Histogram sort for integers (fast) contains the C source code for a histogram based math sort. It is quite efficient for small n (e.g. n<100000) but less so for large n because of caching issues.

The htree package is one of two implementations of unordered radix trees, a fast and efficient method for storing and retrieving data. The theory of unordered radix trees is given in The readme.txt file describes the interface and usage.

An implementation of the two heap moving window median algorithm contains the C source code for the two heap algorithm for determining the median of a moving window traversing a one dimensional stream.

Articles containing source code

This section lists articles that contain source code.

The utilities group

Errmgr has two purposes. The first is to supply functions for setting and getting standard files called errfile, logfile, and infofile. These functions take care of default initialization. The second is to provide an error exit function that (a) will write a formatted error message with parameters to the error file, and (b) will add informative dumps from utilities. Currently the error exit provides the trace dump and the getspace dump.

Getfline is a utility for reading files one line at a time. It has many features that the author believes that such a utility should have. The usage and specification are documented at

Getspace is a dynamic storage allocation package that sits on top of malloc/free. It is instrumented and has error checking and error reporting facilities not found in raw malloc/free. Usage and the rationale are described in ../../cri_a/source_code/getspace/readme.txt.
This is a small linked list management utility. It permits the existence of multiple lists over a domain of objects. It takes care of appending and prepending items to a list and efficiently concatenating lists. OBJTAB
This is an object management utility for C programs. Instead of representing objects by raw pointers it uses “smart pointers” that know whether the smart pointer is valid or not. OPTPROC
This is an option processing package used for processing command line options. The rationale and usage are described in the include file optproc.h. STGPOOL
This is a storage management package. It is designed for use in situations where one wants to allocate a number of buffers very cheaply and then free them en masse. TRACE

The trace package keep track of the last 256 times it has been called. Typical usage is to put a call to trace as the first executable statement in functions with the argument identifying the calling function. A trace dump lists the functions making the previous 256 calls to trace. URTREE
The urtree package is the other unordered radix tree implementation. The theory of unordered radix trees is given in