# HG changeset patch
# User Eris Caffee <discordia@eldalin.com>
# Date 1348874693 18000
# Node ID 68f85ffc6029be17e582bb3a51a6d0a042ed28bf
# Parent  abdba37f67a27fa869b333ac5b19f393e646daf3
Finished rbtree.  Reworked the iterators in list.  Minor tweaks to others.

diff -r abdba37f67a2 -r 68f85ffc6029 CMakeLists.txt
--- a/CMakeLists.txt	Fri Sep 28 03:08:25 2012 -0500
+++ b/CMakeLists.txt	Fri Sep 28 18:24:53 2012 -0500
@@ -76,3 +76,8 @@
 add_executable (bst_test
   ${bst_SRCS}
   )
+
+set (rbtree_SRCS src/rbtree.h src/rbtree.c src/rbtree_test.c)
+add_executable (rbtree_test
+  ${rbtree_SRCS}
+  )
diff -r abdba37f67a2 -r 68f85ffc6029 src/bst.c
--- a/src/bst.c	Fri Sep 28 03:08:25 2012 -0500
+++ b/src/bst.c	Fri Sep 28 18:24:53 2012 -0500
@@ -25,7 +25,6 @@
    struct bst_node * curr;
    };
 
-// Private functions.
 void bst_data_walk_inorder(struct bst_node * node, void (*op)(void * data));
 void bst_data_walk_preorder(struct bst_node * node, void (*op)(void * data));
 void bst_data_walk_postorder(struct bst_node * node, void (*op)(void * data));
@@ -35,11 +34,14 @@
 void * bst_data_search(struct bst * bst, struct bst_node * node, void * data);
 void * bst_node_minimum(struct bst_node * node);
 void * bst_node_maximum(struct bst_node * node);
+
 void bst_node_free(struct bst_node * node);
 
 struct bst_node * bst_node_search(struct bst * bst, struct bst_node * node, void * data);
+struct bst_node * bst_transplant(struct bst * bst, struct bst_node * a, struct bst_node * b);
 
-struct bst_node * bst_transplant(struct bst * bst, struct bst_node * a, struct bst_node * b);
+void bst_dump(struct bst * bst, void (*print_val)(void *) );
+void bst_node_dump_preorder(struct bst * bst, struct bst_node * node, void (*print_val)(void *), int depth);
 
 ////////////////////////////////////////////////////////////////////////////////
 struct bst *
@@ -473,3 +475,23 @@
    return data;
    }
 
