Source code released for public use

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
Articles
   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
Utilities
   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
————————————————————-

Introduction

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

DOMSORT
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.

HISTSORT
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.

HTREE
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 http://richardhartersworld.com/test/~cri/2007/urtree.html. The readme.txt file describes the interface and usage.

WINMEDIAN
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 minimum on a sliding window algorithm: This article presents an O(1) algorithm for computing the minumum/maximum of a sliding window as it traverses a data stream. C code for the algorithm is included.
The minimal longest ascending subsequence algorithm: This article presents an O(n*log(n)) algorithm for constructing the minimal longest ascending subsequence of a sequence. Pseudocode for the algorithm is included.
Array rotation revisited: This article analyzes the array rotation problem. The best algorithm in terms of operations is derived. The article recognizes that it may not be best in terms of memory access costs. Pseudocode for the algorithm is included.
Are two vertices connected in a graph: This article provides an algorithm for determining whether two vertices are connected in a graph. Pseudocode for the algorithm is included.
Choosing k random lines from a file: This article analyzes the problem of selecting a random subset of elements from a larger set of elements. An optimal algorithm is described. Pseudocode for the algorithm is included.
McCarthy’s Mergesort Algorithm: This article discusses McCarthy’s algorithm for merge sorting and presents two pseudosource implementations. McCarthy’s algorithm is particularly useful when the input stream to be sorted is a stream of unknown size.
Heap structured search trees: This article presents a possibly novel data structure, the heap structured search tree. The text includes pseudocode for the basic operations. Using heap structured search trees is mentioned in an article on gaps in arrays.
Optimizing the merging of sorted arrays: This article discusses the details of optimizing the merge loop in the merging of sorted arrays. The issues are explored and C code for the optimized merge is included. The gains are minor (improvements on the order of 5-10% over naive code have been reported) but are signifigant and the optimization is simple.

The utilities group

ERRMGR
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
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 http://richardhartersworld.com/test/~cri/2007/gflspec.html.

GETSPACE
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.

LISTPKG
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 http://richardhartersworld.com/test/~cri/2007/urtree.html.

Source code released for public use

Table of contents

Introduction

Stand alone packages

Articles containing source code

The utilities group