LIBLIST List Manipulation Library

CONTENTS

• Introduction
• Using this library
• List Classes
• Ordered and Unordered lists
• Embedded lists
• List Data Types
• List Properties
• List Methods
• User supplied functions
• Utility Methods
• Error Codes
• Example program
• Author and Copyright
• Release History

* INTRODUCTION

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

* USING THIS LIBRARY

When you get this library, then you should have the following files provided:

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:

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

Debug Version

RLL Version (QDOS based systems only)

All variants of the library are functionally identical as far as the methods and properties supported are concerned. This means that you can develop your program using the debugging variant of the library. When you have finished debugging your program, then you can simply change the parameter(s) to the LD linker, and relink your program with either the standard version or the RLL version to get a reduction in program size; reduced runtime memory usage; and an increase in speed.

* LIST CLASSES

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

Double Linked List

Queues (FIFO)

Stacks (LIFO)

Binary Tree

Balanced Binary Tree

Hash Table

The liblist.h header file contains the following constants that are used when defining the various types of list:

* ORDERED and UNORDERED LISTS

Within the LIBLIST library we have the concept of ordered and unordered lists.

Ordered Lists

Unordered Lists

* EMBEDDED LISTS

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.

* LIST DATA TYPES

There are a number of specific data types that are used throughout this library.

list_t

listclass_t

node_t

* LIST PROPERTIES

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.

listclass_t LIST_Class(list_t list);

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.

long LIST_Count(list_t list);

Returns a count of the number of items in the list. A value of 0 means that the list is empty.

int LIST_Embedded(list_t list);

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.

node_t LIST_First(list_t list);

Returns a pointer to the first node in the list, or NULL if the list is empty.

This property would normally only be used on unordered lists. On ordered lists you are more likely to be using the LIST_Find or LIST_Enumerate methods.

size_t LIST_Index(list_t list, node_t node);

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 LIST_Position method to obtain a pointer to the node with a given index value.

One point to watch though is the index value may not stay valid if you insert new data into a list. Whether it does or not will depend on the relative positions in the list at which the new data is inserted. You should always assume that inserting new data invalidates any current index property that you may have obtained earlier.

list_t LIST_Inner(list_t list);

Returns a pointer to an inner list (assuming that there is one) for an embedded list type, or NULL if there is no inner list.

For lists that are not embedded lists, this function will always return NULL

node_t LIST_Last(list_t list);

Returns a pointer to the last node in the list, or NULL if the list is empty.

This property would normally only be used on unordered lists. On ordered lists you are more likely to be using the LIST_Find or LIST_Enumerate methods.

node_t LIST_Next(list_t list>, node_t node);

Returns a pointer to the next node in the list, or NULL if the end of the list has been reached.

int LIST_Ordered(list_t List);

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.

list_t LIST_Outer(list_t list);

Returns a pointer to an outer list (assuming that there is one) for an embedded list type, or NULL if there is no outer list.

For lists that are not embedded lists, this function will always return NULL

node_t LIST_Previous(list_t list, node_t node);

Returns a pointer to the previous node in the list, or NULL if the start of the list has been reached.

int LIST_Type(list_t list);

Determine the type of list associated with a particular list handle. The symbolic names for these list classes are defined in the liblist.h header file.

Unlike the 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.

*LIST METHODS

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.

int LIST_Add(list_t list, node_t node);

This method adds a node to the list at an appropriate point. It will return LIST_ERROR_NONE on success, and an error code on failure.

t 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 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);

This method adds a node after the given node. It will return LIST_ERROR_NONE on success, and an error code on failure.

It is normally expected to be used with unordered lists. If used with ordered lists, then it an LIST_ERROR_SEQUENCE error code will be returned if inserting the specified node at the specified point would violate the ordering constraints.

If the oldnode parameter is 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);

This method inserts the given node at the end of the list. It will return LIST_ERROR_NONE on success, and an error code on failure.

It is normally expected that it will be used with unordered lists. If used with ordered lists, then it a LIST_ERROR_SEQUENCE error code will be returned if inserting the specified node at the end of the list would violate the ordering constraints.

int LIST_Before(list_t list, node_t newnode, node_t oldnode);

This method adds a node before the given node. It will return LIST_ERROR_NONE on success, and an error code on failure.

It is normally expected that it will be used with unordered lists. If used with ordered lists, then it a LIST_ERROR_SEQUENCE error code will be returned if inserting the specified node at the specified point would violate the ordering constraints.

If the oldnode parameter is NULL, then this will act just like the LIST_Insert method and insert the new node as the first node in the list.

list_t LIST_Clone(list_t oldlist);

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

The value returned is a handle to the new list instance if the method was successful. If for any reason an error occurred, then 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.

The fundamental difference between using the 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.

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

int LIST_Compare(list_t list, node_t node1, node_t node2)

This method is used to compare two nodes.

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