+////////////////////////////////////////////////////////////////////////////////
+void
+bst_dump(struct bst * bst, void (*print_val)(void *) )
+   {
+   bst_node_dump_preorder(bst, bst->root, print_val, 0);
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+void
+bst_node_dump_preorder(struct bst * bst, struct bst_node * node, void (*print_val)(void *), int depth)
+   {
+   for (int i=0; i < depth; i++)
+      printf("\t");
+   print_val(node->data);
+   printf("\n");
+   if (NULL != node->left)
+      bst_node_dump_preorder(bst, node->left, print_val, depth+1);
+   if (NULL != node->right)
+      bst_node_dump_preorder(bst, node->right, print_val, depth+1);
+   }
diff -r abdba37f67a2 -r 68f85ffc6029 src/bst.h
--- a/src/bst.h	Fri Sep 28 03:08:25 2012 -0500
+++ b/src/bst.h	Fri Sep 28 18:24:53 2012 -0500
@@ -10,20 +10,25 @@
 
 struct bst * bst_new(bool (*le)(void * a, void * b), bool (*eq)(void * a, void * b));
 void bst_delete(struct bst * bst);
-void * bst_insert(struct bst * bst, void * data);
-void * bst_search(struct bst * bst, void * data);
-void * bst_search_iterative(struct bst * bst, void * data);
-void * bst_minimum(struct bst * bst);
-void * bst_maximum(struct bst * bst);
-void bst_walk_inorder(struct bst * bst, void (*op)(void * data));
-void bst_walk_preorder(struct bst * bst, void (*op)(void * data));
-void bst_walk_postorder(struct bst * bst, void (*op)(void * data));
-struct bst_iterator * bst_begin(struct bst * bst);
-struct bst_iterator * bst_end(struct bst * bst);
-struct bst_iterator * bst_next(struct bst_iterator * it);
-struct bst_iterator * bst_prev(struct bst_iterator * it);
-void * bst_value(struct bst_iterator * it);
-void * bst_find(struct bst_iterator * it, void * data);
-void * bst_remove(struct bst_iterator * it);
+
+void * bst_insert  (struct bst * bst, void * data);
+void * bst_search  (struct bst * bst, void * data);
+void * bst_search_iterative (struct bst * bst, void * data);
+void * bst_minimum (struct bst * bst);
+void * bst_maximum (struct bst * bst);
+
+void bst_walk_inorder   (struct bst * bst, void (*op)(void * data));
+void bst_walk_preorder  (struct bst * bst, void (*op)(void * data));
+void bst_walk_postorder (struct bst * bst, void (*op)(void * data));
+
+struct bst_iterator * bst_begin  (struct bst * bst);
+struct bst_iterator * bst_end    (struct bst * bst);
+struct bst_iterator * bst_next   (struct bst_iterator * it);
+struct bst_iterator * bst_prev   (struct bst_iterator * it);
+void *                bst_value  (struct bst_iterator * it);
+void *                bst_find   (struct bst_iterator * it, void * data);
+void *                bst_remove (struct bst_iterator * it);
+
+void bst_dump (struct bst * bst, void (*print_val)(void *) );
 
 #endif
diff -r abdba37f67a2 -r 68f85ffc6029 src/bst_test.c
--- a/src/bst_test.c	Fri Sep 28 03:08:25 2012 -0500
+++ b/src/bst_test.c	Fri Sep 28 18:24:53 2012 -0500
@@ -5,7 +5,12 @@
 
 #include "bst.h"
 
-#define MAX_NUMS 10
+#define MAX_NUMS 20
+
+void print_val(void * data)
+   {
+   printf("%d", *((int *) data));
+   }
 
 bool le(void *a, void * b)
    {
@@ -29,6 +34,19 @@
 
 int main(int argc, char ** argv)
    {
+   int sorted[100] = {
+   35005211, 42999170, 84353895, 135497281, 137806862, 149798315, 184803526, 233665123, 278722862, 294702567,
+   304089172, 336465782, 356426808, 412776091, 424238335, 468703135, 491705403, 511702305, 521595368, 572660336,
+   596516649, 608413784, 610515434, 628175011, 635723058, 709393584, 719885386, 749241873, 752392754, 756898537,
+   760313750, 783368690, 805750846, 846930886, 855636226, 859484421, 861021530, 939819582, 943947739, 945117276,
+   982906996, 1025202362, 1059961393, 1100661313, 1101513929, 1102520059, 1125898167, 1129566413, 1131176229, 1141616124,
+   1159126505, 1189641421, 1264095060, 1303455736, 1315634022, 1350490027, 1365180540, 1369133069, 1374344043, 1411549676,
+   1424268980, 1433925857, 1469348094, 1474612399, 1477171087, 1540383426, 1548233367, 1585990364, 1632621729, 1649760492,
+   1653377373, 1656478042, 1681692777, 1714636915, 1726956429, 1734575198, 1749698586, 1780695788, 1801979802, 1804289383,
+   1827336327, 1843993368, 1889947178, 1911759956, 1914544919, 1918502651, 1937477084, 1956297539, 1957747793, 1967513926,
+   1973594324, 1984210012, 1998898814, 2001100545, 2038664370, 2044897763, 2053999932, 2084420925, 2089018456, 2145174067,
+   };
+
    struct bst * bst = bst_new(le, eq);
    if (NULL == bst)
       {
@@ -50,6 +68,7 @@
 	 }
 
       *ip = rand();
+      //      *ip = sorted[i];
       printf("%d\n", *ip);
       if (NULL == bst_insert(bst, ip))
 	 {
@@ -60,6 +79,8 @@
    printf ("======================\n");
 
 
+   bst_dump(bst, print_val);
+
    ////////////////////////////////////////
    bst_walk_inorder(bst, print);
 
diff -r abdba37f67a2 -r 68f85ffc6029 src/dequeue.c
--- a/src/dequeue.c	Fri Sep 28 03:08:25 2012 -0500
+++ b/src/dequeue.c	Fri Sep 28 18:24:53 2012 -0500
@@ -12,7 +12,8 @@
    };
 
 ////////////////////////////////////////////////////////////////////////////////
-struct dequeue * dequeue_new(size_t const max)
+struct dequeue *
+dequeue_new(size_t const max)
    {
    if (max < 1)
       return NULL;
@@ -39,7 +40,8 @@
 // NULL on error
 // elem on success and the buffer is not full
 // the overwritten element on success if the buffer was full
-void * dequeue_push_top(struct dequeue * deq, void * elem)
+void *
+dequeue_push_top(struct dequeue * deq, void * elem)
    {
    if ((NULL == deq) || (NULL == elem))
       return NULL;
@@ -59,7 +61,8 @@
    }
 
 ////////////////////////////////////////////////////////////////////////////////
-void * dequeue_push_bottom(struct dequeue * deq, void * elem)
+void *
+dequeue_push_bottom(struct dequeue * deq, void * elem)
    {
    if ((NULL == deq) || (NULL == elem))
       return NULL;
@@ -79,7 +82,8 @@
    }
 
 ////////////////////////////////////////////////////////////////////////////////
-void * dequeue_pop_top(struct dequeue * deq)
+void *
+dequeue_pop_top(struct dequeue * deq)
    {
    if (NULL == deq)
       return NULL;
@@ -100,7 +104,8 @@
    }
 
 ////////////////////////////////////////////////////////////////////////////////
-void * dequeue_pop_bottom(struct dequeue * deq)
+void *
+dequeue_pop_bottom(struct dequeue * deq)
    {
    if (NULL == deq)
       return NULL;
@@ -122,7 +127,8 @@
 
 
 ////////////////////////////////////////////////////////////////////////////////
-size_t dequeue_size(struct dequeue * deq)
+size_t
+dequeue_size(struct dequeue * deq)
    {
    if (NULL == deq)
       return 0;
@@ -130,7 +136,8 @@
    }
 
 ////////////////////////////////////////////////////////////////////////////////
-void dequeue_delete(struct dequeue * deq)
+void
+dequeue_delete(struct dequeue * deq)
    {
    if (NULL != deq)
       {
diff -r abdba37f67a2 -r 68f85ffc6029 src/dequeue.h
--- a/src/dequeue.h	Fri Sep 28 03:08:25 2012 -0500
+++ b/src/dequeue.h	Fri Sep 28 18:24:53 2012 -0500
@@ -7,10 +7,12 @@
 
 struct dequeue * dequeue_new(size_t const size);
 void dequeue_delete(struct dequeue * deq);
-void * dequeue_push_top(struct dequeue * deq, void * elem);
-void * dequeue_pop_top(struct dequeue * deq);
-void * dequeue_push_bottom(struct dequeue * deq, void * elem);
-void * dequeue_pop_bottom(struct dequeue * deq);
-size_t dequeue_size(struct dequeue * deq);
+
+void * dequeue_push_top    (struct dequeue * deq, void * elem);
+void * dequeue_pop_top     (struct dequeue * deq);
+void * dequeue_push_bottom (struct dequeue * deq, void * elem);
+void * dequeue_pop_bottom  (struct dequeue * deq);
+
+size_t dequeue_size (struct dequeue * deq);
 
 #endif
diff -r abdba37f67a2 -r 68f85ffc6029 src/dequeue_test.c
--- a/src/dequeue_test.c	Fri Sep 28 03:08:25 2012 -0500
+++ b/src/dequeue_test.c	Fri Sep 28 18:24:53 2012 -0500
@@ -38,6 +38,7 @@
    printf("dequeue size is %zd\n", dequeue_size(deq));
 
    // Overfill the dequeue
+   printf("Overfilling the queue.  5 failures are expected.\n");
    for (i=MAX; i < 2*MAX; i++)
       {
        ip = malloc(sizeof(int));
@@ -50,7 +51,7 @@
       errno = 0;
       if (NULL == dequeue_push_top(deq, (void *) ip))
          {
-         perror("dequeue_push_top");
+         printf("dequeue_push_top failed\n");
          free(ip);
          }
       }
@@ -71,7 +72,7 @@
       *ip = i;
       if (NULL == dequeue_push_top(deq, (void *) ip))
          {
-         perror("dequeue_push");
+         printf("dequeue_push_top failed\n");
          free(ip);
          }
       }
diff -r abdba37f67a2 -r 68f85ffc6029 src/list.c
--- a/src/list.c	Fri Sep 28 03:08:25 2012 -0500
+++ b/src/list.c	Fri Sep 28 18:24:53 2012 -0500
@@ -176,6 +176,10 @@
    return t;
    }
 
+
+
+
+
 ////////////////////////////////////////////////////////////////////////////////
 // Intialize an iterator to point to the first element of the list
 struct list_iterator *
@@ -213,72 +217,74 @@
    }
 
 ////////////////////////////////////////////////////////////////////////////////
-// Move the iterator to the next element in the list, returning its value.
-void *
-list_next(struct list_iterator * lit)
+// Move the iterator to the next element in the list.
+struct list_iterator *
+list_next(struct list_iterator * it)
    {
-   if (NULL == lit)
+   if (NULL == it)
       return NULL;
 
-   lit->curr = lit->curr->next;
-
-   if (lit->curr)
-      return lit->curr->data;
-
-   return NULL;
+   it->curr = it->curr->next;
+   return it->curr;
    }
 
 ////////////////////////////////////////////////////////////////////////////////
-// Move the iterator to the previous element in the list, returning its value.
-void *
-list_prev(struct list_iterator * lit)
+// Move the iterator to the previous element in the list.
+struct list_iterator *
+list_prev(struct list_iterator * it)
    {
-   if (NULL == lit)
+   if (NULL == it)
       return NULL;
 
-   lit->curr = lit->curr->prev;
-
-   if (lit->curr)
-      return lit->curr->data;
-
-   return NULL;
+   it->curr = it->curr->prev;
+   return it->curr;
    }
 
 ////////////////////////////////////////////////////////////////////////////////
-// Remove the current element pointed to by the iterator, returning that elements value.
+// Remove the current element pointed to by the iterator.
+// Returns the data element that was removed so the caller can free it.
 void *
-list_erase(struct list_iterator * lit)
+list_remove(struct list_iterator * it)
    {
-   if ( (NULL == lit) || (NULL == lit->curr) )
+   if ( (NULL == it) || (NULL == it->curr) )
       return NULL;
 
-   if (lit->curr->prev)
-      lit->curr->prev->next = lit->curr->next;
+   if (it->curr->prev)
+      it->curr->prev->next = it->curr->next;
 
-   if (lit->curr->next)
-      lit->curr->next->prev = lit->curr->prev;
+   if (it->curr->next)
+      it->curr->next->prev = it->curr->prev;
 
-   struct list_node * temp = lit->curr;
-   void * elem = lit->curr->data;
+   struct list_node * temp = it->curr;
+   void * elem = it->curr->data;
 
-   lit->curr = lit->curr->next;
+   it->curr = it->curr->next;
    free(temp);
 
-   lit->l->size--;
-   if (0 == lit->l->size)
-      lit->l->tail = lit->l->head = NULL;
+   it->l->size--;
+   if (0 == it->l->size)
+      it->l->tail = it->l->head = NULL;
 
    return elem;
    }
 
 ////////////////////////////////////////////////////////////////////////////////
+// Return the value of the element pointed to by the iterator.
+void *
+list_value(struct list_iterator * it)
+   {
+   if ( (NULL == it) || (NULL == it->curr) )
+      return NULL;
+   return it->curr->data;
+   }
+
+////////////////////////////////////////////////////////////////////////////////
 // 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)
+struct list_iterator *
+list_insert_after(struct list_iterator * it, void * elem)
    {
-   if ( (NULL == lit) || (NULL == elem) || (NULL == lit->curr) )
+   if ( (NULL == it) || (NULL == elem) || (NULL == it->curr) )
       return NULL;
 
    struct list_node * new = malloc(sizeof(struct list_node));
@@ -286,29 +292,28 @@
       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;
+   new->prev = it->curr;
+   if (it->curr->next)
+      it->curr->next->prev = new;
+   new->next = it->curr->next;
+   it->curr->next = new;
 
-   lit->curr = new;
+   it->curr = new;
 
-   lit->l->size++;
-   if (NULL == lit->curr->next)
-      lit->l->tail = lit->curr;
+   it->l->size++;
+   if (NULL == it->curr->next)
+      it->l->tail = it->curr;
 
-   return elem;
+   return it;
    }
 
 ////////////////////////////////////////////////////////////////////////////////
 // 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)
+struct list_iterator *
+list_insert_before(struct list_iterator * it, void * elem)
    {
-   if ( (NULL == lit) || (NULL == elem) || (NULL == lit->curr) )
+   if ( (NULL == it) || (NULL == elem) || (NULL == it->curr) )
       return NULL;
 
    struct list_node * new = malloc(sizeof(struct list_node));
@@ -316,28 +321,18 @@
       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;
+   new->next = it->curr;
+   if (it->curr->prev)
+      it->curr->prev->next = new;
+   new->prev = it->curr->prev;
+   it->curr->prev = new;
 
-   lit->curr = new;
+   it->curr = new;
 
-   lit->l->size++;
-   if (NULL == lit->curr->prev)
-      lit->l->head = lit->curr;
+   it->l->size++;
+   if (NULL == it->curr->prev)
+      it->l->head = it->curr;
 
-   return elem;
+   return it;
    }
 
-////////////////////////////////////////////////////////////////////////////////
-// 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 abdba37f67a2 -r 68f85ffc6029 src/list.h
--- a/src/list.h	Fri Sep 28 03:08:25 2012 -0500
+++ b/src/list.h	Fri Sep 28 18:24:53 2012 -0500
@@ -9,6 +9,7 @@
 
 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);
@@ -17,13 +18,15 @@
 
 // The iterators are different than their c++ STL counterparts.
 // They are bi-directional, and list_end points to the last element, not the empty space beyond the last elem.
-struct list_iterator * list_begin(struct list * l);
-struct list_iterator * list_end(struct list * l);
-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);
+struct list_iterator * list_begin  (struct list * l);
+struct list_iterator * list_end    (struct list * l);
+struct list_iterator * list_next   (struct list_iterator * lit);
+struct list_iterator * list_prev   (struct list_iterator * lit);
+struct list_iterator * list_find   (struct list_iterator * it, void * data);
+void *                 list_remove (struct list_iterator * lit);
+void *                 list_value  (struct list_iterator * lit);
+
+struct list_iterator * list_insert_after  (struct list_iterator * lit, void * elem);
+struct list_iterator * list_insert_before (struct list_iterator * lit, void * elem);
 
 #endif
diff -r abdba37f67a2 -r 68f85ffc6029 src/list_test.c
--- a/src/list_test.c	Fri Sep 28 03:08:25 2012 -0500
+++ b/src/list_test.c	Fri Sep 28 18:24:53 2012 -0500
@@ -71,7 +71,7 @@
 
 
    /////////////////////////////////////
-   // Push back and pop back
+   // Push back and pop front
    for (int i = 0; i < MAX ; i++)
       {
       int * ip = malloc(sizeof(int));
@@ -119,16 +119,18 @@
    printf("size %zd\n", list_size(l));
 
    struct list_iterator * lit;
+   struct list_iterator * next;
    int * ip;
 
    printf("Walking front to back\n");
-   for (lit = list_begin(l); NULL != ip; ip = list_next( &lit))
-      printf("%d\n", *ip);
+   for (next = lit = list_begin(l); NULL != next; next = list_next(lit))
+      printf("%d\n", *((int *) list_value(lit)));
+   free(lit);
 
    printf("Inserting 15 after 5\n");
-   for (ip = list_begin(l, &lit); NULL != ip; ip = list_next( &lit))
+   for (next = lit = list_begin(l); NULL != next ; next = list_next(lit))
       {
-      if (5 == *ip)
+      if (5 == *((int *) list_value(lit)))
 	 {
 	 int * newip = malloc(sizeof(int));
 	 if (NULL == newip)
@@ -137,7 +139,7 @@
 	    exit(EXIT_FAILURE);
 	    }
 	 *newip = 15;
-	 if (NULL == list_insert_after(&lit, newip))
+	 if (NULL == list_insert_after(lit, newip))
 	    {
 	    perror("malloc");
 	    exit(EXIT_FAILURE);
@@ -145,11 +147,12 @@
 	 break;
 	 }
       }
+   free(lit);
 
    printf("Inserting 20 before 8\n");
-   for (ip = list_begin(l, &lit); NULL != ip; ip = list_next( &lit))
+   for (next = lit = list_begin(l); NULL != next ; next = list_next(lit))
       {
-      if (8 == *ip)
+      if (8 == *((int *) list_value(lit)))
 	 {
 	 int * newip = malloc(sizeof(int));
 	 if (NULL == newip)
@@ -158,7 +161,7 @@
 	    exit(EXIT_FAILURE);
 	    }
 	 *newip = 20;
-	 if (NULL == list_insert_before(&lit, newip))
+	 if (NULL == list_insert_before(lit, newip))
 	    {
 	    perror("malloc");
 	    exit(EXIT_FAILURE);
@@ -166,22 +169,23 @@
 	 break;
 	 }
       }
+   free(lit);
 
    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);
-
+   for (next = lit = list_end(l); NULL != next ; next = list_prev(lit))
+      printf("%d\n", *((int *) list_value(lit)));
+   free(lit);
 
    printf("Erasing front to back\n");
-   list_begin(l, &lit);
-   while (NULL != (ip = list_value(&lit)))
+   lit = list_begin(l);
+   while (NULL != (ip = list_remove(lit)))
       {
       printf("%d\n", *ip);
-      list_erase(&lit);
       free(ip);
       }
+   free(lit);
    printf("size %zd\n", list_size(l));
 
    list_delete(l);
diff -r abdba37f67a2 -r 68f85ffc6029 src/pqueue.h
--- a/src/pqueue.h	Fri Sep 28 03:08:25 2012 -0500
+++ b/src/pqueue.h	Fri Sep 28 18:24:53 2012 -0500
@@ -8,9 +8,10 @@
 
 struct pqueue * pqueue_new(size_t max, bool (*comp)(void const * const a, void const * const b));
 void pqueue_delete(struct pqueue * pq);
-void * pqueue_push(struct pqueue * pq, void * elem);
-void * pqueue_pop(struct pqueue * pq);
-void * pqueue_peek(struct pqueue * pq);
-size_t  pqueue_size(struct pqueue * pq);
+
+void *  pqueue_push (struct pqueue * pq, void * elem);
+void *  pqueue_pop  (struct pqueue * pq);
+void *  pqueue_peek (struct pqueue * pq);
+size_t  pqueue_size (struct pqueue * pq);
 
 #endif // ndef PQUEUE_
diff -r abdba37f67a2 -r 68f85ffc6029 src/queue.c
--- a/src/queue.c	Fri Sep 28 03:08:25 2012 -0500
+++ b/src/queue.c	Fri Sep 28 18:24:53 2012 -0500
@@ -12,13 +12,11 @@
    };
 
 ////////////////////////////////////////////////////////////////////////////////
-struct queue * queue_new(size_t const max)
+struct queue *
+queue_new(size_t const max)
    {
    if (max < 1)
-      {
-      errno = EINVAL;
       return NULL;
-      }
 
    struct queue * queue = malloc(sizeof(struct queue));
    if (NULL == queue)
@@ -42,19 +40,14 @@
 // NULL on error
 // elem on success and the buffer is not full
 // the overwritten element on success if the buffer was full
-void * queue_push(struct queue * queue, void * elem)
+void *
+queue_push(struct queue * queue, void * elem)
    {
    if ((NULL == queue) || (NULL == elem))
-      {
-      errno = EINVAL;
       return NULL;
-      }
 
    if (queue->count == queue->max)
-      {
-      errno = ENOMEM;
       return NULL;
-      }
 
    size_t end = (queue->start + queue->count) % queue->max;
 
@@ -65,13 +58,11 @@
    }
 
 ////////////////////////////////////////////////////////////////////////////////
-void * queue_pop(struct queue * queue)
+void *
+queue_pop(struct queue * queue)
    {
    if (NULL == queue)
-      {
-      errno = EINVAL;
       return NULL;
-      }
 
    if (0 == queue->count)
       return NULL;
@@ -84,19 +75,18 @@
    }
 
 ////////////////////////////////////////////////////////////////////////////////
-size_t queue_size(struct queue * queue)
+size_t
+queue_size(struct queue * queue)
    {
    if (NULL == queue)
-      {
-      errno = EINVAL;
-      return -1;
-      }
+      return 0;
 
    return queue->count;
    }
 
 ////////////////////////////////////////////////////////////////////////////////
-void queue_delete(struct queue * queue)
+void
+queue_delete(struct queue * queue)
    {
    if (NULL != queue) free(queue->data);
    free(queue);
diff -r abdba37f67a2 -r 68f85ffc6029 src/queue.h
--- a/src/queue.h	Fri Sep 28 03:08:25 2012 -0500
+++ b/src/queue.h	Fri Sep 28 18:24:53 2012 -0500
@@ -7,8 +7,9 @@
 
 struct queue * queue_new(size_t const size);
 void queue_delete(struct queue * queue);
-void * queue_push(struct queue * queue, void * elem);
-void * queue_pop(struct queue * queue);
-size_t queue_size(struct queue * queue);
+
+void * queue_push (struct queue * queue, void * elem);
+void * queue_pop  (struct queue * queue);
+size_t queue_size (struct queue * queue);
 
 #endif
diff -r abdba37f67a2 -r 68f85ffc6029 src/queue_test.c
--- a/src/queue_test.c	Fri Sep 28 03:08:25 2012 -0500
+++ b/src/queue_test.c	Fri Sep 28 18:24:53 2012 -0500
@@ -24,7 +24,10 @@
        ip = malloc(sizeof(int));
       *ip = i;
       if (NULL == queue_push(q, (void *) ip))
-         perror("queue_push");
+	 {
+         printf("queue_push failed\n");
+	 free(ip);
+	 }
       }
 
    // remove 5 items
@@ -43,7 +46,7 @@
       *ip = i;
       if (NULL == queue_push(q, (void *) ip))
 	 {
-         perror("queue_push");
+         printf("queue_push failed\n");
 	 free(ip);
 	 }
       }
diff -r abdba37f67a2 -r 68f85ffc6029 src/rbtree.c
--- a/src/rbtree.c	Fri Sep 28 03:08:25 2012 -0500
+++ b/src/rbtree.c	Fri Sep 28 18:24:53 2012 -0500
@@ -30,21 +30,26 @@
    struct rbtree_node * curr;
    };
 
