+ initial CVS importsvn2git-root

svn path=/trunk/externals/moocow/; revision=4534

9 files changed, 1443 insertions, 0 deletions

diff --git a/deque/src/Makefile.am b/deque/src/Makefile.am
new file mode 100644
index 0000000..28579d0
--- /dev/null
+++ b/deque/src/Makefile.am
@@ -0,0 +1,137 @@
+# File: ./src/Makefile.am
+# Package: deque
+# Description:
+#   + src-level automake file
+#
+# Process this file with Automake to create Makefile.in.
+#-----------------------------------------------------------------------
+
+#-----------------------------------------------------------------------
+# Options & Subdirectories
+#-----------------------------------------------------------------------
+
+## --- recursion subdirectories
+#SUBDIRS = 
+
+## --- pseudo-deps for '.SUFFIXES'
+SUFFIXES = .@PDEXT@
+
+#-----------------------------------------------------------------------
+# Flags and variables
+#-----------------------------------------------------------------------
+PDEXT    = @PDEXT@
+EXEEXT   = .@PDEXT@
+
+#-----------------------------------------------------------------------
+# pd externals (hacked _PROGRAMS target)
+#-----------------------------------------------------------------------
+
+## --- externals
+pdexterns_PROGRAMS = @PD_OBJECT_EXTERNALS@
+
+## --- possible externals
+EXTRA_PROGRAMS = \
+	deque
+
+## --- patches
+pdexterns_DATA =
+
+## --- documentation
+pddoc_DATA = deque-help.pd
+
+
+#-----------------------------------------------------------------------
+# sources
+#-----------------------------------------------------------------------
+
+deque_SOURCES = \
+	squeue.c squeue.h \
+	dsqueue.c dsqueue.h \
+	deque.c
+
+#-----------------------------------------------------------------------
+# external compilation : flags
+#-----------------------------------------------------------------------
+DEFS    = @DEFS@
+AFLAGS  = @AFLAGS@
+DFLAGS  = @DFLAGS@
+IFLAGS  = @IFLAGS@
+LFLAGS  = @LFLAGS@
+OFLAGS  = @OFLAGS@
+WFLAGS  = -Wall -Winline
+
+#GLIB_IFLAGS = @GLIB_IFLAGS@
+#GLIB_LFLAGS = @GLIB_LFLAGS@
+
+AM_CPPFLAGS = $(IFLAGS) $(GLIB_IFLAGS) $(DFLAGS)
+AM_CFLAGS   = $(OFLAGS) $(WFLAGS) $(AFLAGS)
+
+deque_LDFLAGS = $(LFLAGS)
+deque_LDADD   = $(GLIB_LFLAGS)
+
+#-----------------------------------------------------------------------
+# Variables: cleanup
+#-----------------------------------------------------------------------
+## --- mostlyclean: built by 'make' & commonly rebuilt
+#MOSTLYCLEANFILES =
+
+## --- clean: built by 'make'
+CLEANFILES = *$(EXEEXT)
+
+## --- distclean: built by 'configure'
+DISTCLEANFILES = \
+	config.log	\
+	config.cache	\
+	config.status
+
+## -- maintainerclean: built by maintainer / by hand
+MAINTAINERCLEANFILES = *~ \
+	$(PODS:.pod=.txt) \
+	Makefile Makefile.in \
+	aclocal.m4 \
+	configure \
+	install-sh \
+	stamp-h.in \
+	config.h.in
+
+maintainer-clean-local:
+	rm -rf autom4te.cache
+
+#CVSCLEAN_SUBDIRS = $(SUBDIRS)
+
+#CVSCLEANFILES = Makefile.in Makefile
+
+
+#-----------------------------------------------------------------------
+# Variables: distribution
+#-----------------------------------------------------------------------
+
+## --- extra distribution files
+EXTRA_DIST = \
+	$(pddoc_DATA) \
+	$(pdexterns_DATA)
+
+## --- recursion subdirectories for 'make dist'
+DIST_SUBDIRS = $(SUBDIRS)
+
+## --- dist-hook: when another 'Makefile.am' is overkill
+#DISTHOOK_DIRS = foo
+#DISTHOOK_FILES = foo/bar.txt foo/baz.txt
+#dist-hook:
+#	for d in $(DISTHOOK_DIRS); do\
+#	  mkdir -p $(distdir)/$$d ;\
+#	done
+#	for f in $(DISTHOOK_FILES); do\
+#	  cp -p $(srcdir)/$$f $(distdir)/$$f ;\
+#	done
+
+#dist-bz2: dist-bzip2 ;
+
+
+#-----------------------------------------------------------------------
+# Rules: cleanup
+#-----------------------------------------------------------------------
+.PHONY: cvsclean cvsclean-hook
+
+cvsclean: maintainer-clean ;
+
diff --git a/deque/src/deque-help.pd b/deque/src/deque-help.pd
new file mode 100644
index 0000000..e9b4b85
--- /dev/null
+++ b/deque/src/deque-help.pd
@@ -0,0 +1,45 @@
+#N canvas 62 30 512 484 10;
+#X text 89 3 deque : double-ended message queue;
+#X text 47 27 INLETS:;
+#X text 58 40 1 - control messages;
+#X text 58 53 2 - unshift (list);
+#X text 57 67 3 - push (list);
+#X text 253 28 OUTLETS:;
+#X text 267 41 1 - dequeued messages;
+#X text 198 455 Bryan Jurish <moocow@ling.uni-potsdam.de>;
+#X obj 51 391 deque;
+#X msg 51 103 push foo bar;
+#X msg 57 125 unshift baz bonk;
+#X msg 77 180 pop;
+#X text 241 177 "pop" : remove & outlet from end;
+#X text 226 200 "shift" : remove & outlet from front;
+#X msg 80 201 shift;
+#X text 208 102 "push MSG" : add MSG to end;
+#X text 187 125 "unshift MSG" : add MSG to front;
+#X msg 86 223 bang;
+#X text 232 222 "bang" : alias for "shift";
+#X msg 92 261 clear;
+#X msg 93 284 flush;
+#X text 225 256 "clear" : clear all elements;
+#X msg 97 328 list bink bop;
+#X msg 106 351 list fink fop;
+#X text 216 328 LIST (inlet-2) : like "unshift LIST";
+#X text 216 352 LIST (inlet-3) : like "push LIST";
+#X text 225 278 "flush" : output front-to-back & clear;
+#X msg 70 157 size;
+#X text 233 156 "size" : get number of stored messages;
+#X obj 81 414 print deque-status;
+#X obj 51 438 print deque-content;
+#X text 266 55 2 - status messages;
+#X connect 8 0 30 0;
+#X connect 8 1 29 0;
+#X connect 9 0 8 0;
+#X connect 10 0 8 0;
+#X connect 11 0 8 0;
+#X connect 14 0 8 0;
+#X connect 17 0 8 0;
+#X connect 19 0 8 0;
+#X connect 20 0 8 0;
+#X connect 22 0 8 1;
+#X connect 23 0 8 2;
+#X connect 27 0 8 0;
diff --git a/deque/src/deque-test.pd b/deque/src/deque-test.pd
new file mode 100644
index 0000000..e7a0cf5
--- /dev/null
+++ b/deque/src/deque-test.pd
@@ -0,0 +1,66 @@
+#N canvas 180 20 689 473 10;
+#X obj 187 129 deque;
+#X obj 128 163 print dq-elt;
+#X obj 221 164 print dq-eoq;
+#X msg 93 28 shift;
+#X msg 95 49 pop;
+#X msg 14 28 clear;
+#X msg 15 52 flush;
+#X msg 28 207 ------;
+#X obj 27 232 print -------;
+#X msg 172 27 push foo bar;
+#X msg 174 50 push baz bonk;
+#X msg 275 29 push list foo bar;
+#X msg 280 50 push list baz bonk;
+#X msg 265 88 list a b;
+#X msg 330 89 list c d;
+#X obj 446 256 deque;
+#X floatatom 449 160 5 0 0 0 - - -;
+#X msg 383 213 shift;
+#X floatatom 441 288 5 0 0 0 - - -;
+#X obj 441 306 bng 15 250 50 0 empty empty empty 0 -6 0 8 -262144 -1
+-1;
+#X obj 490 288 bng 15 250 50 0 empty empty empty 0 -6 0 8 -262144 -1
+-1;
+#X msg 383 194 clear;
+#X msg 448 180 push \$1;
+#X floatatom 519 161 5 0 0 0 - - -;
+#X msg 518 181 push float \$1;
+#X floatatom 22 102 5 0 0 0 - - -;
+#X msg 20 119 push \$1;
+#X floatatom 399 90 5 0 0 0 - - -;
+#X msg 11 6 size;
+#X msg 10 83 1;
+#X msg 39 83 2;
+#X msg 364 233 flush;
+#X msg 401 106 list \$1;
+#X connect 0 0 1 0;
+#X connect 0 1 2 0;
+#X connect 3 0 0 0;
+#X connect 4 0 0 0;
+#X connect 5 0 0 0;
+#X connect 6 0 0 0;
+#X connect 7 0 8 0;
+#X connect 9 0 0 0;
+#X connect 10 0 0 0;
+#X connect 11 0 0 0;
+#X connect 12 0 0 0;
+#X connect 13 0 0 2;
+#X connect 14 0 0 2;
+#X connect 15 0 18 0;
+#X connect 15 1 20 0;
+#X connect 16 0 22 0;
+#X connect 17 0 15 0;
+#X connect 18 0 19 0;
+#X connect 21 0 15 0;
+#X connect 22 0 15 0;
+#X connect 23 0 24 0;
+#X connect 24 0 15 0;
+#X connect 25 0 26 0;
+#X connect 26 0 0 0;
+#X connect 27 0 32 0;
+#X connect 28 0 0 0;
+#X connect 29 0 25 0;
+#X connect 30 0 25 0;
+#X connect 31 0 15 0;
+#X connect 32 0 0 2;
diff --git a/deque/src/deque.c b/deque/src/deque.c
new file mode 100644
index 0000000..fd12b53
--- /dev/null
+++ b/deque/src/deque.c
@@ -0,0 +1,316 @@
+/* -*- Mode: C -*- */
+/*=============================================================================*\
+ * File: deque.c
+ * Author: Bryan Jurish <moocow@ling.uni-potsdam.de>
+ * Description: double-ended message queue for pd
+ *
+ * Copyright (c) 2003,2004 Bryan Jurish.  All Rights Reserved.
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2, or (at your option)
+ * any later version.
+ *=============================================================================*/
+
+
+/* black magic */
+#ifdef NT
+#pragma warning( disable : 4244 )
+#pragma warning( disable : 4305 )
+#endif
+
+#ifndef _M_PD_H
+# include <m_pd.h>
+# define _M_PD_H
+#endif
+
+#include "dsqueue.h"
+
+#ifdef HAVE_CONFIG_H
+# include "config.h"
+#endif
+
+#ifndef PACKAGE_VERSION
+# define PACKAGE_VERSION "(unknown)"
+#endif
+
+/*--------------------------------------------------------------------
+ * DEBUG
+ *--------------------------------------------------------------------*/
+//#define DEQUE_DEBUG 1
+//#undef DEQUE_DEBUG
+
+/*--------------------------------------------------------------------
+ * Globals
+ *--------------------------------------------------------------------*/
+#define DEQUE_DEFAULT_BLOCKSIZE 32
+
+/*=====================================================================
+ * pd_deque_elt
+ *   + element class
+ *=====================================================================*/
+typedef struct pd_deque_elt
+{
+  //t_symbol  *sel;  // message selector
+  int       argc;  // number of message arguments
+  t_atom   *argv;  // message arguments
+} t_pd_deque_elt;
+
+/*--------------------------------------------------------------------
+ * pd_deque_elt_new()
+ *  + create a new deque element
+ *  + arg 'sel' currently ignored
+ */
+static t_pd_deque_elt *pd_deque_elt_new(t_symbol *sel, int argc, t_atom *argv)
+{
+  t_pd_deque_elt *elt = (t_pd_deque_elt *)getbytes(sizeof(t_pd_deque_elt));
+
+#ifdef DEQUE_DEBUG
+  post("pd_deque_elt_new: got message with argc=%d", argc);
+#endif
+
+  //elt->sel  = sel;
+  elt->argc = argc;
+  if (argc>0) {
+    elt->argv = (t_atom *)copybytes(argv, argc*sizeof(t_atom));
+  } else {
+    elt->argv = NULL;
+  }
+  return elt;
+}
+
+static void pd_deque_elt_free(t_pd_deque_elt *elt)
+{
+  if (elt->argc > 0) {
+    freebytes(elt->argv, elt->argc*sizeof(t_atom));
+  }
+  elt->argv = NULL;
+  freebytes(elt, sizeof(t_pd_deque_elt));
+}
+
+/*=====================================================================
+ * pd_deque_class
+ *=====================================================================*/
+static t_class *pd_deque_class;
+typedef struct _pd_deque_class
+{
+  t_object        x_obj;     // black magic
+  dsqueue_ptr     x_deque;   // ye olde guts
+  t_pd_deque_elt *x_cur;     // current element
+  unsigned int    x_size;    // number of stored messages
+  t_outlet       *elt_out;   // data outlet
+  t_outlet       *eoq_out;   // end-of-queue bang-outlet / other data
+} t_pd_deque;
+
+
+/*=====================================================================
+ * pd methods
+ *=====================================================================*/
+
+/*--------------------------------------------------------------------
+ * push_front
+ *  + push to the front of the queue
+ */
+static void pd_deque_push_front(t_pd_deque *x, t_symbol *sel, int argc, t_atom *argv)
+{
+  t_pd_deque_elt *elt = pd_deque_elt_new(sel,argc,argv);
+
+#ifdef DEQUE_DEBUG
+  post("pd_deque_push_back: got sel='%s', argc=%d", sel->s_name, argc);
+#endif
+
+  dsqueue_prepend(x->x_deque, elt);
+  ++x->x_size;
+}
+
+/*--------------------------------------------------------------------
+ * push_back
+ *  + push to the back of the queue
+ */
+static void pd_deque_push_back(t_pd_deque *x, t_symbol *sel, int argc, t_atom *argv)
+{
+  t_pd_deque_elt *elt = pd_deque_elt_new(sel,argc,argv);
+
+#ifdef DEQUE_DEBUG
+  post("pd_deque_push_back: got sel='%s', argc=%d", sel->s_name, argc);
+#endif
+
+  dsqueue_append(x->x_deque, elt);
+  ++x->x_size;
+}
+
+/*--------------------------------------------------------------------
+ * outlet_cur
+ *  + outlets current element to outlet-1, if non-NULL
+ *  + otherwise, bangs to outlet-2
+ */
+static void pd_deque_outlet_cur(t_pd_deque *x)
+{
+  if (x->x_cur) {
+    --x->x_size;
+    if (x->x_cur->argc == 1) {
+      switch (x->x_cur->argv->a_type) {
+      case A_FLOAT:
+	outlet_float(x->elt_out, x->x_cur->argv->a_w.w_float);
+	return;
+      case A_SYMBOL:
+	outlet_symbol(x->elt_out, x->x_cur->argv->a_w.w_symbol);
+	return;
+      case A_POINTER:
+	outlet_pointer(x->elt_out, x->x_cur->argv->a_w.w_gpointer);
+	return;
+      default:
+	error("Error: deque: unrecognized atom type '%d' defaults to 'bang'.",
+	      x->x_cur->argv->a_type);
+	outlet_bang(x->elt_out);
+      }
+    } else {
+      outlet_anything(x->elt_out,
+		      atom_getsymbol(x->x_cur->argv),
+		      x->x_cur->argc-1,
+		      x->x_cur->argv+1
+		      );
+    }
+  } else {
+    outlet_bang(x->eoq_out);
+  }
+}
+
+/*--------------------------------------------------------------------
+ * pop_front
+ *  + pop from the front of the queue
+ */
+static void pd_deque_pop_front(t_pd_deque *x)
+{
+  if (x->x_cur) {
+    pd_deque_elt_free(x->x_cur);
+  }
+  x->x_cur = (t_pd_deque_elt *)dsqueue_shift(x->x_deque);
+  pd_deque_outlet_cur(x);
+}
+
+/*--------------------------------------------------------------------
+ * pop_back
+ *  + pop from the back of the queue
+ */
+static void pd_deque_pop_back(t_pd_deque *x)
+{
+  if (x->x_cur) {
+    pd_deque_elt_free(x->x_cur);
+  }
+  x->x_cur = (t_pd_deque_elt *)dsqueue_pop(x->x_deque);
+  pd_deque_outlet_cur(x);
+}
+
+
+/*--------------------------------------------------------------------
+ * clear
+ *  + clear the queue
+ */
+static void pd_deque_clear(t_pd_deque *x)
+{
+  if (x->x_cur) pd_deque_elt_free(x->x_cur);
+  while ( (x->x_cur = (t_pd_deque_elt *)dsqueue_shift(x->x_deque)) )
+    pd_deque_elt_free(x->x_cur);
+  x->x_size = 0;
+}
+
+/*--------------------------------------------------------------------
+ * flush
+ *  + flush queue contents (front-to-back)
+ *  + probably dangerous
+ */
+static void pd_deque_flush(t_pd_deque *x)
+{
+  if (x->x_cur) pd_deque_elt_free(x->x_cur);
+  while ( (x->x_cur = (t_pd_deque_elt *)dsqueue_shift(x->x_deque)) ) {
+    pd_deque_outlet_cur(x);
+    pd_deque_elt_free(x->x_cur);
+  }
+  x->x_size = 0;
+}
+
+/*--------------------------------------------------------------------
+ * size
+ *  + get number of stored messages
+ */
+static void pd_deque_size(t_pd_deque *x)
+{
+  t_atom sizeatom;
+  SETFLOAT(&sizeatom, x->x_size);
+  outlet_anything(x->eoq_out, gensym("size"), 1, &sizeatom);
+}
+
+/*--------------------------------------------------------------------
+ * newmethod, freemethod
+ */
+static void *pd_deque_new(t_floatarg f)
+{
+  t_pd_deque *x;
+  x = (t_pd_deque *)pd_new(pd_deque_class);
+
+  /* -- queue -- */
+  if (!f) f = DEQUE_DEFAULT_BLOCKSIZE;   // 0: use default value
+  if (f < 1) {                           // specified but goofy: complain
+    error("deque: bad blocksize %g", f);
+    f = DEQUE_DEFAULT_BLOCKSIZE;
+  }
+  x->x_deque = dsqueue_new((unsigned)f);
+
+  /* -- defaults --- */
+  x->x_cur = NULL;
+  x->x_size = 0;
+
+  /* --- extra inlet(s) --- */
+  inlet_new(&x->x_obj, &x->x_obj.ob_pd, &s_list, gensym("unshift"));
+  inlet_new(&x->x_obj, &x->x_obj.ob_pd, &s_list, gensym("push"));
+
+  /* -- outlets -- */
+  x->elt_out = outlet_new(&x->x_obj, &s_anything);
+  x->eoq_out = outlet_new(&x->x_obj, &s_bang);
+
+  return (void *)x;
+}
+
+static void pd_deque_free(t_pd_deque *x) {
+  pd_deque_clear(x);
+  dsqueue_destroy(x->x_deque);
+}
+
+
+/*--------------------------------------------------------------------
+ * setup
+ *--------------------------------------------------------------------*/
+void deque_setup(void) {
+  /* banner */
+  post("\ndeque version %s by Bryan Jurish <moocow@ling.uni-potsdam.de>",
+       PACKAGE_VERSION);
+
+  /* register class */
+  pd_deque_class = class_new(gensym("deque"),              // name 
+			     (t_newmethod)pd_deque_new,    // newmethod
+			     (t_method)pd_deque_free,      // freemethod
+			     sizeof(t_pd_deque),           // size
+			     CLASS_DEFAULT,                // flags
+			     A_DEFFLOAT,                   // args
+			     0);
+
+  /* --- methods: primary inlet --- */
+  class_addmethod(pd_deque_class, (t_method)pd_deque_push_front, gensym("unshift"), A_GIMME, 0);
+  class_addmethod(pd_deque_class, (t_method)pd_deque_pop_front, gensym("bang"), 0);
+  class_addmethod(pd_deque_class, (t_method)pd_deque_pop_front, gensym("shift"), 0);
+
+  class_addmethod(pd_deque_class, (t_method)pd_deque_push_back, gensym("push"), A_GIMME, 0);
+  class_addmethod(pd_deque_class, (t_method)pd_deque_pop_back, gensym("pop"), 0);
+
+  class_addmethod(pd_deque_class, (t_method)pd_deque_clear, gensym("clear"), 0);
+  class_addmethod(pd_deque_class, (t_method)pd_deque_flush, gensym("flush"), 0);
+
+  class_addmethod(pd_deque_class, (t_method)pd_deque_size, gensym("size"), 0);
+
+  class_addanything(pd_deque_class, (t_method)pd_deque_push_back);   // default: push_back
+
+  /* --- help --- */
+  class_sethelpsymbol(pd_deque_class, gensym("deque-help.pd"));
+}
+
diff --git a/deque/src/dsqueue.c b/deque/src/dsqueue.c
new file mode 100644
index 0000000..e328af0
--- /dev/null
+++ b/deque/src/dsqueue.c
@@ -0,0 +1,283 @@
+/*
+ * File: dsqueue.c
+ * Author: Bryan Jurish <moocow@ling.uni-potsdam.de>
+ *
+ * Copyright (c) 2003 Bryan Jurish.  All Rights Reserved.
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2, or (at your option)
+ * any later version.
+ *
+ */
+#include <stdlib.h>
+#include <errno.h>
+
+#include "dsqueue.h"
+#include "squeue.h"
+
+/*----------------------------------------------------------------------
+ * Creation / Deletion
+ *----------------------------------------------------------------------*/
+dsqueue_ptr dsqueue_new(unsigned blocksize) {
+  dsqueue_ptr dsq = (dsqueue_ptr)malloc(sizeof(dsqueue_t));
+  if (!dsq) {
+    errno = ENOMEM;
+    return NULL;
+  }
+  dsq->blocksize = blocksize;
+  dsq->trash = NULL;
+  dsq->head = NULL;
+  dsq->tail = NULL;
+  return dsq;
+}
+
+void dsqueue_destroy(dsqueue_ptr dsq) {
+  dsqueue_block_t *dsqe, *dsqe_next;
+  dsqueue_clear(dsq);
+  for (dsqe = dsq->head; dsqe != NULL; dsqe = dsqe_next) {
+    squeue_destroy(dsqe->sq);
+    dsqe_next = dsqe->next;
+    free(dsqe);
+  }
+  for (dsqe = dsq->trash; dsqe != NULL; dsqe = dsqe_next) {
+    squeue_destroy(dsqe->sq);
+    dsqe_next = dsqe->next;
+    free(dsqe);
+  }
+  free(dsq);
+}
+
+/*----------------------------------------------------------------------
+ * Predicates
+ *----------------------------------------------------------------------*/
+char dsqueue_is_empty(dsqueue_ptr dsq) {
+  while (dsq->head && squeue_empty(dsq->head->sq)) {
+    dsqueue_block_t *dsqe = dsqueue_block_shift(dsq);
+    dsqe->next = dsq->trash;
+    if (dsq->trash) dsq->trash->prev = dsqe;
+    dsq->trash = dsqe;
+  }
+  return dsq->head ? 0 : 1;
+}
+
+/*----------------------------------------------------------------------
+ * Manipulation
+ *----------------------------------------------------------------------*/
+
+void dsqueue_clear(dsqueue_ptr dsq) {
+  if (dsq->head && dsq->tail) {
+    dsq->tail->next = dsq->trash;
+    if (dsq->trash) dsq->trash->prev = dsq->tail;
+    dsq->trash = dsq->head;
+  }
+  dsq->head = NULL;
+  dsq->tail = NULL;
+}
+
+dsqueue_block_t *dsqueue_prepend(dsqueue_ptr dsq, void *data) {
+  dsqueue_block_t *dsqe = dsq->head;
+  while (!dsqe || squeue_full(dsqe->sq)) {
+    dsqe = dsqueue_block_new(dsq);
+    if (!dsqe) {
+      errno = ENOMEM;
+      return NULL;
+    }
+    dsqueue_block_prepend(dsq,dsqe);
+  }
+  squeue_prepend(dsqe->sq,data);
+  return dsqe;
+}
+
+dsqueue_block_t *dsqueue_append(dsqueue_ptr dsq, void *data) {
+  dsqueue_block_t *dsqe = dsq->tail;
+  while (!dsqe || squeue_full(dsqe->sq)) {
+    dsqe = dsqueue_block_new(dsq);
+    if (!dsqe) {
+      errno = ENOMEM;
+      return NULL;
+    }
+    dsqueue_block_append(dsq,dsqe);
+  }
+  squeue_append(dsqe->sq,data);
+  return dsqe;
+}
+
+
+
+/*----------------------------------------------------------------------
+ * Access
+ *----------------------------------------------------------------------*/
+
+void *dsqueue_shift(dsqueue_ptr dsq) {
+  dsqueue_trim_front(dsq);
+  return dsq->head ? squeue_shift(dsq->head->sq) : NULL;
+}
+
+void *dsqueue_pop(dsqueue_ptr dsq) {
+  dsqueue_trim_back(dsq);
+  return dsq->tail ? squeue_pop(dsq->tail->sq) : NULL;
+}
+
+
+/*----------------------------------------------------------------------
+ * Iterators
+ *----------------------------------------------------------------------*/
+
+// Returns an iterator for the first datum in the queue,
+// or NULL if queue is empty.
+dsqueue_iter_t dsqueue_iter_first(dsqueue_t *dsq) {
+  dsqueue_iter_t dsqi = {NULL,NULL};
+  dsqueue_trim_front(dsq);
+  if (dsq->head) {
+    dsqi.block = dsq->head;
+    dsqi.sqi = squeue_iter_first(dsqi.block->sq);
+  }
+  return dsqi;
+}
+
+/// Returns an iterator for the final datum in the queue,
+/// or NULL if queue is empty.
+dsqueue_iter_t dsqueue_iter_last(dsqueue_t *dsq) {
+  dsqueue_iter_t dsqi = {NULL,NULL};
+  dsqueue_trim_back(dsq);
+  if (dsq->tail) {
+    dsqi.block = dsq->tail;
+    dsqi.sqi = squeue_iter_last(dsqi.block->sq);
+  }
+  return dsqi;
+}
+
+
+/// Returns an iterator for the next datum in the queue, or
+/// NULL if already at end-of-queue.
+dsqueue_iter_t dsqueue_iter_next(dsqueue_t *dsq, dsqueue_iter_t dsqi) {
+  while (dsqi.block) {
+    dsqi.sqi = squeue_iter_next(dsqi.block->sq, dsqi.sqi);
+    if (dsqi.sqi) break;
+    dsqi.block = dsqi.block->next;
+  }
+  return dsqi;
+}
+
+/// Returns an iterator for the previous datum in the queue,
+/// or NULL if already at beginning-of-queue.
+dsqueue_iter_t dsqueue_iter_prev(dsqueue_t *dsq, dsqueue_iter_t dsqi) {
+  while (dsqi.block) {
+    dsqi.sqi = squeue_iter_prev(dsqi.block->sq, dsqi.sqi);
+    if (dsqi.sqi) break;
+    dsqi.block = dsqi.block->prev;
+  }
+  return dsqi;
+}
+
+/// Returns a true value if p is a valid iterator value, false otherwise.
+char dsqueue_iter_valid(dsqueue_t *dsq, dsqueue_iter_t dsqi) {
+  return (dsqi.block && dsqi.sqi && 
+	  squeue_iter_valid(dsqi.block->sq, dsqi.sqi));
+}
+
+/// Get the datum from an iterator.
+void *dsqueue_iter_data(dsqueue_iter_t dsqi) {
+  return (dsqi.block && dsqi.sqi ? squeue_iter_data(dsqi.sqi) : NULL);
+}
+
+
+
+/*----------------------------------------------------------------------
+ * Utilities
+ *----------------------------------------------------------------------*/
+
+// Allocate and return a new block.
+dsqueue_block_t *dsqueue_block_new(dsqueue_t *dsq) {
+  // -- first try trashbin
+  dsqueue_block_t *dsqe = dsq->trash;
+  if (dsqe) {
+    dsq->trash = dsqe->next;
+    if (dsq->trash) dsq->trash->prev = NULL;
+  } else {
+    dsqe = (dsqueue_block_t *)malloc(sizeof(dsqueue_block_t));
+    if (!dsqe) {
+      errno = ENOMEM;
+      return NULL;
+    }
+    dsqe->sq = squeue_new(dsq->blocksize);
+    if (!dsqe->sq) {
+      errno = ENOMEM;
+      free(dsqe);
+      return NULL;
+    }
+  }
+  // -- initialize
+  dsqe->prev = NULL;
+  dsqe->next = NULL;
+  return dsqe;
+}
+
+
+#ifdef DSQUEUE_DEBUG
+
+dsqueue_block_t *dsqueue_block_prepend(dsqueue_t *dsq, dsqueue_block_t *e) {
+  if (!e) return NULL;
+  else if (dsq->head) dsq->head->prev = e;
+  else dsq->tail = e;
+  e->next = dsq->head;
+  dsq->head = e;
+  return dsq->head;
+}
+
+dsqueue_block_t *dsqueue_block_append(dsqueue_t *dsq, dsqueue_block_t *e) {
+  if (!e) return NULL;
+  else if (dsq->tail) dsq->tail->next = e;
+  else dsq->head = e;
+  e->prev = dsq->tail;
+  dsq->tail = e;
+  return dsq->tail;
+}
+
+#endif
+
+
+dsqueue_block_t *dsqueue_block_shift(dsqueue_t *dsq) {
+  dsqueue_block_t *dsqe = dsq->head;
+  if (!dsqe) return dsqe;
+  dsq->head = dsqe->next;
+  if (dsq->head) {
+    dsq->head->prev = NULL;
+  } else {
+    dsq->tail = NULL;
+  }
+  dsqe->next = NULL;
+  return dsqe;
+}
+dsqueue_block_t *dsqueue_block_pop(dsqueue_t *dsq) {
+  dsqueue_block_t *dsqe = dsq->tail;
+  if (!dsqe) return dsqe;
+  dsq->tail = dsqe->prev;
+  if (dsq->tail) {
+    dsq->tail->next = NULL;
+  } else {
+    dsq->head = NULL;
+  }
+  dsqe->prev = NULL;
+  return dsqe;
+}
+
+
+void dsqueue_trim_front(dsqueue_t *dsq) {
+  while (dsq->head && squeue_empty(dsq->head->sq)) {
+    dsqueue_block_t *dsqe = dsqueue_block_shift(dsq);
+    if (dsq->trash) dsq->trash->prev = dsqe;
+    dsqe->next = dsq->trash;
+    dsq->trash = dsqe;
+  }
+}
+
+void dsqueue_trim_back(dsqueue_t *dsq) {
+  while (dsq->tail && squeue_empty(dsq->tail->sq)) {
+    dsqueue_block_t *dsqe = dsqueue_block_pop(dsq);
+    if (dsq->trash) dsq->trash->prev = dsqe;
+    dsqe->next = dsq->trash;
+    dsq->trash = dsqe;
+  }
+}
diff --git a/deque/src/dsqueue.h b/deque/src/dsqueue.h
new file mode 100644
index 0000000..b0fae20
--- /dev/null
+++ b/deque/src/dsqueue.h
@@ -0,0 +1,171 @@
+/* -*- Mode: C -*- */
+/*
+ * File: dsqueue.h
+ * Author: Bryan Jurish <moocow@ling.uni-potsdam.de>
+ *
+ * Copyright (c) 2003 Bryan Jurish.  All Rights Reserved.
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2, or (at your option)
+ * any later version.
+ *
+ */
+
+#ifndef DSQUEUE_H
+#define DSQUEUE_H
+
+#ifdef HAVE_CONFIG_H
+# include "config.h"
+#endif
+
+#include "squeue.h"
+
+
+/**
+ * \file dsqueue.h
+ * \brief Headers for linked-list queues.
+ */
+
+/// Queue block structure.
+typedef struct dsqueue_block {
+  squeue_t           *sq;
+  struct dsqueue_block *next;
+  struct dsqueue_block *prev;
+} dsqueue_block_t, *dsqueue_block_ptr;
+
+/// Queue structure.
+typedef struct {
+  dsqueue_block_t *head;     // head of the queue
+  dsqueue_block_t *tail;     // tail of the queue
+  dsqueue_block_t *trash;    // recycling bin
+  unsigned      blocksize;
+} dsqueue_t, *dsqueue_ptr;
+
+
+/// Queue iterator structure
+typedef struct {
+  dsqueue_block_t *block;
+  squeue_iter_t   sqi;
+} dsqueue_iter_t;
+
+/*----------------------------------------------------------------------
+ * Creation / Deletion
+ *----------------------------------------------------------------------*/
+
+/// Create and initialize a new dsqueue. Returns NULL on failure.
+extern dsqueue_ptr dsqueue_new(unsigned blocksize);
+
+/// Destroy an dsqueue -- implicitly calls clear().
+extern void dsqueue_destroy(dsqueue_ptr dsq);
+
+/*----------------------------------------------------------------------
+ * Predicates
+ *----------------------------------------------------------------------*/
+
+/// True if the dsqueue has no blocks.
+extern char dsqueue_is_empty(dsqueue_ptr dsq);
+
+#define dsqueue_empty(dsq) (!dsq->head || dsqueue_is_empty(dsq))
+
+/*----------------------------------------------------------------------
+ * Manipulation
+ *----------------------------------------------------------------------*/
+
+/// Clear all blocks from an dsqueue.  'data' members will not be freed.
+extern void dsqueue_clear(dsqueue_ptr dsq);
+
+/// Prepend data to the front of an dsqueue.
+extern dsqueue_block_t *dsqueue_prepend(dsqueue_ptr dsq, void *data);
+
+/// Append data to the end of an dsqueue.
+extern dsqueue_block_t *dsqueue_append(dsqueue_ptr dsq, void *data);
+
+/*----------------------------------------------------------------------
+ * Access
+ *----------------------------------------------------------------------*/
+
+/// Shift an block off the front of an dsqueue.
+/// Returns a pointer to the block's data, or NULL if dsqueue is empty.
+extern void *dsqueue_shift(dsqueue_ptr dsq);
+
+/// Pop an block off the back of an dsqueue.
+/// Returns a pointer to the block's data, or NULL if dsqueue is empty.
+extern void *dsqueue_pop(dsqueue_ptr dsq);
+
+
+/*----------------------------------------------------------------------
+ * Iteration
+ *----------------------------------------------------------------------*/
+/// Returns an iterator for the first datum in the queue,
+/// or NULL if queue is empty.
+extern dsqueue_iter_t dsqueue_iter_first(dsqueue_t *dsq);
+
+/// Returns an iterator for the next datum in the queue, or
+/// NULL if already at end-of-queue.
+extern dsqueue_iter_t dsqueue_iter_next(dsqueue_t *dsq, dsqueue_iter_t dsqi);
+
+/// Returns an iterator for the final datum in the queue,
+/// or NULL if queue is empty.
+extern dsqueue_iter_t dsqueue_iter_last(dsqueue_t *dsq);
+
+/// Returns an iterator for the previous datum in the queue,
+/// or NULL if already at beginning-of-queue.
+extern dsqueue_iter_t dsqueue_iter_prev(dsqueue_t *dsq, dsqueue_iter_t dsqi);
+
+/// Returns a true value if p is a valid iterator value, false otherwise.
+extern char dsqueue_iter_valid(dsqueue_t *dsq, dsqueue_iter_t dsqi);
+
+/// Get the datum from an iterator.
+extern void *dsqueue_iter_data(dsqueue_iter_t dsqi);
+
+/*----------------------------------------------------------------------
+ * Utilities
+ *----------------------------------------------------------------------*/
+
+/// Allocate and return a new block (try trashbin first)
+extern dsqueue_block_t *dsqueue_block_new(dsqueue_t *dsq);
+
+#ifdef DSQUEUE_DEBUG
+
+/// Prepend a block
+extern dsqueue_block_t *dsqueue_block_prepend(dsqueue_t *dsq, dsqueue_block_t *e);
+
+/// Append a block
+extern dsqueue_block_t *dsqueue_block_append(dsqueue_t *dsq, dsqueue_block_t *e);
+
+#else
+
+#define dsqueue_block_prepend(dsq,e) \
+  if (e) { \
+    if (dsq->head) dsq->head->prev = e; \
+    else dsq->tail = e; \
+    e->next = dsq->head; \
+    dsq->head = e; \
+  }
+
+
+#define dsqueue_block_append(dsq,e) \
+  if (e) { \
+    if (dsq->tail) dsq->tail->next = e; \
+    else dsq->head = e; \
+    e->prev = dsq->tail; \
+    dsq->tail = e; \
+  }
+
+#endif
+
+
+/// Shift a block from the front (trashing it)
+extern dsqueue_block_t *dsqueue_block_shift(dsqueue_t *dsq);
+
+/// Pop a block from the end (trashing it)
+extern dsqueue_block_t *dsqueue_block_pop(dsqueue_t *dsq);
+
+/// Trim empty blocks off the front of the queue.
+extern void dsqueue_trim_front(dsqueue_t *dsq);
+
+/// Trim empty blocks off the back of the queue.
+extern void dsqueue_trim_back(dsqueue_t *dsq);
+
+#endif /* DSQUEUE_H */
diff --git a/deque/src/squeue.c b/deque/src/squeue.c
new file mode 100644
index 0000000..0c24c93
--- /dev/null
+++ b/deque/src/squeue.c
@@ -0,0 +1,216 @@
+/*
+ *
+ * File: squeue.h
+ * Author: Bryan Jurish <moocow@ling.uni-potsdam.de>
+ *
+ * Copyright (c) 2003 Bryan Jurish.  All Rights Reserved.
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2, or (at your option)
+ * any later version.
+ *
+ */
+
+#include <stdlib.h>
+#include <errno.h>
+#include "squeue.h"
+
+/*----------------------------------------------------------------------
+ * Creation / Deletion
+ *----------------------------------------------------------------------*/
+squeue_ptr squeue_new(unsigned int size) {
+  squeue_ptr sq = (squeue_ptr)malloc(sizeof(squeue_t));
+  if (!sq || !size) {
+    errno = ENOMEM;
+    return NULL;
+  }
+  sq->data = (void **)malloc(size*sizeof(void *));
+  if (!sq->data) {
+    errno = ENOMEM;
+    return NULL;
+  }
+# ifdef SQUEUE_DEBUG
+  memset(sq->data,0,size*sizeof(void *));
+# endif
+  sq->size = size-1;
+  sq->head = NULL;
+  sq->tail = NULL;
+  return sq;
+}
+
+void squeue_destroy(squeue_ptr sq) {
+  squeue_clear(sq);
+  free(sq->data);
+  free(sq);
+}
+
+/*----------------------------------------------------------------------
+ * Predicates
+ *----------------------------------------------------------------------*/
+#ifdef SQUEUE_DEBUG
+
+char squeue_empty(squeue_ptr sq) {
+  return (!sq->head);
+}
+
+char squeue_full(squeue_ptr sq) {
+  return (sq->head && sq->head == squeue_next(sq,sq->tail));
+}
+
+#endif
+
+
+/*----------------------------------------------------------------------
+ * utilities
+ *----------------------------------------------------------------------*/
+#ifdef SQUEUE_DEBUG
+
+void **squeue_prev(squeue_t *sq, void **p) {
+  //return (p && p > sq->data ? p-1 : p+sq->size);
+  return (p && p > sq->data ? p-1 : sq->data+sq->size);
+}
+
+void **squeue_next(squeue_t *sq, void **p) {
+  return (p && p < sq->data+sq->size ? p+1 : sq->data);
+}
+
+#endif
+
+/*----------------------------------------------------------------------
+ * Manipulation
+ *----------------------------------------------------------------------*/
+
+#ifdef SQUEUE_DEBUG
+
+void squeue_clear(squeue_ptr sq) {
+  sq->head = NULL;
+  sq->tail = NULL;
+# ifdef SQUEUE_DEBUG
+  memset(sq->data,0,sq->size*sizeof(void *));
+# endif
+}
+
+#endif
+
+void **squeue_prepend(squeue_ptr sq, void *data) {
+  sq->head = squeue_prev(sq,sq->head);
+  if (!sq->tail) {
+    // -- empty-queue
+    sq->tail = sq->head;
+  } else if (sq->head == sq->tail) {
+    // -- xrun (full queue)
+    sq->head = squeue_next(sq,sq->head);
+    return NULL;
+    // alternative: push the overwritten older pointer along a notch
+    //sq->tail = squeue_prev(sq,sq->tail);
+  }
+  // -- set the data
+  *(sq->head) = data;
+  return sq->head;
+}
+
+void **squeue_append(squeue_ptr sq, void *data) {
+  sq->tail = squeue_next(sq,sq->tail);
+  if (!sq->head) {
+    // -- empty-queue check
+    sq->head = sq->tail;
+  } else if (sq->tail == sq->head) {
+    // -- xrun (full queue)
+    sq->tail = squeue_prev(sq,sq->tail);
+    return NULL;
+    // alternative: push the overwritten older pointer along a notch
+    //sq->head = squeue_next(sq,sq->head);
+  }
+  // -- set the data
+  *(sq->tail) = data;
+  return sq->tail;
+}
+
+
+/*----------------------------------------------------------------------
+ * Access
+ *----------------------------------------------------------------------*/
+
+void *squeue_shift(squeue_ptr sq) {
+  if (squeue_empty(sq)) return NULL;
+  else {
+    void *data = *(sq->head);
+    // -- empty queue check
+    if (sq->head == sq->tail) {
+      sq->head = NULL;
+      sq->tail = NULL;
+    } else {
+      sq->head = squeue_next(sq, sq->head);
+    }
+    return data;
+  }
+}
+
+void *squeue_pop(squeue_ptr sq) {
+  if (squeue_empty(sq)) return NULL;
+  else {
+    void *data = *(sq->tail);
+    if (sq->head == sq->tail) {
+      sq->head = NULL;
+      sq->tail = NULL;
+    } else {
+      sq->tail = squeue_prev(sq, sq->tail);
+    }
+    return data;
+  }
+}
+
+#ifdef SQUEUE_DEBUG
+
+// Returns the first datum in the queue, or NULL if queue is empty.
+void *squeue_peek_head(squeue_ptr sq) {
+  return sq->head ? *(sq->head) : NULL;
+}
+
+// Returns the final datum in the queue, or NULL if queue is empty.
+void *squeue_peek_tail(squeue_ptr sq) {
+  return sq->tail ? *(sq->tail) : NULL;
+}
+
+#endif
+
+/*----------------------------------------------------------------------
+ * Iteration
+ *----------------------------------------------------------------------*/
+#ifdef SQUEUE_DEBUG
+
+// Returns a pointer-pointer to the first datum in the queue,
+// or NULL if queue is empty.
+squeue_iter_t squeue_iter_first(squeue_t *sq) { return sq->head; }
+
+// Returns a pointer-pointer to the final datum in the queue,
+// or NULL if queue is empty.
+squeue_iter_t squeue_iter_last(squeue_t *sq) { return sq->tail; }
+
+
+
+// Returns a pointer to the next datum in the queue, or
+// NULL if queue is empty.
+squeue_iter_t squeue_iter_next(squeue_t *sq, squeue_iter_t p) {
+  return p == sq->tail ? NULL : squeue_next(sq,p);
+}
+
+// Returns a pointer-pointer to the final datum in the queue,
+// or NULL if queue is empty.
+extern squeue_iter_t squeue_iter_prev(squeue_t *sq, squeue_iter_t p) {
+  return p == sq->head ? NULL : squeue_prev(sq,p);
+}
+
+
+// Returns a true value if p is a valid iterator value, false otherwise.
+// Warning: this is not even as paranoid as it ought to be!
+extern char squeue_iter_valid(squeue_t *sq, squeue_iter_t p) {
+  return (p && p >= sq->data && p <= sq->data+sq->size);
+}
+
+/// Get the datum from an iterator.
+void *squeue_iter_data(squeue_iter_t p) { return *p; }
+
+
+#endif
diff --git a/deque/src/squeue.h b/deque/src/squeue.h
new file mode 100644
index 0000000..9a963c2
--- /dev/null
+++ b/deque/src/squeue.h
@@ -0,0 +1,199 @@
+/* -*- Mode: C -*- */
+/*
+ * File: squeue.h
+ * Author: Bryan Jurish <moocow@ling.uni-potsdam.de>
+ *
+ * Copyright (c) 2003 Bryan Jurish.  All Rights Reserved.
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2, or (at your option)
+ * any later version.
+ *
+ */
+
+#ifndef SQUEUE_H
+#define SQUEUE_H
+
+#ifdef HAVE_CONFIG_H
+# include "config.h"
+#endif
+
+/**
+ * \file squeue.h
+ * \brief Headers for static queues.
+ */
+
+/// Queue structure.
+typedef struct {
+  void          **data;      // data array
+  unsigned        size;      // number of allocated elements - 1 (index-max)
+  void          **head;      // head of queue
+  void          **tail;      // tail of queue
+} squeue_t, *squeue_ptr;
+
+typedef void **squeue_iter_t;
+
+/*----------------------------------------------------------------------
+ * Creation / Deletion
+ *----------------------------------------------------------------------*/
+
+/// Create and initialize a new squeue. Returns NULL on failure.
+extern squeue_ptr squeue_new(unsigned int size);
+
+/// Destroy an squeue -- implicitly calls clear().
+extern void squeue_destroy(squeue_ptr sq);
+
+/*----------------------------------------------------------------------
+ * Predicates
+ *----------------------------------------------------------------------*/
+
+#ifdef SQUEUE_DEBUG
+
+/// Returns true if the squeue has no elements.
+extern char squeue_empty(squeue_ptr sq);
+
+/// Returns true if the squeue has no empty slots remaining.
+extern char squeue_full(squeue_ptr sq);
+
+#else
+
+/// Returns true if the squeue has no elements.
+# define squeue_empty(sq) (!sq->head)
+
+/// Returns true if the squeue has no empty slots remaining.
+# define squeue_full(sq) (sq->head && sq->head == squeue_next(sq,sq->tail))
+
+#endif
+
+
+/*----------------------------------------------------------------------
+ * Manipulation
+ *----------------------------------------------------------------------*/
+
+#ifdef SQUEUE_DEBUG
+
+/// Clear all elements from an squeue.  User data is not freed.
+extern void squeue_clear(squeue_ptr sq);
+
+#else
+
+/// Clear all elements from an squeue.  User data will not be freed.
+# define squeue_clear(sq) sq->head = sq->tail = NULL
+
+#endif
+
+/// Prepend data to the front of an squeue.
+/// Returns new head or NULL if queue is full.
+extern void **squeue_prepend(squeue_ptr sq, void *data);
+
+/// Append data to the end of an squeue.
+/// Returns new tail or NULL if queue is full.
+extern void **squeue_append(squeue_ptr sq, void *data);
+
+/*----------------------------------------------------------------------
+ * Access
+ *----------------------------------------------------------------------*/
+
+/// Shift an element off the front of an squeue.
+/// Returns a pointer to the element's data, or NULL if queue is empty.
+extern void *squeue_shift(squeue_ptr sq);
+
+/// Pop an element off the back of an squeue.
+/// Returns a pointer to the element's data, or NULL if queue is empty.
+extern void *squeue_pop(squeue_ptr sq);
+
+#ifdef SQUEUE_DEBUG
+
+/// Returns the first datum in the queue, or NULL if queue is empty.
+extern void *squeue_peek_head(squeue_ptr sq);
+
+/// Returns the final datum in the queue, or NULL if queue is empty.
+extern void *squeue_peek_tail(squeue_ptr sq);
+
+#else
+
+/// Returns the first datum in the queue, or NULL if queue is empty.
+# define squeue_peek_head(sq) (sq->head ? *(sq->head) : NULL)
+
+/// Returns the final datum in the queue, or NULL if queue is empty.
+# define squeue_peek_tail(sq) (sq->tail ? *(sq->tail) : NULL)
+
+#endif /* SQUEUE_DEBUG */
+
+/*----------------------------------------------------------------------
+ * Utilities
+ *----------------------------------------------------------------------*/
+#ifdef SQUEUE_DEBUG
+
+/// Returns the index immediately preceeding 'p' (wrapped)
+extern void **squeue_prev(squeue_t *sq, void **p);
+
+/// Returns the index immediately follwoing 'p' (wrapped)
+extern void **squeue_next(squeue_t *sq, void **p);
+
+#else
+
+/// Returns the index immediately preceeding 'p' (wrapped)
+# define squeue_prev(sq,p) (p && p > sq->data ? p-1 : sq->data+sq->size)
+
+/// Returns the index immediately follwoing 'p' (wrapped)
+# define squeue_next(sq,p) (p && p < sq->data+sq->size ? p+1 : sq->data)
+
+#endif /* SQUEUE_DEBUG */
+
+
+/*----------------------------------------------------------------------
+ * Iteration
+ *----------------------------------------------------------------------*/
+#ifdef SQUEUE_DEBUG
+
+/// Returns an iterator (pointer-pointer) for the first datum in the queue,
+/// or NULL if queue is empty.
+extern squeue_iter_t squeue_iter_first(squeue_t *sq);
+
+/// Returns an iterator for the next datum in the queue, or
+/// NULL if already at end-of-queue.
+extern squeue_iter_t squeue_iter_next(squeue_t *sq, squeue_iter_t sqi);
+
+/// Returns an iterator (pointer-pointer) for the final datum in the queue,
+/// or NULL if queue is empty.
+extern squeue_iter_t squeue_iter_last(squeue_t *sq);
+
+/// Returns an iterator for the previous datum in the queue,
+/// or NULL if already at beginning-of-queue.
+extern squeue_iter_t squeue_iter_prev(squeue_t *sq, squeue_iter_t sqi);
+
+
+/// Returns a true value if p is a valid iterator value, false otherwise.
+/// If you have initialized an incremented your iterator with the
+/// squeue_iter() functions, a simple 'p != NULL' will suffice.
+extern char squeue_iter_valid(squeue_t *sq, squeue_iter_t sqi);
+
+
+/// Get the datum from an iterator or NULL if the iterator is invalid.
+extern void *squeue_iter_data(squeue_iter_t sqi);
+
+
+#else
+
+# define squeue_iter_first(sq) (sq->head)
+
+# define squeue_iter_last(sq) (sq->tail)
+
+# define squeue_iter_next(sq,sqi) \
+  (sqi == sq->tail ? NULL : (sqi && sqi < sq->data+sq->size ? sqi+1 : sq->data))
+
+# define squeue_iter_prev(sq,sqi) \
+  (sqi == sq->head ? NULL : (sqi && sqi > sq->data ? sqi-1 : sqi+sq->size))
+
+# define squeue_iter_valid(sq,sqi) \
+  (sqi && sqi >= sq->data && sqi <= sq->data+sq->size)
+
+# define squeue_iter_data(sqi) (sqi ? *sqi : NULL)
+
+#endif /* SQUEUE_DEBUG */
+
+
+
+#endif /* SQUEUE_H */
diff --git a/deque/src/testme.c b/deque/src/testme.c
new file mode 100644
index 0000000..ebd9a10
--- /dev/null
+++ b/deque/src/testme.c
@@ -0,0 +1,10 @@
+#include <stdio.h>
+
+#define FOO 42
+#define BAR(x) x + FOO
+
+int main (void) {
+  printf("BAR(1) = %d\n", BAR(1));
+  return 0;
+}
+