Make libbmm more efficient

libbmm calls into the kernel a lot to perform various functions such as
translating between virtual and physical addresses, finding out the
buffer size, and so forth.  Much of this can be done in userspace,
because we have that information at the point where the buffer is
allocated.

Rather than having to keep fetching it from the kernel, store it in our
own local bmm_buffer structure, and store this in a pair of rb trees -
one indexed by physical address and the other by virtual address.  This
allows us to efficiently look up the bmm_buffer structure by either
address, and retrieve the other buffer attribute(s).

Reference: http://web.eecs.utk.edu/~plank/plank/rbtree/rbtree.html

4 files changed, 888 insertions, 55 deletions

diff --git a/Makefile.am b/Makefile.am
index c135cb7..02ab833 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -5,7 +5,7 @@ libbmm_la_LTLIBRARIES = libbmm.la
 libbmm_ladir = $(libdir)
 libbmm_la_LDFLAGS = -no-undefined -export-symbols-regex "bmm_*" \
 	-version-info @ABI_VERSION@:@ABI_REVISION@:@ABI_AGE@
-libbmm_la_SOURCES = bmm_lib.c bmm_lib_priv.h
+libbmm_la_SOURCES = bmm_lib.c bmm_lib_priv.h rb.c rb.h
 
 libbmm_laincludedir = $(includedir)
 libbmm_lainclude_HEADERS = bmm_lib.h
diff --git a/bmm_lib.c b/bmm_lib.c
index 1b3a156..3e4ebd2 100644
--- a/bmm_lib.c
+++ b/bmm_lib.c
@@ -15,11 +15,15 @@
 #include <sys/types.h>
 #include <sys/stat.h>
 #include <sys/mman.h>
+#include <assert.h>
 #include <fcntl.h>
+#include <pthread.h>
+#include <stdlib.h>
 #include <unistd.h>
 
 #include "bmm_lib_priv.h"
 #include "bmm_lib.h"
+#include "rb.h"
 
 #undef DEBUG
 
@@ -38,6 +42,108 @@
 
 static unsigned bmm_api;
 static int bmm_fd = -1;
