Dec 192017
 
C source code for generic list handling routines: double-linked lists, queues, stacks, sorted lists, etc. FREEWARE.

Full Description of File


C source code for generic list handling
routines: double-linked lists, queues,
stacks, sorted lists, etc. FREEWARE.


File GENLIST.ZIP from The Programmer’s Corner in
Category C Source Code
C source code for generic list handling routines: double-linked lists, queues, stacks, sorted lists, etc. FREEWARE.
File Name File Size Zip Size Zip Type
FILE_ID.DIZ 119 102 deflated
GENLIST.C 15249 1674 deflated
GENLIST.DOC 24400 4871 deflated
GENLIST.H 4214 824 deflated

Download File GENLIST.ZIP Here

Contents of the GENLIST.DOC file


/*
Newsgroups: alt.sources
From: [email protected] (Keith Pomakis)
Subject: Generic List Library for C -- documentation
Organization: University of Waterloo
Date: Thu, 16 Jun 1994 15:13:50 GMT
*/

*************************************************************************
*************************************************************************
** **
** Generic List Library **
** **
** by Keith Pomakis **
** [email protected] **
** **
** Spring, 1994 **
** **
*************************************************************************
*************************************************************************

**** Documentation ****


****************************************************************************
PURPOSE AND HISTORY
****************************************************************************

The basic data structures of lists, stacks and queues are fundamental to
programming at almost every level. However, because of the nature of the C
programming language, it is difficult to program a set of generic list
functions without sacrificing simplicity. Therefore, C programmers often
find themselves programming specialized list functions over and over again.
This is not only a large waste of effort, but can also be the source of many
errors since each individual implementation is often tested only
haphazardly.

After countless assignments and projects (both academic and personal) in
which I found myself constantly rewriting the same list manipulation
functions in slightly different contexts, I figured it was about time to
take the effort and program an efficient, flexible, and easy-to-use library
of generic list functions. And that is exactly what I did!

It is my hope that, in distributing this library, others will be able to use
what I've put together to increase their own programming productivity.


****************************************************************************
DISCLAIMER
****************************************************************************

I am releasing this library to the public domain. Therefore, people can use
it, copy it, distribute it, modify it, and do whatever they want with it.

Although this library has been well thought out, tested, and used in real
applications, it is not guaranteed to be bug-free. Therefore, I am not
responsible for anything that happens, either directly or indirectly, due to
the usage of this library.

If you modify or add to this library in any way, I'd appreciate it if you
dropped me a line (or Internet packet, whatever) telling me what you did.
I'm always interested in potential improvements to my work!

Also, if you find any bugs (gasp!) or have any questions or comments about
the library, you can contact me as well. My e-mail address is
"[email protected]". I'd be interested in hearing what you
think!

Oh, one other thing... I've put a lot of work into this library, so I'd
appreciate it if you kept my name attached to it when distributing or
modifying it.


****************************************************************************
REQUIREMENTS
****************************************************************************

The only requirements for the usage of this library are an ANSI C compiler,
a machine to run it on, and a project that is in need of generic list
functions! This library has been tested with gcc on a Sun 4 and with Think
C on a Macintosh. The code is ANSI-compliant, and should present no problem
with any other setup.


****************************************************************************
PHILOSOPHY
****************************************************************************

My goal when designing this library was to make it as flexible and complete
as possible, while still keeping it efficient and easy to use. I have seen
and have tried to use other generic list libraries (and yes, I realize they
are numerous), but often they have failed me on one or more of the above
points. I also realize that such a library would be a trivial piece of work
in C++. However, as much of a proponent of the object-oriented paradigm as
I am, I tend to dislike C++ because of the hideous syntactic nightmares I
get when tackling the language. Therefore, I have decided to write the
library in C.

A set of basic generic doubly-linked list functions were designed and
programmed first (along with a suitable efficient data structure), and then
some higher-level functions were added to increase ease of use. The
functionality of stacks, queues and sorted lists were then added. In
actuality, these functions (with the exception of one of the sorted-list
functions) are nothing more than aliases for the appropriate generic list
operations. This aliasing is behind the scenes, however, and the user of
this library may treat the operation of lists, stacks and queues in this
library as completely separate functionality.

In order to make the library completely generic, it was designed to
manipulate pointers of type void *. Therefore, it is assumed that the
programmer is statically or dynamically creating the objects of interest,
and using the generic list functions to manipulate them. It is up to the
programmer to handle the allocation and deallocation of the memory for the
objects themselves.

A pointer to the same object may be stored in a list multiple times. The
only restriction imposed is that a NULL pointer may not be stored.


****************************************************************************
USAGE
****************************************************************************

