Simplify Radix handling by storing tags in the lowest two bits

The radix tree stores a pointer and 2 tags per entry. These fit neatly
into a single machine word since pointers are aligned to 4 byte boundaries.
This makes the lowest bits always zero. Thus we can stuff the tags in there
eliminating the tags and simplifying the algorithms.

Step 2

The size of the radix tree is 2^RADIX_TREE_MAP_SHIFT plus a 32 bit count.
If this word is removed then the radix tree could have a size of 2^X which
is easier to manage

Index: linux-2.6.13-rc6-mm2/lib/radix-tree.c
===================================================================
--- linux-2.6.13-rc6-mm2.orig/lib/radix-tree.c	2005-08-24 16:57:42.000000000 -0700
+++ linux-2.6.13-rc6-mm2/lib/radix-tree.c	2005-08-25 17:44:51.000000000 -0700
@@ -41,13 +41,9 @@
 #define RADIX_TREE_MAP_SIZE	(1UL << RADIX_TREE_MAP_SHIFT)
 #define RADIX_TREE_MAP_MASK	(RADIX_TREE_MAP_SIZE-1)
 
-#define RADIX_TREE_TAG_LONGS	\
-	((RADIX_TREE_MAP_SIZE + BITS_PER_LONG - 1) / BITS_PER_LONG)
-
 struct radix_tree_node {
 	unsigned int	count;
-	void		*slots[RADIX_TREE_MAP_SIZE];
-	unsigned long	tags[RADIX_TREE_TAGS][RADIX_TREE_TAG_LONGS];
+	unsigned long	slots[RADIX_TREE_MAP_SIZE];
 };
 
 struct radix_tree_path {
@@ -137,18 +133,33 @@ EXPORT_SYMBOL(radix_tree_preload);
 
 static inline void tag_set(struct radix_tree_node *node, int tag, int offset)
 {
-	if (!test_bit(offset, &node->tags[tag][0]))
-		__set_bit(offset, &node->tags[tag][0]);
+	if (!test_bit(1 << tag, &node->slots[offset]))
+		__set_bit(1 << tag, &node->slots[offset]);
 }
 
 static inline void tag_clear(struct radix_tree_node *node, int tag, int offset)
 {
-	__clear_bit(offset, &node->tags[tag][0]);
+	__clear_bit(1 << tag, &node->slots[offset]);
 }
 
 static inline int tag_get(struct radix_tree_node *node, int tag, int offset)
 {
-	return test_bit(offset, &node->tags[tag][0]);
+	return ((node->slots[offset] >> tag) & 1)
+}
+
+static inline void *slot_get(struct radix_tree_node *node, int offset)
+{
+	return (void *)(node->slots[offset] & ~0x3);
+}
+
+static inline void slot_set(struct radix_tree_node *node, int tag, int offset, void *s)
+{
+	node->slot[offset] = 1 << tag + (unsigned long)s;
+}
+
+static inline unsigned int slot_get_tags(struct radix_tree_node *node, int tags, int offset)
+{
+	return node->slot[offset] & 0x3;
 }
 
 /*
@@ -167,7 +178,7 @@ static int radix_tree_extend(struct radi
 {
 	struct radix_tree_node *node;
 	unsigned int height;
-	char tags[RADIX_TREE_TAGS];
+	int tags;
 	int tag;
 
 	/* Figure out what the height should be.  */
@@ -184,16 +195,10 @@ static int radix_tree_extend(struct radi
 	 * Prepare the tag status of the top-level node for propagation
 	 * into the newly-pushed top-level node(s)
 	 */
-	for (tag = 0; tag < RADIX_TREE_TAGS; tag++) {
-		int idx;
+	tags = 0;
 
-		tags[tag] = 0;
-		for (idx = 0; idx < RADIX_TREE_TAG_LONGS; idx++) {
-			if (root->rnode->tags[tag][idx]) {
-				tags[tag] = 1;
-				break;
-			}
-		}
+	for (idx = 0; idx < RADIX_TREE_MAP_SIZE; idx++)
+		tags |= slot_get_flags(node, idx);
 	}
 
 	do {
@@ -201,13 +206,8 @@ static int radix_tree_extend(struct radi
 			return -ENOMEM;
 
 		/* Increase the height.  */
-		node->slots[0] = root->rnode;
-
 		/* Propagate the aggregated tag info into the new root */
-		for (tag = 0; tag < RADIX_TREE_TAGS; tag++) {
-			if (tags[tag])
-				tag_set(node, tag, 0);
-		}
+		slot_set(node, tags, 0, root->rnode);
 
 		node->count = 1;
 		root->rnode = node;
@@ -247,7 +247,7 @@ int radix_tree_insert(struct radix_tree_
 
 	offset = 0;			/* uninitialised var warning */
 	while (height > 0) {
-		if (*slot == NULL) {
+		if (!*slot) {
 			/* Have to add a child node.  */
 			if (!(tmp = radix_tree_node_alloc(root)))
 				return -ENOMEM;
@@ -258,7 +258,7 @@ int radix_tree_insert(struct radix_tree_
 
 		/* Go a level down */
 		offset = (index >> shift) & RADIX_TREE_MAP_MASK;
-		node = *slot;
+		node = slot_get(slot);
 		slot = (struct radix_tree_node **)(node->slots + offset);
 		shift -= RADIX_TREE_MAP_SHIFT;
 		height--;
@@ -272,7 +272,7 @@ int radix_tree_insert(struct radix_tree_
 		BUG_ON(tag_get(node, 1, offset));
 	}
 
-	*slot = item;
+	slot_set(slot, item, 0);
 	return 0;
 }
 EXPORT_SYMBOL(radix_tree_insert);
@@ -295,8 +295,8 @@ static inline void **__lookup_slot(struc
 			return NULL;
 
 		slot = (struct radix_tree_node **)
-			((*slot)->slots +
-				((index >> shift) & RADIX_TREE_MAP_MASK));
+			slot_get(((*slot)->slots +
+				((index >> shift) & RADIX_TREE_MAP_MASK)));
 		shift -= RADIX_TREE_MAP_SHIFT;
 		height--;
 	}
@@ -364,7 +364,7 @@ void *radix_tree_tag_set(struct radix_tr
 
 		offset = (index >> shift) & RADIX_TREE_MAP_MASK;
 		tag_set(*slot, tag, offset);
-		slot = (struct radix_tree_node **)((*slot)->slots + offset);
+		slot = (struct radix_tree_node **)slot_get(((*slot)->slots + offset));
 		BUG_ON(*slot == NULL);
 		shift -= RADIX_TREE_MAP_SHIFT;
 		height--;
@@ -412,7 +412,7 @@ void *radix_tree_tag_clear(struct radix_
 		pathp[1].offset = offset;
 		pathp[1].node = *pathp[0].slot;
 		pathp[1].slot = (struct radix_tree_node **)
-				(pathp[1].node->slots + offset);
+				slot_get((pathp[1].node->slots + offset));
 		pathp++;
 		shift -= RADIX_TREE_MAP_SHIFT;
 		height--;