version: 1.1.1
website: http:/info.fwsentry.org/projects/dlist/
contact: dbw <dbw@fwsentry.org>
license: BSD revised (see http://www.opensource.org/licenses/bsd-license.php)
USAGE / INSTALLATION
====================
D-List is 3 clause BSD-licensed, so you can use source code, in whole or part,
and integrate it into your project or application.
You only need to include the dlist.h file in your source code. The other include
file in the release is incorporated directly by the dlist source code, you do not
need to include it in your code.
Alternately, D-List can be installed as a shared library. Here is a suggested
command set to build a shared library, install it in one of your default search
paths for the linker.
1. enter the package root directory
2. cd src
3. compile
standard, no debug messages
$ gcc -c -std=gnu99 -O2 -Wall -Werror -fpic dlist.c
or, if you want debug messages enabled (very helpful for code development)
$ gcc -c -std=gnu99 -g -O2 -Wall -Werror -fpic dlist.c -DDEBUG
4. link
$ gcc -shared -o libdlist.so dlist.o
As of release 1.1 D-List also contains an optional set of code files that implement
a generalized form of hashed lists. These are built on top of the normal D-List
functions, and placed in separate files to allow users to pick and choose what set
of list types they want to compile. To compile the hashed lists package
1. enter the package root directory
2. cd src
3. compile
standard, no debug messages
$ gcc -c -std=gnu99 -O2 -Wall -Werror -fpic dlist.c
$ gcc -c -std=gnu99 -O2 -Wall -Werror -fpic dhashed.c
or, if you want debug messages enabled (very helpful for code development)
$ gcc -c -std=gnu99 -g -O2 -Wall -Werror -fpic dlist.c -DDEBUG
$ gcc -c -std=gnu99 -g -O2 -Wall -Werror -fpic dhashed.c -DDEBUG
4. link
$ gcc -shared -o libdlist.so dlist.o dhashed.o
PACKAGE CONTENTS
================
-- src source code for the library ( dlist.c, dlist.h, dlist_internal.h )
-- src optional source for hashed lists (dhashed.c, dhashed.h)
-- example_code/* examples on how to use the API and list types
-- regression_tests/* sources for regression testing dlist
-- performance/* sources for performance testing dlist
-- doxy separate .h file adapted for use by Doxygen,
a doxyfile to process it and a set of pre-built HTML docs
The regression test and example packages have autoconf and automake files. To simplify
usage.
API'S & DOCUMENTATION
=====================
The header file dlist.h contains all the information that is required to use D-List
all function descriptions, error codes and arguments are described in that file.
List Function groups.
=====================
List Object Management Functions calls that update the list object itself. The list object
is the user provided memory object that acts as the definitive point
to identify and work on a list. Each list has its own list object.
List Function Management Function calls that set and retrieve pointers to special user
provided that are used during specific list operations, such as a
search function to process list_search() types calls. The list
subsystem has no knowledge of the contents of the users elements,
only how to organize and retrieve them.
List Information Functions Function calls to retrieve specific size information about a list.
List Transformation Functions Function calls to provide transformation operations on complete
lists of elements, such as copying or splitting lists.
Element Placement Functions Function calls to permit the insertion or other placement of new
elements in a list.
Element Relocation Functions Function calls to relocate elements between different lists.
Element Removal Functions Function calls to remove elements from a list.
Element Retrieval Functions Function calls to locate and retrieve element data, from
presumably unsorted lists.
Element Search Functions Function calls to perform searches for elements, from presumably
unsorted lists.
Sorted List Element Functions Function calls to perform various operations including searches
for elements, from previously sorted lists. The intent of this
group of functions is to be able to update and modify the lists
while maintaining the original sorted element order. It is also
assumed that the same compare function that was used to sort the
list is used with these find functions.
Element Transformation Functions Function calls to transform the relative order of elements in a
list.
Miscellaneous List Functions Functions to perform technical operations on lists.
Here is a table of available D-List functions, grouped by function type.
List functions, grouped by type.
================================
List Object Management
----------------------
list_create() Initialize a list object as linear class list, prior to using a list.
list_create_finite() Initialize a list object as finite class list, prior to using a list.
list_create_pivot() Initialize a list object as pivot class list, prior to using a list.
list_set_finite_limit() Change the max size of a finite class list.
list_erase() Erase all elements of a list and the list object itself.
List Function Management
------------------------
list_set_compare_function() Set the compare function for a list, used for element sorts and evaluations.
list_get_compare_function() Retrieve the compare function for a list.
list_set_pivot_function() Set the pivot function for a pivot class list, used by list_store().
list_set_search_function() Set the search function for a list, used for element searches.
list_get_search_function() Retrieve the search function for a list.
list_set_size_function() Set the size function for a list, used for lists that manage element storage.
list_set_insert_function() Set the insert function for a list, used upon placement to process an element.
list_set_remove_function() Set the remove function for a list, used upon removal to process an element.
list_set_iterate_function() Set the iteration function for a list, used by list_callback_iteration().
List Information Functions
--------------------------
list_is_empty() Check if a list is empty, or not.
list_size() Retrieve the number of elements in any list.
list_size_pivot() Retrieve the number of elements, by section, in a pivot class list.
list_is_sorted() Check if list is currently sorted, or not.
List Transformation Functions
-----------------------------
list_concatenate() Concatenate 2 lists together, serially, into the destination list.
list_merge() See function list_assay()
list_clone() Create a clone of a list.
list_transfer() Transfer the elements of a list, into another list.
list_weave() Merge 2 lists together, element by element, into a destination list
list_assay() Analyze 2 lists locating unique elements and those elements in common.
list_split_pivot() Split a pivot class list, and create 2 destination lists from its contents.
list_compare() Perform a comparison of two lists, indicating if they are the same.
list_differences() Perform a comparison of two lists, returning the number of differences.
Element Placement Functions
---------------------------
list_append() Append an element to the end of a list.
list_prepend() Prepend an element to the front of a list.
list_insert_index() Add an element to a list, in the position indicated by an index number.
list_insert_ref() Add an element to a list, in the location indicated by an element reference.
list_store() Add an element to a pivot class list, as indicated by the pivot function.
Element Relocation Functions
----------------------------
list_copy_index() Copy an element to another list, from the position indicated by an index number.
list_move_index() Move an element to another list, from the position indicated by an index number.
list_copy_ref() Copy an element to another list, from the location indicated by an element reference.
list_move_ref() Move an element to another list, from the location indicated by an element reference.
list_search_copy() Search for, and then copy, all instances of an element to another list.
list_search_move() Search for, and then move, all instances of an element to another list.
list_evaluate_copy() Compare all elements in a list, and copy elements that meet criteria to another list.
list_evaluate_move() Compare all elements in a list, and move elements that meet criteria to another list.
list_range_copy() Compare all elements in a list, and copy all that are with a range, to another list.
list_range_move() Compare all elements in a list, and move all that are with a range, to another list.
Element Removal Functions
-------------------------
list_clear() Remove all elements from a list, leave it empty.
list_fetch() Extract an element from the front (head), or the tail (end), of a list.
list_fetch_pivot() Extract an element from the pivot point, of a pivot class list.
list_extract_index() Extract an element, from the position indicated by an index number.
list_extract_ref() Extract an element, from the location indicated by an element reference.
list_delete_index() Remove an element, from the position indicated by an index number.
list_delete_group() Remove a block of elements, between the indicated by index numbers.
list_delete_ref() Remove an element, from the location indicated by an element reference.
list_delete_duplicates() Remove all elements that are duplicates of other elements in the list.
list_search_extract() Search for, and then extract, an element in a list.
list_search_delete() Search for, and then delete, an element in a list.
list_search_expunge() Search for, and then delete, all instances of an element from a list.
Element Retrieval Functions
---------------------------
list_get_index() Retrieve an element, from the position indicated by an index number.
list_get_index_ref() Retrieve an element and its reference, using position indicated by an index number.
list_get_ref() Retrieve an element, from the location indicated by an element reference.
list_get_next_ref() Retrieve the next element in a list, as indicated by an element reference.
list_locate_index() Locate an element index in a list, identified by its element datum pointer.
list_locate_pivot() Locate an element pivot value in a list, identified by its element datum pointer
list_locate_ref() Locate an element reference in a list, identified by its element datum pointer.
list_valid_ref() Verify if an element reference is valid for the list.
list_iteration_start() Start a sequence of iteration of all the elements, from one end of a list.
list_iteration_start_pivot() Start a sequence of iteration of all the elements, from the pivot point of a list.
list_iteration_has_more() Inquire if there are more elements, during an iteration sequence of a list.
list_iteration_has_more_pivot() Inquire if there are more elements on this side of the pivot point.
list_iteration_get_next() Retrieve the next element in an iteration sequence of a list.
list_iteration_stop() Stop an iteration sequence of a list.
Element Search Functions
------------------------
list_simple_search() Search for an element in a list, using element datum as the search criteria.
list_occurrences() Search for all occurrences of an element, using datum as the search criteria.
list_search() Search for an element in a list, using element datum as the search criteria.
list_search_pivot() Search a pivot class list, using element datum as both pivot value and search criteria.
list_search_ref() Search for an element, backwards or forwards, from a given reference point.
list_search_shift() Search for an element, and if found, shift the element to the head of the list
list_locate_maximum() Search for an element in a list, using maximum quantity as the search criteria.
list_locate_minimum() Search for an element in a list, using minimum quantity as the search criteria.
Sorted List Element Functions
-----------------------------
list_sorted_find() Search for an element in a sorted list, using datum as the search criteria.
list_sorted_insert() Add an element to a sorted list, in the position indicated by sort order.
list_sorted_extract() Extract an element from a sorted list, by the position indicated by sort order.
list_sorted_delete() Delete an element from a sorted list, by the position indicated by sort order.
list_sorted_expunge() Search for, and then delete, all instances of an element from a list.
Element Transformation Functions
--------------------------------
list_sort() Sort all the elements in a list, using either ascending or descending order.
list_safe_sort() Sort all the elements in a list, by order, in a guaranteed safe order.
list_fast_sort() Sort all the elements in a list, by order, voiding element references.
list_tiny_sort() Sort all the elements in a list, by order, slower but with no extra resources.
list_shift_index() Shift an element, identified by index number, to the end of a list.
list_shift_ref() Shift an element, identified by an element reference, to the end of a list.
list_rotate() Rotate the elements in a list, either to the left or right.
list_flip() Reverse all the elements in a list.
list_shuffle() Shuffle the elements in a list, by randomly, and repeatedly relocating them.
list_process() Process all elements in list using a user function to operate on element data.
list_process_range() Process a range of elements in list using a user function to operate on element data.
list_callback_iteration() Start a sequence of callback iteration, to process all the elements in a list.
Miscellaneous List Functions
----------------------------
list_optimize_index() Perform an optimization of the element index in a list.
list_optimize_memory() Perform an optimization of the element memory storage in a list.
list_do_not_seed_random() Prevent D-List from seeding the underlying random number functions.
list_information() Provide details about a list to stdout.
list_error_string() Return pointer to string corresponding to D-List error code.
Here is a table of available D-List functions, and how they apply to each class
of list.
Table of D-List functions by availability for class type
========================================================
if LIST_COPY_DATA
Linear Finite Pivot frees object used
====== ====== =====
list_create() yes
list_create_finite() yes
list_create_pivot() yes
list_set_finite_limit() yes
list_erase() yes yes yes yes
list_set_compare_function() yes yes yes
list_get_compare_function() yes yes yes
list_set_pivot_function() yes
list_set_search_function() yes yes yes
list_get_search_function() yes yes yes
list_set_size_function() yes yes yes
list_set_insert_function() yes yes yes
list_set_remove_function() yes yes yes
list_set_iterate_function() yes yes yes
list_is_empty() yes yes yes
list_size() yes yes yes
list_size_pivot() yes yes yes
list_is_sorted() yes yes
list_concatenate() yes yes(4) yes(1) copy
list_clone() yes yes(4) yes copy
list_transfer() yes yes yes copy
list_weave() yes yes(4) yes(1) copy
list_assay() yes yes yes(1) copy
list_split_pivot() yes copy
list_compare() yes yes yes
list_differences() yes yes yes
list_append() yes
list_prepend() yes yes
list_insert_index() yes yes
list_insert_ref() yes
list_store() yes
list_copy_index() yes yes(4) yes copy
list_move_index() yes yes(4) yes yes
list_copy_ref() yes yes(4) yes copy
list_move_ref() yes yes(4) yes yes
list_search_copy() yes yes(4) yes copy
list_search_move() yes yes(4) yes yes
list_evaluate_copy() yes yes(4) yes copy
list_evaluate_move() yes yes(4) yes yes
list_range_copy() yes yes(4) yes copy
list_range_move() yes yes(4) yes yes
list_clear() yes yes yes yes
list_fetch() yes yes yes no
list_fetch_pivot() yes no
list_extract_index() yes yes yes no
list_extract_ref() yes yes yes no
list_delete_index() yes yes yes yes
list_delete_group() yes yes yes yes
list_delete_ref() yes yes(1) yes yes
list_delete_duplicates() yes yes yes yes
list_search_extract() yes yes yes no
list_search_delete() yes yes yes yes
list_search_expunge() yes yes yes yes
list_get_index() yes yes yes
list_get_index_ref() yes yes yes
list_get_ref() yes yes
list_get_next_ref() yes yes
list_locate_index() yes yes yes
list_locate_pivot() yes(2) yes(2) yes
list_locate_ref() yes yes yes
list_valid_ref() yes yes yes
list_iteration_start() yes yes yes
list_iteration_start_pivot() yes
list_iteration_has_more() yes yes yes
list_iteration_has_more_pivot() yes
list_iteration_get_next() yes yes yes
list_iteration_stop() yes yes yes
list_simple_search() yes yes yes
list_occurrences() yes yes yes
list_search() yes yes yes
list_search_pivot() yes
list_search_ref() yes yes yes
list_search_shift() yes yes
list_locate_maximum() yes yes yes
list_locate_minimum() yes yes yes
list_sorted_find() yes yes yes
list_sorted_insert() yes yes yes yes
list_sorted_extract() yes yes yes yes
list_sorted_delete() yes yes yes yes
list_sorted_expunge() yes yes yes yes
list_sort() yes yes yes
list_safe_sort() yes yes yes
list_fast_sort() yes yes yes
list_tiny_sort() yes yes yes
list_shift_index() yes yes
list_shift_ref() yes yes
list_rotate() yes yes
list_flip() yes yes yes(1)
list_shuffle() yes yes yes
list_process() yes yes yes
list_process_range() yes yes yes
list_callback_iteration() yes yes yes
list_optimize_index() yes yes yes
list_optimize_memory() yes yes yes
list_do_not_seed_random() n/a n/a n/a
list_information() yes yes yes
list_error_string() n/a n/a n/a
Notes:
(1) restrictions apply, refer to function documentation
(2) will always return ENTIRE_LIST
(3) may not retain pivot alignment, depending of search criteria,
refer to function documentation
(4) destination list cannot be finite class
NOTES
=====
Non default compile options are described in the notes in the file dlist.c, and
in the Doxygen documentation. For most users the only import option to consider
is to define DEBUG in the dlist.c compile environment, during your code development.
The author has carefully considered adding functions to save and restore lists to
the file system. However the author uses this list package extensively and finds
that all occurrences of saving out and restoring lists have so many variations and
project dependent requirements, that providing a simple general function set to do
this seems like a waste of resources. If there is enough user demand, the author
will add such functions to the package, however it is felt that most users would
generally prefer to have their own save and restore functions, instead of trying
to adapt their project to a simplified basic implementation. The code does contain
a few references to this, but none of the code is compiled, it is all defined out.
Hashed List Function groups.
============================
Hashed List Object Management Functions calls that operate on a hashed list object.
Hashed List Function Management Function calls that set and retrieve pointers to special user
provided that are used during specific list operations, such as a
search function to process list_search() types calls. The list
subsystem has no knowledge of the contents of the users elements,
only how to organize and retrieve them.
Hashed List Information Functions Function calls to retrieve specific size information about a list.
Element Insertion Functions Function calls to permit the insertion or other placement of new
elements in a hashed list.
Element Removal Functions Function calls to remove elements from a hashed list.
Element Retrieval Functions Function calls to locate and retrieve element data, from
presumably unsorted lists.
Hashed List Search Functions Function calls to perform searches for elements.
Element Transformation Functions Function calls to transform the relative order of elements in a
hashed list.
Miscellaneous List Functions Functions to perform technical operations on hashed lists.
Hashed List functions, grouped by type.
=======================================
Hashed List Object Management
-----------------------------
hash_list_create() Initialize a hashed list object, prior to using the list.
hash_list_erase() Erase all elements of a hashed list and the hashed list object itself.
hash_list_merge() Create a copy of a hashed list, written out to a D-List linear list.
list_split_hashed() Create a copy of a D-List list, imported into a hashed list.
hash_list_swap() Swap 2 hashed lists, swapping all the elements between the 2 lists.
hash_list_compare() Perform a comparison of two lists, indicating if they are the same.
Hashed List Function Management
-------------------------------
hash_list_set_compare_function() Set the compare function for a hashed list, used for element sorts and evaluations.
hash_list_get_compare_function() Retrieve the compare function for a hashed list.
hash_list_set_search_function() Set the search function for a hashed list, used for element searches.
hash_list_get_search_function() Retrieve the search function for a hashed list.
hash_list_set_size_function() Set the size function for a hashed list, used for lists that manage element storage.
hash_list_set_insert_function() Set the insert function for a hashed list, used upon placement to process an element.
hash_list_set_remove_function() Set the remove function for a hashed list, used upon removal to process an element.
hash_list_set_iterate_function() Set the iteration function for a hashed list, used by list_callback_iteration().
Hashed List Information Functions
---------------------------------
hash_list_is_empty() Check if a hashed list is empty, or not.
hash_list_size() Retrieve the number of elements in a hashed list.
hash_list_size_bucket() Retrieve the number of elements, by hash bucket, in a hashed list.
hash_list_get_bucket() Retrieve the pointer to the list_object for a specific hashed list bucket.
hash_list_is_sorted() Check if list is currently sorted, or not.
Element Insertion Functions
---------------------------
hash_list_append() Append an element to the end of a hashed list bucket.
hash_list_prepend() Prepend an element to the front of a hashed list bucket.
hash_list_insert_ref() Add an element to a list, in the location indicated by a hashed element reference.
Element Removal Functions
-------------------------
hash_list_clear() Remove all elements from a hashed list, leave it empty.
hash_list_fetch() Extract an element from the front (head), or the tail (end), of a hashed list.
hash_list_extract_ref() Extract an element, from the location indicated by a hashed element reference.
hash_list_delete_ref() Remove an element, from the location indicated by a hashed element reference.
hash_list_delete_duplicates() Remove all elements that are duplicates of other elements in the list.
hash_list_search_extract() Search for, and then extract, an element in a hashed list.
hash_list_search_delete() Search for, and then delete, an element in a hashed list.
hash_list_search_expunge() Search for, and then delete, all instances of an element from a hashed list.
Element Retrieval Functions
---------------------------
hash_list_get_ref() Retrieve an element, from the location indicated by a hashed element reference.
hash_list_get_next_ref() Retrieve the next element in a list, as indicated by a hashed element reference.
hash_list_locate_ref() Locate a hashed element reference in a list, identified by its element datum pointer.
hash_list_valid_ref() Verify if a hashed element reference is valid for the list.
hash_list_ref_equal() Validate if two hash element references are equal, and valid for the list.
hash_list_iteration_start() Start a sequence of iteration of all elements in a hashed list.
hash_list_iteration_has_more() Inquire if there are more elements, during an iteration sequence of a hashed list.
hash_list_iteration_get_next() Retrieve the next element in an iteration sequence of a hashed list.
hash_list_iteration_stop() Stop an iteration sequence of a hashed list.
Hashed List Search Functions
----------------------------
hash_list_simple_search() Search for an element in a hashed list, using element datum as the search criteria.
hash_list_occurrences() Search for all occurrences of an element, using datum as the search criteria.
hash_list_search() Search for an element in a hashed list, using element datum as the search criteria.
hash_list_search_ref() Search for an element, backwards or forwards, from a given reference point.
hash_list_locate_maximum() Search for an element in a hashed list, using maximum quantity as the search criteria.
hash_list_locate_minimum() Search for an element in a hashed list, using minimum quantity as the search criteria.
Sorted List Element Functions
-----------------------------
hash_list_sorted_find() Search for an element in a sorted hashed list, using datum as the search criteria.
hash_list_sorted_insert() Add an element to a sorted hashed list, in the position indicated by sort order.
hash_list_sorted_extract() Extract an element from a sorted hashed list, by the position indicated by sort order.
hash_list_sorted_delete() Delete an element from a sorted hashed list, by the position indicated by sort order.
hash_list_sorted_expunge() Search for, and then delete, all instances of an element from a sorted hashed list.
Element Transformation Functions
--------------------------------
hash_list_sort() Sort all the elements in a hashed list, using either ascending or descending order.
hash_list_fast_sort() Sort all the elements in a hashed list, by order, voiding element references.
hash_list_process() Process a list bucket of elements in a hashed list using a user function to operate on element data.
hash_list_callback_iteration() Start a sequence of callback iteration, to process all the elements in a hashed list.
Miscellaneous List Functions
----------------------------
hash_list_optimize_index() Perform an optimization of the element indexes in a hashed list.
hash_list_optimize_memory() Perform an optimization of the element memory storage in a hashed list.
hash_list_information() Provide details about a hashed list to stdout.
Note
====
Please refer to dhashed.h for more information about using D-List hashed lists and functions.
