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

1 files changed, 128 insertions, 0 deletions

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))