1 files changed, 283 insertions, 0 deletions
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;
+  }
+}