# HG changeset patch
# User Eris Caffee <discordia@eldalin.com>
# Date 1348200700 18000
# Node ID 392ce56806f9fdfc79c102e9ae6dc8ffbf124daf
# Parent  5af32066927f9ccb78872b73c7bdc33614a3dafe
Added dequeue, cmake file, fix copypasta in queue

diff -r 5af32066927f -r 392ce56806f9 .hgignore
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/.hgignore	Thu Sep 20 23:11:40 2012 -0500
@@ -0,0 +1,5 @@
+syntax: glob
+
+build*/*
+*~
+
diff -r 5af32066927f -r 392ce56806f9 CMakeLists.txt
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/CMakeLists.txt	Thu Sep 20 23:11:40 2012 -0500
@@ -0,0 +1,64 @@
+cmake_minimum_required (VERSION 2.6 FATAL_ERROR)
+#set (CMAKE_VERBOSE_MAKEFILE ON)
+
+project (data_structures)
+
+################################################################################
+# Ensure that we are not building in our source directories.
+
+set (Build_Dir_OK "TRUE")
+string (REGEX MATCH "^${CMAKE_SOURCE_DIR}" In_Sub_Dir ${CMAKE_BINARY_DIR})
+if (In_Sub_Dir)
+  string (REGEX MATCH "^${CMAKE_SOURCE_DIR}/build" In_Build_Dir ${CMAKE_BINARY_DIR})
+  if (NOT In_Build_Dir)
+    set (Build_Dir_OK "FALSE")
+  endif ()
+endif ()
+
+if (NOT Build_Dir_OK)
+  message (FATAL_ERROR "You must run cmake from a directory that is not in your source tree, or that is in a special subdirectory of the tree whose name begins with 'build'.")
+endif ()
+
+
+if (CMAKE_BUILD_TYPE STREQUAL "")
+  # CMake defaults to leaving CMAKE_BUILD_TYPE empty. This messes up differentiation between debug and release builds.               
+  set (CMAKE_BUILD_TYPE "RelWithDebInfo" CACHE STRING "Choose the type of build, options are: None Debug Release RelWithDebInfo MinSizeRel." FORCE)
+endif ()
+
+
+if (CMAKE_COMPILER_IS_GNUCXX)
+  add_definitions(-pedantic -Wall -std=gnu99)
+endif ()
+
+
+################################################################################
+
+option(Option_Profile_Program "Build for gprof profiling." OFF)
+if (Option_Profile_Program)
+  add_definitions(-pg)
+  set (CMAKE_EXE_LINKER_FLAGS "${CMAKE_EXE_LINKER_FLAGS} -pg")
+endif ()
+
+
+################################################################################
+
+set (stack_SRCS src/stack.h src/stack.c src/stack_test.c)
+add_executable (stack_test
+  ${stack_SRCS}
+  )
+
+set (ring_buffer_SRCS src/ring_buffer.h src/ring_buffer.c src/ring_buffer_test.c)
+add_executable (ring_buffer_test
+  ${ring_buffer_SRCS}
+  )
+
+set (queue_SRCS src/queue.h src/queue.c src/queue_test.c)
+add_executable (queue_test
+  ${queue_SRCS}
+  )
+
+set (dequeue_SRCS src/dequeue.h src/dequeue.c src/dequeue_test.c)
+add_executable (dequeue_test
+  ${dequeue_SRCS}
+  )
+
diff -r 5af32066927f -r 392ce56806f9 src/dequeue.c
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/dequeue.c	Thu Sep 20 23:11:40 2012 -0500
@@ -0,0 +1,156 @@
+#include <stdlib.h>
+#include <errno.h>
+
+#include "dequeue.h"
+
+////////////////////////////////////////////////////////////////////////////////
+struct dequeue * dequeue_new(size_t const max)
+   {
+   if (max < 1)
+      {
+      errno = EINVAL;
+      return NULL;
+      }
+
+   struct dequeue * deq = malloc(sizeof(struct dequeue));
+   if (NULL == deq)
+      return NULL;
+
+   deq->bottom = deq->top = deq->count = 0;
+   deq->max = max;
+
+   deq->data = calloc(deq->max, sizeof(void *));
+   if (NULL == deq->data)
+      {
+      free(deq);
+      return NULL;
+      }
+
+   return deq;
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+// Returns:
+// NULL on error
+// elem on success and the buffer is not full
+// the overwritten element on success if the buffer was full
+void * dequeue_push_top(struct dequeue * deq, void * elem)
+   {
+   if ((NULL == deq) || (NULL == elem))
+      {
+      errno = EINVAL;
+      return NULL;
+      }
+
+   if (deq->count == deq->max)
+      {
+      errno = ENOMEM;
+      return NULL;
+      }
+
+   if (deq->max - 1 == deq->top)
+      deq->top = 0;
+   else
+      deq->top++;
+
+   deq->data[deq->top] = elem;
+   deq->count++;
+
+   return elem;
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+void * dequeue_push_bottom(struct dequeue * deq, void * elem)
+   {
+   if ((NULL == deq) || (NULL == elem))
+      {
+      errno = EINVAL;
+      return NULL;
+      }
+
+   if (deq->count == deq->max)
+      {
+      errno = ENOMEM;
+      return NULL;
+      }
+
+   if (0 == deq->bottom)
+      deq->bottom = deq->max - 1;
+   else
+      deq->bottom--;
+
+   deq->data[deq->bottom] = elem;
+   deq->count++;
+
+   return elem;
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+void * dequeue_pop_top(struct dequeue * deq)
+   {
+   if (NULL == deq)
+      {
+      errno = EINVAL;
+      return NULL;
+      }
+
+   if (deq->count == 0)
+      return NULL;
+
+   void * t = deq->data[deq->top];
+
+   if (deq->top == 0)
+      deq->top = deq->max - 1;
+   else
+      deq->top--;
+
+   deq->count--;
+
+   return t;
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+void * dequeue_pop_bottom(struct dequeue * deq)
+   {
+   if (NULL == deq)
+      {
+      errno = EINVAL;
+      return NULL;
+      }
+
+   if (deq->count == 0)
+      return NULL;
+
+   void * t = deq->data[deq->bottom];
+
+   if (deq->bottom == deq->max - 1)
+      deq->bottom = 0;
+   else
+      deq->bottom++;
+
+   deq->count--;
+
+   return t;
+   }
+
+
+////////////////////////////////////////////////////////////////////////////////
+size_t dequeue_size(struct dequeue * deq)
+   {
+   if (NULL == deq)
+      {
+      errno = EINVAL;
+      return 0;
+      }
+   return deq->count;
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+void dequeue_delete(struct dequeue * deq)
+   {
+   if (NULL != deq)
+      {
+      free(deq->data);
+      free(deq);
+      }
+   }
diff -r 5af32066927f -r 392ce56806f9 src/dequeue.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/dequeue.h	Thu Sep 20 23:11:40 2012 -0500
@@ -0,0 +1,21 @@
+#ifndef DEQUEUE_H_
+#define DEQUEUE_H_
+
+struct dequeue
+   {
+   void ** data;
+   size_t max;
+   size_t bottom;
+   size_t top;
+   size_t count;
+   };
+
+struct dequeue * dequeue_new(size_t const size);
+void dequeue_delete(struct dequeue * deq);
+void * dequeue_push_top(struct dequeue * deq, void * elem);
+void * dequeue_pop_top(struct dequeue * deq);
+void * dequeue_push_bottom(struct dequeue * deq, void * elem);
+void * dequeue_pop_bottom(struct dequeue * deq);
+size_t dequeue_size(struct dequeue * deq);
+
+#endif
diff -r 5af32066927f -r 392ce56806f9 src/dequeue_test.c
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/dequeue_test.c	Thu Sep 20 23:11:40 2012 -0500
@@ -0,0 +1,102 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+#include "dequeue.h"
+
+#define MAX 10
+
+int main(int argc, char**argv)
+   {
+   int i, j;
+   int *ip;
+   struct dequeue * deq;
+
+   deq = dequeue_new(MAX);
+   if (NULL == deq)
+      {
+      perror("dequeue_new");
+      exit(EXIT_FAILURE);
+      }
+
+   // Fill the dequeue
+   for (i=0; i < MAX; i++)
+      {
+       ip = malloc(sizeof(int));
+      *ip = i;
+      if (NULL == dequeue_push_top(deq, (void *) ip))
+         perror("dequeue_push");
+      }
+
+   // remove 5 items
+   printf("dequeue size is %zd\n", dequeue_size(deq));
+   for (j=0; j < 5 && NULL != (ip = dequeue_pop_top(deq)); j++)
+      {
+      printf("%d\n", *ip);
+      free(ip);
+      }
+   printf("dequeue size is %zd\n", dequeue_size(deq));
+
+   // Overfill the dequeue
+   for (i=MAX; i < 2*MAX; i++)
+      {
+       ip = malloc(sizeof(int));
+      *ip = i;
+      if (NULL == dequeue_push_top(deq, (void *) ip))
+         {
+         perror("dequeue_push");
+         free(ip);
+         }
+      }
+
+   // Empty the dequeue
+   printf("dequeue size is %zd\n", dequeue_size(deq));
+   while (NULL != (ip = dequeue_pop_top(deq)))
+      {
+      printf("%d\n", *ip);
+      free(ip);
+      }
+   printf("dequeue size is %zd\n", dequeue_size(deq));
+
+   // Add 3 to top
+   for (i=0; i < 3; i++)
+      {
+       ip = malloc(sizeof(int));
+      *ip = i;
+      if (NULL == dequeue_push_top(deq, (void *) ip))
+         {
+         perror("dequeue_push");
+         free(ip);
+         }
+      }
+   // Add 3 to bottom
+   for (;i < 6; i++)
+      {
+       ip = malloc(sizeof(int));
+      *ip = i;
+      if (NULL == dequeue_push_bottom(deq, (void *) ip))
+         {
+         perror("dequeue_push");
+         free(ip);
+         }
+      }
+   // empty by alternation
+   printf("dequeue size is %zd\n", dequeue_size(deq));
+   while (0 != dequeue_size(deq))
+      {
+      if ((ip = dequeue_pop_top(deq)))
+         {
+         printf("%d\n", *ip);
+         free(ip);
+         }
+      if ((ip = dequeue_pop_bottom(deq)))
+         {
+         printf("%d\n", *ip);
+         free(ip);
+         }
+      }
+   printf("dequeue size is %zd\n", dequeue_size(deq));
+
+   dequeue_delete(deq);
+
+   exit(EXIT_SUCCESS);
+   }
diff -r 5af32066927f -r 392ce56806f9 src/queue.c
--- a/src/queue.c	Thu Sep 20 00:08:32 2012 -0500
+++ b/src/queue.c	Thu Sep 20 23:11:40 2012 -0500
@@ -12,21 +12,21 @@
       return NULL;
       }
 
-   struct queue * rb = malloc(sizeof(struct queue));
-   if (NULL == rb)
+   struct queue * queue = malloc(sizeof(struct queue));
+   if (NULL == queue)
       return NULL;
 
-   rb->start = rb->count = 0;
-   rb->max = max;
+   queue->start = queue->count = 0;
+   queue->max = max;
 
-   rb->data = calloc(rb->max, sizeof(void *));
-   if (NULL == rb->data)
+   queue->data = calloc(queue->max, sizeof(void *));
+   if (NULL == queue->data)
       {
-      free(rb);
+      free(queue);
       return NULL;
       }
 
-   return rb;
+   return queue;
    }
 
 ////////////////////////////////////////////////////////////////////////////////
@@ -34,62 +34,62 @@
 // NULL on error
 // elem on success and the buffer is not full
 // the overwritten element on success if the buffer was full
-void * queue_push(struct queue * rb, void * elem)
+void * queue_push(struct queue * queue, void * elem)
    {
-   if ((NULL == rb) || (NULL == elem))
+   if ((NULL == queue) || (NULL == elem))
       {
       errno = EINVAL;
       return NULL;
       }
 
-   if (rb->count == rb->max)
+   if (queue->count == queue->max)
       {
       errno = ENOMEM;
       return NULL;
       }
 
-   size_t end = (rb->start + rb->count) % rb->max;
+   size_t end = (queue->start + queue->count) % queue->max;
 
-   rb->data[end] = elem;
-   rb->count++;
+   queue->data[end] = elem;
+   queue->count++;
 
    return elem;
    }
 
 ////////////////////////////////////////////////////////////////////////////////
-void * queue_pop(struct queue * rb)
+void * queue_pop(struct queue * queue)
    {
-   if (NULL == rb)
+   if (NULL == queue)
       {
       errno = EINVAL;
       return NULL;
       }
 
-   if (0 == rb->count)
+   if (0 == queue->count)
       return NULL;
 
-   void * t = rb->data[rb->start];
-   rb->count--;
-   rb->start = (rb->start + 1) % rb->max;
+   void * t = queue->data[queue->start];
+   queue->count--;
+   queue->start = (queue->start + 1) % queue->max;
 
    return t;
    }
 
 ////////////////////////////////////////////////////////////////////////////////
-size_t queue_size(struct queue * rb)
+size_t queue_size(struct queue * queue)
    {
-   if (NULL == rb)
+   if (NULL == queue)
       {
       errno = EINVAL;
       return -1;
       }
 
-   return rb->count;
+   return queue->count;
    }
 
 ////////////////////////////////////////////////////////////////////////////////
-void queue_delete(struct queue * rb)
+void queue_delete(struct queue * queue)
    {
-   if (NULL != rb) free(rb->data);
-   free(rb);
+   if (NULL != queue) free(queue->data);
+   free(queue);
    }
diff -r 5af32066927f -r 392ce56806f9 src/queue.h
--- a/src/queue.h	Thu Sep 20 00:08:32 2012 -0500
+++ b/src/queue.h	Thu Sep 20 23:11:40 2012 -0500
@@ -10,9 +10,9 @@
    };
 
 struct queue * queue_new(size_t const size);
-void queue_delete(struct queue * rb);
-void * queue_push(struct queue * rb, void * elem);
-void * queue_pop(struct queue * rb);
-size_t queue_size(struct queue * rb);
+void queue_delete(struct queue * queue);
+void * queue_push(struct queue * queue, void * elem);
+void * queue_pop(struct queue * queue);
+size_t queue_size(struct queue * queue);
 
 #endif
diff -r 5af32066927f -r 392ce56806f9 src/queue_test.c
--- a/src/queue_test.c	Thu Sep 20 00:08:32 2012 -0500
+++ b/src/queue_test.c	Thu Sep 20 23:11:40 2012 -0500
@@ -10,7 +10,6 @@
    int i, j;
    int *ip;
    struct queue * q;
-   void * p;
 
    q = queue_new(MAX);
    if (NULL == q)