1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/.hgignore	Thu Sep 20 23:11:40 2012 -0500
     1.3 @@ -0,0 +1,5 @@
     1.4 +syntax: glob
     1.5 +
     1.6 +build*/*
     1.7 +*~
     1.8 +

     2.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     2.2 +++ b/CMakeLists.txt	Thu Sep 20 23:11:40 2012 -0500
     2.3 @@ -0,0 +1,64 @@
     2.4 +cmake_minimum_required (VERSION 2.6 FATAL_ERROR)
     2.5 +#set (CMAKE_VERBOSE_MAKEFILE ON)
     2.6 +
     2.7 +project (data_structures)
     2.8 +
     2.9 +################################################################################
    2.10 +# Ensure that we are not building in our source directories.
    2.11 +
    2.12 +set (Build_Dir_OK "TRUE")
    2.13 +string (REGEX MATCH "^${CMAKE_SOURCE_DIR}" In_Sub_Dir ${CMAKE_BINARY_DIR})
    2.14 +if (In_Sub_Dir)
    2.15 +  string (REGEX MATCH "^${CMAKE_SOURCE_DIR}/build" In_Build_Dir ${CMAKE_BINARY_DIR})
    2.16 +  if (NOT In_Build_Dir)
    2.17 +    set (Build_Dir_OK "FALSE")
    2.18 +  endif ()
    2.19 +endif ()
    2.20 +
    2.21 +if (NOT Build_Dir_OK)
    2.22 +  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'.")
    2.23 +endif ()
    2.24 +
    2.25 +
    2.26 +if (CMAKE_BUILD_TYPE STREQUAL "")
    2.27 +  # CMake defaults to leaving CMAKE_BUILD_TYPE empty. This messes up differentiation between debug and release builds.               
    2.28 +  set (CMAKE_BUILD_TYPE "RelWithDebInfo" CACHE STRING "Choose the type of build, options are: None Debug Release RelWithDebInfo MinSizeRel." FORCE)
    2.29 +endif ()
    2.30 +
    2.31 +
    2.32 +if (CMAKE_COMPILER_IS_GNUCXX)
    2.33 +  add_definitions(-pedantic -Wall -std=gnu99)
    2.34 +endif ()
    2.35 +
    2.36 +
    2.37 +################################################################################
    2.38 +
    2.39 +option(Option_Profile_Program "Build for gprof profiling." OFF)
    2.40 +if (Option_Profile_Program)
    2.41 +  add_definitions(-pg)
    2.42 +  set (CMAKE_EXE_LINKER_FLAGS "${CMAKE_EXE_LINKER_FLAGS} -pg")
    2.43 +endif ()
    2.44 +
    2.45 +
    2.46 +################################################################################
    2.47 +
    2.48 +set (stack_SRCS src/stack.h src/stack.c src/stack_test.c)
    2.49 +add_executable (stack_test
    2.50 +  ${stack_SRCS}
    2.51 +  )
    2.52 +
    2.53 +set (ring_buffer_SRCS src/ring_buffer.h src/ring_buffer.c src/ring_buffer_test.c)
    2.54 +add_executable (ring_buffer_test
    2.55 +  ${ring_buffer_SRCS}
    2.56 +  )
    2.57 +
    2.58 +set (queue_SRCS src/queue.h src/queue.c src/queue_test.c)
    2.59 +add_executable (queue_test
    2.60 +  ${queue_SRCS}
    2.61 +  )
    2.62 +
    2.63 +set (dequeue_SRCS src/dequeue.h src/dequeue.c src/dequeue_test.c)
    2.64 +add_executable (dequeue_test
    2.65 +  ${dequeue_SRCS}
    2.66 +  )
    2.67 +

     3.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     3.2 +++ b/src/dequeue.c	Thu Sep 20 23:11:40 2012 -0500
     3.3 @@ -0,0 +1,156 @@
     3.4 +#include <stdlib.h>
     3.5 +#include <errno.h>
     3.6 +
     3.7 +#include "dequeue.h"
     3.8 +
     3.9 +////////////////////////////////////////////////////////////////////////////////
    3.10 +struct dequeue * dequeue_new(size_t const max)
    3.11 +   {
    3.12 +   if (max < 1)
    3.13 +      {
    3.14 +      errno = EINVAL;
    3.15 +      return NULL;
    3.16 +      }
    3.17 +
    3.18 +   struct dequeue * deq = malloc(sizeof(struct dequeue));
    3.19 +   if (NULL == deq)
    3.20 +      return NULL;
    3.21 +
    3.22 +   deq->bottom = deq->top = deq->count = 0;
    3.23 +   deq->max = max;
    3.24 +
    3.25 +   deq->data = calloc(deq->max, sizeof(void *));
    3.26 +   if (NULL == deq->data)
    3.27 +      {
    3.28 +      free(deq);
    3.29 +      return NULL;
    3.30 +      }
    3.31 +
    3.32 +   return deq;
    3.33 +   }
    3.34 +
    3.35 +////////////////////////////////////////////////////////////////////////////////
    3.36 +// Returns:
    3.37 +// NULL on error
    3.38 +// elem on success and the buffer is not full
    3.39 +// the overwritten element on success if the buffer was full
    3.40 +void * dequeue_push_top(struct dequeue * deq, void * elem)
    3.41 +   {
    3.42 +   if ((NULL == deq) || (NULL == elem))
    3.43 +      {
    3.44 +      errno = EINVAL;
    3.45 +      return NULL;
    3.46 +      }
    3.47 +
    3.48 +   if (deq->count == deq->max)
    3.49 +      {
    3.50 +      errno = ENOMEM;
    3.51 +      return NULL;
    3.52 +      }
    3.53 +
    3.54 +   if (deq->max - 1 == deq->top)
    3.55 +      deq->top = 0;
    3.56 +   else
    3.57 +      deq->top++;
    3.58 +
    3.59 +   deq->data[deq->top] = elem;
    3.60 +   deq->count++;
    3.61 +
    3.62 +   return elem;
    3.63 +   }
    3.64 +
    3.65 +////////////////////////////////////////////////////////////////////////////////
    3.66 +void * dequeue_push_bottom(struct dequeue * deq, void * elem)
    3.67 +   {
    3.68 +   if ((NULL == deq) || (NULL == elem))
    3.69 +      {
    3.70 +      errno = EINVAL;
    3.71 +      return NULL;
    3.72 +      }
    3.73 +
    3.74 +   if (deq->count == deq->max)
    3.75 +      {
    3.76 +      errno = ENOMEM;
    3.77 +      return NULL;
    3.78 +      }
    3.79 +
    3.80 +   if (0 == deq->bottom)
    3.81 +      deq->bottom = deq->max - 1;
    3.82 +   else
    3.83 +      deq->bottom--;
    3.84 +
    3.85 +   deq->data[deq->bottom] = elem;
    3.86 +   deq->count++;
    3.87 +
    3.88 +   return elem;
    3.89 +   }
    3.90 +
    3.91 +////////////////////////////////////////////////////////////////////////////////
    3.92 +void * dequeue_pop_top(struct dequeue * deq)
    3.93 +   {
    3.94 +   if (NULL == deq)
    3.95 +      {
    3.96 +      errno = EINVAL;
    3.97 +      return NULL;
    3.98 +      }
    3.99 +
   3.100 +   if (deq->count == 0)
   3.101 +      return NULL;
   3.102 +
   3.103 +   void * t = deq->data[deq->top];
   3.104 +
   3.105 +   if (deq->top == 0)
   3.106 +      deq->top = deq->max - 1;
   3.107 +   else
   3.108 +      deq->top--;
   3.109 +
   3.110 +   deq->count--;
   3.111 +
   3.112 +   return t;
   3.113 +   }
   3.114 +
   3.115 +////////////////////////////////////////////////////////////////////////////////
   3.116 +void * dequeue_pop_bottom(struct dequeue * deq)
   3.117 +   {
   3.118 +   if (NULL == deq)
   3.119 +      {
   3.120 +      errno = EINVAL;
   3.121 +      return NULL;
   3.122 +      }
   3.123 +
   3.124 +   if (deq->count == 0)
   3.125 +      return NULL;
   3.126 +
   3.127 +   void * t = deq->data[deq->bottom];
   3.128 +
   3.129 +   if (deq->bottom == deq->max - 1)
   3.130 +      deq->bottom = 0;
   3.131 +   else
   3.132 +      deq->bottom++;
   3.133 +
   3.134 +   deq->count--;
   3.135 +
   3.136 +   return t;
   3.137 +   }
   3.138 +
   3.139 +
   3.140 +////////////////////////////////////////////////////////////////////////////////
   3.141 +size_t dequeue_size(struct dequeue * deq)
   3.142 +   {
   3.143 +   if (NULL == deq)
   3.144 +      {
   3.145 +      errno = EINVAL;
   3.146 +      return 0;
   3.147 +      }
   3.148 +   return deq->count;
   3.149 +   }
   3.150 +
   3.151 +////////////////////////////////////////////////////////////////////////////////
   3.152 +void dequeue_delete(struct dequeue * deq)
   3.153 +   {
   3.154 +   if (NULL != deq)
   3.155 +      {
   3.156 +      free(deq->data);
   3.157 +      free(deq);
   3.158 +      }
   3.159 +   }

     4.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     4.2 +++ b/src/dequeue.h	Thu Sep 20 23:11:40 2012 -0500
     4.3 @@ -0,0 +1,21 @@
     4.4 +#ifndef DEQUEUE_H_
     4.5 +#define DEQUEUE_H_
     4.6 +
     4.7 +struct dequeue
     4.8 +   {
     4.9 +   void ** data;
    4.10 +   size_t max;
    4.11 +   size_t bottom;
    4.12 +   size_t top;
    4.13 +   size_t count;
    4.14 +   };
    4.15 +
    4.16 +struct dequeue * dequeue_new(size_t const size);
    4.17 +void dequeue_delete(struct dequeue * deq);
    4.18 +void * dequeue_push_top(struct dequeue * deq, void * elem);
    4.19 +void * dequeue_pop_top(struct dequeue * deq);
    4.20 +void * dequeue_push_bottom(struct dequeue * deq, void * elem);
    4.21 +void * dequeue_pop_bottom(struct dequeue * deq);
    4.22 +size_t dequeue_size(struct dequeue * deq);
    4.23 +
    4.24 +#endif

     5.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     5.2 +++ b/src/dequeue_test.c	Thu Sep 20 23:11:40 2012 -0500
     5.3 @@ -0,0 +1,102 @@
     5.4 +#include <stdio.h>
     5.5 +#include <stdlib.h>
     5.6 +
     5.7 +#include "dequeue.h"
     5.8 +
     5.9 +#define MAX 10
    5.10 +
    5.11 +int main(int argc, char**argv)
    5.12 +   {
    5.13 +   int i, j;
    5.14 +   int *ip;
    5.15 +   struct dequeue * deq;
    5.16 +
    5.17 +   deq = dequeue_new(MAX);
    5.18 +   if (NULL == deq)
    5.19 +      {
    5.20 +      perror("dequeue_new");
    5.21 +      exit(EXIT_FAILURE);
    5.22 +      }
    5.23 +
    5.24 +   // Fill the dequeue
    5.25 +   for (i=0; i < MAX; i++)
    5.26 +      {
    5.27 +       ip = malloc(sizeof(int));
    5.28 +      *ip = i;
    5.29 +      if (NULL == dequeue_push_top(deq, (void *) ip))
    5.30 +         perror("dequeue_push");
    5.31 +      }
    5.32 +
    5.33 +   // remove 5 items
    5.34 +   printf("dequeue size is %zd\n", dequeue_size(deq));
    5.35 +   for (j=0; j < 5 && NULL != (ip = dequeue_pop_top(deq)); j++)
    5.36 +      {
    5.37 +      printf("%d\n", *ip);
    5.38 +      free(ip);
    5.39 +      }
    5.40 +   printf("dequeue size is %zd\n", dequeue_size(deq));
    5.41 +
    5.42 +   // Overfill the dequeue
    5.43 +   for (i=MAX; i < 2*MAX; i++)
    5.44 +      {
    5.45 +       ip = malloc(sizeof(int));
    5.46 +      *ip = i;
    5.47 +      if (NULL == dequeue_push_top(deq, (void *) ip))
    5.48 +         {
    5.49 +         perror("dequeue_push");
    5.50 +         free(ip);
    5.51 +         }
    5.52 +      }
    5.53 +
    5.54 +   // Empty the dequeue
    5.55 +   printf("dequeue size is %zd\n", dequeue_size(deq));
    5.56 +   while (NULL != (ip = dequeue_pop_top(deq)))
    5.57 +      {
    5.58 +      printf("%d\n", *ip);
    5.59 +      free(ip);
    5.60 +      }
    5.61 +   printf("dequeue size is %zd\n", dequeue_size(deq));
    5.62 +
    5.63 +   // Add 3 to top
    5.64 +   for (i=0; i < 3; i++)
    5.65 +      {
    5.66 +       ip = malloc(sizeof(int));
    5.67 +      *ip = i;
    5.68 +      if (NULL == dequeue_push_top(deq, (void *) ip))
    5.69 +         {
    5.70 +         perror("dequeue_push");
    5.71 +         free(ip);
    5.72 +         }
    5.73 +      }
    5.74 +   // Add 3 to bottom
    5.75 +   for (;i < 6; i++)
    5.76 +      {
    5.77 +       ip = malloc(sizeof(int));
    5.78 +      *ip = i;
    5.79 +      if (NULL == dequeue_push_bottom(deq, (void *) ip))
    5.80 +         {
    5.81 +         perror("dequeue_push");
    5.82 +         free(ip);
    5.83 +         }
    5.84 +      }
    5.85 +   // empty by alternation
    5.86 +   printf("dequeue size is %zd\n", dequeue_size(deq));
    5.87 +   while (0 != dequeue_size(deq))
    5.88 +      {
    5.89 +      if ((ip = dequeue_pop_top(deq)))
    5.90 +         {
    5.91 +         printf("%d\n", *ip);
    5.92 +         free(ip);
    5.93 +         }
    5.94 +      if ((ip = dequeue_pop_bottom(deq)))
    5.95 +         {
    5.96 +         printf("%d\n", *ip);
    5.97 +         free(ip);
    5.98 +         }
    5.99 +      }
   5.100 +   printf("dequeue size is %zd\n", dequeue_size(deq));
   5.101 +
   5.102 +   dequeue_delete(deq);
   5.103 +
   5.104 +   exit(EXIT_SUCCESS);
   5.105 +   }

     6.1 --- a/src/queue.c	Thu Sep 20 00:08:32 2012 -0500
     6.2 +++ b/src/queue.c	Thu Sep 20 23:11:40 2012 -0500
     6.3 @@ -12,21 +12,21 @@
     6.4        return NULL;
     6.5        }
     6.6  
     6.7 -   struct queue * rb = malloc(sizeof(struct queue));
     6.8 -   if (NULL == rb)
     6.9 +   struct queue * queue = malloc(sizeof(struct queue));
    6.10 +   if (NULL == queue)
    6.11        return NULL;
    6.12  
    6.13 -   rb->start = rb->count = 0;
    6.14 -   rb->max = max;
    6.15 +   queue->start = queue->count = 0;
    6.16 +   queue->max = max;
    6.17  
    6.18 -   rb->data = calloc(rb->max, sizeof(void *));
    6.19 -   if (NULL == rb->data)
    6.20 +   queue->data = calloc(queue->max, sizeof(void *));
    6.21 +   if (NULL == queue->data)
    6.22        {
    6.23 -      free(rb);
    6.24 +      free(queue);
    6.25        return NULL;
    6.26        }
    6.27  
    6.28 -   return rb;
    6.29 +   return queue;
    6.30     }
    6.31  
    6.32  ////////////////////////////////////////////////////////////////////////////////
    6.33 @@ -34,62 +34,62 @@
    6.34  // NULL on error
    6.35  // elem on success and the buffer is not full
    6.36  // the overwritten element on success if the buffer was full
    6.37 -void * queue_push(struct queue * rb, void * elem)
    6.38 +void * queue_push(struct queue * queue, void * elem)
    6.39     {
    6.40 -   if ((NULL == rb) || (NULL == elem))
    6.41 +   if ((NULL == queue) || (NULL == elem))
    6.42        {
    6.43        errno = EINVAL;
    6.44        return NULL;
    6.45        }
    6.46  
    6.47 -   if (rb->count == rb->max)
    6.48 +   if (queue->count == queue->max)
    6.49        {
    6.50        errno = ENOMEM;
    6.51        return NULL;
    6.52        }
    6.53  
    6.54 -   size_t end = (rb->start + rb->count) % rb->max;
    6.55 +   size_t end = (queue->start + queue->count) % queue->max;
    6.56  
    6.57 -   rb->data[end] = elem;
    6.58 -   rb->count++;
    6.59 +   queue->data[end] = elem;
    6.60 +   queue->count++;
    6.61  
    6.62     return elem;
    6.63     }
    6.64  
    6.65  ////////////////////////////////////////////////////////////////////////////////
    6.66 -void * queue_pop(struct queue * rb)
    6.67 +void * queue_pop(struct queue * queue)
    6.68     {
    6.69 -   if (NULL == rb)
    6.70 +   if (NULL == queue)
    6.71        {
    6.72        errno = EINVAL;
    6.73        return NULL;
    6.74        }
    6.75  
    6.76 -   if (0 == rb->count)
    6.77 +   if (0 == queue->count)
    6.78        return NULL;
    6.79  
    6.80 -   void * t = rb->data[rb->start];
    6.81 -   rb->count--;
    6.82 -   rb->start = (rb->start + 1) % rb->max;
    6.83 +   void * t = queue->data[queue->start];
    6.84 +   queue->count--;
    6.85 +   queue->start = (queue->start + 1) % queue->max;
    6.86  
    6.87     return t;
    6.88     }
    6.89  
    6.90  ////////////////////////////////////////////////////////////////////////////////
    6.91 -size_t queue_size(struct queue * rb)
    6.92 +size_t queue_size(struct queue * queue)
    6.93     {
    6.94 -   if (NULL == rb)
    6.95 +   if (NULL == queue)
    6.96        {
    6.97        errno = EINVAL;
    6.98        return -1;
    6.99        }
   6.100  
   6.101 -   return rb->count;
   6.102 +   return queue->count;
   6.103     }
   6.104  
   6.105  ////////////////////////////////////////////////////////////////////////////////
   6.106 -void queue_delete(struct queue * rb)
   6.107 +void queue_delete(struct queue * queue)
   6.108     {
   6.109 -   if (NULL != rb) free(rb->data);
   6.110 -   free(rb);
   6.111 +   if (NULL != queue) free(queue->data);
   6.112 +   free(queue);
   6.113     }

     7.1 --- a/src/queue.h	Thu Sep 20 00:08:32 2012 -0500
     7.2 +++ b/src/queue.h	Thu Sep 20 23:11:40 2012 -0500
     7.3 @@ -10,9 +10,9 @@
     7.4     };
     7.5  
     7.6  struct queue * queue_new(size_t const size);
     7.7 -void queue_delete(struct queue * rb);
     7.8 -void * queue_push(struct queue * rb, void * elem);
     7.9 -void * queue_pop(struct queue * rb);
    7.10 -size_t queue_size(struct queue * rb);
    7.11 +void queue_delete(struct queue * queue);
    7.12 +void * queue_push(struct queue * queue, void * elem);
    7.13 +void * queue_pop(struct queue * queue);
    7.14 +size_t queue_size(struct queue * queue);
    7.15  
    7.16  #endif

     8.1 --- a/src/queue_test.c	Thu Sep 20 00:08:32 2012 -0500
     8.2 +++ b/src/queue_test.c	Thu Sep 20 23:11:40 2012 -0500
     8.3 @@ -10,7 +10,6 @@
     8.4     int i, j;
     8.5     int *ip;
     8.6     struct queue * q;
     8.7 -   void * p;
     8.8  
     8.9     q = queue_new(MAX);
    8.10     if (NULL == q)