# HG changeset patch
# User Eris Caffee <discordia@eldalin.com>
# Date 1348819705 18000
# Node ID abdba37f67a27fa869b333ac5b19f393e646daf3
# Parent  6605a342e8f885438d9d725fbadcbb0c7d6819d1
Red-black tree in progress.  Linked list needs iterators redone, also in progress. Sleepy.

diff -r 6605a342e8f8 -r abdba37f67a2 src/bst.c
--- a/src/bst.c	Thu Sep 27 10:57:41 2012 -0500
+++ b/src/bst.c	Fri Sep 28 03:08:25 2012 -0500
@@ -3,6 +3,28 @@
 
 #include "bst.h"
 
+struct bst_node
+   {
+   struct bst_node * parent;
+   struct bst_node * left;
+   struct bst_node * right;
+   void * data;
+   };
+
+struct bst
+   {
+   struct bst_node * root;
+   size_t size;
+   bool (*le)(void * a, void * b);
+   bool (*eq)(void * a, void * b);
+   };
+
+struct bst_iterator
+   {
+   struct bst * bst;
+   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));
@@ -77,6 +99,7 @@
    if (NULL == bst->root)
       {
       bst->root = new;
+      bst->size = 1;
       return new->data;
       }
 
diff -r 6605a342e8f8 -r abdba37f67a2 src/bst.h
--- a/src/bst.h	Thu Sep 27 10:57:41 2012 -0500
+++ b/src/bst.h	Fri Sep 28 03:08:25 2012 -0500
@@ -4,50 +4,25 @@
 #include <stddef.h>
 #include <stdbool.h>
 
-struct bst_node
-   {
-   struct bst_node * parent;
-   struct bst_node * left;
-   struct bst_node * right;
-   void * data;
-   };
-
-struct bst
-   {
-   struct bst_node * root;
-   size_t size;
-   bool (*le)(void * a, void * b);
-   bool (*eq)(void * a, void * b);
-   };
-
-struct bst_iterator
-   {
-   struct bst * bst;
-   struct bst_node * curr;
-   };
+struct bst_node;
+struct bst;
+struct bst_iterator;
 
 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);
 
diff -r 6605a342e8f8 -r abdba37f67a2 src/dequeue.c
--- a/src/dequeue.c	Thu Sep 27 10:57:41 2012 -0500
+++ b/src/dequeue.c	Fri Sep 28 03:08:25 2012 -0500
@@ -1,16 +1,21 @@
 #include <stdlib.h>
-#include <errno.h>
 
 #include "dequeue.h"
 
