The libdeque is a library for double-ended queues and stacks.

The term "deque" (pronounced like "deck") 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 instances are typically created with a call to the "deque_new" function:

	struct deque *q = deque_new();

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

	unsigned char bytes[1000];
	struct deque *q = deque_new_no_allocator(bytes, 1000);

The space for the deque structure is allocated from the byte array
which is passed in. As such it's good to provide at least 88 extra
bytes.

Or even, if needed, a custom allocator can be provided:

	struct eembed_allocator *ea = my_custom_allocator();
	struct deque *q = deque_new_custom_allocator(ea);


Items can be added to either end of the deque using the "push" and
"unshift" member functions. Items can be removed 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(q, "foo");
	deque_push(q, "bar");
	deque_push(q, "baz");

	/* remove item from front of queue (or bottom of stack): */
	char *foo = deque_shift(q);

	/* remove items from end of queue (or top of stack): */
	char *baz = deque_pop(q);

	/* prepend items to queue (or bottom of stack): */
	deque_unshift(q, "butt-in");

Additional member functions are provided which do not change the state
of the deque, but give some information about the correct 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(q);

	/* pointer to data at the end of the queue (or top of the stack) */
	void *foo = deque_peek_top(q, 0);

	/* pointer to data 2 in from the end of the queue */
	void *bar = deque_peek_top(q, 2);

	/* pointer to data at the front of the queue (or bottom of the stack) */
	void *baz = deque_peek_bottom(q, 0);

	/* pointer to data 3 behind the front of the queue */
	void *val = deque_peek_bottom(q, 3);

Additionally, the "deque_for_each" function takes a deque_iterator_func
function pointer which is defined as:

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

And can be called like:

	int x = deque_for_each(q, my_func, my_context);

The "deque_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 allocator the deque_free
function will use the provided allocator:

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

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 &&
 sensible-browser ./coverage_html/index.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.