-// Private functions.
-void rbtree_data_walk_inorder(struct rbtree * rbtree, struct rbtree_node * node, void (*op)(void * data));
-void rbtree_data_walk_preorder(struct rbtree * rbtree, struct rbtree_node * node, void (*op)(void * data));
-void rbtree_data_walk_postorder(struct rbtree * rbtree, struct rbtree_node * node, void (*op)(void * data));
-void rbtree_node_walk_postorder(struct rbtree * rbtree, struct rbtree_node * node, void (*op)(struct rbtree_node * n));
-void * rbtree_data_search(struct rbtree * rbtree, struct rbtree_node * node, void * data);
-void * rbtree_node_minimum(struct rbtree * rbtree, struct rbtree_node * node);
-void * rbtree_node_maximum(struct rbtree * rbtree, struct rbtree_node * node);
-void rbtree_node_free(struct rbtree_node * node);
-struct rbtree_node * rbtree_node_search(struct rbtree * rbtree, struct rbtree_node * node, void * data);
-struct rbtree_node * rbtree_transplant(struct rbtree * rbtree, struct rbtree_node * a, struct rbtree_node * b);
-void rbtree_rotate_left(struct rbtree * rbtree, struct rbtree_node * node);
-void rbtree_rotate_right(struct rbtree * rbtree, struct rbtree_node * node);
-void rbtree_insert_fixup(struct rbtree * rbtree, struct rbtree_node * node);
-void rbtree_remove_fixup(struct rbtree * rbtree, struct rbtree_node * node);
+void * rbtree_data_search  (struct rbtree * rbtree, struct rbtree_node * node, void * data);
+void * rbtree_node_minimum (struct rbtree * rbtree, struct rbtree_node * node);
+void * rbtree_node_maximum (struct rbtree * rbtree, struct rbtree_node * node);
+
+void rbtree_data_walk_inorder   (struct rbtree * rbtree, struct rbtree_node * node, void (*op)(void * data));
+void rbtree_data_walk_preorder  (struct rbtree * rbtree, struct rbtree_node * node, void (*op)(void * data));
+void rbtree_data_walk_postorder (struct rbtree * rbtree, struct rbtree_node * node, void (*op)(void * data));
+void rbtree_node_walk_postorder (struct rbtree * rbtree, struct rbtree_node * node, void (*op)(struct rbtree_node * n));
+
+void rbtree_node_free (struct rbtree_node * node);
+
+struct rbtree_node * rbtree_node_search (struct rbtree * rbtree, struct rbtree_node * node, void * data);
+
+struct rbtree_node * rbtree_transplant  (struct rbtree * rbtree, struct rbtree_node * a, struct rbtree_node * b);
+void rbtree_rotate_left  (struct rbtree * rbtree, struct rbtree_node * node);
+void rbtree_rotate_right (struct rbtree * rbtree, struct rbtree_node * node);
+void rbtree_insert_fixup (struct rbtree * rbtree, struct rbtree_node * node);
+void rbtree_remove_fixup (struct rbtree * rbtree, struct rbtree_node * node);
+
+void rbtree_node_dump_preorder(struct rbtree * rbtree, struct rbtree_node * node, void (*print_val)(void *), int depth);
 
 ////////////////////////////////////////////////////////////////////////////////
 struct rbtree *