The use of this library is simple and straight-forward. In every source
file that requires the use of generic list functions, the line:

#include "generic_list.h"

must be included at the top of the file. For those who hand-craft their own
makefiles, "generic_list.h" should become a prerequisite for each of these
files, as well as for "generic_list.c" itself.

The library defines three data types:

Generic_list
Generic_stack
Generic_queue

The usage of these functions is best illustrated with an example:

foo() {
Generic_stack stack;
My_object *obj;

initialize_stack(&stack);

obj = new_object();
push(stack, obj);
...
obj = pop(stack);
free(obj);
...
destroy_stack(&stack);
}

Each list must be initialized before use and should be destroyed after it is
no longer needed. The programmer must handle the allocation and

deallocation of the memory for the objects being stored. Explicit memory
management for the lists is not necessary.


****************************************************************************
LIST OF FUNCTIONS
****************************************************************************

The following are the headers of the functions provided in the generic list
library. They are described in more detail later.

Generic Lists
-------------

void initialize_list(Generic_list *list);
void destroy_list(Generic_list *list);
void add_to_beginning(Generic_list list, void *pointer);
void add_to_end(Generic_list list, void *pointer);
void add_to_list(Generic_list list, void *pointer);
void *remove_from_beginning(Generic_list list);
void *remove_from_end(Generic_list list);
void *remove_from_list(Generic_list list, void *pointer);
void remove_all(Generic_list list);
void *peek_at_beginning(Generic_list list);
void *peek_at_end(Generic_list list);

void *first_in_list(Generic_list list);

void *next_in_list(Generic_list list);
void *current_in_list(Generic_list list);
void *remove_current(Generic_list list);
void *previous_in_list(Generic_list list);
void *last_in_list(Generic_list list);
void reset_to_beginning(Generic_list list);
void reset_to_end(Generic_list list);

int num_of_objects(Generic_list list);
int is_empty(Generic_list list);
int is_in_list(Generic_list list, void *pointer);
Generic_list copy_list(Generic_list list);

void perform_on_list
(Generic_list list, void (*fn)(void *pointer, void *args), void *args);
void *first_that
(Generic_list list, int (*fn)(void *pointer, void *args), void *args);
void *next_that
(Generic_list list, int (*fn)(void *pointer, void *args), void *args);
void *previous_that
(Generic_list list, int (*fn)(void *pointer, void *args), void *args);
void *last_that
(Generic_list list, int (*fn)(void *pointer, void *args), void *args);
Generic_list all_such_that
(Generic_list list, int (*fn)(void *pointer, void *args), void *args);
void remove_all_such_that
(Generic_list list, int (*fn)(void *pointer, void *args), void *args);


Generic Sorted Lists
--------------------

void initialize_sorted_list(Generic_list *list, int (*lt)(void *a, void *b));

...and all Generic_list functions except:

void add_to_beginning(Generic_list list, void *pointer);
void add_to_end(Generic_list list, void *pointer);
void *remove_from_beginning(Generic_list list);
void *remove_from_end(Generic_list list);


Generic Stacks
--------------

void initialize_stack(Generic_stack *stack);
void destroy_stack(Generic_stack *stack);
void push(Generic_stack stack, void *pointer);
void *pop(Generic_stack stack);
void pop_all(Generic_stack stack);
void *peek_at_top(Generic_stack stack);
Generic_stack copy_stack(Generic_stack stack);
int is_empty(Generic_stack stack);


Generic Queues
--------------

void initialize_queue(Generic_queue *queue);
void destroy_queue(Generic_queue *queue);
void enqueue(Generic_queue queue, void *pointer);
void *dequeue(Generic_queue queue);
void dequeue_all(Generic_queue queue);
void *peek_at_head(Generic_queue queue);
void *peek_at_tail(Generic_queue queue);
Generic_queue copy_queue(Generic_queue queue);
int is_empty(Generic_queue queue);


****************************************************************************
DETAILED DESCRIPTION OF FUNCTIONS
****************************************************************************

Generic Lists
-------------

void initialize_list(Generic_list *list);

Every list must be initialized before it is used. The only time it is
valid to re-initialize a list is after it has been destroyed.

void destroy_list(Generic_list *list);

When a list is no longer needed, it should be destroyed. This process
will automatically remove all remaining objects from the list. However,
the memory for these objects will not be reclaimed, so if the objects
have no other references, care should be taken to purge the list and
free all objects before destroying the list.

It is an error to destroy a list more than once (unless it has been
re-initialized in the meantime).

void add_to_beginning(Generic_list list, void *pointer);

This function will add the specified object to the beginning of the
list. The pointer must not be NULL.

