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