+struct dequeue
+   {
+   void ** data;
+   size_t max;
+   size_t bottom;
+   size_t top;
+   size_t count;
+   };
+
 ////////////////////////////////////////////////////////////////////////////////
 struct dequeue * dequeue_new(size_t const max)
    {
    if (max < 1)
-      {
-      errno = EINVAL;
       return NULL;
-      }
 
    struct dequeue * deq = malloc(sizeof(struct dequeue));
    if (NULL == deq)
@@ -37,16 +42,10 @@
 void * dequeue_push_top(struct dequeue * deq, void * elem)
    {
    if ((NULL == deq) || (NULL == elem))
-      {
-      errno = EINVAL;
       return NULL;
-      }
 
    if (deq->count == deq->max)
-      {
-      errno = ENOMEM;
       return NULL;
-      }
 
    if (deq->max - 1 == deq->top)
       deq->top = 0;
@@ -63,16 +62,10 @@
 void * dequeue_push_bottom(struct dequeue * deq, void * elem)
    {
    if ((NULL == deq) || (NULL == elem))
-      {
-      errno = EINVAL;
       return NULL;
-      }
 
    if (deq->count == deq->max)
-      {
-      errno = ENOMEM;
       return NULL;
-      }
 
    if (0 == deq->bottom)
       deq->bottom = deq->max - 1;
@@ -89,10 +82,7 @@
 void * dequeue_pop_top(struct dequeue * deq)
    {
    if (NULL == deq)
-      {
-      errno = EINVAL;
       return NULL;
-      }
 
    if (deq->count == 0)
       return NULL;
@@ -113,10 +103,7 @@
 void * dequeue_pop_bottom(struct dequeue * deq)
    {
    if (NULL == deq)
-      {
-      errno = EINVAL;
       return NULL;
-      }
 
    if (deq->count == 0)
       return NULL;
@@ -138,10 +125,7 @@
 size_t dequeue_size(struct dequeue * deq)
    {
    if (NULL == deq)
-      {
-      errno = EINVAL;
       return 0;
-      }
    return deq->count;
    }
 
diff -r 6605a342e8f8 -r abdba37f67a2 src/dequeue.h
--- a/src/dequeue.h	Thu Sep 27 10:57:41 2012 -0500
+++ b/src/dequeue.h	Fri Sep 28 03:08:25 2012 -0500
@@ -3,14 +3,7 @@
 
 #include <stddef.h>
 
-struct dequeue
-   {
-   void ** data;
-   size_t max;
-   size_t bottom;
-   size_t top;
-   size_t count;
-   };
+struct dequeue;
 
 struct dequeue * dequeue_new(size_t const size);
 void dequeue_delete(struct dequeue * deq);
diff -r 6605a342e8f8 -r abdba37f67a2 src/dequeue_test.c
--- a/src/dequeue_test.c	Thu Sep 27 10:57:41 2012 -0500
+++ b/src/dequeue_test.c	Fri Sep 28 03:08:25 2012 -0500
@@ -1,5 +1,6 @@
 #include <stdio.h>
 #include <stdlib.h>
+#include <errno.h>
 
 #include "dequeue.h"
 
@@ -40,10 +41,16 @@
    for (i=MAX; i < 2*MAX; i++)
       {
        ip = malloc(sizeof(int));
+       if (NULL == ip)
+	  {
+	  perror("malloc");
+	  exit(EXIT_FAILURE);
+	  }
       *ip = i;
+      errno = 0;
       if (NULL == dequeue_push_top(deq, (void *) ip))
          {
-         perror("dequeue_push");
+         perror("dequeue_push_top");
          free(ip);
          }
       }
diff -r 6605a342e8f8 -r abdba37f67a2 src/list.c
--- a/src/list.c	Thu Sep 27 10:57:41 2012 -0500
+++ b/src/list.c	Fri Sep 28 03:08:25 2012 -0500
@@ -2,6 +2,25 @@
 
 #include "list.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;
+   };
 
 ////////////////////////////////////////////////////////////////////////////////
 // Allocates new list and returns poitner to it.
@@ -159,38 +178,38 @@
 
 ////////////////////////////////////////////////////////////////////////////////
 // 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)
+struct list_iterator *
+list_begin(struct list * l)
    {
-   if ( (NULL == l) || (NULL == lit) )
+   if ( (NULL == l) || (NULL == l->head) )
       return NULL;
 
-   lit->l = l;
-   lit->curr = l->head;
+   struct list_iterator * it = malloc(sizeof(struct list_iterator));
+   if (NULL == it)
+      return NULL;
 
-   if (lit->curr)
-      return lit->curr->data;
+   it->l = l;
+   it->curr = l->head;
 
-   return NULL;
+   return it;
    }
 
 ////////////////////////////////////////////////////////////////////////////////
 // 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)
+struct list_iterator *
+list_end(struct list * l)
    {
-   if ( (NULL == l) || (NULL == lit) )
+   if ( (NULL == l) || (NULL == l->head) )
       return NULL;
 
-   lit->l = l;
-   lit->curr = l->tail;
+   struct list_iterator * it = malloc(sizeof(struct list_iterator));
+   if (NULL == it)
+      return NULL;
 
-   if (lit->curr)
-      return lit->curr->data;
+   it->l = l;
+   it->curr = l->tail;
 
-   return NULL;
+   return it;
    }
 
 ////////////////////////////////////////////////////////////////////////////////
diff -r 6605a342e8f8 -r abdba37f67a2 src/list.h
--- a/src/list.h	Thu Sep 27 10:57:41 2012 -0500
+++ b/src/list.h	Fri Sep 28 03:08:25 2012 -0500
@@ -3,41 +3,22 @@
 
 #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_node;
+struct list;
+struct list_iterator;
 
 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.
+// 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.
-void * list_begin(struct list * l, struct list_iterator * lit);
-void * list_end(struct list * l, struct list_iterator * lit);
+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);
diff -r 6605a342e8f8 -r abdba37f67a2 src/list_test.c
--- a/src/list_test.c	Thu Sep 27 10:57:41 2012 -0500
+++ b/src/list_test.c	Fri Sep 28 03:08:25 2012 -0500
@@ -118,11 +118,11 @@
 
    printf("size %zd\n", list_size(l));
 
-   struct list_iterator lit;
+   struct list_iterator * lit;
    int * ip;
 
    printf("Walking front to back\n");
-   for (ip = list_begin(l, &lit); NULL != ip; ip = list_next( &lit))
+   for (lit = list_begin(l); NULL != ip; ip = list_next( &lit))
       printf("%d\n", *ip);
 
    printf("Inserting 15 after 5\n");
diff -r 6605a342e8f8 -r abdba37f67a2 src/pqueue.c
--- a/src/pqueue.c	Thu Sep 27 10:57:41 2012 -0500
+++ b/src/pqueue.c	Fri Sep 28 03:08:25 2012 -0500
@@ -2,6 +2,14 @@
 
 #include "pqueue.h"
 
+struct pqueue
+   {
+   void ** data;
+   size_t max;
+   size_t size;
+   bool (*comp)(void const * const a, void const * const b);
+   };
+
 ////////////////////////////////////////////////////////////////////////////////
 // comp should return true if *a comp *b.
 // So, for a min priority queue, comp will be defined to return true if *a < *b,
diff -r 6605a342e8f8 -r abdba37f67a2 src/pqueue.h
--- a/src/pqueue.h	Thu Sep 27 10:57:41 2012 -0500
+++ b/src/pqueue.h	Fri Sep 28 03:08:25 2012 -0500
@@ -4,22 +4,13 @@
 #include <stddef.h>
 #include <stdbool.h>
 
-struct pqueue
-   {
-   void ** data;
-   size_t max;
-   size_t size;
-   bool (*comp)(void const * const a, void const * const b);
-   };
+struct pqueue;
 
-struct pqueue * pqueue_new(size_t max, 
-			   bool (*comp)(void const * const a, void const * const b));
+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);
 
 #endif // ndef PQUEUE_
diff -r 6605a342e8f8 -r abdba37f67a2 src/queue.c
--- a/src/queue.c	Thu Sep 27 10:57:41 2012 -0500
+++ b/src/queue.c	Fri Sep 28 03:08:25 2012 -0500
@@ -3,6 +3,14 @@
 
 #include "queue.h"
 
+struct queue
+   {
+   void ** data;
+   size_t max;
+   size_t start;
+   size_t count;
+   };
+
 ////////////////////////////////////////////////////////////////////////////////
 struct queue * queue_new(size_t const max)
    {
diff -r 6605a342e8f8 -r abdba37f67a2 src/queue.h
--- a/src/queue.h	Thu Sep 27 10:57:41 2012 -0500
+++ b/src/queue.h	Fri Sep 28 03:08:25 2012 -0500
@@ -3,13 +3,7 @@
 
 #include <stddef.h>
 
-struct queue
-   {
-   void ** data;
-   size_t max;
-   size_t start;
-   size_t count;
-   };
+struct queue;
 
 struct queue * queue_new(size_t const size);
 void queue_delete(struct queue * queue);
diff -r 6605a342e8f8 -r abdba37f67a2 src/rbtree.c
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/rbtree.c	Fri Sep 28 03:08:25 2012 -0500
@@ -0,0 +1,704 @@
+#include <stdio.h>
+#include <stdlib.h>
+
+#include "rbtree.h"
+
+enum rbtree_color { RED, BLACK };
+
+struct rbtree_node
+   {
+   enum rbtree_color color;
+   struct rbtree_node * parent;
+   struct rbtree_node * left;
+   struct rbtree_node * right;
+   void * data;
+   };
+
+struct rbtree
+   {
+   struct rbtree_node nil_node;
+   struct rbtree_node * nil;
+   struct rbtree_node * root;
+   size_t size;
+   bool (*le)(void * a, void * b);
+   bool (*eq)(void * a, void * b);
+   };
+
+struct rbtree_iterator
+   {
+   struct rbtree * rbtree;
+   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);
+
+////////////////////////////////////////////////////////////////////////////////
+struct rbtree *
+rbtree_new(bool (*le)(void * a, void * b),
+	bool (*eq)(void * a, void * b))
+   {
+   if ( (NULL == le) || (NULL == eq) )
+      return NULL;
+
+   struct rbtree * rbtree = malloc(sizeof(struct rbtree));
+   if (NULL == rbtree)
+      return NULL;
+
+   rbtree->nil_node = (struct rbtree_node) { BLACK, &rbtree->nil_node, &rbtree->nil_node, &rbtree->nil_node, NULL };
+   rbtree->nil = &(rbtree->nil_node);
+   rbtree->root = rbtree->nil;
+   rbtree->size = 0;
+   rbtree->le = le;
+   rbtree->eq = eq;
+   return rbtree;
+   }
+
+
+////////////////////////////////////////////////////////////////////////////////
+void
+rbtree_delete(struct rbtree * rbtree)
+   {
+   if (NULL == rbtree) return;
+   if (0 < rbtree->size)
+      {
+      // Walk the tree and delete the nodes.
+      // This may cause memory leaks, so hopefully the user has already
+      // emptied the tree.
+      rbtree_node_walk_postorder(rbtree, rbtree->root, rbtree_node_free);
+      }
+   free(rbtree);
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+void
+rbtree_node_free(struct rbtree_node * node)
+   {
+   free(node);
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+void *
+rbtree_insert(struct rbtree * rbtree, void * data)
+   {
+   if ( (NULL == rbtree) || (NULL == data) )
+      return NULL;
+
+   struct rbtree_node * new = malloc(sizeof(struct rbtree_node));
+   if (NULL == new)
+      return NULL;
+   new->left = new->right = new->parent = rbtree->nil;
+   new->color = RED;
+   new->data = data;
+
+   if (rbtree->nil == rbtree->root)
+      {
+      rbtree->root = new;
+      new->color = BLACK;
+      new->parent = rbtree->nil;
+      rbtree->size = 1;
+      return new->data;
+      }
+
+   struct rbtree_node * p = rbtree->nil;
+   struct rbtree_node * c = rbtree->root;
+
+   while (rbtree->nil != c)
+      {
+      p = c;
+      if (rbtree->le(new->data, c->data))
+	 c = c->left;
+      else
+	 c = c->right;
+      }
+   new->parent = p;
+   if (rbtree->le(new->data, p->data))
+      p->left = new;
+   else
+      p->right = new;
+
+   rbtree_insert_fixup(rbtree, new);
+
+   rbtree->size++;
+   return new->data;
+   }
+
+
+////////////////////////////////////////////////////////////////////////////////
+void
+rbtree_insert_fixup(struct rbtree * rbtree, struct rbtree_node * node)
+   {
+   if ( (NULL == rbtree) || (NULL == node) )
+      return;
+
+   while (RED == node->parent->color)
+      {
+      if (node->parent == node->parent->parent->left)
+	 {
+	 struct rbtree_node * y = node->parent->parent->right;
+	 if (RED == y->color)
+	    {
+	    node->parent->color = BLACK;
+	    y->color = BLACK;
+	    node->parent->parent->color = RED;
+	    node = node->parent->parent;
+	    }
+	 else 
+	    {
+	    if (node == node->parent->right)
+	       {
+	       node = node->parent;
+	       rbtree_rotate_left(rbtree, node);
+	       }
+	    node->parent->color = BLACK;
+	    node->parent->parent->color = RED;
+	    rbtree_rotate_right(rbtree, node->parent->parent);
+	    }
+	 }
+      else
+	 {
+	 struct rbtree_node * y = node->parent->parent->left;
+	 if (RED == y->color)
+	    {
+	    node->parent->color = BLACK;
+	    y->color = BLACK;
+	    node->parent->parent->color = RED;
+	    node = node->parent->parent;
+	    }
+	 else 
+	    {
+	    if (node == node->parent->left)
+	       {
+	       node = node->parent;
+	       rbtree_rotate_right(rbtree, node);
+	       }
+	    node->parent->color = BLACK;
+	    node->parent->parent->color = RED;
+	    rbtree_rotate_left(rbtree, node->parent->parent);
+	    }
+	 }
+      }
+   rbtree->root->color = BLACK;
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+void
+rbtree_walk_inorder(struct rbtree * rbtree, void (*op)(void * data))
+   {
+   if ( (NULL == rbtree) || (rbtree->nil == rbtree->root) || (NULL == op) )
+      return;
+
+   rbtree_data_walk_inorder(rbtree, rbtree->root, op);
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+void
+rbtree_walk_postorder(struct rbtree * rbtree, void (*op)(void * data))
+   {
+   if ( (NULL == rbtree) || (rbtree->nil == rbtree->root) || (NULL == op) )
+      return;
+
+   rbtree_data_walk_postorder(rbtree, rbtree->root, op);
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+void
+rbtree_walk_preorder(struct rbtree * rbtree, void (*op)(void * data))
+   {
+   if ( (NULL == rbtree) || (rbtree->nil == rbtree->root) || (NULL == op) )
+      return;
+
+   rbtree_data_walk_preorder(rbtree, rbtree->root, op);
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+void
+rbtree_data_walk_inorder(struct rbtree * rbtree, struct rbtree_node * node, void (*op)(void * data))
+   {
+   if (rbtree->nil != node)
+      {
+      rbtree_data_walk_inorder(rbtree, node->left, op);
+      op(node->data);
+      rbtree_data_walk_inorder(rbtree, node->right, op);
+      }
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+void
+rbtree_data_walk_postorder(struct rbtree * rbtree, struct rbtree_node * node, void (*op)(void * data))
+   {
+   if (rbtree->nil != node)
+      {
+      rbtree_data_walk_postorder(rbtree, node->left, op);
+      rbtree_data_walk_postorder(rbtree, node->right, op);
+      op(node->data);
+      }
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+void
+rbtree_data_walk_preorder(struct rbtree * rbtree, struct rbtree_node * node, void (*op)(void * data))
+   {
+   if (rbtree->nil != node)
+      {
+      op(node->data);
+      rbtree_data_walk_preorder(rbtree, node->left, op);
+      rbtree_data_walk_preorder(rbtree, node->right, op);
+      }
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+void
+rbtree_node_walk_postorder(struct rbtree * rbtree, struct rbtree_node * node, void (*op)(struct rbtree_node * n))
+   {
+   if (rbtree->nil != node)
+      {
+      rbtree_node_walk_postorder(rbtree, node->left, op);
+      rbtree_node_walk_postorder(rbtree, node->right, op);
+      op(node);
+      }
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+void *
+rbtree_search(struct rbtree * rbtree, void * data)
+   {
+   if ( (NULL == rbtree) || (rbtree->nil == rbtree->root) || (NULL == data) )
+      return NULL;
+
+   return rbtree_data_search(rbtree, rbtree->root, data);
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+// Recursive
+void *
+rbtree_data_search(struct rbtree * rbtree, struct rbtree_node * node, void * data)
+   {
+   if (rbtree->nil == node)
+      return NULL;
+
+   if (rbtree->eq(data, node->data))
+      return node->data;
+
+   if (rbtree->le(data, node->data))
+      return rbtree_data_search(rbtree, node->left, data);
+   else
+      return rbtree_data_search(rbtree, node->right, data);
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+// Iterative
+void *
+rbtree_search_iterative(struct rbtree * rbtree, void * data)
+   {
+   if ( (NULL == rbtree) || (rbtree->nil == rbtree->root) || (NULL == data) )
+      return NULL;
+
+   struct rbtree_node * node = rbtree->root;
+   while (1)
+      {
+      if (rbtree->nil == node)
+	 return NULL;
+      
+      if (rbtree->eq(data, node->data))
+	 return node->data;
+      
+      if (rbtree->le(data, node->data))
+	 node = node->left;
+      else
+	 node = node->right;
+      }
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+void *
+rbtree_minimum(struct rbtree * rbtree)
+   {
+   if (NULL == rbtree)
+      return NULL;
+
+   return rbtree_node_minimum(rbtree, rbtree->root);
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+void *
+rbtree_node_minimum(struct rbtree * rbtree, struct rbtree_node * node)
+   {
+   while ( (rbtree->nil != node) && (rbtree->nil != node->left) )
+      node = node->left;
+   if (rbtree->nil == node)
+      return NULL;
+   return node->data;
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+void *
+rbtree_maximum(struct rbtree * rbtree)
+   {
+   if (NULL == rbtree)
+      return NULL;
+
+   return rbtree_node_maximum(rbtree, rbtree->root);
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+void *
+rbtree_node_maximum(struct rbtree * rbtree, struct rbtree_node * node)
+   {
+   while ( (rbtree->nil != node) && (rbtree->nil != node->right) )
+      node = node->right;
+   if (rbtree->nil == node)
+      return NULL;
+   return node->data;
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+struct rbtree_iterator *
+rbtree_begin(struct rbtree * rbtree)
+   {
+   if ( (NULL == rbtree) || (rbtree->nil == rbtree->root) )
+      return NULL;
+
+   struct rbtree_node * min = rbtree->root;
+   while (min->left)
+      min = min->left;
+
+   struct rbtree_iterator * it = malloc(sizeof(struct rbtree_iterator));
+   if (NULL == it)
+      return NULL;
+
+   it->rbtree = rbtree;
+   it->curr = min;
+   return it;
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+struct rbtree_iterator *
+rbtree_end(struct rbtree * rbtree)
+   {
+   if ( (NULL == rbtree) || (rbtree->nil == rbtree->root) )
+      return NULL;
+
+   struct rbtree_node * max = rbtree->root;
+   while (max->right)
+      max = max->right;
+
+   struct rbtree_iterator * it = malloc(sizeof(struct rbtree_iterator));
+   if (NULL == it)
+      return NULL;
+
+   it->rbtree = rbtree;
+   it->curr = max;
+   return it;
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+struct rbtree_iterator *
+rbtree_next(struct rbtree_iterator * it)
+   {
+   if ( (NULL == it) || (NULL == it->rbtree) || (it->rbtree->nil == it->curr) )
+      return NULL;
+
+   if (it->rbtree->nil == it->curr->right)
+      {
+      struct rbtree_node * p = it->curr;
+      it->curr = it->curr->parent;
+      while ( (it->rbtree->nil != it->curr) && (p == it->curr->right) )
+	 {
+	 p = it->curr;
+	 it->curr = it->curr->parent;
+	 }
+
+      if (it->curr == it->rbtree->nil)
+	 return NULL;
+      }
+   else
+      {
+      struct rbtree_node * min = it->curr->right;
+      while (min->left)
+	 min = min->left;
+      it->curr = min;
+      }
+   return it;
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+struct rbtree_iterator *
+rbtree_prev(struct rbtree_iterator * it)
+   {
+   if ( (NULL == it) || (NULL == it->rbtree) || (it->rbtree->nil == it->curr) )
+      return NULL;
+
+   if (it->rbtree->nil == it->curr->left)
+      {
+      struct rbtree_node * p = it->curr;
+      it->curr = it->curr->parent;
+      while ( (it->rbtree->nil != it->curr) && (p == it->curr->left) )
+	 {
+	 p = it->curr;
+	 it->curr = it->curr->parent;
+	 }
+
+      if (it->curr == it->rbtree->nil)
+	 return NULL;
+      }
+   else
+      {
+      struct rbtree_node * max = it->curr->left;
+      while (max->right)
+	 max = max->right;
+      it->curr = max;
+      }
+   return it;
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+void *
+rbtree_value(struct rbtree_iterator * it)
+   {
+   if ( (NULL == it) || (NULL == it->rbtree) || (it->rbtree->nil == it->curr) )
+      return NULL;
+
+   return it->curr->data;
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+void *
+rbtree_find(struct rbtree_iterator * it, void * data)
+   {
+   if ( (NULL == it) || (NULL == it->rbtree) || (it->rbtree->nil == it->rbtree->root) || (NULL == data) )
+      return NULL;
+
+   return rbtree_node_search(it->rbtree, it->rbtree->root, data);
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+// Recursive
+struct rbtree_node *
+rbtree_node_search(struct rbtree * rbtree, struct rbtree_node * node, void * data)
+   {
+   if (rbtree->nil == node)
+      return NULL;
+
+   if (rbtree->eq(data, node->data))
+      return node;
+
+   if (rbtree->le(data, node->data))
+      return rbtree_node_search(rbtree, node->left, data);
+   else
+      return rbtree_node_search(rbtree, node->right, data);
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+struct rbtree_node *
+rbtree_transplant(struct rbtree * rbtree, struct rbtree_node * a, struct rbtree_node * b)
+   {
+   if ( (NULL == a) || (NULL == b) )
+      return NULL;
+
+   if (rbtree->nil == a->parent)
+      rbtree->root = b;
+   else if (a == a->parent->left)
+      a->parent->left = b;
+   else
+      a->parent->right = b;
+
+   b->parent = a->parent;
+
+   return a;
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+void *
+rbtree_remove(struct rbtree_iterator * it)
+   {
+   if ( (NULL == it) || (NULL == it->curr) )
+      return NULL;
+
+   // Get predecessor and save it
+   struct rbtree_iterator pred;
+   pred.curr = it->curr;
+   pred.rbtree = it->rbtree;
+   rbtree_prev(&pred);
+
+   struct rbtree_node * x;
+   struct rbtree_node * y = it->curr;
+   enum rbtree_color original_color = y->color;
+
+   if (it->rbtree->nil == it->curr->left)
+      {
+      x = it->curr->right;
+      rbtree_transplant(it->rbtree, it->curr, it->curr->right);
+      }
+   else if (it->rbtree->nil == it->curr->right)
+      {
+      x = it->curr->left;
+      rbtree_transplant(it->rbtree, it->curr, it->curr->left);
+      }
+   else
+      {
+      y = rbtree_node_minimum(it->rbtree, it->curr->right);
+      original_color = y->color;
+      x = y->right;
+      if (it->curr == y->parent)
+	 x->parent = y;
+      else
+	 {
+	 rbtree_transplant(it->rbtree, y, y->right);
+	 y->right = it->curr->right;
+	 y->right->parent = y;
+	 }
+      rbtree_transplant(it->rbtree, it->curr, y);
+      y->left = it->curr->left;
+      y->left->parent = y;
+      y->color = it->curr->color;
+      }
+
+   if (BLACK == original_color)
+      rbtree_remove_fixup(it->rbtree, x);
+
+   void * data = it->curr->data;
+   free(it->curr);
+
+   // Update it to point to pred's successor
+   rbtree_next(&pred);
+   it->curr = pred.curr;
+
+   return data;
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+void
+rbtree_remove_fixup(struct rbtree * rbtree, struct rbtree_node * node)
+   {
+   while ( (rbtree->root != node) && (BLACK == node->color) )
+      {
+      if (node == node->parent->left)
+	 {
+	 struct rbtree_node * w = node->parent->right;
+	 if (RED == w->color)
+	    {
+	    w->color = BLACK;
+	    node->parent->color = RED;
+	    rbtree_rotate_left(rbtree, node->parent);
+	    w = node->parent->right;
+	    }
+	 if ( (BLACK == w->left->color) && (BLACK == w->right->color) )
+	    {
+	    w->left->color = RED;
+	    node = node->parent;
+	    }
+	 else
+	    {
+	    if (BLACK == w->right->color)
+	       {
+	       w->left->color = BLACK;
+	       w->color = RED;
+	       rbtree_rotate_right(rbtree, w);
+	       w = node->parent->right;
+	       }
+	    w->color = node->parent->color;
+	    node->parent->color = BLACK;
+	    w->right->color = BLACK;
+	    rbtree_rotate_left(rbtree, node->parent);
+	    node = rbtree->root;
+	    }
+	 }
+      else
+	 {
+	 struct rbtree_node * w = node->parent->left;
+	 if (RED == w->color)
+	    {
+	    w->color = BLACK;
+	    node->parent->color = RED;
+	    rbtree_rotate_right(rbtree, node->parent);
+	    w = node->parent->left;
+	    }
+	 if ( (BLACK == w->right->color) && (BLACK == w->left->color) )
+	    {
+	    w->right->color = RED;
+	    node = node->parent;
+	    }
+	 else
+	    {
+	    if (BLACK == w->left->color)
+	       {
+	       w->right->color = BLACK;
+	       w->color = RED;
+	       rbtree_rotate_left(rbtree, w);
+	       w = node->parent->left;
+	       }
+	    w->color = node->parent->color;
+	    node->parent->color = BLACK;
+	    w->left->color = BLACK;
+	    rbtree_rotate_right(rbtree, node->parent);
+	    node = rbtree->root;
+	    }
+	 }
+      }
+   node->color = BLACK;
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+void
+rbtree_rotate_left(struct rbtree * rbtree, struct rbtree_node * node)
+   {
+   if ( (NULL == rbtree) || (rbtree->nil == node) || (rbtree->nil == node->right) )
+      return;
+
+   struct rbtree_node * y = node->right;
+
+   node->right = y->left;
+   if (rbtree->nil != y->left)
+      y->left->parent = node;
+
+   y->parent = node->parent;
+   if (rbtree->nil == node->parent)
+      rbtree->root = y;
+   else if (node == node->parent->left)
+      node->parent->left = y;
+   else
+      node->parent->right = y;
+
+   y->left = node;
+   node->parent = y;
+   }
+
+////////////////////////////////////////////////////////////////////////////////
+void
+rbtree_rotate_right(struct rbtree * rbtree, struct rbtree_node * node)
+   {
+   if ( (NULL == rbtree) || (rbtree->nil == node) || (rbtree->nil == node->left) )
+      return;
+
+   struct rbtree_node * y = node->left;
+
+   node->left = y->right;
+   if (rbtree->nil != y->right)
+      y->right->parent = node;
+
+   y->parent = node->parent;
+   if (rbtree->nil == node->parent)
+      rbtree->root = y;
+   else if (node == node->parent->right)
+      node->parent->right = y;
+   else
+      node->parent->left = y;
+
+   y->right = node;
+   node->parent = y;
+   }
+
diff -r 6605a342e8f8 -r abdba37f67a2 src/rbtree.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/rbtree.h	Fri Sep 28 03:08:25 2012 -0500
@@ -0,0 +1,31 @@
+#ifndef RBTREE_H_
+#define RBTREE_H_
+
+#include <stddef.h>
+#include <stdbool.h>
+
+struct rbtree;
+struct rbtree_node;
+struct rbtree_iterator;
+
+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));
+
+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);
+
+#endif
diff -r 6605a342e8f8 -r abdba37f67a2 src/ring_buffer.c
--- a/src/ring_buffer.c	Thu Sep 27 10:57:41 2012 -0500
+++ b/src/ring_buffer.c	Fri Sep 28 03:08:25 2012 -0500
@@ -3,6 +3,14 @@
 
 #include "ring_buffer.h"
 
+struct ring_buffer
+   {
+   void ** data;
+   size_t max;
+   size_t start;
+   size_t count;
+   };
+
 ////////////////////////////////////////////////////////////////////////////////
 struct ring_buffer * ring_buffer_new(size_t const max)
    {
diff -r 6605a342e8f8 -r abdba37f67a2 src/ring_buffer.h
--- a/src/ring_buffer.h	Thu Sep 27 10:57:41 2012 -0500
+++ b/src/ring_buffer.h	Fri Sep 28 03:08:25 2012 -0500
@@ -3,13 +3,7 @@
 
 #include <stddef.h>
 
-struct ring_buffer
-   {
-   void ** data;
-   size_t max;
-   size_t start;
-   size_t count;
-   };
+struct ring_buffer;
 
 struct ring_buffer * ring_buffer_new(size_t const size);
 void ring_buffer_delete(struct ring_buffer * rb);
diff -r 6605a342e8f8 -r abdba37f67a2 src/stack.c
--- a/src/stack.c	Thu Sep 27 10:57:41 2012 -0500
+++ b/src/stack.c	Fri Sep 28 03:08:25 2012 -0500
@@ -3,6 +3,13 @@
 
 #include "stack.h"
 
+struct stack
+   {
+   void ** data;
+   size_t size;
+   size_t max;
+   };
+
 ////////////////////////////////////////////////////////////////////////////////
 struct stack * stack_new(size_t const max)
    {
diff -r 6605a342e8f8 -r abdba37f67a2 src/stack.h
--- a/src/stack.h	Thu Sep 27 10:57:41 2012 -0500
+++ b/src/stack.h	Fri Sep 28 03:08:25 2012 -0500
@@ -3,12 +3,7 @@
 
 #include <stddef.h>
 
-struct stack
-   {
-   void ** data;
-   size_t size;
-   size_t max;
-   };
+struct stack;
 
 struct stack * stack_new(size_t const max);
 void stack_delete(struct stack * s);