Since the book explains its design and implementation in a very comprehensive way, not to mention the copyright issues, it is nothing but waste to repeat it here, so I finish this document by giving introduction to the library; how to use the facilities is deeply explained in files that define them.
The List Library reserves identifiers starting with list_
and LIST_
, and imports the Assertion Library (which requires the Exception Handling Library) and the Memory Management Library.
Similarly for other data structure libraries, use of the List Library follows this sequence: create, use and destroy. Except for functions to inspect lists, all other functions do one of them in various ways.
As oppsed to a doubly-linked list, a singly-linked list does not support random access, thus there are facilities to aid sequential access to a list: list_toarray(), list_map() and LIST_FOREACH(). These facilities help a user to convert a list to an array, call a user-defined function for each node in a list and traverse a list.
As always, if functions that should allocate storage to finish their job fail memory allocation, an exception mem_exceptfail
is raised rather than returning an error indicator like a null pointer.
The following paragraphs describe differences this library has when compared to other data structure libraries.
In general, pointers that library functions take and return point to descriptors for the data structure the library implements. Once an instance of the structure is created, the location of a desciptor for it remains unchanged until destroyed. This property does not hold for pointers that this library takes and returns. Those pointers in this library point to the head node of a list rather than a descriptor for it. Because it can be replaced as a result of operations like adding or removing a node, a user program is obliged to update the pointer variable it passed with a returned one. Functions that accept a list and return a modified list are list_push(), list_pop() and list_reverse().
A null pointer, which is considered invalid in other libraries, is a valid and only representation for an empty list. This means creating a null pointer of the list_t * type in effect creats an empty list. You can freely pass it to any functions in this library and they are guaranteed to work well with it. Because of this, functions to add data to a list can be considered to also create lists; invoking them with a null pointer gives you a list containing the given data. This includes list_list(), list_append(), list_push() and list_copy().
It is considered good to hide implementation details behind an abstract type with only interfaces exposed when designing and implementing a data structure. Exposing its implementation to users often brings nothing beneficial but unnecessary dependency on it. In this implementation, however, the author decided to expose its implementation since its merits trumph demerits; see the book for more discussion on this issue.
Once a list has been created, a new node can be pushed (list_push()) and inspected (list_pop()). list_pop() pops a node (that is, gets rid of a node with returning the data in it). If you need to handle a list as if it were an array, list_toarray() converts a list to a dynamically-allocated array. You can find the length of the resulting array by calling list_length() or specifying a value used as a terminator (a null pointer in most cases). A function, list_map() and a macro, LIST_FOREACH() also provide a way to access nodes in sequence. list_reverse() reverses a list, which is useful when it is necessary to repeatedly access a list in the reverse order.
list_free() destroys a list that is no longer necessary, but note that any storage that is allocated by a user program does not get freed with it; list_free() only returns back the storage allocated by the library.
As an example, the following code creates a list and stores input characters into each node until EOF
encountered. After read, it prints the characters twice by traversing the list and converting it to an array. Since the last input character resides in the head node, the list behaves like a stack, which is the reason list_push() and list_pop() are named so. The list is then reversed and again prints the stored characters by popping nodes; since it is reversed, the order in which character are printed out differs from the former two cases.
int c; int i; char *p; void *pv, **a; list_t *mylist, *iter; mylist = NULL; while ((c = getc(stdin)) != EOF) { MEM_NEW(p); *p = c; mylist = list_push(mylist, p); } LIST_FOREACH(iter, mylist) { putchar(*(char *)iter->data); } putchar('\n'); a = list_toarray(mylist, NULL); for (i = 0; a[i] != NULL; i++) putchar(*(char *)a[i]); putchar('\n'); MEM_FREE(a); mylist = list_reverse(mylist); while (list_length(mylist) > 0) { mylist = list_pop(mylist, &pv); putchar(*(char *)pv); MEM_FREE(pv); } putchar('\n'); list_free(&mylist);
where MEM_NEW() and MEM_FREE() come from the Memory Management Library.
In this example, the storage for each node is returned back when popping nodes from the list. If list_map() were used instead to free storage, a call like this:
list_map(mylist, mylistfree, NULL);
would be used, where a call-back function, mylistfree() is defined as follows:
void mylistfree(void **pdata, void *ignored) { MEM_FREE(*pdata); }
Any comments about the library are welcomed. If you have a proposal or question on the library just email me, and then I will reply as soon as possible.
Copyright (c) 1994,1995,1996,1997 by David R. Hanson.
Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
For the parts I added or modified, the following applies:
Copyright (C) 2009-2011 by Jun Woong.
This package is a singly-linked list implementation by Jun Woong. The implementation was written so as to conform with the Standard C published by ISO 9899:1990 and ISO 9899:1999.
Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.