Mercurial > data_structures

changeset 9:abdba37f67a2

find changesets by author, revision, files, or words in the commit message
Red-black tree in progress. Linked list needs iterators redone, also in progress. Sleepy.
author Eris Caffee <discordia@eldalin.com>
date Fri, 28 Sep 2012 03:08:25 -0500
parents 6605a342e8f8
children 68f85ffc6029
files src/bst.c src/bst.h src/dequeue.c src/dequeue.h src/dequeue_test.c src/list.c src/list.h src/list_test.c src/pqueue.c src/pqueue.h src/queue.c src/queue.h src/rbtree.c src/rbtree.h src/ring_buffer.c src/ring_buffer.h src/stack.c src/stack.h
diffstat 18 files changed, 860 insertions(+), 138 deletions(-) [+]
line diff
     1.1 --- a/src/bst.c	Thu Sep 27 10:57:41 2012 -0500
     1.2 +++ b/src/bst.c	Fri Sep 28 03:08:25 2012 -0500
     1.3 @@ -3,6 +3,28 @@
     1.4  
     1.5  #include "bst.h"
     1.6  
     1.7 +struct bst_node
     1.8 +   {
     1.9 +   struct bst_node * parent;
    1.10 +   struct bst_node * left;
    1.11 +   struct bst_node * right;
    1.12 +   void * data;
    1.13 +   };
    1.14 +
    1.15 +struct bst
    1.16 +   {
    1.17 +   struct bst_node * root;
    1.18 +   size_t size;
    1.19 +   bool (*le)(void * a, void * b);
    1.20 +   bool (*eq)(void * a, void * b);
    1.21 +   };
    1.22 +
    1.23 +struct bst_iterator
    1.24 +   {
    1.25 +   struct bst * bst;
    1.26 +   struct bst_node * curr;
    1.27 +   };
    1.28 +
    1.29  // Private functions.
    1.30  void bst_data_walk_inorder(struct bst_node * node, void (*op)(void * data));
    1.31  void bst_data_walk_preorder(struct bst_node * node, void (*op)(void * data));
    1.32 @@ -77,6 +99,7 @@
    1.33     if (NULL == bst->root)
    1.34        {
    1.35        bst->root = new;
    1.36 +      bst->size = 1;
    1.37        return new->data;
    1.38        }
    1.39  

     2.1 --- a/src/bst.h	Thu Sep 27 10:57:41 2012 -0500
     2.2 +++ b/src/bst.h	Fri Sep 28 03:08:25 2012 -0500
     2.3 @@ -4,50 +4,25 @@
     2.4  #include <stddef.h>
     2.5  #include <stdbool.h>
     2.6  
     2.7 -struct bst_node
     2.8 -   {
     2.9 -   struct bst_node * parent;
    2.10 -   struct bst_node * left;
    2.11 -   struct bst_node * right;
    2.12 -   void * data;
    2.13 -   };
    2.14 -
    2.15 -struct bst
    2.16 -   {
    2.17 -   struct bst_node * root;
    2.18 -   size_t size;
    2.19 -   bool (*le)(void * a, void * b);
    2.20 -   bool (*eq)(void * a, void * b);
    2.21 -   };
    2.22 -
    2.23 -struct bst_iterator
    2.24 -   {
    2.25 -   struct bst * bst;
    2.26 -   struct bst_node * curr;
    2.27 -   };
    2.28 +struct bst_node;
    2.29 +struct bst;
    2.30 +struct bst_iterator;
    2.31  
    2.32  struct bst * bst_new(bool (*le)(void * a, void * b), bool (*eq)(void * a, void * b));
    2.33  void bst_delete(struct bst * bst);
    2.34 -
    2.35  void * bst_insert(struct bst * bst, void * data);
    2.36 -
    2.37  void * bst_search(struct bst * bst, void * data);
    2.38  void * bst_search_iterative(struct bst * bst, void * data);
    2.39 -
    2.40  void * bst_minimum(struct bst * bst);
    2.41  void * bst_maximum(struct bst * bst);
    2.42 -
    2.43  void bst_walk_inorder(struct bst * bst, void (*op)(void * data));
    2.44  void bst_walk_preorder(struct bst * bst, void (*op)(void * data));
    2.45  void bst_walk_postorder(struct bst * bst, void (*op)(void * data));
    2.46 -
    2.47 -
    2.48  struct bst_iterator * bst_begin(struct bst * bst);
    2.49  struct bst_iterator * bst_end(struct bst * bst);
    2.50  struct bst_iterator * bst_next(struct bst_iterator * it);
    2.51  struct bst_iterator * bst_prev(struct bst_iterator * it);
    2.52  void * bst_value(struct bst_iterator * it);
    2.53 -
    2.54  void * bst_find(struct bst_iterator * it, void * data);
    2.55  void * bst_remove(struct bst_iterator * it);
    2.56  

     3.1 --- a/src/dequeue.c	Thu Sep 27 10:57:41 2012 -0500
     3.2 +++ b/src/dequeue.c	Fri Sep 28 03:08:25 2012 -0500
     3.3 @@ -1,16 +1,21 @@
     3.4  #include <stdlib.h>
     3.5 -#include <errno.h>
     3.6  
     3.7  #include "dequeue.h"
     3.8  
     3.9 +struct dequeue
    3.10 +   {
    3.11 +   void ** data;
    3.12 +   size_t max;
    3.13 +   size_t bottom;
    3.14 +   size_t top;
    3.15 +   size_t count;
    3.16 +   };
    3.17 +
    3.18  ////////////////////////////////////////////////////////////////////////////////
    3.19  struct dequeue * dequeue_new(size_t const max)
    3.20     {
    3.21     if (max < 1)
    3.22 -      {
    3.23 -      errno = EINVAL;
    3.24        return NULL;
    3.25 -      }
    3.26  
    3.27     struct dequeue * deq = malloc(sizeof(struct dequeue));
    3.28     if (NULL == deq)
    3.29 @@ -37,16 +42,10 @@
    3.30  void * dequeue_push_top(struct dequeue * deq, void * elem)
    3.31     {
    3.32     if ((NULL == deq) || (NULL == elem))
    3.33 -      {
    3.34 -      errno = EINVAL;
    3.35        return NULL;
    3.36 -      }
    3.37  
    3.38     if (deq->count == deq->max)
    3.39 -      {
    3.40 -      errno = ENOMEM;
    3.41        return NULL;
    3.42 -      }
    3.43  
    3.44     if (deq->max - 1 == deq->top)
    3.45        deq->top = 0;
    3.46 @@ -63,16 +62,10 @@
    3.47  void * dequeue_push_bottom(struct dequeue * deq, void * elem)
    3.48     {
    3.49     if ((NULL == deq) || (NULL == elem))
    3.50 -      {
    3.51 -      errno = EINVAL;
    3.52        return NULL;
    3.53 -      }
    3.54  
    3.55     if (deq->count == deq->max)
    3.56 -      {
    3.57 -      errno = ENOMEM;
    3.58        return NULL;
    3.59 -      }
    3.60  
    3.61     if (0 == deq->bottom)
    3.62        deq->bottom = deq->max - 1;
    3.63 @@ -89,10 +82,7 @@
    3.64  void * dequeue_pop_top(struct dequeue * deq)
    3.65     {
    3.66     if (NULL == deq)
    3.67 -      {
    3.68 -      errno = EINVAL;
    3.69        return NULL;
    3.70 -      }
    3.71  
    3.72     if (deq->count == 0)
    3.73        return NULL;
    3.74 @@ -113,10 +103,7 @@
    3.75  void * dequeue_pop_bottom(struct dequeue * deq)
    3.76     {
    3.77     if (NULL == deq)
    3.78 -      {
    3.79 -      errno = EINVAL;
    3.80        return NULL;
    3.81 -      }
    3.82  
    3.83     if (deq->count == 0)
    3.84        return NULL;
    3.85 @@ -138,10 +125,7 @@
    3.86  size_t dequeue_size(struct dequeue * deq)
    3.87     {
    3.88     if (NULL == deq)
    3.89 -      {
    3.90 -      errno = EINVAL;
    3.91        return 0;
    3.92 -      }
    3.93     return deq->count;
    3.94     }
    3.95  

     4.1 --- a/src/dequeue.h	Thu Sep 27 10:57:41 2012 -0500
     4.2 +++ b/src/dequeue.h	Fri Sep 28 03:08:25 2012 -0500
     4.3 @@ -3,14 +3,7 @@
     4.4  
     4.5  #include <stddef.h>
     4.6  
     4.7 -struct dequeue
     4.8 -   {
     4.9 -   void ** data;
    4.10 -   size_t max;
    4.11 -   size_t bottom;
    4.12 -   size_t top;
    4.13 -   size_t count;
    4.14 -   };
    4.15 +struct dequeue;
    4.16  
    4.17  struct dequeue * dequeue_new(size_t const size);
    4.18  void dequeue_delete(struct dequeue * deq);

     5.1 --- a/src/dequeue_test.c	Thu Sep 27 10:57:41 2012 -0500
     5.2 +++ b/src/dequeue_test.c	Fri Sep 28 03:08:25 2012 -0500
     5.3 @@ -1,5 +1,6 @@
     5.4  #include <stdio.h>
     5.5  #include <stdlib.h>
     5.6 +#include <errno.h>
     5.7  
     5.8  #include "dequeue.h"
     5.9  
    5.10 @@ -40,10 +41,16 @@
    5.11     for (i=MAX; i < 2*MAX; i++)
    5.12        {
    5.13         ip = malloc(sizeof(int));
    5.14 +       if (NULL == ip)
    5.15 +	  {
    5.16 +	  perror("malloc");
    5.17 +	  exit(EXIT_FAILURE);
    5.18 +	  }
    5.19        *ip = i;
    5.20 +      errno = 0;
    5.21        if (NULL == dequeue_push_top(deq, (void *) ip))
    5.22           {
    5.23 -         perror("dequeue_push");
    5.24 +         perror("dequeue_push_top");
    5.25           free(ip);
    5.26           }
    5.27        }

     6.1 --- a/src/list.c	Thu Sep 27 10:57:41 2012 -0500
     6.2 +++ b/src/list.c	Fri Sep 28 03:08:25 2012 -0500
     6.3 @@ -2,6 +2,25 @@
     6.4  
     6.5  #include "list.h"
     6.6  
     6.7 +struct list_node
     6.8 +   {
     6.9 +   struct list_node * next;
    6.10 +   struct list_node * prev;
    6.11 +   void * data;
    6.12 +   };
    6.13 +
    6.14 +struct list
    6.15 +   {
    6.16 +   struct list_node * head;
    6.17 +   struct list_node * tail;
    6.18 +   size_t size;
    6.19 +   };
    6.20 +
    6.21 +struct list_iterator
    6.22 +   {
    6.23 +   struct list * l;
    6.24 +   struct list_node * curr;
    6.25 +   };
    6.26  
    6.27  ////////////////////////////////////////////////////////////////////////////////
    6.28  // Allocates new list and returns poitner to it.
    6.29 @@ -159,38 +178,38 @@
    6.30  
    6.31  ////////////////////////////////////////////////////////////////////////////////
    6.32  // Intialize an iterator to point to the first element of the list
    6.33 -// Returns the elements value.
    6.34 -void *
    6.35 -list_begin(struct list * l, struct list_iterator * lit)
    6.36 +struct list_iterator *
    6.37 +list_begin(struct list * l)
    6.38     {
    6.39 -   if ( (NULL == l) || (NULL == lit) )
    6.40 +   if ( (NULL == l) || (NULL == l->head) )
    6.41        return NULL;
    6.42  
    6.43 -   lit->l = l;
    6.44 -   lit->curr = l->head;
    6.45 +   struct list_iterator * it = malloc(sizeof(struct list_iterator));
    6.46 +   if (NULL == it)
    6.47 +      return NULL;
    6.48  
    6.49 -   if (lit->curr)
    6.50 -      return lit->curr->data;
    6.51 +   it->l = l;
    6.52 +   it->curr = l->head;
    6.53  
    6.54 -   return NULL;
    6.55 +   return it;
    6.56     }
    6.57  
    6.58  ////////////////////////////////////////////////////////////////////////////////
    6.59  // Intialize an iterator to point to the last element of the list
    6.60 -// Returns the elements value.
    6.61 -void *
    6.62 -list_end(struct list * l, struct list_iterator * lit)
    6.63 +struct list_iterator *
    6.64 +list_end(struct list * l)
    6.65     {
    6.66 -   if ( (NULL == l) || (NULL == lit) )
    6.67 +   if ( (NULL == l) || (NULL == l->head) )
    6.68        return NULL;
    6.69  
    6.70 -   lit->l = l;
    6.71 -   lit->curr = l->tail;
    6.72 +   struct list_iterator * it = malloc(sizeof(struct list_iterator));
    6.73 +   if (NULL == it)
    6.74 +      return NULL;
    6.75  
    6.76 -   if (lit->curr)
    6.77 -      return lit->curr->data;
    6.78 +   it->l = l;
    6.79 +   it->curr = l->tail;
    6.80  
    6.81 -   return NULL;
    6.82 +   return it;
    6.83     }
    6.84  
    6.85  ////////////////////////////////////////////////////////////////////////////////

     7.1 --- a/src/list.h	Thu Sep 27 10:57:41 2012 -0500
     7.2 +++ b/src/list.h	Fri Sep 28 03:08:25 2012 -0500
     7.3 @@ -3,41 +3,22 @@
     7.4  
     7.5  #include <stddef.h>
     7.6  
     7.7 -struct list_node
     7.8 -   {
     7.9 -   struct list_node * next;
    7.10 -   struct list_node * prev;
    7.11 -   void * data;
    7.12 -   };
    7.13 -
    7.14 -struct list
    7.15 -   {
    7.16 -   struct list_node * head;
    7.17 -   struct list_node * tail;
    7.18 -   size_t size;
    7.19 -   };
    7.20 -
    7.21 -struct list_iterator
    7.22 -   {
    7.23 -   struct list * l;
    7.24 -   struct list_node * curr;
    7.25 -   };
    7.26 +struct list_node;
    7.27 +struct list;
    7.28 +struct list_iterator;
    7.29  
    7.30  struct list * list_new(void);
    7.31  void list_delete(struct list * l);
    7.32 -
    7.33  size_t list_size(struct list * l);
    7.34 -
    7.35  void * list_push_back(struct list * l, void * elem);
    7.36  void * list_pop_back(struct list * l);
    7.37  void * list_push_front(struct list * l, void * elem);
    7.38  void * list_pop_front(struct list * l);
    7.39  
    7.40 -
    7.41 -// The iterators are different that their c++ STL counterparts.
    7.42 +// The iterators are different than their c++ STL counterparts.
    7.43  // They are bi-directional, and list_end points to the last element, not the empty space beyond the last elem.
    7.44 -void * list_begin(struct list * l, struct list_iterator * lit);
    7.45 -void * list_end(struct list * l, struct list_iterator * lit);
    7.46 +struct list_iterator * list_begin(struct list * l);
    7.47 +struct list_iterator * list_end(struct list * l);
    7.48  void * list_next(struct list_iterator * lit);
    7.49  void * list_prev(struct list_iterator * lit);
    7.50  void * list_erase(struct list_iterator * lit);

     8.1 --- a/src/list_test.c	Thu Sep 27 10:57:41 2012 -0500
     8.2 +++ b/src/list_test.c	Fri Sep 28 03:08:25 2012 -0500
     8.3 @@ -118,11 +118,11 @@
     8.4  
     8.5     printf("size %zd\n", list_size(l));
     8.6  
     8.7 -   struct list_iterator lit;
     8.8 +   struct list_iterator * lit;
     8.9     int * ip;
    8.10  
    8.11     printf("Walking front to back\n");
    8.12 -   for (ip = list_begin(l, &lit); NULL != ip; ip = list_next( &lit))
    8.13 +   for (lit = list_begin(l); NULL != ip; ip = list_next( &lit))
    8.14        printf("%d\n", *ip);
    8.15  
    8.16     printf("Inserting 15 after 5\n");

     9.1 --- a/src/pqueue.c	Thu Sep 27 10:57:41 2012 -0500
     9.2 +++ b/src/pqueue.c	Fri Sep 28 03:08:25 2012 -0500
     9.3 @@ -2,6 +2,14 @@
     9.4  
     9.5  #include "pqueue.h"
     9.6  
     9.7 +struct pqueue
     9.8 +   {
     9.9 +   void ** data;
    9.10 +   size_t max;
    9.11 +   size_t size;
    9.12 +   bool (*comp)(void const * const a, void const * const b);
    9.13 +   };
    9.14 +
    9.15  ////////////////////////////////////////////////////////////////////////////////
    9.16  // comp should return true if *a comp *b.
    9.17  // So, for a min priority queue, comp will be defined to return true if *a < *b,

    10.1 --- a/src/pqueue.h	Thu Sep 27 10:57:41 2012 -0500
    10.2 +++ b/src/pqueue.h	Fri Sep 28 03:08:25 2012 -0500
    10.3 @@ -4,22 +4,13 @@
    10.4  #include <stddef.h>
    10.5  #include <stdbool.h>
    10.6  
    10.7 -struct pqueue
    10.8 -   {
    10.9 -   void ** data;
   10.10 -   size_t max;
   10.11 -   size_t size;
   10.12 -   bool (*comp)(void const * const a, void const * const b);
   10.13 -   };
   10.14 +struct pqueue;
   10.15  
   10.16 -struct pqueue * pqueue_new(size_t max, 
   10.17 -			   bool (*comp)(void const * const a, void const * const b));
   10.18 +struct pqueue * pqueue_new(size_t max, bool (*comp)(void const * const a, void const * const b));
   10.19  void pqueue_delete(struct pqueue * pq);
   10.20 -
   10.21  void * pqueue_push(struct pqueue * pq, void * elem);
   10.22  void * pqueue_pop(struct pqueue * pq);
   10.23  void * pqueue_peek(struct pqueue * pq);
   10.24 -
   10.25  size_t  pqueue_size(struct pqueue * pq);
   10.26  
   10.27  #endif // ndef PQUEUE_

    11.1 --- a/src/queue.c	Thu Sep 27 10:57:41 2012 -0500
    11.2 +++ b/src/queue.c	Fri Sep 28 03:08:25 2012 -0500
    11.3 @@ -3,6 +3,14 @@
    11.4  
    11.5  #include "queue.h"
    11.6  
    11.7 +struct queue
    11.8 +   {
    11.9 +   void ** data;
   11.10 +   size_t max;
   11.11 +   size_t start;
   11.12 +   size_t count;
   11.13 +   };
   11.14 +
   11.15  ////////////////////////////////////////////////////////////////////////////////
   11.16  struct queue * queue_new(size_t const max)
   11.17     {

    12.1 --- a/src/queue.h	Thu Sep 27 10:57:41 2012 -0500
    12.2 +++ b/src/queue.h	Fri Sep 28 03:08:25 2012 -0500
    12.3 @@ -3,13 +3,7 @@
    12.4  
    12.5  #include <stddef.h>
    12.6  
    12.7 -struct queue
    12.8 -   {
    12.9 -   void ** data;
   12.10 -   size_t max;
   12.11 -   size_t start;
   12.12 -   size_t count;
   12.13 -   };
   12.14 +struct queue;
   12.15  
   12.16  struct queue * queue_new(size_t const size);
   12.17  void queue_delete(struct queue * queue);

    13.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
    13.2 +++ b/src/rbtree.c	Fri Sep 28 03:08:25 2012 -0500
    13.3 @@ -0,0 +1,704 @@
    13.4 +#include <stdio.h>
    13.5 +#include <stdlib.h>
    13.6 +
    13.7 +#include "rbtree.h"
    13.8 +
    13.9 +enum rbtree_color { RED, BLACK };
   13.10 +
   13.11 +struct rbtree_node
   13.12 +   {
   13.13 +   enum rbtree_color color;
   13.14 +   struct rbtree_node * parent;
   13.15 +   struct rbtree_node * left;
   13.16 +   struct rbtree_node * right;
   13.17 +   void * data;
   13.18 +   };
   13.19 +
   13.20 +struct rbtree
   13.21 +   {
   13.22 +   struct rbtree_node nil_node;
   13.23 +   struct rbtree_node * nil;
   13.24 +   struct rbtree_node * root;
   13.25 +   size_t size;
   13.26 +   bool (*le)(void * a, void * b);
   13.27 +   bool (*eq)(void * a, void * b);
   13.28 +   };
   13.29 +
   13.30 +struct rbtree_iterator
   13.31 +   {
   13.32 +   struct rbtree * rbtree;
   13.33 +   struct rbtree_node * curr;
   13.34 +   };
   13.35 +
   13.36 +// Private functions.
   13.37 +void rbtree_data_walk_inorder(struct rbtree * rbtree, struct rbtree_node * node, void (*op)(void * data));
   13.38 +void rbtree_data_walk_preorder(struct rbtree * rbtree, struct rbtree_node * node, void (*op)(void * data));
   13.39 +void rbtree_data_walk_postorder(struct rbtree * rbtree, struct rbtree_node * node, void (*op)(void * data));
   13.40 +void rbtree_node_walk_postorder(struct rbtree * rbtree, struct rbtree_node * node, void (*op)(struct rbtree_node * n));
   13.41 +void * rbtree_data_search(struct rbtree * rbtree, struct rbtree_node * node, void * data);
   13.42 +void * rbtree_node_minimum(struct rbtree * rbtree, struct rbtree_node * node);
   13.43 +void * rbtree_node_maximum(struct rbtree * rbtree, struct rbtree_node * node);
   13.44 +void rbtree_node_free(struct rbtree_node * node);
   13.45 +struct rbtree_node * rbtree_node_search(struct rbtree * rbtree, struct rbtree_node * node, void * data);
   13.46 +struct rbtree_node * rbtree_transplant(struct rbtree * rbtree, struct rbtree_node * a, struct rbtree_node * b);
   13.47 +void rbtree_rotate_left(struct rbtree * rbtree, struct rbtree_node * node);
   13.48 +void rbtree_rotate_right(struct rbtree * rbtree, struct rbtree_node * node);
   13.49 +void rbtree_insert_fixup(struct rbtree * rbtree, struct rbtree_node * node);
   13.50 +void rbtree_remove_fixup(struct rbtree * rbtree, struct rbtree_node * node);
   13.51 +
   13.52 +////////////////////////////////////////////////////////////////////////////////
   13.53 +struct rbtree *
   13.54 +rbtree_new(bool (*le)(void * a, void * b),
   13.55 +	bool (*eq)(void * a, void * b))
   13.56 +   {
   13.57 +   if ( (NULL == le) || (NULL == eq) )
   13.58 +      return NULL;
   13.59 +
   13.60 +   struct rbtree * rbtree = malloc(sizeof(struct rbtree));
   13.61 +   if (NULL == rbtree)
   13.62 +      return NULL;
   13.63 +
   13.64 +   rbtree->nil_node = (struct rbtree_node) { BLACK, &rbtree->nil_node, &rbtree->nil_node, &rbtree->nil_node, NULL };
   13.65 +   rbtree->nil = &(rbtree->nil_node);
   13.66 +   rbtree->root = rbtree->nil;
   13.67 +   rbtree->size = 0;
   13.68 +   rbtree->le = le;
   13.69 +   rbtree->eq = eq;
   13.70 +   return rbtree;
   13.71 +   }
   13.72 +
   13.73 +
   13.74 +////////////////////////////////////////////////////////////////////////////////
   13.75 +void
   13.76 +rbtree_delete(struct rbtree * rbtree)
   13.77 +   {
   13.78 +   if (NULL == rbtree) return;
   13.79 +   if (0 < rbtree->size)
   13.80 +      {
   13.81 +      // Walk the tree and delete the nodes.
   13.82 +      // This may cause memory leaks, so hopefully the user has already
   13.83 +      // emptied the tree.
   13.84 +      rbtree_node_walk_postorder(rbtree, rbtree->root, rbtree_node_free);
   13.85 +      }
   13.86 +   free(rbtree);
   13.87 +   }
   13.88 +
   13.89 +////////////////////////////////////////////////////////////////////////////////
   13.90 +void
   13.91 +rbtree_node_free(struct rbtree_node * node)
   13.92 +   {
   13.93 +   free(node);
   13.94 +   }
   13.95 +
   13.96 +////////////////////////////////////////////////////////////////////////////////
   13.97 +void *
   13.98 +rbtree_insert(struct rbtree * rbtree, void * data)
   13.99 +   {
  13.100 +   if ( (NULL == rbtree) || (NULL == data) )
  13.101 +      return NULL;
  13.102 +
  13.103 +   struct rbtree_node * new = malloc(sizeof(struct rbtree_node));
  13.104 +   if (NULL == new)
  13.105 +      return NULL;
  13.106 +   new->left = new->right = new->parent = rbtree->nil;
  13.107 +   new->color = RED;
  13.108 +   new->data = data;
  13.109 +
  13.110 +   if (rbtree->nil == rbtree->root)
  13.111 +      {
  13.112 +      rbtree->root = new;
  13.113 +      new->color = BLACK;
  13.114 +      new->parent = rbtree->nil;
  13.115 +      rbtree->size = 1;
  13.116 +      return new->data;
  13.117 +      }
  13.118 +
  13.119 +   struct rbtree_node * p = rbtree->nil;
  13.120 +   struct rbtree_node * c = rbtree->root;
  13.121 +
  13.122 +   while (rbtree->nil != c)
  13.123 +      {
  13.124 +      p = c;
  13.125 +      if (rbtree->le(new->data, c->data))
  13.126 +	 c = c->left;
  13.127 +      else
  13.128 +	 c = c->right;
  13.129 +      }
  13.130 +   new->parent = p;
  13.131 +   if (rbtree->le(new->data, p->data))
  13.132 +      p->left = new;
  13.133 +   else
  13.134 +      p->right = new;
  13.135 +
  13.136 +   rbtree_insert_fixup(rbtree, new);
  13.137 +
  13.138 +   rbtree->size++;
  13.139 +   return new->data;
  13.140 +   }
  13.141 +
  13.142 +
  13.143 +////////////////////////////////////////////////////////////////////////////////
  13.144 +void
  13.145 +rbtree_insert_fixup(struct rbtree * rbtree, struct rbtree_node * node)
  13.146 +   {
  13.147 +   if ( (NULL == rbtree) || (NULL == node) )
  13.148 +      return;
  13.149 +
  13.150 +   while (RED == node->parent->color)
  13.151 +      {
  13.152 +      if (node->parent == node->parent->parent->left)
  13.153 +	 {
  13.154 +	 struct rbtree_node * y = node->parent->parent->right;
  13.155 +	 if (RED == y->color)
  13.156 +	    {
  13.157 +	    node->parent->color = BLACK;
  13.158 +	    y->color = BLACK;
  13.159 +	    node->parent->parent->color = RED;
  13.160 +	    node = node->parent->parent;
  13.161 +	    }
  13.162 +	 else 
  13.163 +	    {
  13.164 +	    if (node == node->parent->right)
  13.165 +	       {
  13.166 +	       node = node->parent;
  13.167 +	       rbtree_rotate_left(rbtree, node);
  13.168 +	       }
  13.169 +	    node->parent->color = BLACK;
  13.170 +	    node->parent->parent->color = RED;
  13.171 +	    rbtree_rotate_right(rbtree, node->parent->parent);
  13.172 +	    }
  13.173 +	 }
  13.174 +      else
  13.175 +	 {
  13.176 +	 struct rbtree_node * y = node->parent->parent->left;
  13.177 +	 if (RED == y->color)
  13.178 +	    {
  13.179 +	    node->parent->color = BLACK;
  13.180 +	    y->color = BLACK;
  13.181 +	    node->parent->parent->color = RED;
  13.182 +	    node = node->parent->parent;
  13.183 +	    }
  13.184 +	 else 
  13.185 +	    {
  13.186 +	    if (node == node->parent->left)
  13.187 +	       {
  13.188 +	       node = node->parent;
  13.189 +	       rbtree_rotate_right(rbtree, node);
  13.190 +	       }
  13.191 +	    node->parent->color = BLACK;
  13.192 +	    node->parent->parent->color = RED;
  13.193 +	    rbtree_rotate_left(rbtree, node->parent->parent);
  13.194 +	    }
  13.195 +	 }
  13.196 +      }
  13.197 +   rbtree->root->color = BLACK;
  13.198 +   }
  13.199 +
  13.200 +////////////////////////////////////////////////////////////////////////////////
  13.201 +void
  13.202 +rbtree_walk_inorder(struct rbtree * rbtree, void (*op)(void * data))
  13.203 +   {
  13.204 +   if ( (NULL == rbtree) || (rbtree->nil == rbtree->root) || (NULL == op) )
  13.205 +      return;
  13.206 +
  13.207 +   rbtree_data_walk_inorder(rbtree, rbtree->root, op);
  13.208 +   }
  13.209 +
  13.210 +////////////////////////////////////////////////////////////////////////////////
  13.211 +void
  13.212 +rbtree_walk_postorder(struct rbtree * rbtree, void (*op)(void * data))
  13.213 +   {
  13.214 +   if ( (NULL == rbtree) || (rbtree->nil == rbtree->root) || (NULL == op) )
  13.215 +      return;
  13.216 +
  13.217 +   rbtree_data_walk_postorder(rbtree, rbtree->root, op);
  13.218 +   }
  13.219 +
  13.220 +////////////////////////////////////////////////////////////////////////////////
  13.221 +void
  13.222 +rbtree_walk_preorder(struct rbtree * rbtree, void (*op)(void * data))
  13.223 +   {
  13.224 +   if ( (NULL == rbtree) || (rbtree->nil == rbtree->root) || (NULL == op) )
  13.225 +      return;
  13.226 +
  13.227 +   rbtree_data_walk_preorder(rbtree, rbtree->root, op);
  13.228 +   }
  13.229 +
  13.230 +////////////////////////////////////////////////////////////////////////////////
  13.231 +void
  13.232 +rbtree_data_walk_inorder(struct rbtree * rbtree, struct rbtree_node * node, void (*op)(void * data))
  13.233 +   {
  13.234 +   if (rbtree->nil != node)
  13.235 +      {
  13.236 +      rbtree_data_walk_inorder(rbtree, node->left, op);
  13.237 +      op(node->data);
  13.238 +      rbtree_data_walk_inorder(rbtree, node->right, op);
  13.239 +      }
  13.240 +   }
  13.241 +
  13.242 +////////////////////////////////////////////////////////////////////////////////
  13.243 +void
  13.244 +rbtree_data_walk_postorder(struct rbtree * rbtree, struct rbtree_node * node, void (*op)(void * data))
  13.245 +   {
  13.246 +   if (rbtree->nil != node)
  13.247 +      {
  13.248 +      rbtree_data_walk_postorder(rbtree, node->left, op);
  13.249 +      rbtree_data_walk_postorder(rbtree, node->right, op);
  13.250 +      op(node->data);
  13.251 +      }
  13.252 +   }
  13.253 +
  13.254 +////////////////////////////////////////////////////////////////////////////////
  13.255 +void
  13.256 +rbtree_data_walk_preorder(struct rbtree * rbtree, struct rbtree_node * node, void (*op)(void * data))
  13.257 +   {
  13.258 +   if (rbtree->nil != node)
  13.259 +      {
  13.260 +      op(node->data);
  13.261 +      rbtree_data_walk_preorder(rbtree, node->left, op);
  13.262 +      rbtree_data_walk_preorder(rbtree, node->right, op);
  13.263 +      }
  13.264 +   }
  13.265 +
  13.266 +////////////////////////////////////////////////////////////////////////////////
  13.267 +void
  13.268 +rbtree_node_walk_postorder(struct rbtree * rbtree, struct rbtree_node * node, void (*op)(struct rbtree_node * n))
  13.269 +   {
  13.270 +   if (rbtree->nil != node)
  13.271 +      {
  13.272 +      rbtree_node_walk_postorder(rbtree, node->left, op);
  13.273 +      rbtree_node_walk_postorder(rbtree, node->right, op);
  13.274 +      op(node);
  13.275 +      }
  13.276 +   }
  13.277 +
  13.278 +////////////////////////////////////////////////////////////////////////////////
  13.279 +void *
  13.280 +rbtree_search(struct rbtree * rbtree, void * data)
  13.281 +   {
  13.282 +   if ( (NULL == rbtree) || (rbtree->nil == rbtree->root) || (NULL == data) )
  13.283 +      return NULL;
  13.284 +
  13.285 +   return rbtree_data_search(rbtree, rbtree->root, data);
  13.286 +   }
  13.287 +
  13.288 +////////////////////////////////////////////////////////////////////////////////
  13.289 +// Recursive
  13.290 +void *
  13.291 +rbtree_data_search(struct rbtree * rbtree, struct rbtree_node * node, void * data)
  13.292 +   {
  13.293 +   if (rbtree->nil == node)
  13.294 +      return NULL;
  13.295 +
  13.296 +   if (rbtree->eq(data, node->data))
  13.297 +      return node->data;
  13.298 +
  13.299 +   if (rbtree->le(data, node->data))
  13.300 +      return rbtree_data_search(rbtree, node->left, data);
  13.301 +   else
  13.302 +      return rbtree_data_search(rbtree, node->right, data);
  13.303 +   }
  13.304 +
  13.305 +////////////////////////////////////////////////////////////////////////////////
  13.306 +// Iterative
  13.307 +void *
  13.308 +rbtree_search_iterative(struct rbtree * rbtree, void * data)
  13.309 +   {
  13.310 +   if ( (NULL == rbtree) || (rbtree->nil == rbtree->root) || (NULL == data) )
  13.311 +      return NULL;
  13.312 +
  13.313 +   struct rbtree_node * node = rbtree->root;
  13.314 +   while (1)
  13.315 +      {
  13.316 +      if (rbtree->nil == node)
  13.317 +	 return NULL;
  13.318 +      
  13.319 +      if (rbtree->eq(data, node->data))
  13.320 +	 return node->data;
  13.321 +      
  13.322 +      if (rbtree->le(data, node->data))
  13.323 +	 node = node->left;
  13.324 +      else
  13.325 +	 node = node->right;
  13.326 +      }
  13.327 +   }
  13.328 +
  13.329 +////////////////////////////////////////////////////////////////////////////////
  13.330 +void *
  13.331 +rbtree_minimum(struct rbtree * rbtree)
  13.332 +   {
  13.333 +   if (NULL == rbtree)
  13.334 +      return NULL;
  13.335 +
  13.336 +   return rbtree_node_minimum(rbtree, rbtree->root);
  13.337 +   }
  13.338 +
  13.339 +////////////////////////////////////////////////////////////////////////////////
  13.340 +void *
  13.341 +rbtree_node_minimum(struct rbtree * rbtree, struct rbtree_node * node)
  13.342 +   {
  13.343 +   while ( (rbtree->nil != node) && (rbtree->nil != node->left) )
  13.344 +      node = node->left;
  13.345 +   if (rbtree->nil == node)
  13.346 +      return NULL;
  13.347 +   return node->data;
  13.348 +   }
  13.349 +
  13.350 +////////////////////////////////////////////////////////////////////////////////
  13.351 +void *
  13.352 +rbtree_maximum(struct rbtree * rbtree)
  13.353 +   {
  13.354 +   if (NULL == rbtree)
  13.355 +      return NULL;
  13.356 +
  13.357 +   return rbtree_node_maximum(rbtree, rbtree->root);
  13.358 +   }
  13.359 +
  13.360 +////////////////////////////////////////////////////////////////////////////////
  13.361 +void *
  13.362 +rbtree_node_maximum(struct rbtree * rbtree, struct rbtree_node * node)
  13.363 +   {
  13.364 +   while ( (rbtree->nil != node) && (rbtree->nil != node->right) )
  13.365 +      node = node->right;
  13.366 +   if (rbtree->nil == node)
  13.367 +      return NULL;
  13.368 +   return node->data;
  13.369 +   }
  13.370 +
  13.371 +////////////////////////////////////////////////////////////////////////////////
  13.372 +struct rbtree_iterator *
  13.373 +rbtree_begin(struct rbtree * rbtree)
  13.374 +   {
  13.375 +   if ( (NULL == rbtree) || (rbtree->nil == rbtree->root) )
  13.376 +      return NULL;
  13.377 +
  13.378 +   struct rbtree_node * min = rbtree->root;
  13.379 +   while (min->left)
  13.380 +      min = min->left;
  13.381 +
  13.382 +   struct rbtree_iterator * it = malloc(sizeof(struct rbtree_iterator));
  13.383 +   if (NULL == it)
  13.384 +      return NULL;
  13.385 +
  13.386 +   it->rbtree = rbtree;
  13.387 +   it->curr = min;
  13.388 +   return it;
  13.389 +   }
  13.390 +
  13.391 +////////////////////////////////////////////////////////////////////////////////
  13.392 +struct rbtree_iterator *
  13.393 +rbtree_end(struct rbtree * rbtree)
  13.394 +   {
  13.395 +   if ( (NULL == rbtree) || (rbtree->nil == rbtree->root) )
  13.396 +      return NULL;
  13.397 +
  13.398 +   struct rbtree_node * max = rbtree->root;
  13.399 +   while (max->right)
  13.400 +      max = max->right;
  13.401 +
  13.402 +   struct rbtree_iterator * it = malloc(sizeof(struct rbtree_iterator));
  13.403 +   if (NULL == it)
  13.404 +      return NULL;
  13.405 +
  13.406 +   it->rbtree = rbtree;
  13.407 +   it->curr = max;
  13.408 +   return it;
  13.409 +   }
  13.410 +
  13.411 +////////////////////////////////////////////////////////////////////////////////
  13.412 +struct rbtree_iterator *
  13.413 +rbtree_next(struct rbtree_iterator * it)
  13.414 +   {
  13.415 +   if ( (NULL == it) || (NULL == it->rbtree) || (it->rbtree->nil == it->curr) )
  13.416 +      return NULL;
  13.417 +
  13.418 +   if (it->rbtree->nil == it->curr->right)
  13.419 +      {
  13.420 +      struct rbtree_node * p = it->curr;
  13.421 +      it->curr = it->curr->parent;
  13.422 +      while ( (it->rbtree->nil != it->curr) && (p == it->curr->right) )
  13.423 +	 {
  13.424 +	 p = it->curr;
  13.425 +	 it->curr = it->curr->parent;
  13.426 +	 }
  13.427 +
  13.428 +      if (it->curr == it->rbtree->nil)
  13.429 +	 return NULL;
  13.430 +      }
  13.431 +   else
  13.432 +      {
  13.433 +      struct rbtree_node * min = it->curr->right;
  13.434 +      while (min->left)
  13.435 +	 min = min->left;
  13.436 +      it->curr = min;
  13.437 +      }
  13.438 +   return it;
  13.439 +   }
  13.440 +
  13.441 +////////////////////////////////////////////////////////////////////////////////
  13.442 +struct rbtree_iterator *
  13.443 +rbtree_prev(struct rbtree_iterator * it)
  13.444 +   {
  13.445 +   if ( (NULL == it) || (NULL == it->rbtree) || (it->rbtree->nil == it->curr) )
  13.446 +      return NULL;
  13.447 +
  13.448 +   if (it->rbtree->nil == it->curr->left)
  13.449 +      {
  13.450 +      struct rbtree_node * p = it->curr;
  13.451 +      it->curr = it->curr->parent;
  13.452 +      while ( (it->rbtree->nil != it->curr) && (p == it->curr->left) )
  13.453 +	 {
  13.454 +	 p = it->curr;
  13.455 +	 it->curr = it->curr->parent;
  13.456 +	 }
  13.457 +
  13.458 +      if (it->curr == it->rbtree->nil)
  13.459 +	 return NULL;
  13.460 +      }
  13.461 +   else
  13.462 +      {
  13.463 +      struct rbtree_node * max = it->curr->left;
  13.464 +      while (max->right)
  13.465 +	 max = max->right;
  13.466 +      it->curr = max;
  13.467 +      }
  13.468 +   return it;
  13.469 +   }
  13.470 +
  13.471 +////////////////////////////////////////////////////////////////////////////////
  13.472 +void *
  13.473 +rbtree_value(struct rbtree_iterator * it)
  13.474 +   {
  13.475 +   if ( (NULL == it) || (NULL == it->rbtree) || (it->rbtree->nil == it->curr) )
  13.476 +      return NULL;
  13.477 +
  13.478 +   return it->curr->data;
  13.479 +   }
  13.480 +
  13.481 +////////////////////////////////////////////////////////////////////////////////
  13.482 +void *
  13.483 +rbtree_find(struct rbtree_iterator * it, void * data)
  13.484 +   {
  13.485 +   if ( (NULL == it) || (NULL == it->rbtree) || (it->rbtree->nil == it->rbtree->root) || (NULL == data) )
  13.486 +      return NULL;
  13.487 +
  13.488 +   return rbtree_node_search(it->rbtree, it->rbtree->root, data);
  13.489 +   }
  13.490 +
  13.491 +////////////////////////////////////////////////////////////////////////////////
  13.492 +// Recursive
  13.493 +struct rbtree_node *
  13.494 +rbtree_node_search(struct rbtree * rbtree, struct rbtree_node * node, void * data)
  13.495 +   {
  13.496 +   if (rbtree->nil == node)
  13.497 +      return NULL;
  13.498 +
  13.499 +   if (rbtree->eq(data, node->data))
  13.500 +      return node;
  13.501 +
  13.502 +   if (rbtree->le(data, node->data))
  13.503 +      return rbtree_node_search(rbtree, node->left, data);
  13.504 +   else
  13.505 +      return rbtree_node_search(rbtree, node->right, data);
  13.506 +   }
  13.507 +
  13.508 +////////////////////////////////////////////////////////////////////////////////
  13.509 +struct rbtree_node *
  13.510 +rbtree_transplant(struct rbtree * rbtree, struct rbtree_node * a, struct rbtree_node * b)
  13.511 +   {
  13.512 +   if ( (NULL == a) || (NULL == b) )
  13.513 +      return NULL;
  13.514 +
  13.515 +   if (rbtree->nil == a->parent)
  13.516 +      rbtree->root = b;
  13.517 +   else if (a == a->parent->left)
  13.518 +      a->parent->left = b;
  13.519 +   else
  13.520 +      a->parent->right = b;
  13.521 +
  13.522 +   b->parent = a->parent;
  13.523 +
  13.524 +   return a;
  13.525 +   }
  13.526 +
  13.527 +////////////////////////////////////////////////////////////////////////////////
  13.528 +void *
  13.529 +rbtree_remove(struct rbtree_iterator * it)
  13.530 +   {
  13.531 +   if ( (NULL == it) || (NULL == it->curr) )
  13.532 +      return NULL;
  13.533 +
  13.534 +   // Get predecessor and save it
  13.535 +   struct rbtree_iterator pred;
  13.536 +   pred.curr = it->curr;
  13.537 +   pred.rbtree = it->rbtree;
  13.538 +   rbtree_prev(&pred);
  13.539 +
  13.540 +   struct rbtree_node * x;
  13.541 +   struct rbtree_node * y = it->curr;
  13.542 +   enum rbtree_color original_color = y->color;
  13.543 +
  13.544 +   if (it->rbtree->nil == it->curr->left)
  13.545 +      {
  13.546 +      x = it->curr->right;
  13.547 +      rbtree_transplant(it->rbtree, it->curr, it->curr->right);
  13.548 +      }
  13.549 +   else if (it->rbtree->nil == it->curr->right)
  13.550 +      {
  13.551 +      x = it->curr->left;
  13.552 +      rbtree_transplant(it->rbtree, it->curr, it->curr->left);
  13.553 +      }
  13.554 +   else
  13.555 +      {
  13.556 +      y = rbtree_node_minimum(it->rbtree, it->curr->right);
  13.557 +      original_color = y->color;
  13.558 +      x = y->right;
  13.559 +      if (it->curr == y->parent)
  13.560 +	 x->parent = y;
  13.561 +      else
  13.562 +	 {
  13.563 +	 rbtree_transplant(it->rbtree, y, y->right);
  13.564 +	 y->right = it->curr->right;
  13.565 +	 y->right->parent = y;
  13.566 +	 }
  13.567 +      rbtree_transplant(it->rbtree, it->curr, y);
  13.568 +      y->left = it->curr->left;
  13.569 +      y->left->parent = y;
  13.570 +      y->color = it->curr->color;
  13.571 +      }
  13.572 +
  13.573 +   if (BLACK == original_color)
  13.574 +      rbtree_remove_fixup(it->rbtree, x);
  13.575 +
  13.576 +   void * data = it->curr->data;
  13.577 +   free(it->curr);
  13.578 +
  13.579 +   // Update it to point to pred's successor
  13.580 +   rbtree_next(&pred);
  13.581 +   it->curr = pred.curr;
  13.582 +
  13.583 +   return data;
  13.584 +   }
  13.585 +
  13.586 +////////////////////////////////////////////////////////////////////////////////
  13.587 +void
  13.588 +rbtree_remove_fixup(struct rbtree * rbtree, struct rbtree_node * node)
  13.589 +   {
  13.590 +   while ( (rbtree->root != node) && (BLACK == node->color) )
  13.591 +      {
  13.592 +      if (node == node->parent->left)
  13.593 +	 {
  13.594 +	 struct rbtree_node * w = node->parent->right;
  13.595 +	 if (RED == w->color)
  13.596 +	    {
  13.597 +	    w->color = BLACK;
  13.598 +	    node->parent->color = RED;
  13.599 +	    rbtree_rotate_left(rbtree, node->parent);
  13.600 +	    w = node->parent->right;
  13.601 +	    }
  13.602 +	 if ( (BLACK == w->left->color) && (BLACK == w->right->color) )
  13.603 +	    {
  13.604 +	    w->left->color = RED;
  13.605 +	    node = node->parent;
  13.606 +	    }
  13.607 +	 else
  13.608 +	    {
  13.609 +	    if (BLACK == w->right->color)
  13.610 +	       {
  13.611 +	       w->left->color = BLACK;
  13.612 +	       w->color = RED;
  13.613 +	       rbtree_rotate_right(rbtree, w);
  13.614 +	       w = node->parent->right;
  13.615 +	       }
  13.616 +	    w->color = node->parent->color;
  13.617 +	    node->parent->color = BLACK;
  13.618 +	    w->right->color = BLACK;
  13.619 +	    rbtree_rotate_left(rbtree, node->parent);
  13.620 +	    node = rbtree->root;
  13.621 +	    }
  13.622 +	 }
  13.623 +      else
  13.624 +	 {
  13.625 +	 struct rbtree_node * w = node->parent->left;
  13.626 +	 if (RED == w->color)
  13.627 +	    {
  13.628 +	    w->color = BLACK;
  13.629 +	    node->parent->color = RED;
  13.630 +	    rbtree_rotate_right(rbtree, node->parent);
  13.631 +	    w = node->parent->left;
  13.632 +	    }
  13.633 +	 if ( (BLACK == w->right->color) && (BLACK == w->left->color) )
  13.634 +	    {
  13.635 +	    w->right->color = RED;
  13.636 +	    node = node->parent;
  13.637 +	    }
  13.638 +	 else
  13.639 +	    {
  13.640 +	    if (BLACK == w->left->color)
  13.641 +	       {
  13.642 +	       w->right->color = BLACK;
  13.643 +	       w->color = RED;
  13.644 +	       rbtree_rotate_left(rbtree, w);
  13.645 +	       w = node->parent->left;
  13.646 +	       }
  13.647 +	    w->color = node->parent->color;
  13.648 +	    node->parent->color = BLACK;
  13.649 +	    w->left->color = BLACK;
  13.650 +	    rbtree_rotate_right(rbtree, node->parent);
  13.651 +	    node = rbtree->root;
  13.652 +	    }
  13.653 +	 }
  13.654 +      }
  13.655 +   node->color = BLACK;
  13.656 +   }
  13.657 +
  13.658 +////////////////////////////////////////////////////////////////////////////////
  13.659 +void
  13.660 +rbtree_rotate_left(struct rbtree * rbtree, struct rbtree_node * node)
  13.661 +   {
  13.662 +   if ( (NULL == rbtree) || (rbtree->nil == node) || (rbtree->nil == node->right) )
  13.663 +      return;
  13.664 +
  13.665 +   struct rbtree_node * y = node->right;
  13.666 +
  13.667 +   node->right = y->left;
  13.668 +   if (rbtree->nil != y->left)
  13.669 +      y->left->parent = node;
  13.670 +
  13.671 +   y->parent = node->parent;
  13.672 +   if (rbtree->nil == node->parent)
  13.673 +      rbtree->root = y;
  13.674 +   else if (node == node->parent->left)
  13.675 +      node->parent->left = y;
  13.676 +   else
  13.677 +      node->parent->right = y;
  13.678 +
  13.679 +   y->left = node;
  13.680 +   node->parent = y;
  13.681 +   }
  13.682 +
  13.683 +////////////////////////////////////////////////////////////////////////////////
  13.684 +void
  13.685 +rbtree_rotate_right(struct rbtree * rbtree, struct rbtree_node * node)
  13.686 +   {
  13.687 +   if ( (NULL == rbtree) || (rbtree->nil == node) || (rbtree->nil == node->left) )
  13.688 +      return;
  13.689 +
  13.690 +   struct rbtree_node * y = node->left;
  13.691 +
  13.692 +   node->left = y->right;
  13.693 +   if (rbtree->nil != y->right)
  13.694 +      y->right->parent = node;
  13.695 +
  13.696 +   y->parent = node->parent;
  13.697 +   if (rbtree->nil == node->parent)
  13.698 +      rbtree->root = y;
  13.699 +   else if (node == node->parent->right)
  13.700 +      node->parent->right = y;
  13.701 +   else
  13.702 +      node->parent->left = y;
  13.703 +
  13.704 +   y->right = node;
  13.705 +   node->parent = y;
  13.706 +   }
  13.707 +

    14.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
    14.2 +++ b/src/rbtree.h	Fri Sep 28 03:08:25 2012 -0500
    14.3 @@ -0,0 +1,31 @@
    14.4 +#ifndef RBTREE_H_
    14.5 +#define RBTREE_H_
    14.6 +
    14.7 +#include <stddef.h>
    14.8 +#include <stdbool.h>
    14.9 +
   14.10 +struct rbtree;
   14.11 +struct rbtree_node;
   14.12 +struct rbtree_iterator;
   14.13 +
   14.14 +struct rbtree * rbtree_new(bool (*le)(void * a, void * b), bool (*eq)(void * a, void * b));
   14.15 +void rbtree_delete(struct rbtree * rbtree);
   14.16 +void * rbtree_insert(struct rbtree * rbtree, void * data);
   14.17 +void * rbtree_search(struct rbtree * rbtree, void * data);
   14.18 +void * rbtree_search_iterative(struct rbtree * rbtree, void * data);
   14.19 +void * rbtree_minimum(struct rbtree * rbtree);
   14.20 +void * rbtree_maximum(struct rbtree * rbtree);
   14.21 +
   14.22 +void rbtree_walk_inorder(struct rbtree * rbtree, void (*op)(void * data));
   14.23 +void rbtree_walk_preorder(struct rbtree * rbtree, void (*op)(void * data));
   14.24 +void rbtree_walk_postorder(struct rbtree * rbtree, void (*op)(void * data));
   14.25 +
   14.26 +struct rbtree_iterator * rbtree_begin(struct rbtree * rbtree);
   14.27 +struct rbtree_iterator * rbtree_end(struct rbtree * rbtree);
   14.28 +struct rbtree_iterator * rbtree_next(struct rbtree_iterator * it);
   14.29 +struct rbtree_iterator * rbtree_prev(struct rbtree_iterator * it);
   14.30 +void * rbtree_value(struct rbtree_iterator * it);
   14.31 +void * rbtree_find(struct rbtree_iterator * it, void * data);
   14.32 +void * rbtree_remove(struct rbtree_iterator * it);
   14.33 +
   14.34 +#endif

    15.1 --- a/src/ring_buffer.c	Thu Sep 27 10:57:41 2012 -0500
    15.2 +++ b/src/ring_buffer.c	Fri Sep 28 03:08:25 2012 -0500
    15.3 @@ -3,6 +3,14 @@
    15.4  
    15.5  #include "ring_buffer.h"
    15.6  
    15.7 +struct ring_buffer
    15.8 +   {
    15.9 +   void ** data;
   15.10 +   size_t max;
   15.11 +   size_t start;
   15.12 +   size_t count;
   15.13 +   };
   15.14 +
   15.15  ////////////////////////////////////////////////////////////////////////////////
   15.16  struct ring_buffer * ring_buffer_new(size_t const max)
   15.17     {

    16.1 --- a/src/ring_buffer.h	Thu Sep 27 10:57:41 2012 -0500
    16.2 +++ b/src/ring_buffer.h	Fri Sep 28 03:08:25 2012 -0500
    16.3 @@ -3,13 +3,7 @@
    16.4  
    16.5  #include <stddef.h>
    16.6  
    16.7 -struct ring_buffer
    16.8 -   {
    16.9 -   void ** data;
   16.10 -   size_t max;
   16.11 -   size_t start;
   16.12 -   size_t count;
   16.13 -   };
   16.14 +struct ring_buffer;
   16.15  
   16.16  struct ring_buffer * ring_buffer_new(size_t const size);
   16.17  void ring_buffer_delete(struct ring_buffer * rb);

    17.1 --- a/src/stack.c	Thu Sep 27 10:57:41 2012 -0500
    17.2 +++ b/src/stack.c	Fri Sep 28 03:08:25 2012 -0500
    17.3 @@ -3,6 +3,13 @@
    17.4  
    17.5  #include "stack.h"
    17.6  
    17.7 +struct stack
    17.8 +   {
    17.9 +   void ** data;
   17.10 +   size_t size;
   17.11 +   size_t max;
   17.12 +   };
   17.13 +
   17.14  ////////////////////////////////////////////////////////////////////////////////
   17.15  struct stack * stack_new(size_t const max)
   17.16     {

    18.1 --- a/src/stack.h	Thu Sep 27 10:57:41 2012 -0500
    18.2 +++ b/src/stack.h	Fri Sep 28 03:08:25 2012 -0500
    18.3 @@ -3,12 +3,7 @@
    18.4  
    18.5  #include <stddef.h>
    18.6  
    18.7 -struct stack
    18.8 -   {
    18.9 -   void ** data;
   18.10 -   size_t size;
   18.11 -   size_t max;
   18.12 -   };
   18.13 +struct stack;
   18.14  
   18.15  struct stack * stack_new(size_t const max);
   18.16  void stack_delete(struct stack * s);