Dec 082017
 
Doubley-linked list routines in C.
File LLIST102.ZIP from The Programmer’s Corner in
Category C Source Code
Doubley-linked list routines in C.
File Name File Size Zip Size Zip Type
LISTDEMO.C 4706 870 deflated
LISTDEMO.COM 10840 6283 deflated
LISTS.LIB 6656 2579 deflated
LLIST.C 19430 4020 deflated
LLIST.DOC 24571 5115 deflated
LLIST.H 2481 702 deflated
LLIST.OBJ 3204 1966 deflated
TREE.C 6918 1377 deflated
TREE.DOC 6954 2585 deflated
TREE.H 1505 534 deflated
TREE.OBJ 1088 645 deflated

Download File LLIST102.ZIP Here

Contents of the LLIST.DOC file


LLIST -- doubly linked list functions for the Lattice C compiler,
Version 1.0, written 11/86, Bob DuBose



General description: These routines were written to fill a gap
in my programming library; I had no way of dealing with
dynamically allocated memory that would be used in a list
structure. There are a few other linked list libraries on
bulletin boards, but those that I have run across have a
predefined data structure that the list will operate on
(usually char *'s). These programs deal with the data that the
list holds only as a pointer to an undefined data structure
named LST_DATA. The user's calling program must define this
structure or at least give a reference to it as an external
variable. By choosing to use only a pointer to an undefined
data structure, I have tried to make the functions as flexible
as possible. Most of the functions operate solely on the links
of the list or its header, and not the data, so that this poses
no problem. Those functions that create and delete links need
only the aforementioned pointer to function properly. This
pointer can even be a NULL, or a pointer to some other type of
data structure. In the latter case, if the pointer is cast to
be a (struct LST_DATA) pointer, the functions should not
complain. Thus, if used carefully, it is possible to design a
linked list that has data elements that are not the same
structure for each link. CAUTION MUST BE TAKEN TO CAST ALL DATA
POINTERS TO ONE OF TYPE (struct LST_DATA) IN THIS CASE, HOWEVER.
This means that a structure named "LST_DATA" will need to be
declared and defined even if its sole purpose is to serve as a
shell for pointers to be cast to it. I haven't tested the above,
but it should work; the worst case error in any case should be a
warning that "Pointers to not point to same object", although if
that occurs chances are good that there will be other side
effects inside your program as well.
The list functions try to be as conservative with both
allocated memory and elements of the list as possible. Thus,
when links are deleted, the memory for that particular link is
freed, BUT THAT FOR THE DATA IS NOT. Those functions that
delete individual links pass as their return value a pointer to
the data that that link contained. It is up to the calling
function to do something with that pointer, or to ignore it.
The exception to this is the function that deletes multiple
consecutive links. It cannot return the data pointer to the
calling function then call itself again. To make up for this,
one of the function's arguments is a pointer to a function that
has as its argument a pointer to a data structure (struct
LST_DATA *). This user-supplied function is called with the
address of the newly "orphaned" data structure, and it is up to
the user to decide what to do with it. If a list has been
completely deleted, (that is, by one way or another all of its
links have been freed) the memory occupied by the header is not
released; the user must do this manually or use the purging
function to release the header's memory.
These functions should be bug-free. Should you find any
errors, or have any questions, suggestions, or unending praise,
I can be reached at FIDO 100/10 [McDonnell-Douglas RCC],
FIDO 100/4 [St. Louis User's Group IBM-PC], or (finally) the
Lattice Bulletin Board. Enjoy!



Ver 1.0 page 1

LLIST -- doubly linked list functions for the Lattice C compiler,
Version 1.0, written 11/86, Bob DuBose



NOTE: All of the following functions assume that an #include
statement is present in the source code to include the file
LLIST.H


inst_list() -- create new linked list

USAGE:

HEAD_T *inst_list()

This function attempts to allocate memory for the header of a
new linked list, if available.

RETURNS:

Pointer to the header if memory is available, NULL otherwise.

CAUTIONS:

None.



inst_link() -- create a new link in the list

USAGE:

LINK_T *inst_link(data, prev, next)
struct LST_DATA *data;
LINK_T *prev, *next;

data -- pointer to data structure
prev -- pointer to previous link
next -- pointer to next link

The function creates a new link if memory is available, and
sets its pointers to the next and previous elements in the list.

RETURNS:

Pointer to new link if memory is available, NULL otherwise.

CAUTIONS:

The function does not alter the next or previous links in the
chain, nor does it update the chain size in the header.










Ver 1.0 page 2

LLIST -- doubly linked list functions for the Lattice C compiler,
Version 1.0, written 11/86, Bob DuBose



add_first() -- add a new link to the front of a list

USAGE:

BOOLEAN add_first(data, list)
struct LST_DATA *data;
HEAD_T *list;

data -- pointer to the new link's data
list -- pointer to the head of the list

The functions allocates memory for a new link, and appends it to
the beginning of the list. The header pointers are updated as
is the list size.

RETURNS:

TRUE if all is well, FALSE if no memory is available.

CAUTIONS:

Calls inst_link().



add_last() -- create and add a link to the end of a list

USAGE:

BOOLEAN add_last(data, list)
struct LST_DATA *data;
HEAD_T *list;

data -- pointer to link's data
list -- pointer to header of list

Like add_first, this function allocates memory for a new link,
but it appends it to the end of the growing chain. The header
pointers are updated, as is the list size.

RETURNS:

TRUE if successful, FALSE otherwise.

CAUTIONS:

Calls inst_link().










Ver 1.0 page 3

LLIST -- doubly linked list functions for the Lattice C compiler,
Version 1.0, written 11/86, Bob DuBose



add_after() -- add a link anywhere in the list

USAGE:

BOOLEAN add_after(data, list, link)
struct LST_DATA *data;
HEAD_T *list;
int link;

data -- pointer to link's data
list -- pointer to header of list
link -- link after which the new one is inserted

The function allocates memory and inserts the link at the
desired point in the chain. This function will do the jobs of
add_first() and add_last() by calling it with link = 0 for
adding to the front of the list, or link = list->L_LENGTH to add
to the end of the list. As with the previous functions, the
header and the list length are updated.

RETURNS:

TRUE if successful, FALSE if no memory, or the value specified
for link was not allowed (link < 0 or > list->L_LENGTH, the list
length).

CAUTIONS:

Calls inst_link().



del_first() -- delete first link

USAGE:

struct LST_DATA *del_first(list)
HEAD_T *list;

list -- pointer to header of list

This function unlinks the first link from the list, then
reconnects the chain bypassing that link. The header is
updated, along with the list size. The memory held by the link
is freed.

RETURNS:

A pointer to the data of the released link if successful,
otherwise the value L_ERROR cast as a pointer to a data
structure (struct LST_DATA *).

CAUTIONS:

Calling del_first() for a zero length list returns L_ERROR cast
as (struct LST_DATA *).



Ver 1.0 page 4

LLIST -- doubly linked list functions for the Lattice C compiler,
Version 1.0, written 11/86, Bob DuBose



del_last() -- delete last link in chain

USAGE:

struct LST_DATA *del_last(list)
HEAD_T *list;

list -- pointer to header of list.

This function does the same thing as del_first(), but the link
deleted is the last in the chain.

RETURNS:

same as for del_first().

CAUTIONS:

same as for del_first().



del_link() -- delete any internal link

USAGE:

struct LST_DATA *del_link(list, link)
HEAD_T *list;
int link;

list -- pointer to header of list
link -- link number to be deleted

This is the general form of del_first() and del_last(). It
deletes the specified link and frees its memory. The header and
the list count are updated.

RETURNS:

A pointer to the link's data if successful, L_ERROR cast as a
(struct LST_DATA *) if not.

CAUTIONS:

Calling del_link() with a value that is out of range for the
list will return an error.











Ver 1.0 page 5

LLIST -- doubly linked list functions for the Lattice C compiler,
Version 1.0, written 11/86, Bob DuBose



del_from_to() -- delete consecutive links

USAGE:

int del_from_to(list, from, to, process)
HEAD_T *list;
int from, to;
void (*process)(struct LST_DATA *);

list -- pointer to header of list
from -- first link to be deleted
to -- last link to be deleted
process -- pointer to function to handle the link's data

This function will delete a range of links one at a time,
freeing their memory in the process. The pointer to the link's
data is passed to (*process), a pointer to a user-supplied void
function that then does something to that link's data (for
example, frees it). Both the header pointers and the list size
are adjusted as the function calls del_link().

RETURNS:

The number of deleted links if successful, L_ERROR if not.

CAUTIONS:

Calls del_link(). The the user-supplied function to which
"process" is a pointer MUST exist, and it also must be declared
to be of type void. The number of links deleted is kept track
of by a counter variable, which is only incremented if the link
was successfully deleted; this counter does not depend on the
successful completion of (*process)'s action, as long as
(*process) DOES return successfully to del_from_to() which
called it. If a link cannot be deleted, its data will not be
processed, and the counter will not be incremented, but the
function will continue to delete the remaining links if
possible. In any case, an intact list structure (although
potentially of zero length if all links were deleted) will remain
when the function finishes. If no links could be deleted, the
list will remain unchanged; del_from_to() will delete as many
of the links as possible, reconnecting the list as it does.
Finally, if either "from" or "to" are out of bounds with respect
to the list length, or if "to" is less than "from", the function
returns L_ERROR to signal an error.












Ver 1.0 page 6

LLIST -- doubly linked list functions for the Lattice C compiler,
Version 1.0, written 11/86, Bob DuBose



rdel_from_to() -- delete consecutive links recursively

USAGE:

void rdel_from_to(list, from, to, process)
HEAD_T *list;
int from, to;
void (*process)(struct LST_DATA *);

list -- pointer to header of list
from -- first link to be deleted
to -- last link to be deleted
process -- pointer to function to handle the link's data

This function has exactly the same effect as del_from_to(). As
an intellectual exercise (read: the programmer was bored), I
decided to try to write the routine recursively. This is the
result. Except for the return value (void) it is the same as
del_from_to().

RETURNS:

Nothing.

CAUTIONS:

Same as for del_from_to(). The function is recursive, and stack
overflow errors may occur.





























Ver 1.0 page 7

LLIST -- doubly linked list functions for the Lattice C compiler,
Version 1.0, written 11/86, Bob DuBose



merge_after() -- merge to lists together

USAGE:

BOOLEAN merge_after(from_list, to_list, after_link)
HEAD_T *from_list, *to_list;
int after_link;

from_list -- pointer to header of source list
to_list -- pointer to header of destination list
after_link -- link in destination after which the source
fragment is to be added

The function will cut and splice two lists, taking the links
specified from the "from" list, and appending (or inserting)
them into the "to" list after the specified link. If after_link
equals zero, the new link fragments are appended to the
beginning of the "to" list, and its header is adjusted.
Likewise, if after_link == to_list->L_LENGTH, the new links are
appended to the end of the "to" list and its header is again
adjusted. The sizes of the to list is also adjusted.

RETURNS:

TRUE if successful, FALSE if after_link is out of bounds (less
than zero or greater than to_list->L_LENGTH.

CAUTIONS:

All of the links from the "from" list are moved. The function
completely merges the "from" list within the "to" list.

See also move_list(), split_list().
























Ver 1.0 page 8

LLIST -- doubly linked list functions for the Lattice C compiler,
Version 1.0, written 11/86, Bob DuBose



split_list() -- split a list into two smaller lists

USAGE:

HEAD_T *split_list(list, from, to)
HEAD_T *list;
int from, to;

list -- pointer to header of list to be split
from -- first link of new list
to -- last link of new list

This function "extracts" and creates a new list from the one
passed to it. The header of the old list is rearranged if
either "from" or "to" are the first or last links of the list,
and in any case the size of the old list is adjusted. The
function can be used to move the data of one list completely
into a new list, if "from" and "to" are the first and last links
of the old list respectively. The memory for the new list's
header is allocated dynamically, and its pointers and size are

also adjusted.

RETURNS:

A pointer to the header of the new list if successful, otherwise
L_ERROR cast as a (HEAD_T *) if either "from" or "to" are out of
bounds, or if no memory can be allocated for the new list.

CAUTIONS:

Calls inst_list(). The function allocates memory dynamically,
creating the new list de novo. All that is changed are pointer
values for the links in the list, and possibly the pointers in
the header of the old list. If the entire contents of the old
list are moved, the memory occupied by its header is NOT
deallocated, and the header will have two NULL pointers for the
first and last elements in the old list (plus its length will be
zero).



















Ver 1.0 page 9

LLIST -- doubly linked list functions for the Lattice C compiler,
Version 1.0, written 11/86, Bob DuBose



move_list() -- move one section of a list to another

USAGE:

BOOLEAN move_list(from_list, to_list, from_from, from_to, to)
HEAD_T *from_list, *to_list;
int from_from, from_to, to;

from_list -- pointer to header of source list
to_list -- pointer to header of target list
from_from -- first link in source list to be moved
from_to -- last link in source list to be moved
to -- link in target list to which the source list
is to be appended

This function uses split_list() and merge_after() to transfer
the links of one section of a linked list to another section of
a different linked list. It assumes that both lists do exist.

RETURNS:

TRUE if successful, FALSE if the transfer cannot be made.

CAUTIONS:

Calls split_list() and merge_after(). The function first calls
split list to create a temporary list that holds the contents of
the "from" list to be moved, then merge_after to merge this list
into the "to" list. Move_list() then releases the memory held
by temp. If either of these functions fail (see descriptions of
each), the function returns FALSE, and does not attempt to find
out which of the offending functions failed.

























Ver 1.0 page 10

LLIST -- doubly linked list functions for the Lattice C compiler,
Version 1.0, written 11/86, Bob DuBose



free_links() -- delete a list's contents

USAGE:

void free_links(link)
LINK_T *link;

link -- link to be freed

The function frees all of the links in a list by recursively
climbing down the list until the last link is reached. It's
memory is then released, and the function returns (to free the
link above, etc.). The data for each link is also freed. No
changes are made to the header.

RETURNS:

None.

CAUTIONS:

Calls free_links(). The function is recursive, and stack
overflow errors may occur. The function also releases the data
associated with each link, if possible. The header is NOT
adjusted, so strange results be generated if that header is
then treated as if it still had a list hooked up to it!



purge_list() -- free up an entire list

USAGE:

void purge_list(list)
HEAD_T *list;

list -- pointer to header of list to be purged

The function releases the memory occupied by both the links of a
list and their data. The header for the list itself is also
deallocated.

RETURNS:

None.

CAUTIONS:

Calls free_links(). free_links() is recursive, so stack
overflows may occur. This is the proper function to use to
destroy a list and its contents.






Ver 1.0 page 11



 December 8, 2017  Add comments

Leave a Reply