When programming in C and you intend to write any type of complex program then you often find that you want to manipulate lists of data. You therefore find yourself implementing list-handling routines in each such program. This is costly in time and prone to error. Additionally the main logic of your program is often obscured by the code that does the mechanics of the list handling.
This library simplifies this problem by providing a packaged series of list routines that are known to work. The details of the list manipulation are no longer your concern - all you need to do is to specify the actions that you require. All details of the internal control structures used to maintain such lists are hidden from you. Instead you are just provided with a series of properties and methods that you can use against any list type.
The library treats lists in an object-oriented manner that will allow you to clearly separate out those bits of any program that are associated with list handling. This leads to better-structured source code that is much easier to follow. A consequence is that your program is less prone to logic errors.
A variety of different types of list are supported. Each type has different benefits in terms of processing cost, memory overheads per list instance and/or node, etc. The same methods and properties are supported for each list type as far as is practical, even though for some of the types this can be relatively inefficient in processing terms. This means that you can pick the list type that is optimised for your purposes, but if later your requirements change you can change the list type used without major change to your program. The new list type will support the same properties and methods that you have used on the previous list type.
Once you have mastered using this library, then you will find that many problems that manipulate lists become much easier to solve. You no longer have to think of the complexities of how lists operate, but just think of what you want to use them for. This will improve your productivity and reduce the number of errors you need to track down.
When you get this library, then you should have the following files provided:
LIBLIST.HTM | Documentation in HTML format |
LIBLIST.H | Header file for use with library (packed format) |
LIBLIST.HDR | Annotated (unpacked) version of above header |
LIBLIST.A | Standard version of library |
LIBLISTD.A | Debug version of library |
LISTSRC.ZIP | Source of the LIBLIST library as a ZIP archive |
In your source files you must include the liblist.h header file supplied with this library in any module that is going to make use of any of the methods or properties that are part of this library. This is done by including a line of the form:
#include <liblist.h>
You also need to tell the linker that it needs to search the list handling library for the routines that you have used. The library is provided in a number of different formats and you can specify which you want to use:
Standard Version |
This is a normal statically linked version provided in the liblist.a.file.
If you want to use this version then you need to provide parameters to the linker to
get it searched for required routines. The exact format of the parameter can vary
according to the linker used, but would typically be something like:
-llist
|
---|---|
Debug Version |
Programs that make extensive use of lists are often by their very nature
relatively complex and thus more prone to having internal logic faults.
The debugging version of this library helps identify such problems by
including extensive internal checks against you misusing the library and
providing silly parameter values. This is extremely useful while in the
development phase of a program. The penalty is that there is significantly
more overhead in terms of program size, memory usage and processing overhead
while using the debugging version of the library.
To use the debugging version of the library that is provided in the file
liblistD.a -llistd
Once you have finished debugging your program, then by simply changing the parameter provided to the LD linker you can switch to a non-debugging version of the library. |
RLL Version (QDOS based systems only) |
The RLL (Runtime Link Library) version is provided to allow the required
routines to be picked up dynamically at runtime from a separately loaded RLL
library.
To use the RLL version of the library you need to provide parameters of the form -rlist -llist
Note also that if you use this latter format it is necessary to ensure that
the user has a copy of the RLL library file |
There are also a number of compile time source code macros that you can use to provide some
fine-grained control of the features in the LIBLIST library. These macros can
be specified either by using a #define
statement in your source code
before you #include the liblist.h header file, or
alternatively via a command line option to the C pre-processor.
The macros available are:
LIBLIST_MACROS
| This macro specifies that wherever possible macro variants of the LIBLIST library routines should be used. This will generate inline code for the such routines. This will avoid the overhead of making a library call and thus execute faster. The downside tends to be that less runtime checks can be done on the parameters provided, so a fault in program logic is more likely to have serious consequences. |
LISTDEBUG
|
This macro specifies that you want additional debugging checks to be
included. If the LIBLIST_MACROS macro is also specified then it will
effectively be ignored.
It is agood idea to use this option when you are still developing your program and (probably) using the debugging variant of the LIBLIST library. Once you are confident that your code is stable then you can consider removing it to get maxmum speed. However it is your decision - and your code will function quite happily with it present all the time even when you are using the standard variant of the LIBLIST library. |
There are also some additional macros that are only relevant if you are rebuilding the library from the supplied source. | |
LIBDEBUG
| This is the same macro as described above - but it is mandatory if you intend to build a debugging version of the library. |
LISTTRACK
| Include extra code in the library that will keep track of what lists have been created and/or destroyed so that an attempt to delete a non-existent list is detected, rather than (potentially) causing a memory access fault. |
LIBTEST
| Get additional code included that do internal consistency checks on the library logic. Intended for use only when developing new versions of the library code. |
RLL_LIBS
| (QDOS systems only) Used to generate versions of the code that are suitable for inclusion into a RLL library. |
The following are the list classes currently supported by this library (more may be added in future releases). Although the use of this library largely hides the details of such complexity from you, you should still be aware of the characteristics of each list class so that you can select the class that is optimised for the purpose that you have in mind.
Single Linked List |
This is one of the commonest types of list. It is typically used to
store items that are unordered, although ordered operations are still
supported at the expense of additional processing overheads.
The advantages of this type of list are that it has the minimal amount of memory overhead associated with storing each entry (or node) in the list. The disadvantages of this type of list are that operations that involve add new entries towards the end of the list; searching for particular entries in the list; or attempting to move backwards through the list, tend to be rather expensive in processing terms, and the overhead tends to grow linearly with list size. |
---|---|
Double Linked List |
This is another very common type of list. It is typically used to
store items that are unordered, although ordered operations are still
supported at the expense of additional processing overheads.
It is similar in many ways to the Single Linked List mentioned above, except that it also supports reasonably efficient movement backward through the list. The penalty you pay is slightly more memory overhead for each node in the list. |
Queues (FIFO) |
A queue is a specialised use of a list where you normally want to
add items at the end and remove them from the front. This is why it is also
commonly known as a FIFO or First-In-First-Out list.
A queue is optimised for inserting new nodes at the end of the list and removing old nodes from the front. It does not support the concept of an ordered list. In other respects it tends to behave rather like the Single Linked List mentioned earlier. |
Stacks (LIFO) |
A stack is used when you normally want to add items at the front
of the list and also remove them from the front. This is why it is also
commonly known as a LIFO or Last-In-First-Out list.
A stack is optimised for inserting and removing new nodes from the front of the list. It does not support the concept of an ordered list. In all other respects it tends to behave rather like the Single Linked List mentioned earlier. |
Binary Tree |
A binary tree is commonly used when you want to store large numbers
of items that need to be kept in some sort of ordered manner. A typical example
might be a list of program symbols (although for unordered data a
hash table is normally faster).
The advantage of the binary tree is that it is optimised for quick searching and insertion of new nodes at any point using methods where the processing overheads do not grow linearly with list size. The disadvantage of the binary tree is that the storage overhead is slightly more than for any of the linked list types mentioned earlier. It is also a very inefficient way to store unordered data - for this it is better to use one of the linked list variants. |
Balanced Binary Tree |
A balanced binary tree is a specialisation of the standard
binary tree type that tries to optimise the search
operations even more than the simple binary tree type of list.
A standard binary tree type of list will become inefficient at fast searches if you insert data that is largely ordered in nature. The balanced binary tree type of list caters for this situation at the expense of more processing overhead being incurred while adding data using any of the insertion methods, and a larger memory overhead due to having to store slightly more information about each node. |
Hash Table |
A hash table is used in situations in which the key requirement
is very fast look-up of whether nodes already exist or not. It does
not by its very nature support the idea of an
ordered list. A typical use might be in a compiler
for storing information about symbols, as one would continually be checking
to see if a particular symbol exists.
The idea of a hash table is that is initialised with a specified number of nodes (known as buckets). This number is then fixed for the duration of any particular instance of the hash table type of list. A routine (called the hash algorithm) that does some sort of calculation on the supplied data is used to determine in which bucket this data should be stored. As this does not involve any searches, and as the calculations can be optimised for speed and all the required buckets are pre-created, this process can very fast. The main disadvantage of a hash table form of list is the memory overhead required to hold the fixed number of buckets.
In practice a realistic use of a hash table is almost always implemented
as a 'list of lists'. The first level is the true hash table, which uses
the hashing algorithm to get down to a particular bucket within the hash
table. Attached to that bucket is some other sort of list to resolve the
situation of there being more than one node that has the same hash value. This
second level can be another level of hash table (using a different hashing
algorithm to the first level) or some other type of list. In many cases the last
level is a LIFO (or stack) type of list as this means that it
can store any amount of data (memory permitting) and the most recently inserted node
(which is the one you are often most likely to want) is found first in any search.
This is in fact the default that will be assumed if you do not specify otherwise
using a |
The liblist.h
header file contains the following constants that
are used when defining the various types of list:
List Class | List Type | Description |
---|---|---|
LIST_CLASS_SINGLE
| LIST_TYPE_SINGLE
| Single linked list |
LIST_CLASS_DOUBLE
| LIST_TYPE_DOUBLE
| Double linked list |
LIST_CLASS_QUEUE
| LIST_TYPE_QUEUE
| Queue (also known as a FIFO) |
LIST_CLASS_FIFO
| LIST_TYPE_FIFO
| FIFO (another name for queue) |
LIST_CLASS_STACK
| LIST_TYPE_STACK
| Stack (also known as a LIFO) |
LIST_CLASS_LIFO
| LIST_TYPE_LIFO
| LIFO (another name for stack) |
LIST_CLASS_BTREE
| LIST_TYPE_BTREE
| Binary tree |
LIST_CLASS_BALTREE
| LIST_TYPE_BALTREE
| Balanced Binary Tree |
LIST_CLASS_HASH
| LIST_TYPE_HASH
| Hash Table |
Within the LIBLIST library we have the concept of ordered and unordered lists.
Ordered Lists |
In an ordered list one (or more) of the fields within a list node are
designated as key fields. The position that an entry should occupy in
the list is determined by comparing the key fields of the various entries.
When using an ordered list you normally just tell the system to add a new
entry to the list and let it work out the correct position that it should
occupy by doing any needed comparisons on the designated key fields.
A typical use of an ordered list might be for a list of names that you
want maintained in alphabetical order.
If you want to use ordered lists, then you have to supply a Node Comparison function at the time you create the list that is used by the library to decide the correct order. This is described in more detail later in this document in the section on user defined functions. Note also that not all the list types can support the concept of an ordered list. The description of each list type will tell you whether ordered lists are supported or not. |
---|---|
Unordered Lists |
In an unordered list on the other hand there is no explicit key field.
Instead the order is simply determined by the locations at which you
insert new entries. When building an unordered list you have to specify
exactly where any new entry should be inserted. This mode of operation is
particularly suited to lists where you will be inserting and/or deleting
entries from either the front or the back of the list.
It is also worth noting that there are times when the concept of whether a list is ordered or not does not really make sense. This is the case of the Hash Table class of list (where the hash function is always invoked to determine what bucket data is associated with). |
Partially Ordered Lists | There are no lists of this type currently implemented within the LIBLIST library. |
List type | Ordered | Unordered | Partially Ordered |
---|---|---|---|
Single linked list | Yes | Yes | n/a |
Double linked list | Yes | Yes | n/a |
Queue (FIFO) | No | Yes | n/a |
Stack (LIFO) | No | Yes | n/a |
Binary Tree | Yes | No | n/a |
Balanced Binary Tree | Yes | No | n/a |
Hash table | n/a | Yes | n/a |
The LIBLIST library also supports the concepts of embedded lists. An embedded list is defined as one in which a node containing user data is simultaneously a member of two different lists. The information that determines list order is maintained for each of the two different list types even though there is only one copy of the user data. You can also embed an existing embedded list inside another one, so that you can allow a node to simultaneously belong to as many lists as you want.
The drawback of an embedded list is that there are additional overheads in both memory terms and processing terms every time you add or delete nodes. These overheads are less than maintaining the two lists completely separately, but more than maintaining a single list. The big advantage is that it avoids the user having to explicitly use two (or more) method calls when creating, inserting or deleting nodes from the lists making up an embedded list with the possibility of forgetting to do so (and thus getting the lists out of step with each other).
The way an embedded list works is that you first create an empty list of one type.
You then embed this list in another list (using the
LIST_Embed
method) and are returned a
handle to this second list. Once you have done this, then any method that
would add or delete nodes from the list will actually add or delete the node
from both lists in a single call. It does not matter in this case
whether you use the list handle belonging to the original list, or the handle
belonging to the new containing list. The LIBLIST library will automatically
maintain the necessary links to add or delete nodes from both lists simultaneously.
When you use a property or method that does not add or delete nodes, but merely does something that is determined by the lists order, then the LIBLIST library will use the method that is appropriate to the list type associated with the particular list handle that you use.
An example of when you might want to use an embedded list would be the
case in which you wished to build up a symbol list for which you wanted the
ability to access the symbols in either address order or alphabetical name order.
In this case you could first create a list that was specified to maintain the
symbols in address order. You would do this by using the
LIST_Create
method where the parameter
specifying the node compare function was for a function
that did a comparison on the symbol address. You could then embed this list in
another one using the LIST_Embed
method,
but this time the parameter specifying the node compare function
would be for a function that does a comparison on the symbol name. In an extreme
case one could then perhaps embed both of these lists inside another one that
was a hash table optimised for maximum speed on looking up whether the symbol
exists or not.
If you try and use an insertion method on an embedded table that is not supported by all the list classes that are used within the embedded list, then an error will occur. This might mean that for practical reasons to do with the use one wants to make of the list, that there are limitations on which list classes can be used within an embedded list.
There are a number of specific data types that are used throughout this library.
The properties are used to obtain information about the current list. They do not change the list in any way, but just give information about the list. To be able to obtain the properties of any list you must (obviously) have earlier created one.
The LIBLIST library actually supports all properties for all list types. However each list type has a selection of the properties that are most frequently used with that type. Use of other properties is likely in many cases to be relatively expensive in processing terms.
The following table shows the properties that you are most likely to use with each list type, and then for each property (in alphabetical order) a detailed description is given describing its syntax and use.
Properties | List Types | |||||||
---|---|---|---|---|---|---|---|---|
Single Linked List | Double Linked List | FIFO List (Queue) | LIFO List (Stack) | Binary Tree | Balanced Binary Tree | Hash Table | ||
LIST_Version
| n/a | n/a | n/a | n/a | n/a | n/a | n/a | |
LIST_Copyright
| n/a | n/a | n/a | n/a | n/a | n/a | n/a | |
LIST_Class
| yes | yes | yes | yes | yes | yes | yes | |
LIST_Type
| yes | yes | yes | yes | yes | yes | yes | |
LIST_Ordered
| yes | yes | yes | yes | yes | yes | yes | |
LIST_Embedded
| yes | yes | yes | yes | yes | yes | yes | |
LIST_Count
| yes | yes | yes | yes | yes | yes | yes | |
LIST_Index
| yes | yes | yes | rarely | yes | yes | rarely | |
LIST_First
| yes | yes | yes | yes | yes | yes | rarely | |
LIST_Last
| yes | yes | yes | yes | yes | yes | rarely | |
LIST_Next
| yes | yes | rarely | rarely | rarely | rarely | rarely | |
LIST_Previous
| yes | yes | rarely | rarely | rarely | rarely | rarely | |
LIST_Inner
| yes | yes | yes | yes | yes | yes | yes | |
LIST_Outer
| yes | yes | yes | yes | yes | yes | yes | |
LIST_Duplicates
| yes | yes | read only | read only | yes | yes | yes | |
LIST_IsFirst
| yes | yes | yes | yes | yes | yes | rarely | |
LIST_IsLast
| yes | yes | yes | yes | yes | yes | rarely | |
LIST_IsMember
| yes | yes | yes | yes | yes | yes | yes |
*
listclass_t LIST_Class
Determine the class of list associated with a particular list handle.
The value returned is one of the values that can be passed as the type
parameter to the LIST_Create
or
LIST_Embed
methods. The
symbolic names for these list classes are
defined in the liblist.h header file.
Note that if you want to simply test for the list type and do processing that
is dependent on the type, then you are probably better off using the
LIST_Type
property that returns an integral type.
*
Returns a string that contains the copyright statement for the LIBLIST library.
*
Returns a count of the number of items in the list. A value of 0 means that the list is empty.
*
This property is used control the handling of duplicate entries within ordered lists.
You can control whether duplicates are allowed at all, and if they are where they should
normally be inserted relative to each other. If you are going to set this property
you must do so before any nodes have been inserted into the list.
The possible values for the flags parameter are as follows:
*
Determine if a particular list handle applies to an embedded list or not.
Returns 0 if it is not, and non-zero if it is.
*
Returns a pointer to the first node in the list, or
This property would normally only be used on unordered lists. On ordered lists you are
more likely to be using the *
Returns the index of the specified node in the list, or 0 if the node cannot
be found in the list (or if the list is empty). If you later want to retrieve
a pointer to the node then you can use the
Notes:
Returns a pointer to an inner list (assuming that there is one) for an
embedded list type, or
For lists that are not embedded lists, this property will always return *
Used to determine if node is the first node in the list.
Returns one of the following values;
*
Used to determine if node is the last node in the list.
Returns one of the following values;
*
Used to determine if node is a member of the list.
Returns one of the following values;
*
Returns a pointer to the last node in the list, or
This property would normally only be used on unordered lists. On ordered lists you are
more likely to be using the *
Returns a pointer to the next node in the list, or *
Used to determine whether a list is ordered or not. The values that can be returned are:
In practice you would rarely need to use this property, as you had to
specify when you created the list whether it was ordered or not so you
probably already know the answer.
Returns a pointer to an outer list (assuming that there is one) for an
embedded list type, or
For lists that are not embedded lists, this property will always return *
Returns a pointer to the previous node in the list, or *
Determine the type of list associated with a particular list handle.
The symbolic names for these list classes are
defined in the
Unlike the *
Returns a string that contains the version information for the LIBLIST library.
The methods are used to carry out some action on the list.
In most cases they will actually change the contents of the list.
The LIBLIST library supports most methods for all list types.
However each list type has a selection of methods that are most
frequently used with that type. There are a few methods that are very
specific to particular list types, and can return an error code if used
on the wrong type. These are indicated in the table below.
The following table shows the methods that you are most likely to use
with each list type, and then for each method (in alphabetical order)
a detailed description is given describing its syntax and use.
This method adds a node to the list at an appropriate point.
It will return
It is normally expected to be used with ordered lists, and in this case the
new node will be inserted at the correct point to maintain the order.
The user supplied node comparison function will be used
to help determine what is the correct insertion point.
If used with an unordered list, then the new node will be inserted at the most
sensible point. This means that it is treated as if it were an
This method adds a node after the given node.
It will return
It is normally expected to be used with unordered lists.
If used with ordered lists, then a
If the oldnode parameter is
This method inserts the given node at the end of the list. It will return
It is normally expected that it will be used with unordered lists.
If used with ordered lists, then a
The implementation of this operation is such that it is functionally
equivalent to
This method adds a node before the given node. It will return
It is normally expected that it will be used with unordered lists.
If used with ordered lists, then a
If the oldnode parameter is
This method deletes all the nodes currently associated with a list
leaving an empty list.
It is effectively equivalent to calling the
LIST_Delete method on all the nodes
on the list. Unlike the LIST_Destroy
method, the list itself remains in existence and available
for further use.
If this list is part of an embedded list then all the
list that make up the embedded list will be cleared, and all the
handles associated with handling the various embedded lists will remain valid.
This method will make a clone of the specified list.
By this we mean another empty list that is similar in all
respects to the one given in the list parameter. It is as if you
had used the
The value returned is a handle to the new list instance if the method was successful.
If for any reason an error occurred, then
The fundamental difference between using the
An example of when this situation might arise is if you have a list, and then
to each node of that list you are going to attach further lists. In this case
it is much more efficient in memory terms to issue a single *
This method is used to compare two nodes.
node1
This is used to create a new list.
On success it returns a pointer to the list handle which will be used
in all subsequent methods and property calls associated with this list.
On failure
The class parameter can be any one of the list classes whose
symbolic names are defined in the
liblist.h header file:
The node_size parameter is used to specify the size of the
data that the user wishes to store in each list node. It does not need
to include any allowances for fields used to maintain the list structure
as such details are handled internally within the LIBLIST library and are
hidden from the user.
The user can optionally provide the addresses of three
user supplied functions.
It is an error to try and specify ordering for list types that by their
very nature cannot be ordered. Examples of such lists are
Queue/FIFO lists; Stack/LIFO lists;
and Hash table lists that have no linked list.
More detail on these User Supplied Functions
is given later in this document.
Notes:
This method will remove the node from the list and then free it.
The address pointed to by the pnode parameter will be set
to NULL on success.
The method will return
It is effectively a combination of the
This method is provided as the standard way to remove a node from a list
that is acting as a queue.
It is the complement of the LIST_Enqueue method.
It will remove the first node from the given list and return a pointer to node.
If the list is empty, then
It is worth noting, however, that if you have specified that the list for
which is this method is being used is a Queue/FIFO
list type then the LIBLIST library will ensure that it is optimised to make
removing from the start of the list efficient. This might not be the case if
you simply use one of the other list types and use this method on them.
The implementation of this method means that it is functionally equivalent
to writing
This is used when a list is finished with to destroy a list, releasing all the associated memory.
First each node in turn will be destroyed using the
If this is the last instance of a cloned list, then the resources describing
the information that is common between clones will also be released.
If this list is part of an embedded list then all
handles associated with handling the embedded list will be destroyed, including
the other list handles associated with the other list making up
this embedded list .
You must not in this case use
This is used to create a new list with an already existing list embedded in it.
On success it returns a pointer to the list handle for the new list which will
be used in all subsequent methods and property calls associated with this new list.
On failure
The type parameter can be any one of the classes whose
symbolic names are defined in the
The oldlist parameter can be any of the list types, including another
embedded list, so lists can be embedded any number of levels. The oldlist
must not yet contain any data or the method call will fail with errno
set to the
The user can optionally provide the address of one
user supplied function, or
The new list will use the same values for the node initialisation
and the node destruction functions as were used for the list
specified by the oldlist parameter. This makes sense as the actual user
data part of any node is only held once even though the node is linked into two
(or more) different lists simultaneously. More detail on
User Supplied Functions is given later in this document.
*
This routine is provided as the standard way to add nodes to a list that
is acting as a queue. It will return 0 on success, and an error code on failure.
It is the complement of the LIST_Dequeue method.
The implementation of this method means it will insert a given node at the end
of the list, and it is thus functionally equivalent to the
It is worth noting, however, that if you have specified that the list for which
is this method is being used is a Queue/FIFO list type then
the LIBLIST library will ensure that it is optimised to make inserting at the end
of the list efficient. This might not be the case if you simply use one of the
other list types and use this method on them.
This function will work through each node in turn of a list, and for each
node call the user supplied node enumeration function.
If at any node this function returns a non-zero value, then the enumeration
process will be terminated early and the return value from the user function
returned as the result of this method. If the function returns 0 to every
invocation, then every node in the list will be enumerated and the method will
return 0.
The enumeration will proceed according to whatever ordering criteria have been
specified. If no ordering has been specified then physical storage order will
be used. A typical use of this function is when you want to perform an operation
on every node in the list, such as for instance listing out its details.
More details on the func parameter is given in the section on
user defined functions under the
node enumeration functions topic.
If any additional parameters are supplied following the name of the user
defined function, then these will be passed to the function every time it
is invoked using the methods defined in the
Note that the return type of this method is long. This is so that
the user-supplied function can, if desired, pass back a pointer as a result code.
The ISO C standard says that that the programmer is entitled to assume that the
long data type can be freely cast to/from any pointer data type.
This function is used to find a particular node from within a list.
You need to provide the name of the findfunc function that is to
be called for each node (to determine whether it is the one that you want or not.
If any parameters follow the name of the function, then they will be passed to the
function each time it is invoked using the methods defined in the
This method is used to destroy all nodes that are currently linked into the
given list, leaving an empty list. The user supplied
node destruction function (if any) will be called
when each node is freed. The method will return 0 on success, and an error
code on failure. The difference between this method and the
This method is used to destroy a node that is not currently linked into a list.
The user supplied node destruction function (if any)
will be called when the node is freed. On success the address pointed to by the
pnodeparameter will be set to NULL.
The method will return LIST_ERROR_NONE on success, and an error code on failure.
It is an error to call this function for a node that is still linked into the list.
If you want to destroy a node that is still linked into a list you should use the
This method is specific to Hash Tables, and will
return an
The parameters are used as follows:
Note: the value passed is a pointer to the handle returned by
This value can be anything that you like. However a point to note is that
typically prime numbers are often found to give best results in avoiding hash
values tending to cluster at specific points in the list.
Note: to ensure consistency, the NodeHash and
FindHash parameters must either both be
The default function supplied assumes that the first element of the user data
is a pointer to a string that is the 'key' for this node.
More detail is given in the User Defined functions
section of this document under the Node Hash Function
topic.
Note: to ensure consistency, the NodeHash and
FindHash parameters must either both be
It is passed the same user parameters as are passed to the
The default function supplied assumes that the first user parameter to
More detail is given in the User Defined functions
section of this document under the Node Hash Functions
topic.
A special point about treatment of the linked list is that any method call
that is made on the owning hash table (such as for instance a
This method inserts the given node at start of the list.
It will return
It is normally expected that it will be used with unordered lists. If used with
ordered lists, then it is an error if inserting the specified node at the start
of the list would violate the ordering constraints.
This method is used to merge one list into another one.
The source list is destroyed during the process.
It will return
This method is used to create a new node. It will not be inserted anywhere
in the list at this stage. The user supplied node initialisation function
(if any) supplied to the
This method can optionally have additional parameters, and if present they
are passed to the users node initialisation function
as defined in the section on User Supplied Functions.
On success a pointer to the new node is returned. If any error occurs,
then *
For an unordered list, these functions will simply create an empty node at the specified point.
For an ordered list, you must have provided a
node initialisation function to populate the new node
when you created the list via the
These methods are effectively a combination of the creation of a node with the
On success these methods return a pointer to the new node. On failure they return
All these methods can optionally take additional parameters that will (if present)
be passed to the user supplied node initialisation routine in the same manner as
is described under the
For more details read the descriptions given with the
This routine is provided as the standard way to look at the node that would
be returned by the
It is actually implemented as functionally equivalent to the
This method is provided as the standard way to remove a node from a
list that is acting as a stack.
It will remove the first node from the given list and return a pointer to
that node. If the list is empty, then
This method is provided as the way to obtain a pointer to a node at a given
index value in a list. The index parameter is equivalent to the value
returned by the
Notes:
This routine is provided as the standard way to add nodes to a list that is
acting as a stack. It will return
The way it is actually implemented is to simply insert the given node at
the start of the list, so it is functionally equivalent to the
This method unlinks a node from the list without destroying the node.
With unordered lists it can be used if you want to link the node back
into the list at a different point.
These are functions that are supplied by the user.
They are called at specified points in the processing of a list.
They are what is commonly known as Callback Functions in
that they are calls back to user supplied routines from within the
library methods. They are called to carry out a number of different purposes:
When a node is created, this function (if suppled) is called for the node.
The default initialisation of a node is to set any pointer fields to
int initnode (node_t node, va_list);
although the actual name does not have to be initnode but can be any name
that the user desires, and will typically be different for each list that is created.
The
On success this routine should return
The purpose of this function is to simply allow nodes to be initialised immediately
they have been created. This could simply mean setting up parts of the user node to
have given values. More advanced use of this function allows for setting up of
complex lists types such as lists that themselves contain lists linked to each
user node.
If the Node Initialisation function allocates any memory to be attached
to the node, then you should provide a corresponding Node Destruction
function to release this memory. The only exception to this rule would be if you
never use the
When a node is to be destroyed for any reason, this function (if supplied) is called
for each node. It is specified as a parameter to the LIST_Create
method call. As such it is basically a companion function to the
Node Initialisation function.
The prototype of this function is:
int killnode (node_t node)
although the actual name need not be killnode, but can be anything that the
user desires, and will typically be different for each list that is created. The
The normal thing that is done within this routine is the release of any resources
that have been attached to this node. This might simply be
The Node Comparison function is only required if a list is to be ordered
(i.e. maintained in some sort of specified order). The names of such functions
are passed as parameters to the
This function has the following prototype:
int comparenode (node_t node1, node_t node2);
although the name does not need to be comparenode, but can be any name
that the user desires, and would typically be different for each list that is created.
Pointers to the user part of the two nodes to be compared are passed as the
node1 and node2 parameters. The return value is interpreted
(using the same convention as is used by the
Node Enumeration functions are used whenever you decide to enumerate a list
(i.e. do something with every node in turn) using the
This function has the following prototype:
long enumnode (node_t node, va_list ap);
although the name does not need to be enumnode, but can be any name that
the user desires, and will typically be different for each use of the
If the return value is 0, then the list handling code will simply move onto the
next node in the list and call the Node Enumeration function again,
repeating this until the end of the list is reached. If for any reason you
return a non-zero value from this function, then the enumeration of the list
will be terminated immediately, and the value returned as the result of the
Notes:
This function is used when you wish to locate a particular node from within a
list using the
Very often there would only be one instance of the Node Find function
for each list instance as you are probably trying to find node according to the
keys you used for ordering the list. There is nothing, however, that mandates
this and stops you having different versions for different
This function has the following prototype:
int findnode (node_t node, va_list ap);
although the name does not need to be findnode, but can be any name
that the user desires. The
The return value is interpreted as follows:
For ordered lists it is vital that you return the value
These functions are only relevant to Hash Table types of list.
They are passed as parameters to a
There are two different variants of the hash function that have to be supplied:
although the name does not need to be hashnode, but can be any name
that the user desires. The
If the user does not supply a node hash function, then a default one
will be used. This default function assumes that the definition of the user part
of the node starts with a pointer to name along the lines of:
although the name does not need to be hashfind, but can be any name
that the user desires. The ap parameter is a pointer to any additional
parameters that might have been passed with the
If the user does not supply a node find function, then a default one
will be used. This default function assumes that the first user defined parameter
to the
This section covers a few methods that use the rest of the LIBLIST library to
provide functionality that one often wants in a program.
In a lot of programs you often want to be able to use pointers to strings.
If you have lots of occurrences of the same string it is inefficient in memory
terms to create a new copy of the string every times. What the NameSpace utility
routines do is provide a mechanism for allowing you to specify that you would like
to use a given string, and tracking your usage of that string. This type of facility
is often called a 'NameSpace' which is why these routines have been given that name.
The NameSpace utility functions provide you a very simple interface to allow you to
get a new NameSpace entry or to release one you are already using. The user of these
routines does not need to be aware of the internal mechanics of how they operate.
They can therefore be used without the need to understand any of the details about
the way the rest of the methods and properties in the LIBLIST library are used.
The Utility methods available in the LIBLIST library are the following:
This method is indicated that you no longer wish to use the given name from the namespace.
If the old_name parameter is
Notes:
This method is used to indicate that you want to use the given name from the namespace.
If there is no current entry in the NameSpace, then a new entry will be
created and the usage count set to 1. If a namespace entry already exists,
then the usage count is simply incremented. If there is insufficient
memory to create the entry then
The following is a consolidated list of the error codes that can be
generated by the LIBLIST library. They will all be outside the range
of normal system errors that can be returned by routines in the
default C library. They also all follow standard C style by being
negative constants.
For convenience of users who want to define their own error codes
relative to those used by the LIBLIST library, the range of values
of the error codes used by the LIBLIST library is defined by the
In practice you should rarely encounter this error code as if you have not
called the
This error code will only happen when a new facility has been added to
the documentation and has not yet been implemented. Therefore it should
only happen it test releases of this library. If it happens at any other
time please advise the author as it may indicate a discrepancy between the
documentation and the current implementation.
I have not written special example programs because I have found that
the use of the library is intuitive enough that most users do not seem
to need one.
Despite the above statement, example programs are always useful if one can
afford to invest the time in creating them.
Therefore if any user DOES produce example programs and are willing to contribute them
for public distribution then I would be more than willing to include such
example programs in future distributions of the LIBLIST library.
The source to this library does include the file
In particular it is worth seeing how the User Supplied functions
are used as this is the one area that some users initially find confusing.
Once you have seen how it works, instead of being confused, you are likely
to realise how it simplifies the logic of most programs to write them in this way.
This library and associated documentation has been produced by:
Dave Walker
Web: http://www.itimpi.freeserve.co.uk
Every effort has been made to ensure that the LIBLIST software operates correctly
as specified in this document. However no guarantee of any kind is given that the
software is reliable or that the descriptions contained in this document is accurate.
It is up to the user of the LIBLIST library to satisfy himself that it is suitable
for the use to which it will be put.
Permission is given to freely distribute this library, including its documentation
and source as long as the following terms are adhered to:
If anyone wishes to distribute the LIBLIST library under any other terms,
then they should contact the author to discuss these terms.
char * LIST_Copyright/A>(void);
long LIST_Count
int LIST_Duplicates
LIST_DUPLICATES_QUERY
Use this value when you simply wish to find out the current settings
for the handling of duplicates. No change is made to the current settings.
LIST_DUPLICATES_NA
This is returned if you try and read this property for an unordered list.
LIST_DUPLICATES_NONE
No duplicates are allowed. This is the normal default setting for ordered lists.
LIST_DUPLICATES_ALLOW
Duplicates are allowed, and the insertion point depends on the list type.
This means that you do not care where duplicates are inserted
relative to each other and the system is free to select the option that will
give best performance for insertion. Typically this will be equivalent to
using LIST_DUPLICATES_BEFORE
, but this behaviour is not guaranteed.
LIST_DUPLICATES_BEFORE
Duplicates are allowed.
New entries are inserted before existing entries with the same key.
This option is only allowed with ordered lists or hash tables.
LIST_DUPLICATES_AFTER
Duplicates are allowed.
New entries are inserted after any existing entries with the same key.
This option is only allowed with ordered lists or hash tables.
, int LIST_Embedded
node_t LIST_First
NULL
if the list is empty.
LIST_Find
or
LIST_Enumerate
methods.
It would also not make much sense to use this property on a Hash Table.
size_t LIST_Index
LIST_Position
method to obtain a pointer to the node with a given index value.
list_t LIST_Inner(list_t list);
NULL
if there is no inner list.
NULL
int LIST_IsFirst
LIST_TRUE
This value means that the node is the first node in the list
LIST_FALSE
This value means that the node is not the first node in the list
int LIST_IsLast
LIST_TRUE
This value means that the node is the last node in the list
LIST_FALSE
This value means that the node is not the last node in the list
int LIST_IsMember
LIST_TRUE
This value means that the node is a member in the list
LIST_FALSE
This value means that the node is not a member in the list
node_t LIST_Last
NULL
if the list is empty.
LIST_Find
or LIST_Enumerate
methods.
It would also not make much sense to use this property on a Hash Table.
node_t LIST_Next
NULL
if the end of the list has been reached.
int LIST_Ordered
LIST_ORDERED
List is ordered
LIST_UNORDERED
List is unordered
LIST_ORDER_NA
List concept of ordering is not applicable.
This is what is returned if you ask for the ordered property of
a Hash table.
list_t LIST_Outer(list_t list);
NULL
if there is no outer list.
NULL
node_t LIST_Previous
NULL
if the start of the list has been reached.
int LIST_Type
liblist.h
header file.
LIST_Class
property,
this one is an integral type suitable for use in switch
statements,
so is more convenient if you are writing code that needs to take actions that
are dependent on the list type.
char * LIST_Version/A>(void);
* LIST METHODS
Methods
List Types
Single
Linked
List
Double
Linked
List
FIFO
List
(Queue)
LIFO
List
(Stack)
Binary
Tree
Balanced
Binary
Tree
Hash
Table
LIST_Create
yes yes yes yes yes yes yes
LIST_Clone
yes yes yes yes yes yes yes
LIST_Embed
yes yes yes yes yes yes yes
LIST_Merge
yes yes yes yes yes yes yes
LIST_HashSetup
error error error error error error yes
List_Free
yes yes yes yes yes yes yes
LIST_Destroy
yes yes yes yes yes yes yes
LIST_NewNode
yes yes yes yes yes yes yes
LIST_FreeNode
yes yes yes yes yes yes yes
LIST_Add
yes yes yes yes yes yes yes
LIST_NewAdd
yes yes yes yes yes yes yes
LIST_Insert
yes yes yes yes rarely rarely error
LIST_NewInsert
yes yes yes yes rarely rarely error
LIST_Append
yes yes yes rarely rarely rarely error
LIST_NewAppend
yes yes yes rarely rarely rarely error
LIST_Before
yes yes rarely rarely rarely rarely error
LIST_NewBefore
yes yes rarely rarely rarely rarely error
LIST_After
yes yes rarely rarely rarely rarely error
LIST_NewAfter
yes yes rarely rarely rarely rarely error
LIST_Remove
yes yes rarely rarely yes yes yes
LIST_Clear
yes yes yes yes yes yes yes
LIST_Delete
yes yes rarely rarely yes yes yes
LIST_Position
yes yes yes rarely rarely rarely rarely
LIST_Compare
yes yes yes yes yes yes yes
LIST_Find
yes yes yes yes yes yes yes
LIST_Enqueue
rarely rarely yes rarely rarely rarely error
LIST_Dequeue
rarely rarely yes rarely rarely rarely error
LIST_NewEnqueue
rarely rarely yes rarely rarely rarely error
LIST_Push
rarely rarely rarely yes rarely rarely error
LIST_NewPush
rarely rarely rarely yes rarely rarely error
LIST_Pop
rarely rarely rarely yes rarely rarely error
LIST_Peek
rarely rarely yes yes rarely rarely error
*
int LIST_Add(list_t list, node_t node);
LIST_ERROR_NONE
on success, and an error code on failure.
LIST_Append
method for all list types
except for a Stack/LIFO list and the node added at the end of the list.
In the special case of the Stack/LIFO list type, this method acts as if it were
an LIST_Insert
method call and will
insert data at the start of the list.
int LIST_After(list_t list, node_t newnode, node_t oldnode);
LIST_ERROR_NONE
on success, and an error code on failure.
LIST_ERROR_SEQUENCE
error code will be returned if inserting the specified node at the specified
point would violate the ordering constraints.
NULL
, then this method
will act just like the LIST_Append
method
and insert the new node as the last node in the list.
int LIST_Append(list_t list, node_t node);
LIST_ERROR_NONE
on success, and an error code on failure.
LIST_ERROR_SEQUENCE
error code will be returned if inserting the specified node at the end
of the list would violate the ordering constraints.
LIST_After(LIST_LAST(list))
.
int LIST_Before(list_t list, node_t newnode, node_t oldnode);
LIST_ERROR_NONE
on success, and an error code on failure.
LIST_ERROR_SEQUENCE
error code
will be returned if inserting the specified node at the specified point
would violate the ordering constraints.
NULL
, then this will act just
like the LIST_Insert
method and insert the
new node as the first node in the list.
int LIST_Clear(list_t list);
list_t LIST_Clone(list_t oldlist);
LIST_Create
method with
exactly the same parameters as were used to create the oldlist
list specified as the parameter. It is perfectly legal to use the
LIST_Clone
method on a list instance
that is itself a clone - you do not always have to use the same instance as
was specified in the original LIST_Create
method call.
NULL
will be returned and
the global error variable errno
set to indicate the type of error
that occurred. In practice as long the oldlist parameter was valid
probably the only error that will ever occur is ENOMEM
because
you have run out of memory.
LIST_Create
and LIST_Clone
method calls is that,
with the LIST_Clone
method, both the new and the old list will
share information about the list attributes. This will include its node size,
and the user supplied functions for node initialisation, node destruction and
node comparison. This means that there is significantly less memory overhead
when the LIST_Clone
method is used compared to when another
LIST_Create
method call is used. This is particularly important
for situations in which you may have a very large number of occurrences of
a particular list type.
LIST_Create
method call to create the first instance of the attached list, and then use
LIST_Clone
method calls to create all the rest of the instances.
In fact you may well issue a dummy LIST_Create
method call as
part of your program initialisation to create the first instance which you
will never destroy, and then simply use LIST_Clone
method calls
as appropriate to create further instances of this type of list.
*
If this is an ordered list (the user supplied a Node Compare
function when the list was created) it will return values as defined for the
Node Compare function.
 
-ve
The key of node1 is less than the key of node2
 
0
The key of node1 is equal to the key of node2
 
+ve
The key of node1 is greater than the key of node2
 
Note that no check is made to see if the nodes concerned are
actually members of the list. The method just returns the value
that would be used to determine their position relative to each
other if they WERE in the list.
If this is an unordered list then
the comparison will be based on the physical order in the list. This means that
the return values are interpreted as meaning:
 
-ve
node1 is earlier than node2 in the list
OR node2 is not on the list
 
0
node1 and node2 are the same node
OR neither node1 or node2 is in the list
 
+ve
OR node1 is not on the list
 
I have been thinking of changing this behaviour to return LIST_ERROR_NOTFOUND if
either of the nodes is not in the list. I would be interested in feedback from
users if they would find this to be a more useful behaviour or if they prefer
the currently defined behaviour. I suspect that in most cases it makes no
difference?
list_t LIST_Create
(listclass_t class,
size_t node_size,
int (*initnode)(node_t node, va_list params),
int (*killnode)(node_t),
int (*compnode)(node_t, node_t);
NULL
is returned and the global variable
errno
set to indicate the cause of the failure.
A common reason for failure is to try and specify an ordering criteria
that is not supported by the list type.
NULL
if not required.
However, if you wish to use any of the methods that combine a
LIST_NewNode
method with an
insertion method in a single method call then you must
specify the node initialisation function.
NULL
if not required.
NULL
if not required. A value other than NULL
for this
function means that a list is to be an ordered list, while its
absence means that the list is unordered.
LIST_HashSetup
method call,
then if they are not all NULL the values of the initnode
and killnode parameters specified here
take precedence over any similar values used when creating the table
that is linked in via the LIST_HashSetup
method.
int LIST_Delete(list_t list, node_t * pnode);
LIST_ERROR_NONE
on success, and an
error code on failure. In practice the only way an error can occur
is if the node parameter does not point to a valid node,
or if a user supplied node destruction function
returns a non-zero value.
LIST_Remove
method to remove the node from the list, followed immediately by a
LIST_FreeNode
method on the same node.
node_t LIST_Dequeue(list_t list);
NULL
will be returned.
LIST_Remove>/A>(list, LIST_First(list))
int LIST_Destroy(list_t * plist);
LIST_Delete
method, and then when
all the resources associated with the nodes have been freed, the list handle
itself will be destroyed. On success, NULL will be written back to the
plist variable.
LIST_Destroy
on
the other handle(s) associated with the embedded list as they will no
longer be valid once a CODE>LIST_Destroy method call has succeeded on
any of them.
list_t LIST_Embed (listclass_t type, list_t oldlist, int (*compnode)(node_t,node_t));
NULL
is returned and the global variable errno
set to indicate the cause of the failure.
liblist.h
header file:
LIST_ERROR_NOTEMPTY
error code.
NULL
if not required.
LIST_Append
method.
long LIST_Enumerate(list_t list, (*enumfunc)(node_t, va_list), ...);
stdarg.h
header file.
However some care needs to be taken within the user defined function on the use
of these parameters, as they are not reset between invocations for each node.
This means that they must not be changed in any way unless you want the next
invocation of the function on the next node to inherit the changes.
node_t LIST_Find (list_t list, int (*findfunc)(node_t,va_list), ...);
stdarg.h
header file. More detail on how this function should operate is given under the
node find function description in the
user supplied functions section later in this document.
int LIST_Free(list_t list);
LIST_Destroy
method is that the
actual list itself is not destroyed.
int LIST_FreeNode(list_t list, node_t * pnode);
LIST_Delete
method instead.
int LIST_HashSetup
(list_t plist, size_t bucket_count,
size_t (*NodeHash)(node_t, va_list),
size_t (*FindHash(va_list),
list_t LinkedList);
LIST_ERROR_NOTSETUP
error code if used on any other
list type. It is used to specify attributes that are specific to the
hash table type of list. It must be used after you have
used a LIST_Create
, a
LIST_Clone
or a
LIST_Embed
method call to create an
instance of the list, but before you have inserted any data into the list.
A simple set of default values is provided for each of the parameters.
If they are sufficient it is possible to omit the call to this method.
Normally, however, you would want to use this method to tailor the hash
table more directly to your requirements.
LIST_Create
or
LIST_Clone
method call used to
create this particular hash table list.
LIST_Create
, and that the LIST_HashSetup
may change
this value.
LIST_Create
method was used
to create the original instance of the list will be 127 buckets.
NULL
means that the existing
function should be retained. This function will be used whenever you ask for a
node to be inserted into a hash table.
NULL
, or
neither one must be NULL
.
LIST_Find
method. A value of
NULL
means that the existing function should be retained.
NULL
, or
neither one must be NULL
.
LIST_Find
method, so it is up to the
user to ensure that any such parameters are consistent.
LIST_Find
is a pointer to a string
that is the 'key' for this node.
NULL
means do not change the
current setting. A special value of LIST_HASHONLY can be used if you do not
want any type of list to be linked to the hash table level. This has
the implication that only one node can be stored in the bucket with a given
hash value, so it would be very rare to use this value.
LIST_Add
that does not make sense at
that level will actually be performed by first using the NodeHash
function to determine what bucket should contain the node to be acted on,
and then calling the method on the list_t instance that is attached to that bucket.
Any relevant parameters will be passed through so that method finally called will
not be aware of this pass down mechanism.
int LIST_Insert(list_t list, node_t node);
LIST_ERROR_NONE
on success, and an error code on failure.
int LIST_Merge(list_t targetlist,list_t sourcelist);
LIST_ERROR_NONE
on success, and an error code on failure.
node_t LIST_NewNode(list_t list, ...);
LIST_Create
method call that was used to create the list will be called automatically to
complete any user defined initialisation of this new node.
NULL
will be returned, and the global error variable
errno
set to indicate the error type.
node_t LIST_NewAdd
node_t LIST_NewInsert (list_t list, ...);
node_t LIST_NewAppend (list_t list, ...);
node_t LIST_NewBefore (list_t list, node_t oldnode, ...);
node_t LIST_NewAfter (list_t list, node_t oldnode, ...);
node_t LIST_NewEnqueue (list_t list, ...);
node_t LIST_NewPush (list_t list, ...);
LIST_Create
method. If you did not supply the node initialisation function for an ordered list,
then these methods will always fail with the global error variable errno
set to LIST_ERROR_BADINIT
.
LIST_NewNode
method and the corresponding
list insertion method. They are just provided for convenience, as you frequently
want to create a new node and immediately insert it into the list.
NULL
, and the errno
global error variable will be set
to indicate the error type. In fact the only common error is likely to be
LIST_ERROR_NOMEMORY
that would be returned if you run out of free memory.
LIST_NewNode
method.
LIST_NewNode
method and the various
methods for inserting nodes into a list.
node_t LIST_Peek(list_t list);
LIST_Dequeue
or
LIST_Pop
methods without actually
removing the node from the list.
LIST_First
property, but is the term
more commonly associated with handling of queues and stacks.
node_t LIST_Pop(list_t list);
NULL
will be returned.
This method is functionally equivalent to writing
LIST_Remove (list, LIST_First(list))
on a list that is not empty.
node_t LIST_Position(list_t list, size_t index);
LIST_Index
property.
A value of NULL
is returned if there is no node with the supplied
value of index.
int LIST_Push(list_t list, node_t node);
LIST_ERROR_NONE
on success,
and an error code on failure.
LIST_Insert
method.
int LIST_Remove(list_t list, node_t node);
*
USER SUPPLIED FUNCTIONS
Node Initialisation Function
NULL
, and all other data fields to zero. This function
will be used to do any additional initialisation that is required. It is
specified as a parameter to the LIST_Create
method call. This function has the following prototype:
node
parameter is a pointer to the user part of the new node that
has just been created. The ap
parameter is a pointer to any additional
parameters that might have been passed with the LIST_NewNode
method or any of the LIST_NEW
method
calls that combine the creation of a new node with an insertion method. These parameters
are accessed using the standard C library functions associated with the stdarg.h
header file.
LIST_ERROR_NONE
.
Any other value will be treated as an error code, and passed back to the calling program.
List_Delete
method to destroy
individual nodes or the LIST_Destroy
method
to destroy a list. In this case the resources will instead be automatically released
when the program terminates.
*
Node Destruction Function
node
parameter is a pointer to the user part of the node that is about
to be destroyed.
malloc
'ed
memory that has been attached to this node, or it might be something much more
significant such as destroying further lists that are attached to this node.
*
*
Node Compare Function
LIST_Create
and the LIST_EMbed
method calls. The fact
that you have bothered to specify a Node Comparison routine (rather than
passing a NULL
value) means that the particular list instance being
created is to be treated as ordered. The purpose of this function is to compare
two nodes in the list to determine which one is to be considered the larger for
ordering purposes.
strcmp
standard C library
function) as follows:
-ve
The key of node1 is less than the key of node2.
(i.e. node1 is earlier in the list than node2)
0
The key of node1 is equal to the key of node2
+ve
The key of node1 is greater than the key of node2.
(i.e. node1 is later in the list than node2)
*
Node Enumeration Function(s)
LIST_Enumerate
method call. It is likely
that each different use of the LIST_Enumerate
method will have a different
associated node enumeration function that carries out a different action.
LIST_Enumerate
method call.
The node
parameter is a pointer to the user part of the node that
is being enumerated. The ap parameter is a pointer to any additional
parameters that might have been passed with the
LIST_Enumerate
method call. These
parameters are accessed using the standard C library functions associated with
the stdarg.h
header file.
LIST_Enumerate
method call.
*
Node Find Function
LIST_Find
method call.
The name is passed as one of the parameters to this method. The purpose of
this type of function is to check whether a particular node is the one that
you are trying to find.
LIST_Find
method calls.
node
parameter is a pointer to the user
part of the node that is being checked. The ap parameter is a pointer
to any additional parameters that might have been passed with the
LIST_Find
method call. These parameters
are accessed using the standard C library functions associated with the
stdarg.h header file.
-ve
This node is not wanted,
If it is an order list it also indicates that this node is earlier in the list
than the desired node.
0
This is the node that is wanted
+ve
This node is not wanted.
If it is an order list it also indicates that this node is later in the list
than the desired node.
LIST_ORDER_NA
This node is not wanted, and nothing can be said about its relationship
to the desired node. This constant is defined in the liblist.h header file.
LIST_ORDER_NA
when you are searching on some criteria other
than the fields used by the Node Compare Function
and this node is not required.
If you return some other non-zero value, then the LIBLIST library will assume
it indicates the position of the desired node in the list relative to this one,
and will try to optimise the search on this basis - possibly never getting to the
node you are really interested in finding.
LIST_Find
method
with a hash table that the initial parameters passed to the node find
function must correspond to those expected by the find hash user
supplied function.
*
Node Hash Functions
LIST_HashSetup
method call. Their purpose is to calculate the hash value that is used to
determine which bucket of a hash table a node belongs to. The value
returned by this function will be automatically normalised to ensure that it
falls into a valid range for the number of nodes that are actually in the
EM>hash table, so it is not necessary for the hash function itself to do this.
Notes:
node
parameter is a pointer to the existing node
struct { char * name; /* The type is important, not the name */ .... };
LIST_Find
method.
This function has the following prototype:
LIST_Find
method call.
LIST_Find
method is a
char *
parameter pointing to the null terminated string that is the
name being used as a key for the node.
LIST_HashSetup
method call that you have
either specified both these routines or neither of them.
*
*
UTILITY METHODS
NameSpace manipulation
Method
Description
LIST_NameSpace_Use
Use an entry in the namespace
LIST_NameSpace_Free
Stop using an entry in the namespace
void LIST_NameSpace_Free(char **
old_name);
NULL
, or it points
to an entry containing NULL
, simply return back to the calling point.
*
LIST_NameSpace_Free
method call again without
a LIST_NameSpace_Use
method call.
char * LIST_NameSpace_Use(char *
wanted_name);
NULL
is returned.
*
*
ERROR CODES
LIST_ERROR_BASE
and the LIST_ERROR_TOP
constants. These constants are defined in the liblist.h
header file.
Error Code
Description
LIST_ERROR_NONE
The value that is returned when no error has occurred.
LIST_ERROR_BADCLASS
You have supplied a bad parameters to the
LIST_Create
method for the
listclassparameter. It is either NULL or one that is not recognised.
LIST_ERROR_BADHASH
You have not supplied consistent parameters to the
LIST_HashSetup
method for the
user defined hash functions. You must either supply
both of them or neither of them.
LIST_ERROR_BADINDEX
The value that you passed as the index value is outside the range of legal values for this list.
LIST_ERROR_BADINIT
You have not supplied a node initialisation function,
and it is mandatory for the list type you are trying to create.
LIST_ERROR_BADLIST
The value that you passed as the list handle is invalid.
LIST_ERROR_BADNODE
The value that you passed as the address of a list node is invalid.
LIST_ERROR_BADSIZE
The value that you passed as the size of the user data in a node is invalid.
This will be because the value passed is negative or zero.
LIST_ERROR_BADTYPE
The value that you passed as the type of list is invalid.
This should never occur if you stick to the constants that are defined
in the liblist.h header file.
LIST_ERROR_DUPLICATE
You are trying to insert a duplicate node, and this the settings for
this list do not allow duplicates. You need to set the
LIST_Duplicate property after creating
the list if you want duplicates to be allowed.
LIST_ERROR_NOMEMORY
There is not enough free memory to carry out the requested operation.
In most programs this will be a fatal error condition.
LIST_ERROR_NOTEMPTY
The operation that you have requested in not allowed on a list that already contains data.
LIST_ERROR_NOTFOUND
The node that you have specified cannot be found in this list.
LIST_ERROR_NOTSETUP
You have tried to use a Hash Table type of list
before you have used the LIST_HashSetup
method to complete its initialisation.
LIST_HashSetup
method by the
time you first try to add entries into the table, the LIBLIST library will
automatically try and initialise the Hash Table with a
default set of values.
LIST_ERROR_ORDERED
The operation that you have requested in not allowed on ordered lists.
If this occurs on a LIST_Create method then
it means that you have omitted a Node Compare
function for a list type that must be ordered.
LIST_ERROR_SAMELIST
An operation that needs two different lists as parameters actually has the same
list for both parameters. This may no always be obvious as in the case of embedded
lists where one in effect has more than one handle available for the same list.
LIST_ERROR_SEQUENCE
You have asked for a node to be inserted in an order table at a specified point,
and the position that you have specified would break the ordering constraints.
LIST_ERROR_UNORDERED
The operation that you have requested in not allowed on unordered lists
If this occurs on a LIST_Create method then
it means that you have supplied a Node Compare
function for a list type that must be unordered.
LIST_ERROR_NOTREADY
You have asked for a facility that has not yet been implemented.
* EXAMPLE PROGRAM
LISTTEST.C
that is used to test the library. This is not specifically written as an
example program but the source is copiously annotated.
If you are having problems working out how to use this library it
is worth examining as an example of how the various properties and
methods in the library can be used. It does have the advantage that
as it is designed to test the library there should be at least one
use of every property and method in the library.
* IDEAS FOR THE FUTURE
This section contains ideas that I have had for future enhancements
to the facilities offered in this library. I would welcome any
feedback on features that existing users would find useful.
New List Types
These are ideas for supporting either brand new list types or variants
on those already supported.
These are lists where the head and tail are linked to each other so that
you can traverse them without having to know where the head and tail are.
Easy enough to implement but I am not sure how much use they would have.
These are form of tree in which there are an arbitary number of links to
the nodes at each level. As such they are an extension of binary trees
that can be used when depth of the tree is important Probably easy
enough to implement - but again I am not sure how widely this is needed.
These are a form of list implemented as a tree structure where each child
node is either smaller (top-heavy) than its parent or
larger (bottom-heavy) than its parent. The nodes at a particular
level in the tree are only sorted relative to their parent and not to
other nodes at the same level belonging to other parents. A partially sorted
tree of this type is cheaper to maintain than a fully sorted one and it
allows one to always find the maximum (top-heavy) or minimum
(bottom-heavy) value in the tree in the fastest possible way.
A heap organised so that we can find the next highest priority rapidly.
The term "priority" of an element can mean different things in different
problems.
This would be quite an ambitious addition to the library!
Graphs are some of the most flexible data structures used in computing.
Graphs would allow nodes to be arranged with arbitary linkages between
the nodes allowed.
New Utility Routines
These are pre-packaged sets of routines that solve some common problem and
that are implemented on top of one or more list structures.
I have been thinking for a while about implementing sets as they could
quite easily be implemented on top of the current list structures.
In addition to supporting many of the normal list related operations to
do with adding and removing nodes, the intention would be to support set
related operations such as
This is some packaged support for manipulation of symbol tables.
Symbol tables are normally implemented as a Chained Hsh Table
which is basically a standard Hash Table
with some other sort of list attached to each bucket in the hash table.
This is a variant of Hash Table where the data is always
stored directly into the hash table itself and special collision detection
code based on probing the data is used to resolve collisions. I would
probably provide a choice between a Linear probing and
a Double Hashing method of handling the probing as the
two methods are both omptimised for different purposes.
General
When an existing node is destroyed the current implementation actully immediately
destroys all assocaited memory structures. This can be quite an expensive
operation so an alternative would be to simply mark such nodes as "hidden" and
subsequently ignore them unless they get added back into a list. This would
be more effecient in applications in which nodes are regularily destroyed and
recreated although it would be more expensive in total memory usage.
* AUTHOR and COPYRIGHT
22 Kimptons Mead
Potters Bar,
Herts,
EN6 3HZ
United Kingdom
Email: dave.walker@icl.com
or: liblist@itimpi.freeserve.co.uk
*
RELEASE HISTORY
July 2000: Release 1.5
November 1999: Release 1.4
May 1999: Release 1.3
August 1997: Release 1.2
LIST_Inner
and LIST_Outer
properties added.
LIST_Free
method added
LIST_Destroy
method parameter
changed to be address of the list so that NULL
can be written
back to list variable.
June 1996: Release 1.1
May 1996: Release 1.0