+static pthread_mutex_t bmm_mutex = PTHREAD_MUTEX_INITIALIZER;
+static Rb_node virt_rb;
+static Rb_node phys_rb;
+
+struct bmm_buffer {
+	void *vaddr;
+	unsigned long paddr;
+	size_t size;
+	int attr;
+};
+
+static int cmp_virt(const void *key, const void *val)
+{
+	const struct bmm_buffer *buf = val;
+	void *k = (void *)key;
+
+	return (k < buf->vaddr) ? -1 :
+	       (k - buf->vaddr < buf->size) ? 0 : 1;
+}
+
+static int cmp_phys(const void *key, const void *val)
+{
+	const struct bmm_buffer *buf = val;
+	unsigned long k = (unsigned long)key;
+
+	return (k < buf->paddr) ? -1 :
+	       (k - buf->paddr < buf->size) ? 0 : 1;
+}
+
+static struct bmm_buffer *bmm_buf_find_virt(void *virt)
+{
+	struct bmm_buffer *buf = NULL;
+	Rb_node node;
+	int found = 0;
+
+	node = rb_find_key_n(virt_rb, virt, cmp_virt, &found);
+	if (found) {
+		buf = rb_val(node);
+
+		pr_debug("rb: %s(%p) phys=0x%08lx virt=%p size=0x%08lx\n",
+			"find_virt", virt, buf->paddr, buf->vaddr, buf->size);
+	} else {
+		pr_debug("rb: %s(%p): not found\n",
+			"find_virt", virt);
+	}
+
+	return buf;
+}
+
+static struct bmm_buffer *bmm_buf_find_phys(unsigned long phys)
+{
+	struct bmm_buffer *buf = NULL;
+	Rb_node node;
+	int found = 0;
+
+	node = rb_find_key_n(phys_rb, (void *)phys, cmp_phys, &found);
+	if (found) {
+		buf = rb_val(node);
+
+		pr_debug("rb: %s(0x%08lx) phys=0x%08lx virt=%p size=0x%08lx\n",
+			"find_phys", (unsigned long)phys, buf->paddr, buf->vaddr, buf->size);
+	} else {
+		pr_debug("rb: %s(0x%08lx): not found\n",
+			"find_phys", (unsigned long)phys);
+	}
+
+	return buf;
+}
+
+static void bmm_buf_remove(struct bmm_buffer *buf)
+{
+	Rb_node node;
+	int found = 0;
+
+	pr_debug("rb: %s phys=0x%08lx virt=%p size=0x%08lx\n",
+		"remove", buf->paddr, buf->vaddr, buf->size);
+
+	node = rb_find_key_n(virt_rb, buf->vaddr, cmp_virt, &found);
+	assert(found);
+	rb_delete_node(node);
+
+	node = rb_find_key_n(phys_rb, (void *)buf->paddr, cmp_phys, &found);
+	assert(found);
+	rb_delete_node(node);
+}
+
+static void bmm_buf_insert(struct bmm_buffer *buf)
+{
+	Rb_node node;
+	int found = 0;
+
+	pr_debug("rb: %s phys=0x%08lx virt=%p size=0x%08lx\n",
+		"insert", buf->paddr, buf->vaddr, buf->size);
+
+	node = rb_find_key_n(virt_rb, buf->vaddr, cmp_virt, &found);
+	assert(found == 0);
+	rb_insert_b(node, buf);
+
+	node = rb_find_key_n(phys_rb, (void *)buf->paddr, cmp_phys, &found);
+	assert(found == 0);
+	rb_insert_b(node, buf);
+}
 
 static int bmm_get_api_version(void)
 {
@@ -64,10 +170,14 @@ static int bmm_get_api_version(void)
 
 int bmm_init()
 {
-        /* attempt to open the BMM driver */
-	if(bmm_fd < 0) {
-		bmm_fd = open(BMM_DEVICE_FILE, O_RDWR | O_CLOEXEC);
+	if (bmm_fd < 0) {
+		virt_rb = make_rb();
+		phys_rb = make_rb();
+		if (!virt_rb || !phys_rb)
+			goto err_rb;
 
+		/* attempt to open the BMM driver */
+		bmm_fd = open(BMM_DEVICE_FILE, O_RDWR | O_CLOEXEC);
 		pr_debug("BMM device fd: %d\n", bmm_fd);
 		if (bmm_fd < 0)
 			goto err_open;
@@ -82,18 +192,29 @@ int bmm_init()
 	close(bmm_fd);
 	bmm_fd = -1;
  err_open:
+ err_rb:
+	if (phys_rb)
+		rb_free_tree(phys_rb);
+	if (virt_rb)
+		rb_free_tree(virt_rb);
+	phys_rb = virt_rb = NULL;
 	return bmm_fd;
 }
 
 void bmm_exit()
 {
-	if(bmm_fd >= 0)
+	if (bmm_fd >= 0) {
 		close(bmm_fd);
+		rb_free_tree(phys_rb);
+		rb_free_tree(virt_rb);
+		phys_rb = virt_rb = NULL;
+	}
 	bmm_fd = -1;
 }
 
 void *bmm_malloc_aligned(unsigned long size, int attr, unsigned align)
 {
+	struct bmm_buffer *buf;
 	int ret;
 	void *vaddr;
 	ioctl_arg_t io;
@@ -104,6 +225,10 @@ void *bmm_malloc_aligned(unsigned long size, int attr, unsigned align)
 	if(bmm_init() < 0)
 		return NULL;
 
+	buf = malloc(sizeof(*buf));
+	if (!buf)
+		return NULL;
+
 	pr_debug("%s(size=%lu,attr=%x,align=%u)\n", __FUNCTION__, size, attr, align);
 
 	/* obsolete, only for back-compatible */
@@ -118,13 +243,31 @@ void *bmm_malloc_aligned(unsigned long size, int attr, unsigned align)
 	io.output = 0;
 	io.arg = attr;
 	ret = ioctl(bmm_fd, BMM_MALLOC_ALIGNED, &io);
-	if(ret < 0 || io.output == 0)
-		return NULL;
+	if (ret < 0 || io.output == 0)
+		goto err_free_buf;
 
 	pr_debug("bmm_malloc return paddr = 0x%08lx\n", io.output);
 
 	vaddr = mmap(0, size, PROT_READ | PROT_WRITE, MAP_SHARED, bmm_fd, io.output);
-	return ((int)vaddr == -1) ? NULL : vaddr;
+	if ((int)vaddr == -1) {
+		/* FIXME: we can't free the bmm buffer without a vaddr! */
+		goto err_free_buf;
+	}
+
+	buf->vaddr = vaddr;
+	buf->paddr = io.output;
+	buf->size = size;
+	buf->attr = attr;
+
+	pthread_mutex_lock(&bmm_mutex);
+	bmm_buf_insert(buf);
+	pthread_mutex_unlock(&bmm_mutex);
+
+	return vaddr;
+
+ err_free_buf:
+	free(buf);
+	return NULL;
 }
 
 void *bmm_malloc(unsigned long size, int attr)
@@ -134,19 +277,27 @@ void *bmm_malloc(unsigned long size, int attr)
 
 void bmm_free(void *vaddr)
 {
-	unsigned long size;
+	struct bmm_buffer *buf;
 	ioctl_arg_t io;
 
-	if(bmm_init() < 0)
+	if (bmm_init() < 0)
 		return;
 
-	size = bmm_get_mem_size(vaddr);
-	munmap(vaddr, size);
+	pthread_mutex_lock(&bmm_mutex);
+	buf = bmm_buf_find_virt(vaddr);
+	if (buf)
+		bmm_buf_remove(buf);
+	pthread_mutex_unlock(&bmm_mutex);
 
-	io.input = (unsigned long)vaddr;
+	assert(buf);
+
+	munmap(buf->vaddr, buf->size);
+
+	io.input = (unsigned long)buf->vaddr;
 	io.output = 0;
 	io.arg = 0;
 	ioctl(bmm_fd, BMM_FREE, &io);
+	free(buf);
 }
 
 void *bmm_attach(unsigned long paddr, unsigned long len)
@@ -174,38 +325,36 @@ void bmm_detach(void *vaddr, unsigned long len)
 
 void *bmm_get_vaddr(unsigned long paddr)
 {
-	int ret;
-	ioctl_arg_t io;
+	struct bmm_buffer *buf;
+	void *va = NULL;
 
-	if(bmm_init() < 0)
-		return NULL;
+	if (bmm_init() < 0)
+		return 0;
 
-	io.input = paddr;
-	io.output = 0;
-	io.arg = 0;
-	ret = ioctl(bmm_fd, BMM_GET_VIRT_ADDR, &io);
-	if(ret < 0)
-		return NULL;
+	pthread_mutex_lock(&bmm_mutex);
+	buf = bmm_buf_find_phys(paddr);
+	if (buf)
+		va = buf->vaddr + (paddr - buf->paddr);
+	pthread_mutex_unlock(&bmm_mutex);
 
-	return (void *)io.output;
+	return va;
 }
 
 unsigned long bmm_get_paddr(void *vaddr)
 {
-	int ret;
-	ioctl_arg_t io;
+	struct bmm_buffer *buf;
+	unsigned long pa = 0;
 
-	if(bmm_init() < 0)
+	if (bmm_init() < 0)
 		return 0;
 
-	io.input = (unsigned long)vaddr;
-	io.output = 0;
-	io.arg = 0;
-	ret = ioctl(bmm_fd,BMM_GET_PHYS_ADDR, &io);
-	if(ret < 0)
-		return 0;
+	pthread_mutex_lock(&bmm_mutex);
+	buf = bmm_buf_find_virt(vaddr);
+	if (buf)
+		pa = buf->paddr + (vaddr - buf->vaddr);
+	pthread_mutex_unlock(&bmm_mutex);
 
-	return io.output;
+	return pa;
 }
 
 int bmm_get_dmabuf_fd(void *vaddr)
@@ -227,42 +376,41 @@ int bmm_get_dmabuf_fd(void *vaddr)
 
 unsigned long bmm_get_mem_size(void *vaddr)
 {
-	int ret;
-	ioctl_arg_t io;
+	struct bmm_buffer *buf;
+	unsigned long size = 0;
 
-	if(bmm_init() < 0)
+	if (bmm_init() < 0)
 		return 0;
 
-	io.input = (unsigned long)vaddr;
-	io.output = 0;
-	io.arg = 0;
-	ret = ioctl(bmm_fd,BMM_GET_MEM_SIZE, &io);
-	if(ret < 0)
-		return 0;
+	pthread_mutex_lock(&bmm_mutex);
+	buf = bmm_buf_find_virt(vaddr);
+	if (buf)
+		size = buf->size;
+	pthread_mutex_unlock(&bmm_mutex);
 
-	return io.output;
+	return size;
 }
 
 int bmm_get_mem_attr(void *vaddr)
 {
-	int ret;
-	ioctl_arg_t io;
+	struct bmm_buffer *buf;
+	int attr = 0;
 
-	if(bmm_init() < 0)
+	if (bmm_init() < 0)
 		return 0;
 
-	io.input = (unsigned long)vaddr;
-	io.output = 0;
-	io.arg = 0;
-	ret = ioctl(bmm_fd, BMM_GET_MEM_ATTR, &io);
-	if(ret < 0)
-		return 0;
+	pthread_mutex_lock(&bmm_mutex);
+	buf = bmm_buf_find_virt(vaddr);
+	if (buf)
+		attr = buf->attr;
+	pthread_mutex_unlock(&bmm_mutex);
 
-	return (int)io.output;
+	return attr;
 }
 
 int bmm_set_mem_attr(void *vaddr, int attr)
 {
+	struct bmm_buffer *buf;
 	int ret;
 	ioctl_arg_t io;
 
@@ -276,7 +424,15 @@ int bmm_set_mem_attr(void *vaddr, int attr)
 	if(ret < 0)
 		return 0;
 
-	return (int)io.output;
+	attr = io.output;
+
+	pthread_mutex_lock(&bmm_mutex);
+	buf = bmm_buf_find_virt(vaddr);
+	if (buf)
+		buf->attr = attr;
+	pthread_mutex_unlock(&bmm_mutex);
+
+	return attr;
 }
 
 unsigned long bmm_get_total_space()
diff --git a/rb.c b/rb.c
new file mode 100644
index 0000000..34a270e
--- /dev/null
+++ b/rb.c
@@ -0,0 +1,549 @@
+/*
+Generic C code for red-black trees.
+Copyright (C) 2000 James S. Plank
+
+This library is free software; you can redistribute it and/or
+modify it under the terms of the GNU Lesser General Public
+License as published by the Free Software Foundation; either
+version 2.1 of the License, or (at your option) any later version.
+
+This library is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+Lesser General Public License for more details.
+
+You should have received a copy of the GNU Lesser General Public
+License along with this library; if not, write to the Free Software
+Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ */
+/* Revision 1.2.  Jim Plank */
+
+/* Original code by Jim Plank (plank@cs.utk.edu) */
+/* modified for THINK C 6.0 for Macintosh by Chris Bartley */
+
+/* Modified by Russell King to support embedded keys only */
+
+#include <assert.h>
+#include <string.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <ctype.h>
+#include "rb.h"
+
+static void mk_new_int(Rb_node l, Rb_node r, Rb_node p, int il);
+static Rb_node lprev(Rb_node n);
+static Rb_node rprev(Rb_node n);
+static void recolor(Rb_node n);
+static void single_rotate(Rb_node y, int l);
+#ifdef DEBUG
+static void rb_print_tree(Rb_node t, int level);
+static void rb_iprint_tree(Rb_node t, int level);
+#endif
+
+
+#define isred(n) (n->s.red)
+#define isblack(n) (!isred(n))
+#define isleft(n) (n->s.left)
+#define isright(n) (!isleft(n))
+#define isint(n) (n->s.internal)
+#define isext(n) (!isint(n))
+#define ishead(n) (n->s.head)
+#define isroot(n) (n->s.root)
+#define setred(n) n->s.red = 1
+#define setblack(n) n->s.red = 0
+#define setleft(n) n->s.left = 1
+#define setright(n) n->s.left = 0
+#define sethead(n) n->s.head = 1
+#define setroot(n) n->s.root = 1
+#define setint(n) n->s.internal = 1
+#define setext(n) n->s.internal = 0
+#define setnormal(n) { n->s.root = 0; n ->s.head = 0; }
+#define sibling(n) ((isleft(n)) ? n->p.parent->c.child.right \
+                                : n->p.parent->c.child.left)
+
+static void insert(Rb_node item, Rb_node list)	/* Inserts to the end of a list */
+{
+  Rb_node last_node;
+
+  last_node = list->c.list.blink;
+
+  list->c.list.blink = item;
+  last_node->c.list.flink = item;
+  item->c.list.blink = last_node;
+  item->c.list.flink = list;
+}
+
+static void delete_item(Rb_node item)		/* Deletes an arbitrary iterm */
+{
+  item->c.list.flink->c.list.blink = item->c.list.blink;
+  item->c.list.blink->c.list.flink = item->c.list.flink;
+}
+
+#define mk_new_ext(new, vvval) {\
+  new = (Rb_node) malloc(sizeof(struct rb_node));\
+  new->v.val = vvval;\
+  setext(new);\
+  setblack(new);\
+  setnormal(new);\
+}
+
+static void mk_new_int(Rb_node l, Rb_node r, Rb_node p, int il)
+{
+  Rb_node newnode;
+
+  newnode = (Rb_node) malloc(sizeof(struct rb_node));
+  setint(newnode);
+  setred(newnode);
+  setnormal(newnode);
+  newnode->c.child.left = l;
+  newnode->c.child.right = r;
+  newnode->p.parent = p;
+  newnode->k.lext = l;
+  newnode->v.rext = r;
+  l->p.parent = newnode;
+  r->p.parent = newnode;
+  setleft(l);
+  setright(r);
+  if (ishead(p)) {
+    p->p.root = newnode;
+    setroot(newnode);
+  } else if (il) {
+    setleft(newnode);
+    p->c.child.left = newnode;
+  } else {
+    setright(newnode);
+    p->c.child.right = newnode;
+  }
+  recolor(newnode);
+}
+
+
+Rb_node lprev(Rb_node n)
+{
+  if (ishead(n)) return n;
+  while (!isroot(n)) {
+    if (isright(n)) return n->p.parent;
+    n = n->p.parent;
+  }
+  return n->p.parent;
+}
+
+Rb_node rprev(Rb_node n)
+{
+  if (ishead(n)) return n;
+  while (!isroot(n)) {
+    if (isleft(n)) return n->p.parent;
+    n = n->p.parent;
+  }
+  return n->p.parent;
+}
+
+Rb_node make_rb(void)
+{
+  Rb_node head;
+
+  head = (Rb_node) malloc (sizeof(struct rb_node));
+  head->c.list.flink = head;
+  head->c.list.blink = head;
+  head->p.root = head;
+  sethead(head);
+  return head;
+}
+
+Rb_node rb_find_key_n(Rb_node n, const void *key, rb_key_cmp_fn cmp, int *fnd)
+{
+  int rc;
+  *fnd = 0;
+#ifdef DEBUG
+  if (!ishead(n)) {
+    fprintf(stderr, "%s called on non-head %p\n", __FUNCTION__, n);
+    exit(1);
+  }
+#else
+  assert(ishead(n));
+#endif
+  if (n->p.root == n) return n;
+  rc = cmp(key, n->c.list.blink->v.val);
+  if (rc == 0) {
+    *fnd = 1;
+    return n->c.list.blink;
+  }
+  if (rc > 0) return n;
+  else n = n->p.root;
+  while (1) {
+    if (isext(n)) return n;
+    rc = cmp(key, n->k.lext->v.val);
+    if (rc == 0) {
+      *fnd = 1;
+      return n->k.lext;
+    }
+    n = rc < 0 ? n->c.child.left : n->c.child.right;
+  }
+}
+
+Rb_node rb_find_key(Rb_node n, const void *key, rb_key_cmp_fn cmp)
+{
+  int fnd;
+  return rb_find_key_n(n, key, cmp, &fnd);
+}
+
+Rb_node rb_insert_b(Rb_node n, void *val)
+{
+  Rb_node newleft, newright, newnode, p;
+
+  if (ishead(n)) {
+    if (n->p.root == n) {         /* Tree is empty */
+      mk_new_ext(newnode, val);
+      insert(newnode, n);
+      n->p.root = newnode;
+      newnode->p.parent = n;
+      setroot(newnode);
+      return newnode;
+    } else {
+      mk_new_ext(newright, val);
+      insert(newright, n);
+      newleft = newright->c.list.blink;
+      setnormal(newleft);
+      mk_new_int(newleft, newright, newleft->p.parent, isleft(newleft));
+      p = rprev(newright);
+      if (!ishead(p)) p->k.lext = newright;
+      return newright;
+    }
+  } else {
+    mk_new_ext(newleft, val);
+    insert(newleft, n);
+    setnormal(n);
+    mk_new_int(newleft, n, n->p.parent, isleft(n));
+    p = lprev(newleft);
+    if (!ishead(p)) p->v.rext = newleft;
+    return newleft;
+  }
+}
+
+static void recolor(Rb_node n)
+{
+  Rb_node p, gp, s;
+  int done = 0;
+
+  while(!done) {
+    if (isroot(n)) {
+      setblack(n);
+      return;
+    }
+
+    p = n->p.parent;
+
+    if (isblack(p)) return;
+
+    if (isroot(p)) {
+      setblack(p);
+      return;
+    }
+
+    gp = p->p.parent;
+    s = sibling(p);
+    if (isred(s)) {
+      setblack(p);
+      setred(gp);
+      setblack(s);
+      n = gp;
+    } else {
+      done = 1;
+    }
+  }
+  /* p's sibling is black, p is red, gp is black */
+
+  if ((isleft(n) == 0) == (isleft(p) == 0)) {
+    single_rotate(gp, isleft(n));
+    setblack(p);
+    setred(gp);
+  } else {
+    single_rotate(p, isleft(n));
+    single_rotate(gp, isleft(n));
+    setblack(n);
+    setred(gp);
+  }
+}
+
+static void single_rotate(Rb_node y, int l)
+{
+  int rl, ir;
+  Rb_node x, yp;
+
+  ir = isroot(y);
+  yp = y->p.parent;
+  if (!ir) {
+    rl = isleft(y);
+  }
+
+  if (l) {
+    x = y->c.child.left;
+    y->c.child.left = x->c.child.right;
+    setleft(y->c.child.left);
+    y->c.child.left->p.parent = y;
+    x->c.child.right = y;
+    setright(y);
+  } else {
+    x = y->c.child.right;
+    y->c.child.right = x->c.child.left;
+    setright(y->c.child.right);
+    y->c.child.right->p.parent = y;
+    x->c.child.left = y;
+    setleft(y);
+  }
+
+  x->p.parent = yp;
+  y->p.parent = x;
+  if (ir) {
+    yp->p.root = x;
+    setnormal(y);
+    setroot(x);
+  } else {
+    if (rl) {
+      yp->c.child.left = x;
+      setleft(x);
+    } else {
+      yp->c.child.right = x;
+      setright(x);
+    }
+  }
+}
+
+void rb_delete_node(Rb_node n)
+{
+  Rb_node s, p, gp;
+  char ir;
+
+#ifdef DEBUG
+  if (isint(n)) {
+    fprintf(stderr, "Cannot delete an internal node: %p\n", n);
+    exit(1);
+  }
+  if (ishead(n)) {
+    fprintf(stderr, "Cannot delete the head of an rb_tree: %p\n", n);
+    exit(1);
+  }
+#else
+  assert(!isint(n));
+  assert(!ishead(n));
+#endif
+  delete_item(n); /* Delete it from the list */
+  p = n->p.parent;  /* The only node */
+  if (isroot(n)) {
+    p->p.root = p;
+    free(n);
+    return;
+  }
+  s = sibling(n);    /* The only node after deletion */
+  if (isroot(p)) {
+    s->p.parent = p->p.parent;
+    s->p.parent->p.root = s;
+    setroot(s);
+    free(p);
+    free(n);
+    return;
+  }
+  gp = p->p.parent;  /* Set parent to sibling */
+  s->p.parent = gp;
+  if (isleft(p)) {
+    gp->c.child.left = s;
+    setleft(s);
+  } else {
+    gp->c.child.right = s;
+    setright(s);
+  }
+  ir = isred(p);
+  free(p);
+  free(n);
+
+  if (isext(s)) {      /* Update proper rext and lext values */
+    p = lprev(s);
+    if (!ishead(p)) p->v.rext = s;
+    p = rprev(s);
+    if (!ishead(p)) p->k.lext = s;
+  } else if (isblack(s)) {
+#ifdef DEBUG
+    fprintf(stderr, "DELETION PROB -- sib is black, internal\n");
+    exit(1);
+#else
+    assert(1);
+#endif
+  } else {
+    p = lprev(s);
+    if (!ishead(p)) p->v.rext = s->c.child.left;
+    p = rprev(s);
+    if (!ishead(p)) p->k.lext = s->c.child.right;
+    setblack(s);
+    return;
+  }
+
+  if (ir) return;
+
+  /* Recolor */
+
+  n = s;
+  p = n->p.parent;
+  s = sibling(n);
+  while(isblack(p) && isblack(s) && isint(s) &&
+        isblack(s->c.child.left) && isblack(s->c.child.right)) {
+    setred(s);
+    n = p;
+    if (isroot(n)) return;
+    p = n->p.parent;
+    s = sibling(n);
+  }
+
+  if (isblack(p) && isred(s)) {  /* Rotation 2.3b */
+    single_rotate(p, isright(n));
+    setred(p);
+    setblack(s);
+    s = sibling(n);
+  }
+
+  { Rb_node x, z; char il;
+#ifdef DEBUG
+    if (isext(s)) {
+      fprintf(stderr, "DELETION ERROR: sibling not internal\n");
+      exit(1);
+    }
+#else
+    assert(!isext(s));
+#endif
+
+    il = isleft(n);
+    x = il ? s->c.child.left : s->c.child.right;
+    z = sibling(x);
+
+    if (isred(z)) {  /* Rotation 2.3f */
+      single_rotate(p, !il);
+      setblack(z);
+      if (isred(p)) setred(s); else setblack(s);
+      setblack(p);
+    } else if (isblack(x)) {   /* Recoloring only (2.3c) */
+#ifdef DEBUG
+      if (isred(s) || isblack(p)) {
+        fprintf(stderr, "DELETION ERROR: 2.3c not quite right\n");
+        exit(1);
+      }
+#else
+      assert(!isred(s) && !isblack(p));
+#endif
+      setblack(p);
+      setred(s);
+      return;
+    } else if (isred(p)) { /* 2.3d */
+      single_rotate(s, il);
+      single_rotate(p, !il);
+      setblack(x);
+      setred(s);
+      return;
+    } else {  /* 2.3e */
+      single_rotate(s, il);
+      single_rotate(p, !il);
+      setblack(x);
+      return;
+    }
+  }
+}
+
+
+#ifdef DEBUG
+void rb_print_tree(Rb_node t, int level)
+{
+  int i;
+  if (ishead(t) && t->p.parent == t) {
+    printf("tree %p is empty\n", t);
+  } else if (ishead(t)) {
+    printf("Head: %p.  Root = %p\n", t, t->p.root);
+    rb_print_tree(t->p.root, 0);
+  } else {
+    if (isext(t)) {
+      for (i = 0; i < level; i++) putchar(' ');
+      printf("Ext node %p: %c,%c: p=0x%x, k=%s\n",
+              t, isred(t)?'R':'B', isleft(t)?'l':'r', t->p.parent, t->k.key);
+    } else {
+      rb_print_tree(t->c.child.left, level+2);
+      rb_print_tree(t->c.child.right, level+2);
+      for (i = 0; i < level; i++) putchar(' ');
+      printf("Int node %p: %c,%c: l=0x%x, r=0x%x, p=0x%x, lr=(%s,%s)\n",
+              t, isred(t)?'R':'B', isleft(t)?'l':'r', t->c.child.left,
+              t->c.child.right,
+              t->p.parent, t->k.lext->k.key, t->v.rext->k.key);
+    }
+  }
+}
+#endif
+
+int rb_nblack(Rb_node n)
+{
+  int nb;
+#ifdef DEBUG
+  if (ishead(n) || isint(n)) {
+    fprintf(stderr, "ERROR: rb_nblack called on a non-external node %p\n",
+            n);
+    exit(1);
+  }
+#else
+  assert(!ishead(n));
+  assert(!isint(n));
+#endif
+  nb = 0;
+  while(!ishead(n)) {
+    if (isblack(n)) nb++;
+    n = n->p.parent;
+  }
+  return nb;
+}
+
+int rb_plength(Rb_node n)
+{
+  int pl;
+#ifdef DEBUG
+  if (ishead(n) || isint(n)) {
+    fprintf(stderr, "ERROR: rb_plength called on a non-external node %p\n",
+            n);
+    exit(1);
+  }
+#else
+  assert(!ishead(n));
+  assert(!isint(n));
+#endif
+  pl = 0;
+  while(!ishead(n)) {
+    pl++;
+    n = n->p.parent;
+  }
+  return pl;
+}
+
+void rb_free_tree(Rb_node n)
+{
+#ifdef DEBUG
+  if (!ishead(n)) {
+    fprintf(stderr, "ERROR: Rb_free_tree called on a non-head node\n");
+    exit(1);
+  }
+#else
+  assert(ishead(n));
+#endif
+
+  while(rb_first(n) != rb_nil(n)) {
+    rb_delete_node(rb_first(n));
+  }
+  free(n);
+}
+
+void *rb_val(Rb_node n)
+{
+  return n->v.val;
+}
+
+Rb_node rb_insert_a(Rb_node nd, void *val)
+{
+  return rb_insert_b(nd->c.list.flink, val);
+}
+
+Rb_node rb_insert(Rb_node tree, const void *key, rb_key_cmp_fn cmp, void *val)
+{
+  return rb_insert_b(rb_find_key(tree, key, cmp), val);
+}
diff --git a/rb.h b/rb.h
new file mode 100644
index 0000000..80f433c
--- /dev/null
+++ b/rb.h
@@ -0,0 +1,128 @@
+/*
+Generic C code for red-black trees.
+Copyright (C) 2000 James S. Plank
+
+This library is free software; you can redistribute it and/or
+modify it under the terms of the GNU Lesser General Public
+License as published by the Free Software Foundation; either
+version 2.1 of the License, or (at your option) any later version.
+
+This library is distributed in the hope that it will be useful,
+but WITHOUT ANY WARRANTY; without even the implied warranty of
+MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+Lesser General Public License for more details.
+
+You should have received a copy of the GNU Lesser General Public
+License along with this library; if not, write to the Free Software
+Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ */
+
+/* Revision 1.2.  Jim Plank */
+
+/* Original code by Jim Plank (plank@cs.utk.edu) */
+/* modified for THINK C 6.0 for Macintosh by Chris Bartley */
+
+/* Modified by Russell King to support embedded keys only */
+
+typedef struct {
+  unsigned red : 1 ;
+  unsigned internal : 1 ;
+  unsigned left : 1 ;
+  unsigned root : 1 ;
+  unsigned head : 1 ;
+} status;
+
+/* Main rb_node.  You only ever use the fields
+
+   c.list.flink
+   c.list.blink
+
+   k.key or k.ikey
+   v.val
+*/
+
+typedef int (*rb_key_cmp_fn)(const void *, const void *);
+
+typedef struct rb_node {
+  union {
+    struct {
+      struct rb_node *flink;
+      struct rb_node *blink;
+    } list;
+    struct {
+      struct rb_node *left;
+      struct rb_node *right;
+    } child;
+  } c;
+  union {
+    struct rb_node *parent;
+    struct rb_node *root;
+  } p;
+  status s;
+  union {
+    struct rb_node *lext;
+  } k;
+  union {
+    void *val;
+    struct rb_node *rext;
+  } v;
+} *Rb_node;
+
+
+extern Rb_node make_rb(void);   /* Creates a new rb-tree */
+
+
+
+/* Creates a node with key key and val val and inserts it into the tree.
+   rb_insert uses strcmp() as comparison funcion.  rb_inserti uses <>=,
+   rb_insertg uses func() */
+
+extern Rb_node rb_insert(Rb_node tree, const void *key,
+	rb_key_cmp_fn fn, void *data);
+
+
+/* returns an external node in t whose value is equal
+  k or whose value is the smallest value greater than k. */
+
+extern Rb_node rb_find_key(Rb_node root, const void *key,
+	rb_key_cmp_fn fn);
+
+
+/* Works just like the find_key versions only it returns whether or not
+   it found the key in the integer variable found */
+
+extern Rb_node rb_find_key_n(Rb_node root, const void *key,
+	rb_key_cmp_fn fn, int *found);
+
+
+/* Creates a node with key key and val val and inserts it into the
+   tree before/after node nd.  Does not check to ensure that you are
+   keeping the correct order */
+
+extern Rb_node rb_insert_b(Rb_node nd, void *val);
+extern Rb_node rb_insert_a(Rb_node nd, void *val);
+
+
+extern void rb_delete_node(Rb_node node);  /* Deletes and frees a node (but
+                                              not the key or val) */
+extern void rb_free_tree(Rb_node root);  /* Deletes and frees an entire tree */
+
+extern void *rb_val(Rb_node node);  /* Returns node->v.val -- this is to shut
+                                       lint up */
+
+extern int rb_nblack(Rb_node n); /* returns # of black nodes in path from
+                                    n to the root */
+int rb_plength(Rb_node n);       /* returns the # of nodes in path from
+				    n to the root */
+
+#define rb_first(n) (n->c.list.flink)
+#define rb_last(n) (n->c.list.blink)
+#define rb_next(n) (n->c.list.flink)
+#define rb_prev(n) (n->c.list.blink)
+#define rb_empty(t) (t->c.list.flink == t)
+#ifndef rb_nil
+#define rb_nil(t) (t)
+#endif
+
+#define rb_traverse(ptr, lst) \
+  for(ptr = rb_first(lst); ptr != rb_nil(lst); ptr = rb_next(ptr))