1.1 --- a/CMakeLists.txt	Thu Sep 20 23:11:40 2012 -0500
     1.2 +++ b/CMakeLists.txt	Fri Sep 21 02:03:01 2012 -0500
     1.3 @@ -62,3 +62,8 @@
     1.4    ${dequeue_SRCS}
     1.5    )
     1.6  
     1.7 +set (pqueue_SRCS src/pqueue.h src/pqueue.c src/pqueue_test.c)
     1.8 +add_executable (pqueue_test
     1.9 +  ${pqueue_SRCS}
    1.10 +  )
    1.11 +

     2.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     2.2 +++ b/README	Fri Sep 21 02:03:01 2012 -0500
     2.3 @@ -0,0 +1,1 @@
     2.4 +This is just a collection of basic data structures implemented in C.  I did these as a refresher of things I've not had to do in a few years. (why make a dequeue by hand when then STL has a nice one ready to be used?)  Thus, the emphasis is on clarity and demonstrating the fundamental technique.  Performance and features are not the goal here.

     3.1 --- a/src/dequeue.h	Thu Sep 20 23:11:40 2012 -0500
     3.2 +++ b/src/dequeue.h	Fri Sep 21 02:03:01 2012 -0500
     3.3 @@ -1,6 +1,8 @@
     3.4  #ifndef DEQUEUE_H_
     3.5  #define DEQUEUE_H_
     3.6  
     3.7 +#include <stddef.h>
     3.8 +
     3.9  struct dequeue
    3.10     {
    3.11     void ** data;

     4.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     4.2 +++ b/src/pqueue.c	Fri Sep 21 02:03:01 2012 -0500
     4.3 @@ -0,0 +1,127 @@
     4.4 +#include <stdlib.h>
     4.5 +
     4.6 +#include "pqueue.h"
     4.7 +
     4.8 +////////////////////////////////////////////////////////////////////////////////
     4.9 +// comp should return true if *a comp *b.
    4.10 +// So, for a min priority queue, comp will be defined to return true if *a < *b,
    4.11 +// whereas for a max priority queue comp will be defined to return true if *a > *b,
    4.12 +
    4.13 +struct pqueue * 
    4.14 +pqueue_new(size_t max, bool (*comp)(void const * const a, void const * const b))
    4.15 +   {
    4.16 +   if ( (0 == max) || (NULL == comp) )
    4.17 +      return NULL;
    4.18 +
    4.19 +   struct pqueue * pq = malloc(sizeof(struct pqueue));
    4.20 +   if (NULL == pq)
    4.21 +      return NULL;
    4.22 +
    4.23 +   pq->max = max;
    4.24 +   pq->size = 0;
    4.25 +   pq->comp = comp;
    4.26 +
    4.27 +   // Allocate space for max+1 since we are going to waste the first element in order to use a one based array.
    4.28 +   pq->data = malloc((1 + pq->max) * sizeof(void *));
    4.29 +   if (NULL == pq->data)
    4.30 +      {
    4.31 +      free(pq);
    4.32 +      return NULL;
    4.33 +      }
    4.34 +
    4.35 +   return pq;
    4.36 +   }
    4.37 +
    4.38 +
    4.39 +////////////////////////////////////////////////////////////////////////////////
    4.40 +void 
    4.41 +pqueue_delete(struct pqueue * pq)
    4.42 +   {
    4.43 +   if (NULL != pq)
    4.44 +      {
    4.45 +      free(pq->data);
    4.46 +      free(pq);
    4.47 +      }
    4.48 +   }
    4.49 +
    4.50 +////////////////////////////////////////////////////////////////////////////////
    4.51 +void * 
    4.52 +pqueue_push(struct pqueue * pq, void * elem)
    4.53 +   {
    4.54 +   if ( (NULL == pq) || (NULL == elem) )
    4.55 +      return NULL;
    4.56 +
    4.57 +   if (pq->size == pq->max)
    4.58 +      return NULL;
    4.59 +
    4.60 +   pq->size++;
    4.61 +   pq->data[pq->size] = elem;
    4.62 +
    4.63 +   // sift up
    4.64 +   void * temp;
    4.65 +   size_t i, parent;
    4.66 +   for (i = pq->size, parent = i/2;
    4.67 +	(i > 1) && (! pq->comp(pq->data[parent], pq->data[i]));
    4.68 +	i = parent, parent = i/2)
    4.69 +      {
    4.70 +      temp = pq->data[i];
    4.71 +      pq->data[i] = pq->data[parent];
    4.72 +      pq->data[parent] = temp;
    4.73 +      }
    4.74 +
    4.75 +   return elem;
    4.76 +   }
    4.77 +
    4.78 +
    4.79 +////////////////////////////////////////////////////////////////////////////////
    4.80 +void * 
    4.81 +pqueue_pop(struct pqueue * pq)
    4.82 +   {
    4.83 +   if ( (NULL == pq) || (0 == pq->size) )
    4.84 +      return NULL;
    4.85 +   
    4.86 +   void * val = pq->data[1];
    4.87 +
    4.88 +   pq->data[1] = pq->data[pq->size];
    4.89 +   pq->size--;
    4.90 +
    4.91 +   // sift down
    4.92 +   void * temp;
    4.93 +   size_t i, child;
    4.94 +   for (i = 1;  (child = 2*i) <= pq->size; i = child)
    4.95 +      {
    4.96 +      if ( (child+1 <= pq->size) && (pq->comp(pq->data[child+1], pq->data[child])) )
    4.97 +	   child++;
    4.98 +      if (pq->comp(pq->data[child], pq->data[i]))
    4.99 +	 {
   4.100 +	 temp = pq->data[i];
   4.101 +	 pq->data[i] = pq->data[child];
   4.102 +	 pq->data[child] = temp;
   4.103 +	 }
   4.104 +      else
   4.105 +	 break;
   4.106 +      }
   4.107 +
   4.108 +   return val;
   4.109 +   }
   4.110 +
   4.111 +
   4.112 +////////////////////////////////////////////////////////////////////////////////
   4.113 +void *
   4.114 +pqueue_peek(struct pqueue * pq)
   4.115 +   {
   4.116 +   if ( (NULL == pq) || (0 == pq->size) )
   4.117 +      return NULL;
   4.118 +
   4.119 +   return pq->data[1];
   4.120 +   }
   4.121 +
   4.122 +////////////////////////////////////////////////////////////////////////////////
   4.123 +size_t
   4.124 +pqueue_size(struct pqueue * pq)
   4.125 +   {
   4.126 +   if (NULL == pq)
   4.127 +      return 0;
   4.128 +
   4.129 +   return  pq->size;
   4.130 +   }

     5.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     5.2 +++ b/src/pqueue.h	Fri Sep 21 02:03:01 2012 -0500
     5.3 @@ -0,0 +1,25 @@
     5.4 +#ifndef PQUEUE_
     5.5 +#define PQUEUE_
     5.6 +
     5.7 +#include <stddef.h>
     5.8 +#include <stdbool.h>
     5.9 +
    5.10 +struct pqueue
    5.11 +   {
    5.12 +   void ** data;
    5.13 +   size_t max;
    5.14 +   size_t size;
    5.15 +   bool (*comp)(void const * const a, void const * const b);
    5.16 +   };
    5.17 +
    5.18 +struct pqueue * pqueue_new(size_t max, 
    5.19 +			   bool (*comp)(void const * const a, void const * const b));
    5.20 +void pqueue_delete(struct pqueue * pq);
    5.21 +
    5.22 +void * pqueue_push(struct pqueue * pq, void * elem);
    5.23 +void * pqueue_pop(struct pqueue * pq);
    5.24 +void * pqueue_peek(struct pqueue * pq);
    5.25 +
    5.26 +size_t  pqueue_size(struct pqueue * pq);
    5.27 +
    5.28 +#endif // ndef PQUEUE_

     6.1 Binary file src/pqueue_test has changed

     7.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     7.2 +++ b/src/pqueue_test.c	Fri Sep 21 02:03:01 2012 -0500
     7.3 @@ -0,0 +1,73 @@
     7.4 +#include <stdio.h>
     7.5 +#include <stdlib.h>
     7.6 +#include <stdbool.h>
     7.7 +#include <time.h>
     7.8 +
     7.9 +#include "pqueue.h"
    7.10 +
    7.11 +#define MAX 10
    7.12 +
    7.13 +bool int_lt(void const * const a, void const * const b)
    7.14 +   {
    7.15 +   return  *((int *) a) < *((int *) b);
    7.16 +   }
    7.17 +
    7.18 +bool int_gt(void const * const a, void const * const b)
    7.19 +   {
    7.20 +   return  *((int *) a) > *((int *) b);
    7.21 +   }
    7.22 +
    7.23 +int main(int argc, char**argv)
    7.24 +   {
    7.25 +   struct pqueue * pq = pqueue_new(MAX, int_gt);
    7.26 +   if (NULL == pq)
    7.27 +      {
    7.28 +      perror("pqueue_new");
    7.29 +      exit(EXIT_FAILURE);
    7.30 +      }
    7.31 +
    7.32 +   srand(time(NULL));
    7.33 +
    7.34 +   // Fill the queue
    7.35 +   for (int i = 0; i < MAX; i++)
    7.36 +      {
    7.37 +      int * ip = malloc(sizeof(int));
    7.38 +      *ip = rand();
    7.39 +      if (NULL == ip)
    7.40 +	 {
    7.41 +	 perror("malloc");
    7.42 +	 exit(EXIT_FAILURE);
    7.43 +	 }
    7.44 +
    7.45 +      if (NULL == pqueue_push(pq, ip))
    7.46 +	 {
    7.47 +	 perror("pqueue_push");
    7.48 +	 exit(EXIT_FAILURE);
    7.49 +	 }
    7.50 +      }
    7.51 +
    7.52 +   printf("size is %zd\n", pqueue_size(pq));
    7.53 +
    7.54 +   int * ip;
    7.55 +   printf("peeking...");
    7.56 +   ip = pqueue_peek(pq);
    7.57 +   if (NULL == ip)
    7.58 +      {
    7.59 +      perror("pqueue_peek");
    7.60 +      exit(EXIT_FAILURE);
    7.61 +      }
    7.62 +   printf("%d\n", *ip);
    7.63 +
    7.64 +   printf("size is %zd\n", pqueue_size(pq));
    7.65 +
    7.66 +   // Empty the queue
    7.67 +   while (ip = pqueue_pop(pq))
    7.68 +      {
    7.69 +      printf("%d\n", *ip);
    7.70 +      free(ip);
    7.71 +      }
    7.72 +
    7.73 +   printf("size is %zd\n", pqueue_size(pq));
    7.74 +
    7.75 +   pqueue_delete(pq);
    7.76 +   }

     8.1 --- a/src/queue.h	Thu Sep 20 23:11:40 2012 -0500
     8.2 +++ b/src/queue.h	Fri Sep 21 02:03:01 2012 -0500
     8.3 @@ -1,6 +1,8 @@
     8.4  #ifndef QUEUE_
     8.5  #define QUEUE_
     8.6  
     8.7 +#include <stddef.h>
     8.8 +
     8.9  struct queue
    8.10     {
    8.11     void ** data;

     9.1 --- a/src/ring_buffer.h	Thu Sep 20 23:11:40 2012 -0500
     9.2 +++ b/src/ring_buffer.h	Fri Sep 21 02:03:01 2012 -0500
     9.3 @@ -1,6 +1,8 @@
     9.4  #ifndef RING_BUFFER_
     9.5  #define RING_BUFFER_
     9.6  
     9.7 +#include <stddef.h>
     9.8 +
     9.9  struct ring_buffer
    9.10     {
    9.11     void ** data;

    10.1 --- a/src/stack.h	Thu Sep 20 23:11:40 2012 -0500
    10.2 +++ b/src/stack.h	Fri Sep 21 02:03:01 2012 -0500
    10.3 @@ -1,6 +1,8 @@
    10.4  #ifndef STACK_
    10.5  #define STACK_
    10.6  
    10.7 +#include <stddef.h>
    10.8 +
    10.9  struct stack
   10.10     {
   10.11     void ** data;