1 files changed, 171 insertions, 0 deletions
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 */