list_t LIST_Create	(list_t type, size_t node_size,
	int (*initnode)(node_t node, va_list params),
	int (*killnode)(node_t),
	int (*compnode)(node_t, node_t);

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 NULL is returned and the global variable errno set to indicate the cause of the failure.

The type 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.

• The initnode node initialisation function that is to be called each time a new node is created. Can be set to 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.
• The killnode node destroy function that is to be called each time a node is destroyed. Can be NULL if not required.
• The compnode node compare function that is to be called to compare two nodes of a list to decide which is larger. Can be set to 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.

  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.

Note also that if you are setting up a Hash Table type of list, and it later has another table linked in via a LIST_HashSetup method call, then if they are not all NULL the values of the initnode, killnode and compnode 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 node);

This method will remove the node from the list and then free it. It will return 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.

It is effectively a combination of the 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);

This method is provided as the standard way to remove a node from a list that is acting as a queue.

It will remove the first node from the given list and return a pointer to node. If the list is empty, then NULL will be returned.

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

The implementation of this method means that it is functionally equivalent to writing LIST_Remove(LIST_First(list))

int LIST_Destroy(list_t * list);

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 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 list variable.

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 embedding list will be destroyed, including the other list handles associated with the embedded list . You must not in this case use 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);

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 NULL is returned and the global variable errno set to indicate the cause of the failure.

The type parameter can be any one of the classes whose symbolic names are defined in the liblist.h header file:

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 LIST_ERROR_NOTEMPTY error code.

The user can optionally provide the address of one user supplied function, or NULL if not required.

• The compnode node compare function that is to be called to compare two nodes of a list to decide which is larger. The presence of this function means that a list is to be an ordered list, while its absence means that the list is unordered. It would be very rare with an embedded list for a list to be unordered as if so why bother to embed the list at all?

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.

int LIST_Enqueue(list_t list, node_t node);

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.

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 LIST_Append method.

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.

long LIST_Enumerate(list_t list, (*func)(node_t, va_list), ...);

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. 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 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 to inherit the changes.

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.

node_t LIST_Find (list_t list, int (*findfunc)(node_t,va_list), ...);

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

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 LIST_Destroy method is that the actual list itself is not destroyed.

int LIST_FreeNode(list_t list, node_t node);

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. The method will return 0 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 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);

This method is specific to Hash Tables, and will return an 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.

The parameters are used as follows:

• plist is a pointer to the list handle that was returned from the original LIST_Create or LIST_Clone method call used to create this particular hash table list.

  Note: the value passed is a pointer to the handle returned by LIST_Create, and that the LIST_HashSetup may change this value.

• bucket_count is used to set the number of buckets that are to be set up for the hash table (and thus the initial amount of space that will be occupied). A value of 0 means do not change the current value. The default value set when the LIST_Create method was used to create the original instance of the list will be 127 buckets.

  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.

• NodeHash is the name of a function that will calculate the hash value given a pointer to anode. A value of 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.

  Note: to ensure consistency, the NodeHash and FindHash parameters must either both be NULL, or neither one must be NULL.

  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.

• FindHash is the name of a function that will calculate the hash value when trying to find an existing node using the LIST_Find method. A value of NULL means that the existing function should be retained.

  Note: to ensure consistency, the NodeHash and FindHash parameters must either both be NULL, or neither one must be NULL.

  It is passed the same user parameters as are passed to the LIST_Find method, so it is up to the user to ensure that any such parameters are consistent.

  The default function supplied assumes that the first user parameter to LIST_Find 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 Functions topic.

• LinkedList is the instance handle of a list type that is to be attached to each node. A value of 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.

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

This method inserts the given node at start of the list. It will return LIST_ERROR_NONE on success, and an error code on failure.

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.

node_t LIST_NewNode(list_t list, ...);

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

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 NULL will be returned, and the global error variable errno set to indicate the error type.

node_t LIST_NewAdd (list_t list, ...);
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, ...);


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

These methods are effectively a combination of the creation of a node with the 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.

On success these methods return a pointer to the new node. On failure they return 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.

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 LIST_NewNode method.

For more details read the descriptions given with the LIST_NewNode method and the various methods for inserting nodes into a list.

node_t LIST_Peek(list_t list);

This routine is provided as the standard way to look at the node that would be returned by the LIST_Dequeue or LIST_Pop methods without actually removing the node from the list.

It is actually implemented as functionally equivalent to the LIST_First property, but is the term more commonly associated with handling of queues and stacks.

node_t LIST_Pop(list_t list);

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 NULL will be returned. This method is functionally equivalent to writing LIST_Remove (LIST_First(list))

node_t LIST_Position(list_t list, size_t index);

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 LIST_Index property. A value of NULL is returned if there is no node with the supplied value of index.

Note that any time a node is inserted or deleted from a list, the index values associated with the remaining nodes can change, so this needs to be taken into account if using this method.

int LIST_Push(list_t list, node_t node);

This routine is provided as the standard way to add nodes to a list that is acting as a stack. It will return LIST_ERROR_NONE on success, and an error code on failure.

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 LIST_Insert method.