@@ -136,7 +141,6 @@
    return new->data;
    }
 
-
 ////////////////////////////////////////////////////////////////////////////////
 void
 rbtree_insert_fixup(struct rbtree * rbtree, struct rbtree_node * node)
@@ -373,7 +377,7 @@
       return NULL;
 
    struct rbtree_node * min = rbtree->root;
-   while (min->left)
+   while (rbtree->nil != min->left)
       min = min->left;
 
    struct rbtree_iterator * it = malloc(sizeof(struct rbtree_iterator));
@@ -393,7 +397,7 @@
       return NULL;
 
    struct rbtree_node * max = rbtree->root;
-   while (max->right)
+   while (rbtree->nil != max->right)
       max = max->right;
 
    struct rbtree_iterator * it = malloc(sizeof(struct rbtree_iterator));
@@ -428,7 +432,7 @@
    else
       {
       struct rbtree_node * min = it->curr->right;
-      while (min->left)
+      while (it->rbtree->nil != min->left)
 	 min = min->left;
       it->curr = min;
       }
@@ -458,7 +462,7 @@
    else
       {
       struct rbtree_node * max = it->curr->left;
-      while (max->right)
+      while (it->rbtree->nil != max->right)
 	 max = max->right;
       it->curr = max;
       }
@@ -702,3 +706,43 @@
    node->parent = y;
    }
 
