ericherman / libdeque Goto Github PK

The libdeque is a pure ANSI C89 compatible object oriented library for
double-ended queues and stacks.  The term "deque" can be thought of as
an abbreviation of "Double-Ended QUEue." Like a deck of cards, one may
add to (or deal from) the top or bottom.

Inspired by: Donald Knuth.
The Art of Computer Programming, Volume 1: Fundamental Algorithms
Section 2.2.1: Stacks, Queues, and Deques, pp. 238-243.
( third edition, Addison-Wesley, 1997. ISBN 0-201-89683-4 )


Usage
-----
Include the header file:

	#include <deque.h>

New instaces are typically created with a call to the "deque_new" function:

        deque_s *deque = deque_new();

Instead, if needed, a custom allocator can be provided:

	deque_s *deque;
	deque = deque_new_custom_allocator(myalloc, myfree, mycontext);

Or a size-bounded deque can be constructed from a byte array:

	unsigned char bytes[1024];
	deque_s *deque;
	deque = deque_new_no_allocator(bytes, 1024);

(The space for the deque struct and its opaque internal data are
allocated from the byte array which is passed in. As such it's good to
provide an extra 256 bytes to accomodate these.)

Items can be added to either end of the deque using the "push" and
"unshift" member functions. Items can be remonved from either end of the
deque using the "pop" and "shift" member functions. Each of these
functions has two parameters, a "this" pointer, and a "void *" for the
data to be added:

	/* add items to the end of queue (or top of stack): */
	deque->push(deque, "foo");
	deque->push(deque, "bar");
	deque->push(deque, "baz");

	/* remove item from front of queue (or bottom of stack): */
	char *foo = deque->shift(deque);

	/* remove items from end of queue (or top of stack): */
	char *baz = deque->pop(deque);

	/* prepend items to queue (or bottom of stack): */
	deque->unshift(deque, "butt-in");

Additional member functions are provided which do not change the state
of the deque, but give some information about the currect state. These
functions are "size", "peek_top", and "peek_bottom", which can be used
for external iteration:

	/* the number of items in the of the deque */
	int size = deque->size(deque);

	/* pointer to data at the end of the queue (or top of the stack) */
	void *foo = deque->peek_top(deque, 0);

	/* pointer to data 2 in from the end of the queue */
	void *bar = deque->peek_top(deque, 2);

	/* pointer to data at the front of the queue (or bottom of the stack) */
	void *baz = deque->peek_bottom(deque, 0);

	/* pointer to data 3 behind the front of the queue */
	void *val = deque->peek_bottom(deque, 3);

Additionally, there is a "for_each" method which takes a deque_iterator_func
function pointer which is defined as:

typedef int (*deque_iterator_func)(deque_s *d, void *each, void *context);

And can be called like:

	int x = deque->for_each(deque, my_func, my_context);

The "for_each" function handles the iteration internally. It can be halted
early if the "my_func" returns a non-zero value.

Instances can be freed using the "deque_free" function. Of course, if
the instance was created with a custom allocation and free functions,
the deque_free function will use the function pointer which was
provided:

	/* free the deque memory and all memory deque allocated */
	deque_free(deque);

Compile with the "-ldeque" lib:

        gcc -o foo foo.c -ldeque


Dependencies
------------
No external runtime dependencies.

Building requires "context-alloc" which is included in the submodules
directory, as well as the GNU autotools (automake, libtool, autconf).
See also: https://github.com/ericherman/context-alloc

( The tests depend upon libecheck, which is included in the submodules
directory. See also: https://github.com/ericherman/libecheck )


Cloning
-------
git clone -o upstream https://github.com/ericherman/libdeque.git &&
 cd libdeque &&
 git submodule update --init --recursive &&
 autoreconf -iv &&
 ./configure &&
 make -j check &&
 git clean -dxf &&
 git submodule foreach --recursive git clean -dxf


Test Coverage
-------------
autoreconf -iv &&
 ./configure --enable-debug &&
 make &&
 make check &&
 lcov --capture --directory src --output-file coverage.info &&
 genhtml coverage.info --output-directory coverage_html &&
 ${BROWSER} ./coverage_html/src/deque.c.gcov.html



Building on linux from a release tar
--------
tar xfz /path/to/libdeque-$VERSION.tar.gz
cd libdeque-*
./configure && make && make check
sudo make install
sudo ldconfig


Packaging
---------
Typically git submodules are the way to go, but you can use autotools
if you wish:

autoreconf -iv &&
 ./configure &&
 make &&
 make distcheck &&
 echo "Success."


License
-------
GNU Lesser General Public License (LGPL), version 3 or later.
See COPYING and COPYING.LESSER for details.