void add_to_end(Generic_list list, void *pointer);

This function will add the specified object to the end of the
list. The pointer must not be NULL.

void add_to_list(Generic_list list, void *pointer);

This function will add the specified object to the list. The pointer
must not be NULL.

void *remove_from_beginning(Generic_list list);

This function will remove the first object from the beginning of the
list and return it. If the list is empty, NULL is returned.

void *remove_from_end(Generic_list list);

This function will remove the last object from the end of the list and
return it. If the list is empty, NULL is returned.

void *remove_from_list(Generic_list list, void *pointer);

This function will remove the specified object from the list and return
it. If the specified object does not exist in the list, NULL is
returned. If the specified object exists in the list more than once,
only the last reference to it is removed.

void remove_all(Generic_list list);

This function will remove all objects from the list. Note that the
memory for these objects will not be reclaimed, so if the objects have
no other references, it is best to avoid this function and remove the
objects one by one, freeing them when necessary.

void *peek_at_beginning(Generic_list list);

This function will return the first object in the list. If the list is
empty, NULL is returned.

void *peek_at_end(Generic_list list);

This function will return the last object in the list. If the list is
empty, NULL is returned.

void *first_in_list(Generic_list list);

This function will return the first object in the list and mark it as
the current object. If the list is empty, NULL is returned.

void *next_in_list(Generic_list list);

This function will return the next object in the list and mark it as
the current object. If the end of the list is reached, or if the list
is empty, NULL is returned.

void *current_in_list(Generic_list list);

This function will return the object in the list that is considered
the current object (as defined by the surrounding functions). If the
current object has just been removed, if current points to the
beginning or end of the list, or if the list is empty, NULL is
returned.

void *remove_current(Generic_list list);

This function will remove the current object from the list and return
it. If the current object has already been removed, if current points
to the beginning or end of the list, or if the list is empty, NULL is
returned.

void *previous_in_list(Generic_list list);

This function will return the previous object in the list and mark it
as the current object. If the beginning of the list is reached, or if
the list is empty, NULL is returned.

void *last_in_list(Generic_list list);

This function will return the last object in the list and mark it as
the current object. If the list is empty, NULL is returned.

void reset_to_beginning(Generic_list list);

This function will reset the list to the beginning. Therefore, current
points to the beginning of the list, and the next object in the list is
the first object.

void reset_to_end(Generic_list list);

This function will reset the list to the end. Therefore, current
points to the end of the list, and the previous object in the list is
the last object.

int num_of_objects(Generic_list list);

This function will return the number of objects in the list.

int is_empty(Generic_list list);

This function will return TRUE (1) if the list is empty, and FALSE (0)
otherwise.

int is_in_list(Generic_list list, void *pointer);

This function will return TRUE (1) if the specified object is a member
of the list, and FALSE (0) otherwise.

Generic_list copy_list(Generic_list list);

This function will return a copy of the list. The objects themselves
are not copied; only new references to them are made. The new list
loses its concept of the current object.

void perform_on_list
(Generic_list list, void (*fn)(void *pointer, void *args), void *args);

This function will perform the specified function on each object in the
list. Any optional arguments required can be passed through args.

void *first_that
(Generic_list list, int (*fn)(void *pointer, void *args), void *args);

This function will find and return the first object in the list which
causes the specified function to return a TRUE (non-zero) value. Any
optional arguments required can be passed through args. The found
object is then marked as the current object. If no objects in the list
meet the criteria of the specified function, NULL is returned.

void *next_that
(Generic_list list, int (*fn)(void *pointer, void *args), void *args);

This function will find and return the next object in the list which
causes the specified function to return a TRUE (non-zero) value. Any
optional arguments required can be passed through args. The found
object is then marked as the current object. If there are no objects
left in the list that meet the criteria of the specified function,
NULL is returned.

void *previous_that
(Generic_list list, int (*fn)(void *pointer, void *args), void *args);

This function will find and return the previous object in the list
which causes the specified function to return a TRUE (non-zero) value.
Any optional arguments required can be passed through args. The found
object is then marked as the current object. If there are no objects
left in the list that meet the criteria of the specified function,
NULL is returned.

void *last_that
(Generic_list list, int (*fn)(void *pointer, void *args), void *args);

This function will find and return the last object in the list which
causes the specified function to return a TRUE (non-zero) value. Any
optional arguments required can be passed through args. The found
object is then marked as the current object. If no objects in the
list meet the criteria of the specified function, NULL is returned.

Generic_list all_such_that
(Generic_list list, int (*fn)(void *pointer, void *args), void *args);

