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
for the utilities package that compiles object files in an obj directory.
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.
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.
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 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.
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.
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.