# HG changeset patch
# User Eris Caffee <discordia@eldalin.com>
# Date 1348270969 18000
# Node ID e117c4d93602d3303b9a5999a55c2f05b2caf100
# Parent  f32df8c249f0fee56d967b246378b9ab82f84352
Added list - a doubly linked list.  Fixed memory leaks in some of the test drivers.

diff -r f32df8c249f0 -r e117c4d93602 CMakeLists.txt
--- a/CMakeLists.txt	Fri Sep 21 02:08:13 2012 -0500
+++ b/CMakeLists.txt	Fri Sep 21 18:42:49 2012 -0500
@@ -67,3 +67,8 @@
   ${pqueue_SRCS}
   )
 
+set (list_SRCS src/list.h src/list.c src/list_test.c)
+add_executable (list_test
+  ${list_SRCS}
+  )
+
diff -r f32df8c249f0 -r e117c4d93602 src/list.c
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/list.c	Fri Sep 21 18:42:49 2012 -0500
@@ -0,0 +1,324 @@
+#include <stdlib.h>
+
+#include "list.h"
+
+
+////////////////////////////////////////////////////////////////////////////////
+// Allocates new list and returns poitner to it.
+struct list *
+list_new(void)
+   {
+   struct list * l = malloc(sizeof(struct list));
+   if (NULL == l)
+      return NULL;
+
+   l->size = 0;
+   l->head = l->tail = NULL;
+
+   return l;
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+// Deletes list.  Does not delete data elements.  To avoid memory leaks,
+// Only call this on an empty list.
+void
+list_delete(struct list * l)
+   {
+   if (NULL != l)
+      {
+      // This will cause memory leaks, but we don't have destructors.
+      // Hopefuly the caller has already emptied the list.
+      struct list_node * prev;
+      struct list_node * curr = l->tail;
+      while (curr)
+	 {
+	 prev = curr->prev;
+	 free(curr);
+	 curr = prev;
+	 }
+      free(l);
+      }
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+// Returns the numb er of elements in the list.
+size_t
+list_size(struct list * l)
+   {
+   if (NULL == l)
+      return 0;
+   return l->size;
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+// Add an element to the end of the list.
+void *
+list_push_back(struct list * l, void * elem)
+   {
+   if ( (NULL == l) || (NULL == elem) )
+      return NULL;
+
+   struct list_node * new = malloc(sizeof(struct list_node));
+   if (NULL == new)
+      return NULL;
+
+   new->data = elem;
+   new->prev = new->next = NULL;
+
+   if (NULL == l->tail)
+      {
+      l->head = l->tail = new;
+      }
+   else
+      {
+      new->prev = l->tail;
+      l->tail->next = new;
+      l->tail = new;
+      }
+
+   l->size++;
+
+   return elem;
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+// Remove an element from the back of the list.
+void *
+list_pop_back(struct list * l)
+   {
+   if ( (NULL == l) || (NULL == l->tail) )
+      return NULL;
+   
+   void * t = l->tail->data;
+
+   struct list_node * prev = l->tail->prev;
+   if (prev)
+      prev->next = NULL;
+   free(l->tail);
+   l->tail = prev;
+   l->size--;
+   if (0 == l->size)
+      l->head = NULL;
+
+   return t;
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+// Add an element to the front of the list.
+void *
+list_push_front(struct list * l, void * elem)
+   {
+   if ( (NULL == l) || (NULL == elem) )
+      return NULL;
+
+   struct list_node * new = malloc(sizeof(struct list_node));
+   if (NULL == new)
+      return NULL;
+
+   new->data = elem;
+   new->prev = new->next = NULL;
+
+   if (NULL == l->head)
+      {
+      l->head = l->tail = new;
+      }
+   else
+      {
+      new->next = l->head;
+      l->head->prev = new;
+      l->head = new;
+      }
+
+   l->size++;
+
+   return elem;
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+// Remove and element from the front of the list.
+void *
+list_pop_front(struct list * l)
+   {
+   if ( (NULL == l) || (NULL == l->head) )
+      return NULL;
+   
+   void * t = l->head->data;
+
+   struct list_node * next = l->head->next;
+   if (next)
+      next->prev = NULL;
+   free(l->head);
+   l->head = next;
+   l->size--;
+
+   if (0 == l->size)
+      l->tail = NULL;
+
+   return t;
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+// Intialize an iterator to point to the first element of the list
+// Returns the elements value.
+void *
+list_begin(struct list * l, struct list_iterator * lit)
+   {
+   if ( (NULL == l) || (NULL == lit) )
+      return NULL;
+
+   lit->l = l;
+   lit->curr = l->head;
+
+   if (lit->curr)
+      return lit->curr->data;
+
+   return NULL;
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+// Intialize an iterator to point to the last element of the list
+// Returns the elements value.
+void *
+list_end(struct list * l, struct list_iterator * lit)
+   {
+   if ( (NULL == l) || (NULL == lit) )
+      return NULL;
+
+   lit->l = l;
+   lit->curr = l->tail;
+
+   if (lit->curr)
+      return lit->curr->data;
+
+   return NULL;
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+// Move the iterator to the next element in the list, returning its value.
+void *
+list_next(struct list_iterator * lit)
+   {
+   if (NULL == lit)
+      return NULL;
+
+   lit->curr = lit->curr->next;
+
+   if (lit->curr)
+      return lit->curr->data;
+
+   return NULL;
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+// Move the iterator to the previous element in the list, returning its value.
+void *
+list_prev(struct list_iterator * lit)
+   {
+   if (NULL == lit)
+      return NULL;
+
+   lit->curr = lit->curr->prev;
+
+   if (lit->curr)
+      return lit->curr->data;
+
+   return NULL;
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+// Remove the current element pointed to by the iterator, returning that elements value.
+void *
+list_erase(struct list_iterator * lit)
+   {
+   if ( (NULL == lit) || (NULL == lit->curr) )
+      return NULL;
+
+   if (lit->curr->prev)
+      lit->curr->prev->next = lit->curr->next;
+
+   if (lit->curr->next)
+      lit->curr->next->prev = lit->curr->prev;
+
+   struct list_node * temp = lit->curr;
+   void * elem = lit->curr->data;
+
+   lit->curr = lit->curr->next;
+   free(temp);
+
+   lit->l->size--;
+   if (0 == lit->l->size)
+      lit->l->tail = lit->l->head = NULL;
+
+   return elem;
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+// Insert a new element after the one pointed to by the iterator.  
+// The iterator is then set to point to this new element.
+// Return the new elements value.
+void *
+list_insert_after(struct list_iterator * lit, void * elem)
+   {
+   if ( (NULL == lit) || (NULL == elem) || (NULL == lit->curr) )
+      return NULL;
+
+   struct list_node * new = malloc(sizeof(struct list_node));
+   if (NULL == new)
+      return NULL;
+
+   new->data = elem;
+   new->prev = lit->curr;
+   if (lit->curr->next)
+      lit->curr->next->prev = new;
+   new->next = lit->curr->next;
+   lit->curr->next = new;
+
+   lit->curr = new;
+
+   lit->l->size++;
+   if (NULL == lit->curr->next)
+      lit->l->tail = lit->curr;
+
+   return elem;
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+// Insert a new element before the one pointed to by the iterator.  
+// The iterator is then set to point to this new element.
+// Return the new elements value.
+void *
+list_insert_before(struct list_iterator * lit, void * elem)
+   {
+   if ( (NULL == lit) || (NULL == elem) || (NULL == lit->curr) )
+      return NULL;
+
+   struct list_node * new = malloc(sizeof(struct list_node));
+   if (NULL == new)
+      return NULL;
+
+   new->data = elem;
+   new->next = lit->curr;
+   if (lit->curr->prev)
+      lit->curr->prev->next = new;
+   new->prev = lit->curr->prev;
+   lit->curr->prev = new;
+
+   lit->curr = new;
+
+   lit->l->size++;
+   if (NULL == lit->curr->prev)
+      lit->l->head = lit->curr;
+
+   return elem;
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+// Return the value of the element pointed to by the iterator.
+void *
+list_value(struct list_iterator * lit)
+   {
+   if ( (NULL == lit) || (NULL == lit->curr) )
+      return NULL;
+   return lit->curr->data;
+   }
+
diff -r f32df8c249f0 -r e117c4d93602 src/list.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/list.h	Fri Sep 21 18:42:49 2012 -0500
@@ -0,0 +1,48 @@
+#ifndef LIST_H_
+#define LIST_H_
+
+#include <stddef.h>
+
+struct list_node
+   {
+   struct list_node * next;
+   struct list_node * prev;
+   void * data;
+   };
+
+struct list
+   {
+   struct list_node * head;
+   struct list_node * tail;
+   size_t size;
+   };
+
+struct list_iterator
+   {
+   struct list * l;
+   struct list_node * curr;
+   };
+
+struct list * list_new(void);
+void list_delete(struct list * l);
+
+size_t list_size(struct list * l);
+
+void * list_push_back(struct list * l, void * elem);
+void * list_pop_back(struct list * l);
+void * list_push_front(struct list * l, void * elem);
+void * list_pop_front(struct list * l);
+
+
+// The iterators are different that their c++ STL counterparts.
+// They are bi-directional, and list_end points to the last element, not the empty space beyond the last elem.
+void * list_begin(struct list * l, struct list_iterator * lit);
+void * list_end(struct list * l, struct list_iterator * lit);
+void * list_next(struct list_iterator * lit);
+void * list_prev(struct list_iterator * lit);
+void * list_erase(struct list_iterator * lit);
+void * list_insert_after(struct list_iterator * lit, void * elem);
+void * list_insert_before(struct list_iterator * lit, void * elem);
+void * list_value(struct list_iterator * lit);
+
+#endif
diff -r f32df8c249f0 -r e117c4d93602 src/list_test.c
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/list_test.c	Fri Sep 21 18:42:49 2012 -0500
@@ -0,0 +1,190 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+#include "list.h"
+
+#define MAX 10
+
+int main(int argc, char** argv)
+   {
+   struct list * l = list_new();
+   if (NULL == l)
+      {
+      perror("list_new");
+      exit(EXIT_FAILURE);
+      }
+
+
+   /////////////////////////////////////
+   // Push and pop from back
+   for (int i = 0; i < MAX ; i++)
+      {
+      int * ip = malloc(sizeof(int));
+      if (NULL == ip)
+	 {
+	 perror("malloc");
+	 exit(EXIT_FAILURE);
+	 }
+
+      *ip = i;
+      if (NULL == list_push_back(l, ip))
+	 {
+	 perror("list_push_back");
+	 exit(EXIT_FAILURE);
+	 }
+      }
+
+   printf("size %zd\n", list_size(l));
+   while (0 != list_size(l))
+      {
+      int * ip = list_pop_back(l);
+      printf("%d\n", *ip);
+      free(ip);
+      }
+
+   /////////////////////////////////////
+   // Push and pop from front
+   for (int i = 0; i < MAX ; i++)
+      {
+      int * ip = malloc(sizeof(int));
+      if (NULL == ip)
+	 {
+	 perror("malloc");
+	 exit(EXIT_FAILURE);
+	 }
+
+      *ip = i;
+      if (NULL == list_push_front(l, ip))
+	 {
+	 perror("list_push_front");
+	 exit(EXIT_FAILURE);
+	 }
+      }
+
+   printf("size %zd\n", list_size(l));
+   while (0 != list_size(l))
+      {
+      int * ip = list_pop_front(l);
+      printf("%d\n", *ip);
+      free(ip);
+      }
+
+
+   /////////////////////////////////////
+   // Push back and pop back
+   for (int i = 0; i < MAX ; i++)
+      {
+      int * ip = malloc(sizeof(int));
+      if (NULL == ip)
+	 {
+	 perror("malloc");
+	 exit(EXIT_FAILURE);
+	 }
+
+      *ip = i;
+      if (NULL == list_push_back(l, ip))
+	 {
+	 perror("list_push_back");
+	 exit(EXIT_FAILURE);
+	 }
+      }
+
+   printf("size %zd\n", list_size(l));
+   while (0 != list_size(l))
+      {
+      int * ip = list_pop_front(l);
+      printf("%d\n", *ip);
+      free(ip);
+      }
+
+   /////////////////////////////////////
+   // push back, walk front to back
+   for (int i = 0; i < MAX ; i++)
+      {
+      int * ip = malloc(sizeof(int));
+      if (NULL == ip)
+	 {
+	 perror("malloc");
+	 exit(EXIT_FAILURE);
+	 }
+
+      *ip = i;
+      if (NULL == list_push_back(l, ip))
+	 {
+	 perror("list_push_back");
+	 exit(EXIT_FAILURE);
+	 }
+      }
+
+   printf("size %zd\n", list_size(l));
+
+   struct list_iterator lit;
+   int * ip;
+
+   printf("Walking front to back\n");
+   for (ip = list_begin(l, &lit); NULL != ip; ip = list_next( &lit))
+      printf("%d\n", *ip);
+
+   printf("Inserting 15 after 5\n");
+   for (ip = list_begin(l, &lit); NULL != ip; ip = list_next( &lit))
+      {
+      if (5 == *ip)
+	 {
+	 int * newip = malloc(sizeof(int));
+	 if (NULL == newip)
+	    {
+	    perror("malloc");
+	    exit(EXIT_FAILURE);
+	    }
+	 *newip = 15;
+	 if (NULL == list_insert_after(&lit, newip))
+	    {
+	    perror("malloc");
+	    exit(EXIT_FAILURE);
+	    }
+	 break;
+	 }
+      }
+
+   printf("Inserting 20 before 8\n");
+   for (ip = list_begin(l, &lit); NULL != ip; ip = list_next( &lit))
+      {
+      if (8 == *ip)
+	 {
+	 int * newip = malloc(sizeof(int));
+	 if (NULL == newip)
+	    {
+	    perror("malloc");
+	    exit(EXIT_FAILURE);
+	    }
+	 *newip = 20;
+	 if (NULL == list_insert_before(&lit, newip))
+	    {
+	    perror("malloc");
+	    exit(EXIT_FAILURE);
+	    }
+	 break;
+	 }
+      }
+
+   printf("size %zd\n", list_size(l));
+
+   printf("Walking back to front\n");
+   for (ip = list_end(l, &lit); NULL != ip ; ip = list_prev(&lit))
+      printf("%d\n", *ip);
+
+
+   printf("Erasing front to back\n");
+   list_begin(l, &lit);
+   while (NULL != (ip = list_value(&lit)))
+      {
+      printf("%d\n", *ip);
+      list_erase(&lit);
+      free(ip);
+      }
+   printf("size %zd\n", list_size(l));
+
+   list_delete(l);
+   exit(EXIT_SUCCESS);
+
+   }
diff -r f32df8c249f0 -r e117c4d93602 src/queue_test.c
--- a/src/queue_test.c	Fri Sep 21 02:08:13 2012 -0500
+++ b/src/queue_test.c	Fri Sep 21 18:42:49 2012 -0500
@@ -42,7 +42,10 @@
        ip = malloc(sizeof(int));
       *ip = i;
       if (NULL == queue_push(q, (void *) ip))
+	 {
          perror("queue_push");
+	 free(ip);
+	 }
       }
 
    // Empty the queue
diff -r f32df8c249f0 -r e117c4d93602 src/stack_test.c
--- a/src/stack_test.c	Fri Sep 21 02:08:13 2012 -0500
+++ b/src/stack_test.c	Fri Sep 21 18:42:49 2012 -0500
@@ -28,6 +28,7 @@
    while (NULL != (ip = stack_pop(s)))
       {
       printf("%d\n", *ip);
+      free(ip);
       }
    printf("stack size is %zd\n", stack_size(s));