1 files changed, 216 insertions, 0 deletions
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