# This removes the much-hated ghash.h.  physmem now makes do with an rbtree
# instead.
Index: um/arch/um/kernel/physmem.c
===================================================================
--- um.orig/arch/um/kernel/physmem.c	2004-09-14 01:41:21.000000000 -0400
+++ um/arch/um/kernel/physmem.c	2004-09-16 11:14:37.000000000 -0400
@@ -4,7 +4,7 @@
  */
 
 #include "linux/mm.h"
-#include "linux/ghash.h"
+#include "linux/rbtree.h"
 #include "linux/slab.h"
 #include "linux/vmalloc.h"
 #include "linux/bootmem.h"
@@ -19,14 +19,8 @@
 #include "kern.h"
 #include "init.h"
 
-#define PHYS_HASHSIZE (8192)
-
-struct phys_desc;
-
-DEF_HASH_STRUCTS(virtmem, PHYS_HASHSIZE, struct phys_desc);
-
 struct phys_desc {
-	struct virtmem_ptrs virt_ptrs;
+	struct rb_node_s rb;
 	int fd;
 	__u64 offset;
 	void *virt;
@@ -34,21 +28,48 @@
 	struct list_head list;
 };
 
-struct virtmem_table virtmem_hash;
+static struct rb_root_s phys_mappings = RB_ROOT;
 
-static int virt_cmp(void *virt1, void *virt2)
+static struct rb_node_s **find_rb(void *virt)
 {
-	return(virt1 != virt2);
+	struct rb_node_s **n = &phys_mappings.rb_node;
+	struct phys_desc *d;
+
+	while(*n != NULL){
+		d = rb_entry(n, struct phys_desc, rb);
+		if(d->virt == virt)
+			return(n);
+
+		if(d->virt > virt)
+			n = &(*n)->rb_left;
+		else
+			n = &(*n)->rb_right;
+	}
+
+	return(n);
 }
 
-static int virt_hash(void *virt)
+static struct phys_desc *find_phys_mapping(void *virt)
 {
-	unsigned long addr = ((unsigned long) virt) >> PAGE_SHIFT;
-	return(addr % PHYS_HASHSIZE);
+	struct rb_node_s **n = find_rb(virt);
+
+	if(*n == NULL)
+		return(NULL);
+
+	return(rb_entry(n, struct phys_desc, rb));
 }
 
-DEF_HASH(static, virtmem, struct phys_desc, virt_ptrs, void *, virt, virt_cmp, 
-	 virt_hash);
+static void insert_phys_mapping(struct phys_desc *desc)
+{
+	struct rb_node_s **n = find_rb(desc->virt);
+
+	if(*n != NULL)
+		panic("Physical remapping for %p already present", 
+		      desc->virt);
+
+	rb_link_node(&desc->rb, (*n)->rb_parent, n);
+	rb_insert_color(&desc->rb, &phys_mappings);
+}
 
 LIST_HEAD(descriptor_mappings);
 
@@ -101,7 +122,7 @@
 	int err;
 
 	phys = __pa(virt);
-	desc = find_virtmem_hash(&virtmem_hash, (void *) virt);
+	desc = find_phys_mapping(virt);
 	if(desc != NULL){
 		if((virt != desc->virt) || (fd != desc->fd) || 
 		   (offset != desc->offset))
@@ -119,13 +140,12 @@
 		goto out;
 
 	*desc = ((struct phys_desc) 
-		{ .virt_ptrs =	{ NULL, NULL },
-		  .fd =		fd,
+		{ .fd =			fd,
 		  .offset =		offset,
 		  .virt =		virt,
 		  .phys =		__pa(virt),
 		  .list = 		LIST_HEAD_INIT(desc->list) });
-	insert_virtmem_hash(&virtmem_hash, desc);
+	insert_phys_mapping(desc);
 
 	list_add(&desc->list, &fd_maps->pages);
 
@@ -134,7 +154,7 @@
 	if(!err)
 		goto out;
 
-	remove_virtmem_hash(&virtmem_hash, desc);
+	rb_erase(&desc->rb, &phys_mappings);
 	kfree(desc);
  out:
 	return(err);
@@ -147,7 +167,7 @@
 	void *virt = desc->virt;
 	int err;
 
-	remove_virtmem_hash(&virtmem_hash, desc);
+	rb_erase(&desc->rb, &phys_mappings);
 	list_del(&desc->list);
 	kfree(desc);
 
@@ -162,7 +182,7 @@
 	struct phys_desc *desc;
 
 	virt = (void *) ((unsigned long) virt & PAGE_MASK);
-	desc = find_virtmem_hash(&virtmem_hash, virt);
+	desc = find_phys_mapping(virt);
 	if(desc == NULL)
 		return(0);
 
@@ -222,12 +242,12 @@
 {
 	struct phys_desc *desc;
 
-	desc = find_virtmem_hash(&virtmem_hash, (void *) virt);
+	desc = find_phys_mapping((void *) virt);
 	if(desc == NULL)
 		return(0);
 	if(offset != desc->offset)
 		printk("offset mismatch\n");
-	return(find_virtmem_hash(&virtmem_hash, (void *) virt) != NULL);
+	return(find_phys_mapping((void *) virt) != NULL);
 }
 
 /* Changed during early boot */
@@ -360,8 +380,7 @@
 
 int phys_mapping(unsigned long phys, __u64 *offset_out)
 {
-	struct phys_desc *desc = find_virtmem_hash(&virtmem_hash, 
-						   __va(phys & PAGE_MASK));
+	struct phys_desc *desc = find_phys_mapping(__va(phys & PAGE_MASK));
 	int fd = -1;
 
 	if(desc != NULL){