+////////////////////////////////////////////////////////////////////////////////
+unsigned int rbtree_black_depth(struct rbtree * rbtree)
+   {
+   if ( (NULL == rbtree) || (NULL == rbtree->root) )
+      return 0;
+
+   struct rbtree_node * node = rbtree->root;
+   unsigned int black_depth = 0;
+
+   while (rbtree->nil != node)
+      {
+      if (BLACK == node->color)
+	 black_depth++;
+      node = node->left;
+      }
+
+   return black_depth;
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+void
+rbtree_dump(struct rbtree * rbtree, void (*print_val)(void *) )
+   {
+   rbtree_node_dump_preorder(rbtree, rbtree->root, print_val, 0);
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+void
+rbtree_node_dump_preorder(struct rbtree * rbtree, struct rbtree_node * node, void (*print_val)(void *), int depth)
+   {
+   for (int i=0; i < depth; i++)
+      printf("\t");
+   printf("%-8s", (BLACK == node->color ? "black" : "red"));
+   print_val(node->data);
+   printf("\n");
+   if (rbtree->nil != node->left)
+      rbtree_node_dump_preorder(rbtree, node->left, print_val, depth+1);
+   if (rbtree->nil != node->right)
+      rbtree_node_dump_preorder(rbtree, node->right, print_val, depth+1);
+   }
diff -r abdba37f67a2 -r 68f85ffc6029 src/rbtree.h
--- a/src/rbtree.h	Fri Sep 28 03:08:25 2012 -0500
+++ b/src/rbtree.h	Fri Sep 28 18:24:53 2012 -0500
@@ -10,22 +10,26 @@
 
 struct rbtree * rbtree_new(bool (*le)(void * a, void * b), bool (*eq)(void * a, void * b));
 void rbtree_delete(struct rbtree * rbtree);
-void * rbtree_insert(struct rbtree * rbtree, void * data);
-void * rbtree_search(struct rbtree * rbtree, void * data);
-void * rbtree_search_iterative(struct rbtree * rbtree, void * data);
-void * rbtree_minimum(struct rbtree * rbtree);
-void * rbtree_maximum(struct rbtree * rbtree);
 
-void rbtree_walk_inorder(struct rbtree * rbtree, void (*op)(void * data));
-void rbtree_walk_preorder(struct rbtree * rbtree, void (*op)(void * data));
-void rbtree_walk_postorder(struct rbtree * rbtree, void (*op)(void * data));
+void * rbtree_insert (struct rbtree * rbtree, void * data);
+void * rbtree_search (struct rbtree * rbtree, void * data);
+void * rbtree_search_iterative (struct rbtree * rbtree, void * data);
+void * rbtree_minimum (struct rbtree * rbtree);
+void * rbtree_maximum (struct rbtree * rbtree);
 
-struct rbtree_iterator * rbtree_begin(struct rbtree * rbtree);
-struct rbtree_iterator * rbtree_end(struct rbtree * rbtree);
-struct rbtree_iterator * rbtree_next(struct rbtree_iterator * it);
-struct rbtree_iterator * rbtree_prev(struct rbtree_iterator * it);
-void * rbtree_value(struct rbtree_iterator * it);
-void * rbtree_find(struct rbtree_iterator * it, void * data);
-void * rbtree_remove(struct rbtree_iterator * it);
+void rbtree_walk_inorder   (struct rbtree * rbtree, void (*op)(void * data));
+void rbtree_walk_preorder  (struct rbtree * rbtree, void (*op)(void * data));
+void rbtree_walk_postorder (struct rbtree * rbtree, void (*op)(void * data));
+
+struct rbtree_iterator * rbtree_begin  (struct rbtree * rbtree);
+struct rbtree_iterator * rbtree_end    (struct rbtree * rbtree);
+struct rbtree_iterator * rbtree_next   (struct rbtree_iterator * it);
+struct rbtree_iterator * rbtree_prev   (struct rbtree_iterator * it);
+void *                   rbtree_find   (struct rbtree_iterator * it, void * data);
+void *                   rbtree_remove (struct rbtree_iterator * it);
+void *                   rbtree_value  (struct rbtree_iterator * it);
+
+unsigned int rbtree_black_depth(struct rbtree * rbtree);
+void rbtree_dump(struct rbtree * rbtree, void (*print_val)(void *) );
 
 #endif
diff -r abdba37f67a2 -r 68f85ffc6029 src/ring_buffer.c
--- a/src/ring_buffer.c	Fri Sep 28 03:08:25 2012 -0500
+++ b/src/ring_buffer.c	Fri Sep 28 18:24:53 2012 -0500
@@ -12,13 +12,11 @@
    };
 
 ////////////////////////////////////////////////////////////////////////////////
-struct ring_buffer * ring_buffer_new(size_t const max)
+struct ring_buffer *
+ring_buffer_new(size_t const max)
    {
    if (max < 1)
-      {
-      errno = EINVAL;
       return NULL;
-      }
 
    struct ring_buffer * rb = malloc(sizeof(struct ring_buffer));
    if (NULL == rb)
@@ -42,13 +40,11 @@
 // NULL on error
 // elem on success and the buffer is not full
 // the overwritten element on success if the buffer was full
-void * ring_buffer_write(struct ring_buffer * rb, void * elem)
+void *
+ring_buffer_write(struct ring_buffer * rb, void * elem)
    {
    if ((NULL == rb) || (NULL == elem))
-      {
-      errno = EINVAL;
       return NULL;
-      }
 
    size_t end = rb->start + rb->count;
    void * ret = rb->data[end % rb->max];
@@ -65,13 +61,11 @@
    }
 
 ////////////////////////////////////////////////////////////////////////////////
-void * ring_buffer_read(struct ring_buffer * rb)
+void *
+ring_buffer_read(struct ring_buffer * rb)
    {
    if (NULL == rb)
-      {
-      errno = EINVAL;
       return NULL;
-      }
 
    if (0 == rb->count)
       return NULL;
@@ -84,19 +78,18 @@
    }
 
 ////////////////////////////////////////////////////////////////////////////////
-size_t ring_buffer_size(struct ring_buffer * rb)
+size_t
+ring_buffer_size(struct ring_buffer * rb)
    {
    if (NULL == rb)
-      {
-      errno = EINVAL;
-      return -1;
-      }
+      return 0;
 
    return rb->count;
    }
 
 ////////////////////////////////////////////////////////////////////////////////
-void ring_buffer_delete(struct ring_buffer * rb)
+void
+ring_buffer_delete(struct ring_buffer * rb)
    {
    if (NULL != rb) free(rb->data);
    free(rb);
diff -r abdba37f67a2 -r 68f85ffc6029 src/ring_buffer.h
--- a/src/ring_buffer.h	Fri Sep 28 03:08:25 2012 -0500
+++ b/src/ring_buffer.h	Fri Sep 28 18:24:53 2012 -0500
@@ -7,8 +7,9 @@
 
 struct ring_buffer * ring_buffer_new(size_t const size);
 void ring_buffer_delete(struct ring_buffer * rb);
-void * ring_buffer_write(struct ring_buffer * rb, void * elem);
-void * ring_buffer_read(struct ring_buffer * rb);
-size_t ring_buffer_size(struct ring_buffer * rb);
+
+void * ring_buffer_write (struct ring_buffer * rb, void * elem);
+void * ring_buffer_read  (struct ring_buffer * rb);
+size_t ring_buffer_size  (struct ring_buffer * rb);
 
 #endif
diff -r abdba37f67a2 -r 68f85ffc6029 src/stack.h
--- a/src/stack.h	Fri Sep 28 03:08:25 2012 -0500
+++ b/src/stack.h	Fri Sep 28 18:24:53 2012 -0500
@@ -7,8 +7,9 @@
 
 struct stack * stack_new(size_t const max);
 void stack_delete(struct stack * s);
-void * stack_push(struct stack * s, void * elem);
-void * stack_pop(struct stack * s);
-size_t stack_size(struct stack * s);
+
+void * stack_push (struct stack * s, void * elem);
+void * stack_pop  (struct stack * s);
+size_t stack_size (struct stack * s);
 
 #endif