aboutsummaryrefslogtreecommitdiff
path: root/deque/src
diff options
context:
space:
mode:
Diffstat (limited to 'deque/src')
-rw-r--r--deque/src/Makefile.am137
-rw-r--r--deque/src/deque-help.pd45
-rw-r--r--deque/src/deque-test.pd66
-rw-r--r--deque/src/deque.c316
-rw-r--r--deque/src/dsqueue.c283
-rw-r--r--deque/src/dsqueue.h171
-rw-r--r--deque/src/squeue.c216
-rw-r--r--deque/src/squeue.h199
-rw-r--r--deque/src/testme.c10
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;
+}
+
generated by cgit v1.2.1 (git 2.18.0) at 2024-05-22 05:53:45 +0000