Dec 062017

Sorted list data type in ANSI C. | |||
---|---|---|---|

File Name | File Size | Zip Size | Zip Type |

ALIGN.H | 370 | 231 | deflated |

EXAMPLE.C | 2523 | 767 | deflated |

SLAPPLY.C | 2727 | 1007 | deflated |

SLBUILD.C | 3350 | 1206 | deflated |

SLDEL.C | 6134 | 1870 | deflated |

SLINTRNL.H | 1248 | 605 | deflated |

SORTLIST.C | 9814 | 2644 | deflated |

SORTLIST.DOC | 4642 | 1900 | deflated |

SORTLIST.H | 8061 | 2209 | deflated |

STCKALLC.C | 2837 | 800 | deflated |

STCKALLC.H | 1399 | 476 | deflated |

TESTSL.C | 11663 | 2726 | deflated |

# Download File AVLBST11.ZIP Here

## Contents of the SORTLIST.DOC file

SORTED LIST DATA TYPE

IMPLEMENTED IN ANSI C

Version 1.1

8/25/93

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

following characteristics:

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"

relation.

A symbol table would be a typical application for the sorted list data

structure.

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

complexity.

USAGE

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

FILES

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.

PORTING/PERFORMANCE TUNING

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.

VERSION INFORMATION

Version 1.1

o Added the function build_sort_list().

SUPPORT

Please contact:

Walt Karas

118 Barcelona Ct.

Cary, NC 27513

(919)467-9486

with bug reports, questions, or comments.

IMPLEMENTED IN ANSI C

Version 1.1

8/25/93

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

following characteristics:

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"

relation.

A symbol table would be a typical application for the sorted list data

structure.

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

complexity.

USAGE

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

FILES

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.

PORTING/PERFORMANCE TUNING

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.

VERSION INFORMATION

Version 1.1

o Added the function build_sort_list().

SUPPORT

Please contact:

Walt Karas

118 Barcelona Ct.

Cary, NC 27513

(919)467-9486

with bug reports, questions, or comments.

December 6, 2017
Add comments