Contents of the SORTLIST.DOC file
SORTED LIST DATA TYPE
IMPLEMENTED IN ANSI C
by Walt Karas
This document accompanies several ANSI C source files that implement
the "sorted list" data structure. This implementation can be used
whenever the set of possible elements of the sorted list have the
1. All elements are of a single fixed size.
2. Each element is associated with a unique key value.
3. The set of key values has a well-defined "less than, greater than"
A symbol table would be a typical application for the sorted list data
The sorted list data structure is implemented as an AVL tree. AVL
trees were invented by Adelson-Velskii and Landis. The reference from
which I obtained the algorithms is Horowitz and Sahni, "Fundamentals
of Data Structures" (Computer Science Press). The add, find, and
delete operations on an AVL tree have worst-case O(log n) time
The sorted list data type is initialized by calling init_sort_list().
Elements are added to the sorted list by calling add_sort_list(). The
function find_sort_list() is called to search for an element in the
list using its associated key value. Calling the function
apply_sort_list() causes another function (passed as a parameter) to
be called for an (in order) series of elements in the list. A sorted
list can be created from an ascendingly sorted sequence of elements by
calling the function build_sort_list(). Elements are deleted from the
list by calling delete_sort_list(). The function clear_sort_list()
deletes all elements in the list. For detailed information about how
to call these functions, please see the function prototypes and
associated comments in the file SORTLIST.H. An example of how to use
the sorted list data type is provided in the file EXAMPLE.C.
The functions delete_sort_list(), apply_sort_list() and
build_sort_list() are recursive functions. The stack space complexity
for these functions is O(log n).
align.h - definitions related to address alignment.
sortlist.h - header file for code using sorted lists.
sortlist.c - implementation of init., add, find, and clear functions.
slapply.c - implementation of apply function.
sldel.c - implementation of delete function.
slbuild.c - implementation of build from sequence function.
slintrnl.h - internal header file for sorted list functions.
stckallc.h - header file for storage allocation functions.
stckallc.c - storage allocation functions.
example.c - an example of how to use sorted lists.
testsl.c - test suite for sorted list data structure.
sortlist.doc - file containing this document.
For this code to be portable to a particular architecture/ANSI C
implementation, the following condition must be true: there exists at
least one data type, called ALIGN_TYPE, such that if A is a valid
starting address for an instance of ALIGN_TYPE, than A is a valid
starting address for any data structure. ALIGN_TYPE is defined in
align.h. The default for ALIGN_TYPE is short int. The default should
work for any reasonable ANSI C implementation for the following
architectures: 8086, 80x86, DEC VAX-11, 68000, DEC PDP-11. For all
but the last two of these architectures, ALIGN_TYPE could be changed
to char. You may want to make ALIGN_TYPE larger than it needs to be
to reduce skewed word memory references, the trade-off being more
wasted "pad" bytes.
The constant TARGET_ALLOC defines the minimum number of bytes that
should be requested by a call to malloc(). This constant is defined
in the file STCKALLC.C. The allocation function in STCKALLC.C calls
malloc() to get a block of at least TARGET_ALLOC size, then doles it
out node-by-node to the sorted list functions. Set the value of
TARGET_ALLOC to make the appropriate trade-off between minimizing heap
overhead/fragmentation and minimizing wasted unused portions of
allocated memory blocks.
The add, find, and delete functions have worst-case O(log n) time
complexity only if the malloc() function has worst-case O(1) time
complexity. I doubt this will be true for most, if any, malloc()
implementations. To eliminate this problem, change the routines in
STCKALLC.C so that all needed memory for a sorted list is allocated
when the sorted list is initialized.
o Added the function build_sort_list().
118 Barcelona Ct.
Cary, NC 27513
with bug reports, questions, or comments.