node_t LIST_Remove(list_t list, node_t node);

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.

* USER SUPPLIED FUNCTIONS

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:

• Node Initialisation
• Node Destruction
• Node Comparison
• Node Enumeration
• Node Finding
• Node Hashing (Hash tables only)

Node Initialisation Function

When a new node is created, any pointer fields are automatically set to NULL, and all other data fields set 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:

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

On success this routine should return LIST_ERROR_NONE. Any other value will be treated as an error code, and passed back to the calling program.

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

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:

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 node parameter is a pointer to the user part of the node that is about to be destroyed.

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

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

This function has the following prototype:

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 strcmp standard C library function) as follows:

Node Enumeration Function(s)

Node Enumeration functions are used whenever you decide to enumerate a list (i.e. do something with every node in turn) using the 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.

This function has the following prototype:

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

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 LIST_Enumerate method call.

Note that the return type of this function 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.

Node Find Function

This function is used when you wish to locate a particular node from within a list using the 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.

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 LIST_Find method calls.

This function has the following prototype:

although the name does not need to be findnode, but can be any name that the user desires. The 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.

The return value is interpreted as follows:

although in practice for unordered lists the difference between the different non-zero values is ignored (as they have to be searched serially anyway since they are unordered). For ordered lists the information is used where possible to optimise the location process by avoiding visiting every node in the list if the value returned can be used to help navigate to the desired node (assuming that it exists of course).

Note that if using the 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

These functions are only relevant to Hash Table types of list. They are passed as parameters to a 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.

There are two different variants of the hash function that have to be supplied:

• The node hash function used to calculate the hash value given a pointer to an already existing node. This function has the following prototype:
  size_t hashnode (node_t node);

  although the name does not need to be hashnode, but can be any name that the user desires. The node parameter is a pointer to the existing node

  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:

  struct { char * name; /* The type is important, not the name */ .... };

• The find hash function used to calculate the hash value when trying to find a node using the LIST_Find method. This function has the following prototype:
  size_t hashfind (va_list >ap);

  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 LIST_Find method call.

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

The other point to note is that the node hash and the find hash functions always need to be kept in step. Therefore a check will be made in the LIST_HashSetup method call that you have either specified both these routines or neither of them.

* UTILITY METHODS

This section covers a few methods that use the rest of the LIBLIST library to provide functionality that one often wants in a program.

NameSpace manipulation

The Utility methods available in the LIBLIST library are the following:

void LIST_NameSpace_Free(char ** old_name);

This method is indicated that you no longer wish to use the given name from the namespace.

If the old_name parameter is NULL, or it points to an entry containing NULL, simply return back to the calling point.

The usage count of the NameSpace entry will be decremented by 1. If this means that the usage count has reverted to 0, then the NameSpace entry is deleted. Writes a NULL back into the pointer that previously stored the old_name address. This will protect against inadvertently calling the LIST_NameSpace_Free method call again without a LIST_NameSpace_Use method call.

char * LIST_NameSpace_Use(char * wanted_name);

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.

* ERROR CODES

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 LIST_ERROR_BASE and the LIST_ERROR_TOP constants. These constants are defined in the liblist.h header file.

* EXAMPLE PROGRAM

The source to this library includes the file LISTTEST.C that is used to test the library. The source is however copiously annotated, so it is worth examining it as an example of how the various properties and methods in the library can be used.

In particular it is worth seeing how the User Supplied functions are used as this is the one area that many 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.

* AUTHOR and COPYRIGHT

This library and associated documentation has been produced by:

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:

• No attempt is made to claim ownership of this material or any rights to the LIBLIST library software.
• You do not distribute the LIBLIST library as a commercial product, although reasonable charges may be made to cover your time, media costs and postage in the case of software libraries that distribute Public Domain or shareware software.
• When distributing the LIBLIST package, the complete package must be enclosed including this notice.
• The LIBLIST library may be linked into a commercial software package, but in this case no additional charge may be made for the LIBLIST library component.

If anyone wishes to distribute the LIBLIST library under any other terms, then they should contact the author to discuss these terms.

* RELEASE HISTORY

May 1996: Release 1.0

• First version of the library.
• Released via the QDOS BBS network. Does not include the RLL version of the library, as the RLL system has not been made generally available for QDOS based systems.
• Supports Single, Double, Queue (FIFO), Stack (LIFO) and Binary Tree list types.

June 1996: Release 1.1

• Support for hash tables and balanced binary trees completed.
• Embedded list feature specified in documentation, and code to support it added.

August 1997: Release 1.2

• Support for 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.
• New section for Utility functions added, and initially populated with LIST_NameSpace_Use and LIST_NameSpace_Free methods.

March 1998: Release 1.21

• Minor bug fix to handle problem with the LIST_Find() function when used with hash tables that have an attached list, but for which not all buckets have yet had a list created for them.
  (problem report and suggested fix from Gerald Stegmiller).