1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/src/queue.c	Thu Sep 20 00:08:32 2012 -0500
     1.3 @@ -0,0 +1,95 @@
     1.4 +#include <stdlib.h>
     1.5 +#include <errno.h>
     1.6 +
     1.7 +#include "queue.h"
     1.8 +
     1.9 +////////////////////////////////////////////////////////////////////////////////
    1.10 +struct queue * queue_new(size_t const max)
    1.11 +   {
    1.12 +   if (max < 1)
    1.13 +      {
    1.14 +      errno = EINVAL;
    1.15 +      return NULL;
    1.16 +      }
    1.17 +
    1.18 +   struct queue * rb = malloc(sizeof(struct queue));
    1.19 +   if (NULL == rb)
    1.20 +      return NULL;
    1.21 +
    1.22 +   rb->start = rb->count = 0;
    1.23 +   rb->max = max;
    1.24 +
    1.25 +   rb->data = calloc(rb->max, sizeof(void *));
    1.26 +   if (NULL == rb->data)
    1.27 +      {
    1.28 +      free(rb);
    1.29 +      return NULL;
    1.30 +      }
    1.31 +
    1.32 +   return rb;
    1.33 +   }
    1.34 +
    1.35 +////////////////////////////////////////////////////////////////////////////////
    1.36 +// Returns:
    1.37 +// NULL on error
    1.38 +// elem on success and the buffer is not full
    1.39 +// the overwritten element on success if the buffer was full
    1.40 +void * queue_push(struct queue * rb, void * elem)
    1.41 +   {
    1.42 +   if ((NULL == rb) || (NULL == elem))
    1.43 +      {
    1.44 +      errno = EINVAL;
    1.45 +      return NULL;
    1.46 +      }
    1.47 +
    1.48 +   if (rb->count == rb->max)
    1.49 +      {
    1.50 +      errno = ENOMEM;
    1.51 +      return NULL;
    1.52 +      }
    1.53 +
    1.54 +   size_t end = (rb->start + rb->count) % rb->max;
    1.55 +
    1.56 +   rb->data[end] = elem;
    1.57 +   rb->count++;
    1.58 +
    1.59 +   return elem;
    1.60 +   }
    1.61 +
    1.62 +////////////////////////////////////////////////////////////////////////////////
    1.63 +void * queue_pop(struct queue * rb)
    1.64 +   {
    1.65 +   if (NULL == rb)
    1.66 +      {
    1.67 +      errno = EINVAL;
    1.68 +      return NULL;
    1.69 +      }
    1.70 +
    1.71 +   if (0 == rb->count)
    1.72 +      return NULL;
    1.73 +
    1.74 +   void * t = rb->data[rb->start];
    1.75 +   rb->count--;
    1.76 +   rb->start = (rb->start + 1) % rb->max;
    1.77 +
    1.78 +   return t;
    1.79 +   }
    1.80 +
    1.81 +////////////////////////////////////////////////////////////////////////////////
    1.82 +size_t queue_size(struct queue * rb)
    1.83 +   {
    1.84 +   if (NULL == rb)
    1.85 +      {
    1.86 +      errno = EINVAL;
    1.87 +      return -1;
    1.88 +      }
    1.89 +
    1.90 +   return rb->count;
    1.91 +   }
    1.92 +
    1.93 +////////////////////////////////////////////////////////////////////////////////
    1.94 +void queue_delete(struct queue * rb)
    1.95 +   {
    1.96 +   if (NULL != rb) free(rb->data);
    1.97 +   free(rb);
    1.98 +   }

     2.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     2.2 +++ b/src/queue.h	Thu Sep 20 00:08:32 2012 -0500
     2.3 @@ -0,0 +1,18 @@
     2.4 +#ifndef QUEUE_
     2.5 +#define QUEUE_
     2.6 +
     2.7 +struct queue
     2.8 +   {
     2.9 +   void ** data;
    2.10 +   size_t max;
    2.11 +   size_t start;
    2.12 +   size_t count;
    2.13 +   };
    2.14 +
    2.15 +struct queue * queue_new(size_t const size);
    2.16 +void queue_delete(struct queue * rb);
    2.17 +void * queue_push(struct queue * rb, void * elem);
    2.18 +void * queue_pop(struct queue * rb);
    2.19 +size_t queue_size(struct queue * rb);
    2.20 +
    2.21 +#endif

     3.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     3.2 +++ b/src/queue_test.c	Thu Sep 20 00:08:32 2012 -0500
     3.3 @@ -0,0 +1,61 @@
     3.4 +#include <stdio.h>
     3.5 +#include <stdlib.h>
     3.6 +
     3.7 +#include "queue.h"
     3.8 +
     3.9 +#define MAX 10
    3.10 +
    3.11 +int main(int argc, char**argv)
    3.12 +   {
    3.13 +   int i, j;
    3.14 +   int *ip;
    3.15 +   struct queue * q;
    3.16 +   void * p;
    3.17 +
    3.18 +   q = queue_new(MAX);
    3.19 +   if (NULL == q)
    3.20 +      {
    3.21 +      perror("queue_new");
    3.22 +      exit(EXIT_FAILURE);
    3.23 +      }
    3.24 +
    3.25 +   // Fill the queue
    3.26 +   for (i=0; i < MAX; i++)
    3.27 +      {
    3.28 +       ip = malloc(sizeof(int));
    3.29 +      *ip = i;
    3.30 +      if (NULL == queue_push(q, (void *) ip))
    3.31 +         perror("queue_push");
    3.32 +      }
    3.33 +
    3.34 +   // remove 5 items
    3.35 +   printf("queue size is %zd\n", queue_size(q));
    3.36 +   for (j=0; j < 5 && NULL != (ip = queue_pop(q)); j++)
    3.37 +      {
    3.38 +      printf("%d\n", *ip);
    3.39 +      free(ip);
    3.40 +      }
    3.41 +   printf("queue size is %zd\n", queue_size(q));
    3.42 +
    3.43 +   // Overfill the queue
    3.44 +   for (i=MAX; i < 2*MAX; i++)
    3.45 +      {
    3.46 +       ip = malloc(sizeof(int));
    3.47 +      *ip = i;
    3.48 +      if (NULL == queue_push(q, (void *) ip))
    3.49 +         perror("queue_push");
    3.50 +      }
    3.51 +
    3.52 +   // Empty the queue
    3.53 +   printf("queue size is %zd\n", queue_size(q));
    3.54 +   while (NULL != (ip = queue_pop(q)))
    3.55 +      {
    3.56 +      printf("%d\n", *ip);
    3.57 +      free(ip);
    3.58 +      }
    3.59 +   printf("queue size is %zd\n", queue_size(q));
    3.60 +
    3.61 +   queue_delete(q);
    3.62 +
    3.63 +   exit(EXIT_SUCCESS);
    3.64 +   }

     4.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     4.2 +++ b/src/ring_buffer.c	Thu Sep 20 00:08:32 2012 -0500
     4.3 @@ -0,0 +1,95 @@
     4.4 +#include <stdlib.h>
     4.5 +#include <errno.h>
     4.6 +
     4.7 +#include "ring_buffer.h"
     4.8 +
     4.9 +////////////////////////////////////////////////////////////////////////////////
    4.10 +struct ring_buffer * ring_buffer_new(size_t const max)
    4.11 +   {
    4.12 +   if (max < 1)
    4.13 +      {
    4.14 +      errno = EINVAL;
    4.15 +      return NULL;
    4.16 +      }
    4.17 +
    4.18 +   struct ring_buffer * rb = malloc(sizeof(struct ring_buffer));
    4.19 +   if (NULL == rb)
    4.20 +      return NULL;
    4.21 +
    4.22 +   rb->start = rb->count = 0;
    4.23 +   rb->max = max;
    4.24 +
    4.25 +   rb->data = calloc(rb->max, sizeof(void *));
    4.26 +   if (NULL == rb->data)
    4.27 +      {
    4.28 +      free(rb);
    4.29 +      return NULL;
    4.30 +      }
    4.31 +
    4.32 +   return rb;
    4.33 +   }
    4.34 +
    4.35 +////////////////////////////////////////////////////////////////////////////////
    4.36 +// Returns:
    4.37 +// NULL on error
    4.38 +// elem on success and the buffer is not full
    4.39 +// the overwritten element on success if the buffer was full
    4.40 +void * ring_buffer_write(struct ring_buffer * rb, void * elem)
    4.41 +   {
    4.42 +   if ((NULL == rb) || (NULL == elem))
    4.43 +      {
    4.44 +      errno = EINVAL;
    4.45 +      return NULL;
    4.46 +      }
    4.47 +
    4.48 +   size_t end = rb->start + rb->count;
    4.49 +   void * ret = rb->data[end % rb->max];
    4.50 +   rb->data[end % rb->max] = elem;
    4.51 +   if (rb->count == rb->max)
    4.52 +      rb->start = (rb->start + 1) % rb->max;
    4.53 +   else
    4.54 +      {
    4.55 +      rb->count++;
    4.56 +      ret = elem;
    4.57 +      }
    4.58 +
    4.59 +   return ret;
    4.60 +   }
    4.61 +
    4.62 +////////////////////////////////////////////////////////////////////////////////
    4.63 +void * ring_buffer_read(struct ring_buffer * rb)
    4.64 +   {
    4.65 +   if (NULL == rb)
    4.66 +      {
    4.67 +      errno = EINVAL;
    4.68 +      return NULL;
    4.69 +      }
    4.70 +
    4.71 +   if (0 == rb->count)
    4.72 +      return NULL;
    4.73 +
    4.74 +   void * t = rb->data[rb->start];
    4.75 +   rb->count--;
    4.76 +   rb->start = (rb->start + 1) % rb->max;
    4.77 +
    4.78 +   return t;
    4.79 +   }
    4.80 +
    4.81 +////////////////////////////////////////////////////////////////////////////////
    4.82 +size_t ring_buffer_size(struct ring_buffer * rb)
    4.83 +   {
    4.84 +   if (NULL == rb)
    4.85 +      {
    4.86 +      errno = EINVAL;
    4.87 +      return -1;
    4.88 +      }
    4.89 +
    4.90 +   return rb->count;
    4.91 +   }
    4.92 +
    4.93 +////////////////////////////////////////////////////////////////////////////////
    4.94 +void ring_buffer_delete(struct ring_buffer * rb)
    4.95 +   {
    4.96 +   if (NULL != rb) free(rb->data);
    4.97 +   free(rb);
    4.98 +   }

     5.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     5.2 +++ b/src/ring_buffer.h	Thu Sep 20 00:08:32 2012 -0500
     5.3 @@ -0,0 +1,18 @@
     5.4 +#ifndef RING_BUFFER_
     5.5 +#define RING_BUFFER_
     5.6 +
     5.7 +struct ring_buffer
     5.8 +   {
     5.9 +   void ** data;
    5.10 +   size_t max;
    5.11 +   size_t start;
    5.12 +   size_t count;
    5.13 +   };
    5.14 +
    5.15 +struct ring_buffer * ring_buffer_new(size_t const size);
    5.16 +void ring_buffer_delete(struct ring_buffer * rb);
    5.17 +void * ring_buffer_write(struct ring_buffer * rb, void * elem);
    5.18 +void * ring_buffer_read(struct ring_buffer * rb);
    5.19 +size_t ring_buffer_size(struct ring_buffer * rb);
    5.20 +
    5.21 +#endif

     6.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     6.2 +++ b/src/ring_buffer_test.c	Thu Sep 20 00:08:32 2012 -0500
     6.3 @@ -0,0 +1,63 @@
     6.4 +#include <stdio.h>
     6.5 +#include <stdlib.h>
     6.6 +
     6.7 +#include "ring_buffer.h"
     6.8 +
     6.9 +#define MAX 10
    6.10 +
    6.11 +int main(int argc, char**argv)
    6.12 +   {
    6.13 +   int i, j;
    6.14 +   int *ip;
    6.15 +   struct ring_buffer * rb;
    6.16 +   void * p;
    6.17 +   
    6.18 +   rb = ring_buffer_new(MAX);
    6.19 +   if (NULL == rb)
    6.20 +      {
    6.21 +      perror("ring_buffer_new: ");
    6.22 +      exit(EXIT_FAILURE);
    6.23 +      }
    6.24 +
    6.25 +   // Add 10 items
    6.26 +   for (i=0; i < MAX; i++)
    6.27 +      {
    6.28 +       ip = malloc(sizeof(int));
    6.29 +      *ip = i;
    6.30 +      p = ring_buffer_write(rb, (void *) ip);
    6.31 +      if ((p != NULL) && (p != ip))
    6.32 +         free(p);
    6.33 +      }
    6.34 +
    6.35 +   // remove 5 items
    6.36 +   printf("ring_buffer size is %zd\n", ring_buffer_size(rb));
    6.37 +   for (j=0; j < 5 && NULL != (ip = ring_buffer_read(rb)); j++)
    6.38 +      {
    6.39 +      printf("%d\n", *ip);
    6.40 +      free(ip);
    6.41 +      }
    6.42 +   printf("ring_buffer size is %zd\n", ring_buffer_size(rb));
    6.43 +
    6.44 +   // add 8 more items
    6.45 +   for (j = 0; j < MAX-2; j++, i++)
    6.46 +      {
    6.47 +       ip = malloc(sizeof(int));
    6.48 +      *ip = i;
    6.49 +      p = ring_buffer_write(rb, (void *) ip);
    6.50 +      if ((p != NULL) && (p != ip))
    6.51 +         free(p);
    6.52 +      }
    6.53 +
    6.54 +   // remove all items
    6.55 +   printf("ring_buffer size is %zd\n", ring_buffer_size(rb));
    6.56 +   while (NULL != (ip = ring_buffer_read(rb)))
    6.57 +      {
    6.58 +      printf("%d\n", *ip);
    6.59 +      free(ip);
    6.60 +      }
    6.61 +   printf("ring_buffer size is %zd\n", ring_buffer_size(rb));
    6.62 +
    6.63 +   ring_buffer_delete(rb);
    6.64 +
    6.65 +   exit(EXIT_SUCCESS);
    6.66 +   }

     7.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     7.2 +++ b/src/stack.c	Thu Sep 20 00:08:32 2012 -0500
     7.3 @@ -0,0 +1,84 @@
     7.4 +#include <stdlib.h>
     7.5 +#include <errno.h>
     7.6 +
     7.7 +#include "stack.h"
     7.8 +
     7.9 +////////////////////////////////////////////////////////////////////////////////
    7.10 +struct stack * stack_new(size_t const max)
    7.11 +   {
    7.12 +   if (max < 1)
    7.13 +      {
    7.14 +      errno = EINVAL;
    7.15 +      return NULL;
    7.16 +      }
    7.17 +
    7.18 +   struct stack * s = malloc(sizeof(struct stack));
    7.19 +   if (NULL == s)
    7.20 +      return NULL;
    7.21 +
    7.22 +   s->size = 0;
    7.23 +   s->max = max;
    7.24 +
    7.25 +   s->data = calloc(s->max, sizeof(void *));
    7.26 +   if (NULL == s->data)
    7.27 +      {
    7.28 +      free(s);
    7.29 +      return NULL;
    7.30 +      }
    7.31 +
    7.32 +   return s;
    7.33 +   }
    7.34 +
    7.35 +////////////////////////////////////////////////////////////////////////////////
    7.36 +void * stack_push(struct stack * s, void * elem)
    7.37 +   {
    7.38 +   if ((NULL == s) || (NULL == elem))
    7.39 +      {
    7.40 +      errno = EINVAL;
    7.41 +      return NULL;
    7.42 +      }
    7.43 +
    7.44 +   if (s->size == s->max)
    7.45 +      {
    7.46 +      errno = ENOMEM;
    7.47 +      return NULL;
    7.48 +      }
    7.49 +
    7.50 +   return s->data[(s->size)++] = elem;
    7.51 +   }
    7.52 +
    7.53 +////////////////////////////////////////////////////////////////////////////////
    7.54 +void * stack_pop(struct stack * s)
    7.55 +   {
    7.56 +   if (NULL == s)
    7.57 +      {
    7.58 +      errno = EINVAL;
    7.59 +      return NULL;
    7.60 +      }
    7.61 +
    7.62 +   if (0 == s->size)
    7.63 +      {
    7.64 +      return NULL;
    7.65 +      }
    7.66 +
    7.67 +   return s->data[--(s->size)];
    7.68 +   }
    7.69 +
    7.70 +////////////////////////////////////////////////////////////////////////////////
    7.71 +size_t stack_size(struct stack * s)
    7.72 +   {
    7.73 +   if (NULL == s)
    7.74 +      {
    7.75 +      errno = EINVAL;
    7.76 +      return -1;
    7.77 +      }
    7.78 +
    7.79 +   return s->size;
    7.80 +   }
    7.81 +
    7.82 +////////////////////////////////////////////////////////////////////////////////
    7.83 +void stack_delete(struct stack * s)
    7.84 +   {
    7.85 +   if (NULL != s) free(s->data);
    7.86 +   free(s);
    7.87 +   }

     8.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     8.2 +++ b/src/stack.h	Thu Sep 20 00:08:32 2012 -0500
     8.3 @@ -0,0 +1,17 @@
     8.4 +#ifndef STACK_
     8.5 +#define STACK_
     8.6 +
     8.7 +struct stack
     8.8 +   {
     8.9 +   void ** data;
    8.10 +   size_t size;
    8.11 +   size_t max;
    8.12 +   };
    8.13 +
    8.14 +struct stack * stack_new(size_t const max);
    8.15 +void stack_delete(struct stack * s);
    8.16 +void * stack_push(struct stack * s, void * elem);
    8.17 +void * stack_pop(struct stack * s);
    8.18 +size_t stack_size(struct stack * s);
    8.19 +
    8.20 +#endif

     9.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     9.2 +++ b/src/stack_test.c	Thu Sep 20 00:08:32 2012 -0500
     9.3 @@ -0,0 +1,37 @@
     9.4 +#include <stdio.h>
     9.5 +#include <stdlib.h>
     9.6 +#include "stack.h"
     9.7 +
     9.8 +#define MAX 100
     9.9 +
    9.10 +int main(int argc, char**argv)
    9.11 +   {
    9.12 +   int i;
    9.13 +   int *ip;
    9.14 +   struct stack * s;
    9.15 +   
    9.16 +   s = stack_new(MAX);
    9.17 +   if (NULL == s)
    9.18 +      {
    9.19 +      perror("stack_new: ");
    9.20 +      exit(EXIT_FAILURE);
    9.21 +      }
    9.22 +
    9.23 +   for (i=0; i < MAX/2; i++)
    9.24 +      {
    9.25 +       ip = malloc(sizeof(int));
    9.26 +      *ip = i;
    9.27 +      stack_push(s, (void *) ip);
    9.28 +      }
    9.29 +
    9.30 +   printf("stack size is %zd\n", stack_size(s));
    9.31 +   while (NULL != (ip = stack_pop(s)))
    9.32 +      {
    9.33 +      printf("%d\n", *ip);
    9.34 +      }
    9.35 +   printf("stack size is %zd\n", stack_size(s));
    9.36 +
    9.37 +   stack_delete(s);
    9.38 +
    9.39 +   exit(EXIT_SUCCESS);
    9.40 +   }