This function will return a new list containing all of the objects in
the specified list which cause the specified function to return a TRUE
(non-zero) value. Any optional arguments required can be passed
through args. The objects themselves are not copied; only new
references to them are made.

void remove_all_such_that
(Generic_list list, int (*fn)(void *pointer, void *args), void *args);

This function will remove all objects in the list which cause the
specified function to return a TRUE (non-zero) value. Any optional
arguments required can be passed through args. Note that the memory
for these objects will not be reclaimed, so if the objects have
no other references, it is best to avoid this function and remove the
objects one by one, freeing them when necessary.


Generic Sorted Lists
--------------------

void initialize_sorted_list(Generic_list *list, int (*lt)(void *a, void *b));

This function initializes a sorted list. A less-than function must be
specified which accepts two pointers, a and b, and returns TRUE
(non-zero) if a is less than b, FALSE otherwise.

Once a list is initialized in this way, all of the generic list
functions described above can be used, except for:

void add_to_beginning(Generic_list list, void *pointer);
void add_to_end(Generic_list list, void *pointer);
void *remove_from_beginning(Generic_list list);
void *remove_from_end(Generic_list list);

and the list will remain sorted by the criteria specified by the
less-than function. The only time it is valid to re-initialize a list
is after it has been destroyed.


Generic Stacks
--------------

void initialize_stack(Generic_stack *stack);

Every stack must be initialized before it is used. The only time it is
valid to re-initialize a stack is after it has been destroyed.

void destroy_stack(Generic_stack *stack);

When a stack is no longer needed, it should be destroyed. This process
will automatically remove all remaining objects from the stack.
However, the memory for these objects will not be reclaimed, so if the
objects have no other references, care should be taken to purge the
stack and free all objects before destroying the stack.

It is an error to destroy a stack more than once (unless it has been
re-initialized in the meantime).

void push(Generic_stack stack, void *pointer);

This function will push the specified object onto the stack. The
pointer must not be NULL.

void *pop(Generic_stack stack);

This function will pop the first object from the top of the stack and
return it. If the stack is empty, NULL is returned.

void pop_all(Generic_stack stack);

This function will pop all objects from the stack. Note that the
memory for these objects will not be reclaimed, so if the objects have
no other references, it is best to avoid this function and pop the
objects one by one, freeing them when necessary.

void *peek_at_top(Generic_stack stack);

This function will return the object on the top of the stack. If the
stack is empty, NULL is returned.

Generic_stack copy_stack(Generic_stack stack);

This function will return a copy of the stack. The objects themselves
are not copied; only new references to them are made.

int is_empty(Generic_stack stack);

This function will return TRUE (1) if the stack is empty, and FALSE (0)
otherwise.


Generic Queues
--------------

void initialize_queue(Generic_queue *queue);

Every queue must be initialized before it is used. The only time it is
valid to re-initialize a queue is after it has been destroyed.

void destroy_queue(Generic_queue *queue);

When a queue is no longer needed, it should be destroyed. This process
will automatically remove all remaining objects from the queue.
However, the memory for these objects will not be reclaimed, so if the
objects have no other references, care should be taken to purge the
queue and free all objects before destroying the queue.

It is an error to destroy a queue more than once (unless it has been
re-initialized in the meantime).

void enqueue(Generic_queue queue, void *pointer);

This function will add the specified object to the tail of the queue.
The pointer must not be NULL.

void *dequeue(Generic_queue queue);

This function will remove the first object from the head of the queue
and return it. If the queue is empty, NULL is returned.

void dequeue_all(Generic_queue queue);

This function will remove all objects from the queue. Note that the
memory for these objects will not be reclaimed, so if the objects have
no other references, it is best to avoid this function and dequeue the
objects one by one, freeing them when necessary.

void *peek_at_head(Generic_queue queue);

This function will return the object at the head of the queue. If the
queue is empty, NULL is returned.

void *peek_at_tail(Generic_queue queue);

This function will return the object at the tail of the queue. If the
queue is empty, NULL is returned.

Generic_queue copy_queue(Generic_queue queue);

This function will return a copy of the queue. The objects themselves
are not copied; only new references to them are made.

int is_empty(Generic_queue queue);

This function will return TRUE (1) if the queue is empty, and FALSE (0)
otherwise.


****************************************************************************
HINTS
****************************************************************************

Technically, any of the above functions can be used with any of the three
data types. For example, one can use perform_on_list() to perform a
specified function on every object in a queue, or is_in_list() to determine
whether or not a particular object is a member of a stack. One can even
pop from a queue and dequeue from a stack. However, such usage is not
recommended, as it is contrary to the logical usage of such data
structures.




 December 19, 2017  Add comments

Leave a Reply