1.1 --- a/CMakeLists.txt	Fri Sep 21 02:08:13 2012 -0500
     1.2 +++ b/CMakeLists.txt	Fri Sep 21 18:42:49 2012 -0500
     1.3 @@ -67,3 +67,8 @@
     1.4    ${pqueue_SRCS}
     1.5    )
     1.6  
     1.7 +set (list_SRCS src/list.h src/list.c src/list_test.c)
     1.8 +add_executable (list_test
     1.9 +  ${list_SRCS}
    1.10 +  )
    1.11 +

     2.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     2.2 +++ b/src/list.c	Fri Sep 21 18:42:49 2012 -0500
     2.3 @@ -0,0 +1,324 @@
     2.4 +#include <stdlib.h>
     2.5 +
     2.6 +#include "list.h"
     2.7 +
     2.8 +
     2.9 +////////////////////////////////////////////////////////////////////////////////
    2.10 +// Allocates new list and returns poitner to it.
    2.11 +struct list *
    2.12 +list_new(void)
    2.13 +   {
    2.14 +   struct list * l = malloc(sizeof(struct list));
    2.15 +   if (NULL == l)
    2.16 +      return NULL;
    2.17 +
    2.18 +   l->size = 0;
    2.19 +   l->head = l->tail = NULL;
    2.20 +
    2.21 +   return l;
    2.22 +   }
    2.23 +
    2.24 +////////////////////////////////////////////////////////////////////////////////
    2.25 +// Deletes list.  Does not delete data elements.  To avoid memory leaks,
    2.26 +// Only call this on an empty list.
    2.27 +void
    2.28 +list_delete(struct list * l)
    2.29 +   {
    2.30 +   if (NULL != l)
    2.31 +      {
    2.32 +      // This will cause memory leaks, but we don't have destructors.
    2.33 +      // Hopefuly the caller has already emptied the list.
    2.34 +      struct list_node * prev;
    2.35 +      struct list_node * curr = l->tail;
    2.36 +      while (curr)
    2.37 +	 {
    2.38 +	 prev = curr->prev;
    2.39 +	 free(curr);
    2.40 +	 curr = prev;
    2.41 +	 }
    2.42 +      free(l);
    2.43 +      }
    2.44 +   }
    2.45 +
    2.46 +////////////////////////////////////////////////////////////////////////////////
    2.47 +// Returns the numb er of elements in the list.
    2.48 +size_t
    2.49 +list_size(struct list * l)
    2.50 +   {
    2.51 +   if (NULL == l)
    2.52 +      return 0;
    2.53 +   return l->size;
    2.54 +   }
    2.55 +
    2.56 +////////////////////////////////////////////////////////////////////////////////
    2.57 +// Add an element to the end of the list.
    2.58 +void *
    2.59 +list_push_back(struct list * l, void * elem)
    2.60 +   {
    2.61 +   if ( (NULL == l) || (NULL == elem) )
    2.62 +      return NULL;
    2.63 +
    2.64 +   struct list_node * new = malloc(sizeof(struct list_node));
    2.65 +   if (NULL == new)
    2.66 +      return NULL;
    2.67 +
    2.68 +   new->data = elem;
    2.69 +   new->prev = new->next = NULL;
    2.70 +
    2.71 +   if (NULL == l->tail)
    2.72 +      {
    2.73 +      l->head = l->tail = new;
    2.74 +      }
    2.75 +   else
    2.76 +      {
    2.77 +      new->prev = l->tail;
    2.78 +      l->tail->next = new;
    2.79 +      l->tail = new;
    2.80 +      }
    2.81 +
    2.82 +   l->size++;
    2.83 +
    2.84 +   return elem;
    2.85 +   }
    2.86 +
    2.87 +////////////////////////////////////////////////////////////////////////////////
    2.88 +// Remove an element from the back of the list.
    2.89 +void *
    2.90 +list_pop_back(struct list * l)
    2.91 +   {
    2.92 +   if ( (NULL == l) || (NULL == l->tail) )
    2.93 +      return NULL;
    2.94 +   
    2.95 +   void * t = l->tail->data;
    2.96 +
    2.97 +   struct list_node * prev = l->tail->prev;
    2.98 +   if (prev)
    2.99 +      prev->next = NULL;
   2.100 +   free(l->tail);
   2.101 +   l->tail = prev;
   2.102 +   l->size--;
   2.103 +   if (0 == l->size)
   2.104 +      l->head = NULL;
   2.105 +
   2.106 +   return t;
   2.107 +   }
   2.108 +
   2.109 +////////////////////////////////////////////////////////////////////////////////
   2.110 +// Add an element to the front of the list.
   2.111 +void *
   2.112 +list_push_front(struct list * l, void * elem)
   2.113 +   {
   2.114 +   if ( (NULL == l) || (NULL == elem) )
   2.115 +      return NULL;
   2.116 +
   2.117 +   struct list_node * new = malloc(sizeof(struct list_node));
   2.118 +   if (NULL == new)
   2.119 +      return NULL;
   2.120 +
   2.121 +   new->data = elem;
   2.122 +   new->prev = new->next = NULL;
   2.123 +
   2.124 +   if (NULL == l->head)
   2.125 +      {
   2.126 +      l->head = l->tail = new;
   2.127 +      }
   2.128 +   else
   2.129 +      {
   2.130 +      new->next = l->head;
   2.131 +      l->head->prev = new;
   2.132 +      l->head = new;
   2.133 +      }
   2.134 +
   2.135 +   l->size++;
   2.136 +
   2.137 +   return elem;
   2.138 +   }
   2.139 +
   2.140 +////////////////////////////////////////////////////////////////////////////////
   2.141 +// Remove and element from the front of the list.
   2.142 +void *
   2.143 +list_pop_front(struct list * l)
   2.144 +   {
   2.145 +   if ( (NULL == l) || (NULL == l->head) )
   2.146 +      return NULL;
   2.147 +   
   2.148 +   void * t = l->head->data;
   2.149 +
   2.150 +   struct list_node * next = l->head->next;
   2.151 +   if (next)
   2.152 +      next->prev = NULL;
   2.153 +   free(l->head);
   2.154 +   l->head = next;
   2.155 +   l->size--;
   2.156 +
   2.157 +   if (0 == l->size)
   2.158 +      l->tail = NULL;
   2.159 +
   2.160 +   return t;
   2.161 +   }
   2.162 +
   2.163 +////////////////////////////////////////////////////////////////////////////////
   2.164 +// Intialize an iterator to point to the first element of the list
   2.165 +// Returns the elements value.
   2.166 +void *
   2.167 +list_begin(struct list * l, struct list_iterator * lit)
   2.168 +   {
   2.169 +   if ( (NULL == l) || (NULL == lit) )
   2.170 +      return NULL;
   2.171 +
   2.172 +   lit->l = l;
   2.173 +   lit->curr = l->head;
   2.174 +
   2.175 +   if (lit->curr)
   2.176 +      return lit->curr->data;
   2.177 +
   2.178 +   return NULL;
   2.179 +   }
   2.180 +
   2.181 +////////////////////////////////////////////////////////////////////////////////
   2.182 +// Intialize an iterator to point to the last element of the list
   2.183 +// Returns the elements value.
   2.184 +void *
   2.185 +list_end(struct list * l, struct list_iterator * lit)
   2.186 +   {
   2.187 +   if ( (NULL == l) || (NULL == lit) )
   2.188 +      return NULL;
   2.189 +
   2.190 +   lit->l = l;
   2.191 +   lit->curr = l->tail;
   2.192 +
   2.193 +   if (lit->curr)
   2.194 +      return lit->curr->data;
   2.195 +
   2.196 +   return NULL;
   2.197 +   }
   2.198 +
   2.199 +////////////////////////////////////////////////////////////////////////////////
   2.200 +// Move the iterator to the next element in the list, returning its value.
   2.201 +void *
   2.202 +list_next(struct list_iterator * lit)
   2.203 +   {
   2.204 +   if (NULL == lit)
   2.205 +      return NULL;
   2.206 +
   2.207 +   lit->curr = lit->curr->next;
   2.208 +
   2.209 +   if (lit->curr)
   2.210 +      return lit->curr->data;
   2.211 +
   2.212 +   return NULL;
   2.213 +   }
   2.214 +
   2.215 +////////////////////////////////////////////////////////////////////////////////
   2.216 +// Move the iterator to the previous element in the list, returning its value.
   2.217 +void *
   2.218 +list_prev(struct list_iterator * lit)
   2.219 +   {
   2.220 +   if (NULL == lit)
   2.221 +      return NULL;
   2.222 +
   2.223 +   lit->curr = lit->curr->prev;
   2.224 +
   2.225 +   if (lit->curr)
   2.226 +      return lit->curr->data;
   2.227 +
   2.228 +   return NULL;
   2.229 +   }
   2.230 +
   2.231 +////////////////////////////////////////////////////////////////////////////////
   2.232 +// Remove the current element pointed to by the iterator, returning that elements value.
   2.233 +void *
   2.234 +list_erase(struct list_iterator * lit)
   2.235 +   {
   2.236 +   if ( (NULL == lit) || (NULL == lit->curr) )
   2.237 +      return NULL;
   2.238 +
   2.239 +   if (lit->curr->prev)
   2.240 +      lit->curr->prev->next = lit->curr->next;
   2.241 +
   2.242 +   if (lit->curr->next)
   2.243 +      lit->curr->next->prev = lit->curr->prev;
   2.244 +
   2.245 +   struct list_node * temp = lit->curr;
   2.246 +   void * elem = lit->curr->data;
   2.247 +
   2.248 +   lit->curr = lit->curr->next;
   2.249 +   free(temp);
   2.250 +
   2.251 +   lit->l->size--;
   2.252 +   if (0 == lit->l->size)
   2.253 +      lit->l->tail = lit->l->head = NULL;
   2.254 +
   2.255 +   return elem;
   2.256 +   }
   2.257 +
   2.258 +////////////////////////////////////////////////////////////////////////////////
   2.259 +// Insert a new element after the one pointed to by the iterator.  
   2.260 +// The iterator is then set to point to this new element.
   2.261 +// Return the new elements value.
   2.262 +void *
   2.263 +list_insert_after(struct list_iterator * lit, void * elem)
   2.264 +   {
   2.265 +   if ( (NULL == lit) || (NULL == elem) || (NULL == lit->curr) )
   2.266 +      return NULL;
   2.267 +
   2.268 +   struct list_node * new = malloc(sizeof(struct list_node));
   2.269 +   if (NULL == new)
   2.270 +      return NULL;
   2.271 +
   2.272 +   new->data = elem;
   2.273 +   new->prev = lit->curr;
   2.274 +   if (lit->curr->next)
   2.275 +      lit->curr->next->prev = new;
   2.276 +   new->next = lit->curr->next;
   2.277 +   lit->curr->next = new;
   2.278 +
   2.279 +   lit->curr = new;
   2.280 +
   2.281 +   lit->l->size++;
   2.282 +   if (NULL == lit->curr->next)
   2.283 +      lit->l->tail = lit->curr;
   2.284 +
   2.285 +   return elem;
   2.286 +   }
   2.287 +
   2.288 +////////////////////////////////////////////////////////////////////////////////
   2.289 +// Insert a new element before the one pointed to by the iterator.  
   2.290 +// The iterator is then set to point to this new element.
   2.291 +// Return the new elements value.
   2.292 +void *
   2.293 +list_insert_before(struct list_iterator * lit, void * elem)
   2.294 +   {
   2.295 +   if ( (NULL == lit) || (NULL == elem) || (NULL == lit->curr) )
   2.296 +      return NULL;
   2.297 +
   2.298 +   struct list_node * new = malloc(sizeof(struct list_node));
   2.299 +   if (NULL == new)
   2.300 +      return NULL;
   2.301 +
   2.302 +   new->data = elem;
   2.303 +   new->next = lit->curr;
   2.304 +   if (lit->curr->prev)
   2.305 +      lit->curr->prev->next = new;
   2.306 +   new->prev = lit->curr->prev;
   2.307 +   lit->curr->prev = new;
   2.308 +
   2.309 +   lit->curr = new;
   2.310 +
   2.311 +   lit->l->size++;
   2.312 +   if (NULL == lit->curr->prev)
   2.313 +      lit->l->head = lit->curr;
   2.314 +
   2.315 +   return elem;
   2.316 +   }
   2.317 +
   2.318 +////////////////////////////////////////////////////////////////////////////////
   2.319 +// Return the value of the element pointed to by the iterator.
   2.320 +void *
   2.321 +list_value(struct list_iterator * lit)
   2.322 +   {
   2.323 +   if ( (NULL == lit) || (NULL == lit->curr) )
   2.324 +      return NULL;
   2.325 +   return lit->curr->data;
   2.326 +   }
   2.327 +

     3.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     3.2 +++ b/src/list.h	Fri Sep 21 18:42:49 2012 -0500
     3.3 @@ -0,0 +1,48 @@
     3.4 +#ifndef LIST_H_
     3.5 +#define LIST_H_
     3.6 +
     3.7 +#include <stddef.h>
     3.8 +
     3.9 +struct list_node
    3.10 +   {
    3.11 +   struct list_node * next;
    3.12 +   struct list_node * prev;
    3.13 +   void * data;
    3.14 +   };
    3.15 +
    3.16 +struct list
    3.17 +   {
    3.18 +   struct list_node * head;
    3.19 +   struct list_node * tail;
    3.20 +   size_t size;
    3.21 +   };
    3.22 +
    3.23 +struct list_iterator
    3.24 +   {
    3.25 +   struct list * l;
    3.26 +   struct list_node * curr;
    3.27 +   };
    3.28 +
    3.29 +struct list * list_new(void);
    3.30 +void list_delete(struct list * l);
    3.31 +
    3.32 +size_t list_size(struct list * l);
    3.33 +
    3.34 +void * list_push_back(struct list * l, void * elem);
    3.35 +void * list_pop_back(struct list * l);
    3.36 +void * list_push_front(struct list * l, void * elem);
    3.37 +void * list_pop_front(struct list * l);
    3.38 +
    3.39 +
    3.40 +// The iterators are different that their c++ STL counterparts.
    3.41 +// They are bi-directional, and list_end points to the last element, not the empty space beyond the last elem.
    3.42 +void * list_begin(struct list * l, struct list_iterator * lit);
    3.43 +void * list_end(struct list * l, struct list_iterator * lit);
    3.44 +void * list_next(struct list_iterator * lit);
    3.45 +void * list_prev(struct list_iterator * lit);
    3.46 +void * list_erase(struct list_iterator * lit);
    3.47 +void * list_insert_after(struct list_iterator * lit, void * elem);
    3.48 +void * list_insert_before(struct list_iterator * lit, void * elem);
    3.49 +void * list_value(struct list_iterator * lit);
    3.50 +
    3.51 +#endif

     4.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     4.2 +++ b/src/list_test.c	Fri Sep 21 18:42:49 2012 -0500
     4.3 @@ -0,0 +1,190 @@
     4.4 +#include <stdio.h>
     4.5 +#include <stdlib.h>
     4.6 +
     4.7 +#include "list.h"
     4.8 +
     4.9 +#define MAX 10
    4.10 +
    4.11 +int main(int argc, char** argv)
    4.12 +   {
    4.13 +   struct list * l = list_new();
    4.14 +   if (NULL == l)
    4.15 +      {
    4.16 +      perror("list_new");
    4.17 +      exit(EXIT_FAILURE);
    4.18 +      }
    4.19 +
    4.20 +
    4.21 +   /////////////////////////////////////
    4.22 +   // Push and pop from back
    4.23 +   for (int i = 0; i < MAX ; i++)
    4.24 +      {
    4.25 +      int * ip = malloc(sizeof(int));
    4.26 +      if (NULL == ip)
    4.27 +	 {
    4.28 +	 perror("malloc");
    4.29 +	 exit(EXIT_FAILURE);
    4.30 +	 }
    4.31 +
    4.32 +      *ip = i;
    4.33 +      if (NULL == list_push_back(l, ip))
    4.34 +	 {
    4.35 +	 perror("list_push_back");
    4.36 +	 exit(EXIT_FAILURE);
    4.37 +	 }
    4.38 +      }
    4.39 +
    4.40 +   printf("size %zd\n", list_size(l));
    4.41 +   while (0 != list_size(l))
    4.42 +      {
    4.43 +      int * ip = list_pop_back(l);
    4.44 +      printf("%d\n", *ip);
    4.45 +      free(ip);
    4.46 +      }
    4.47 +
    4.48 +   /////////////////////////////////////
    4.49 +   // Push and pop from front
    4.50 +   for (int i = 0; i < MAX ; i++)
    4.51 +      {
    4.52 +      int * ip = malloc(sizeof(int));
    4.53 +      if (NULL == ip)
    4.54 +	 {
    4.55 +	 perror("malloc");
    4.56 +	 exit(EXIT_FAILURE);
    4.57 +	 }
    4.58 +
    4.59 +      *ip = i;
    4.60 +      if (NULL == list_push_front(l, ip))
    4.61 +	 {
    4.62 +	 perror("list_push_front");
    4.63 +	 exit(EXIT_FAILURE);
    4.64 +	 }
    4.65 +      }
    4.66 +
    4.67 +   printf("size %zd\n", list_size(l));
    4.68 +   while (0 != list_size(l))
    4.69 +      {
    4.70 +      int * ip = list_pop_front(l);
    4.71 +      printf("%d\n", *ip);
    4.72 +      free(ip);
    4.73 +      }
    4.74 +
    4.75 +
    4.76 +   /////////////////////////////////////
    4.77 +   // Push back and pop back
    4.78 +   for (int i = 0; i < MAX ; i++)
    4.79 +      {
    4.80 +      int * ip = malloc(sizeof(int));
    4.81 +      if (NULL == ip)
    4.82 +	 {
    4.83 +	 perror("malloc");
    4.84 +	 exit(EXIT_FAILURE);
    4.85 +	 }
    4.86 +
    4.87 +      *ip = i;
    4.88 +      if (NULL == list_push_back(l, ip))
    4.89 +	 {
    4.90 +	 perror("list_push_back");
    4.91 +	 exit(EXIT_FAILURE);
    4.92 +	 }
    4.93 +      }
    4.94 +
    4.95 +   printf("size %zd\n", list_size(l));
    4.96 +   while (0 != list_size(l))
    4.97 +      {
    4.98 +      int * ip = list_pop_front(l);
    4.99 +      printf("%d\n", *ip);
   4.100 +      free(ip);
   4.101 +      }
   4.102 +
   4.103 +   /////////////////////////////////////
   4.104 +   // push back, walk front to back
   4.105 +   for (int i = 0; i < MAX ; i++)
   4.106 +      {
   4.107 +      int * ip = malloc(sizeof(int));
   4.108 +      if (NULL == ip)
   4.109 +	 {
   4.110 +	 perror("malloc");
   4.111 +	 exit(EXIT_FAILURE);
   4.112 +	 }
   4.113 +
   4.114 +      *ip = i;
   4.115 +      if (NULL == list_push_back(l, ip))
   4.116 +	 {
   4.117 +	 perror("list_push_back");
   4.118 +	 exit(EXIT_FAILURE);
   4.119 +	 }
   4.120 +      }
   4.121 +
   4.122 +   printf("size %zd\n", list_size(l));
   4.123 +
   4.124 +   struct list_iterator lit;
   4.125 +   int * ip;
   4.126 +
   4.127 +   printf("Walking front to back\n");
   4.128 +   for (ip = list_begin(l, &lit); NULL != ip; ip = list_next( &lit))
   4.129 +      printf("%d\n", *ip);
   4.130 +
   4.131 +   printf("Inserting 15 after 5\n");
   4.132 +   for (ip = list_begin(l, &lit); NULL != ip; ip = list_next( &lit))
   4.133 +      {
   4.134 +      if (5 == *ip)
   4.135 +	 {
   4.136 +	 int * newip = malloc(sizeof(int));
   4.137 +	 if (NULL == newip)
   4.138 +	    {
   4.139 +	    perror("malloc");
   4.140 +	    exit(EXIT_FAILURE);
   4.141 +	    }
   4.142 +	 *newip = 15;
   4.143 +	 if (NULL == list_insert_after(&lit, newip))
   4.144 +	    {
   4.145 +	    perror("malloc");
   4.146 +	    exit(EXIT_FAILURE);
   4.147 +	    }
   4.148 +	 break;
   4.149 +	 }
   4.150 +      }
   4.151 +
   4.152 +   printf("Inserting 20 before 8\n");
   4.153 +   for (ip = list_begin(l, &lit); NULL != ip; ip = list_next( &lit))
   4.154 +      {
   4.155 +      if (8 == *ip)
   4.156 +	 {
   4.157 +	 int * newip = malloc(sizeof(int));
   4.158 +	 if (NULL == newip)
   4.159 +	    {
   4.160 +	    perror("malloc");
   4.161 +	    exit(EXIT_FAILURE);
   4.162 +	    }
   4.163 +	 *newip = 20;
   4.164 +	 if (NULL == list_insert_before(&lit, newip))
   4.165 +	    {
   4.166 +	    perror("malloc");
   4.167 +	    exit(EXIT_FAILURE);
   4.168 +	    }
   4.169 +	 break;
   4.170 +	 }
   4.171 +      }
   4.172 +
   4.173 +   printf("size %zd\n", list_size(l));
   4.174 +
   4.175 +   printf("Walking back to front\n");
   4.176 +   for (ip = list_end(l, &lit); NULL != ip ; ip = list_prev(&lit))
   4.177 +      printf("%d\n", *ip);
   4.178 +
   4.179 +
   4.180 +   printf("Erasing front to back\n");
   4.181 +   list_begin(l, &lit);
   4.182 +   while (NULL != (ip = list_value(&lit)))
   4.183 +      {
   4.184 +      printf("%d\n", *ip);
   4.185 +      list_erase(&lit);
   4.186 +      free(ip);
   4.187 +      }
   4.188 +   printf("size %zd\n", list_size(l));
   4.189 +
   4.190 +   list_delete(l);
   4.191 +   exit(EXIT_SUCCESS);
   4.192 +
   4.193 +   }

     5.1 --- a/src/queue_test.c	Fri Sep 21 02:08:13 2012 -0500
     5.2 +++ b/src/queue_test.c	Fri Sep 21 18:42:49 2012 -0500
     5.3 @@ -42,7 +42,10 @@
     5.4         ip = malloc(sizeof(int));
     5.5        *ip = i;
     5.6        if (NULL == queue_push(q, (void *) ip))
     5.7 +	 {
     5.8           perror("queue_push");
     5.9 +	 free(ip);
    5.10 +	 }
    5.11        }
    5.12  
    5.13     // Empty the queue

     6.1 --- a/src/stack_test.c	Fri Sep 21 02:08:13 2012 -0500
     6.2 +++ b/src/stack_test.c	Fri Sep 21 18:42:49 2012 -0500
     6.3 @@ -28,6 +28,7 @@
     6.4     while (NULL != (ip = stack_pop(s)))
     6.5        {
     6.6        printf("%d\n", *ip);
     6.7 +      free(ip);
     6.8        }
     6.9     printf("stack size is %zd\n", stack_size(s));
    6.10