[PATCH] radix-tree: Remove unnecessary indirections and clean up code
I was thinking about Nick's lockless pagecache patches and had a look at
radix-tree.c. At first I had some trouble with some of the way things
were done but after getting used to the style it became clear. However,
I'd like to have these things fixed so that others do not get tripped up
too.
---
[PATCH] radix-tree: Remove unnecessary indirections and clean up code
- There is frequent use of indirections in the radix code. This patch
removes those indirections, makes the code more readable and allows
the compilers to generate better code.
- Removing indirections allows the removal of several casts.
- Removing indirections allows the reduction of the radix_tree_path
size from 3 to 2 words.
- Use pathp-> consistently.
- Remove unnecessary tmp variable in radix_tree_insert
- Separate the upper layer processing from the lowest layer in __lookup()
in order to make it easier to understand what is going on and allow
compilers to generate better code for the loop.
Signed-off-by: Christoph Lameter <[EMAIL PROTECTED]>
Index: linux-2.6.13-rc7/lib/radix-tree.c
===
--- linux-2.6.13-rc7.orig/lib/radix-tree.c 2005-08-23 20:39:14.0
-0700
+++ linux-2.6.13-rc7/lib/radix-tree.c 2005-08-26 17:10:54.0 -0700
@@ -1,6 +1,7 @@
/*
* Copyright (C) 2001 Momchil Velikov
* Portions Copyright (C) 2001 Christoph Hellwig
+ * Copyright (C) 2005 SGI, Christoph Lameter <[EMAIL PROTECTED]>
*
* This program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public License as
@@ -51,7 +52,7 @@ struct radix_tree_node {
};
struct radix_tree_path {
- struct radix_tree_node *node, **slot;
+ struct radix_tree_node *node;
int offset;
};
@@ -227,7 +228,7 @@ out:
int radix_tree_insert(struct radix_tree_root *root,
unsigned long index, void *item)
{
- struct radix_tree_node *node = NULL, *tmp, **slot;
+ struct radix_tree_node *node = NULL, *slot;
unsigned int height, shift;
int offset;
int error;
@@ -240,38 +241,42 @@ int radix_tree_insert(struct radix_tree_
return error;
}
- slot = >rnode;
+ slot = root->rnode;
height = root->height;
shift = (height-1) * RADIX_TREE_MAP_SHIFT;
offset = 0; /* uninitialised var warning */
while (height > 0) {
- if (*slot == NULL) {
+ if (slot == NULL) {
/* Have to add a child node. */
- if (!(tmp = radix_tree_node_alloc(root)))
+ if (!(slot = radix_tree_node_alloc(root)))
return -ENOMEM;
- *slot = tmp;
- if (node)
+ if (node) {
+ node->slots[offset] = slot;
node->count++;
+ } else
+ root->rnode = slot;
}
/* Go a level down */
offset = (index >> shift) & RADIX_TREE_MAP_MASK;
- node = *slot;
- slot = (struct radix_tree_node **)(node->slots + offset);
+ node = slot;
+ slot = node->slots[offset];
shift -= RADIX_TREE_MAP_SHIFT;
height--;
}
- if (*slot != NULL)
+ if (slot != NULL)
return -EEXIST;
+
if (node) {
node->count++;
+ node->slots[offset] = item;
BUG_ON(tag_get(node, 0, offset));
BUG_ON(tag_get(node, 1, offset));
- }
+ } else
+ root->rnode = item;
- *slot = item;
return 0;
}
EXPORT_SYMBOL(radix_tree_insert);
@@ -286,27 +291,25 @@ EXPORT_SYMBOL(radix_tree_insert);
void *radix_tree_lookup(struct radix_tree_root *root, unsigned long index)
{
unsigned int height, shift;
- struct radix_tree_node **slot;
+ struct radix_tree_node *slot;
height = root->height;
if (index > radix_tree_maxindex(height))
return NULL;
shift = (height-1) * RADIX_TREE_MAP_SHIFT;
- slot = >rnode;
+ slot = root->rnode;
while (height > 0) {
- if (*slot == NULL)
+ if (slot == NULL)
return NULL;
- slot = (struct radix_tree_node **)
- ((*slot)->slots +
- ((index >> shift) & RADIX_TREE_MAP_MASK));
+ slot = slot->slots[(index >> shift) & RADIX_TREE_MAP_MASK];
shift -= RADIX_TREE_MAP_SHIFT;
height--;
}
- return *slot;
+ return slot;
[PATCH] radix-tree: Remove unnecessary indirections and clean up code
I was thinking about Nick's lockless pagecache patches and had a look at
radix-tree.c. At first I had some trouble with some of the way things
were done but after getting used to the style it became clear. However,
I'd like to have these things fixed so that others do not get tripped up
too.
---
[PATCH] radix-tree: Remove unnecessary indirections and clean up code
- There is frequent use of indirections in the radix code. This patch
removes those indirections, makes the code more readable and allows
the compilers to generate better code.
- Removing indirections allows the removal of several casts.
- Removing indirections allows the reduction of the radix_tree_path
size from 3 to 2 words.
- Use pathp- consistently.
- Remove unnecessary tmp variable in radix_tree_insert
- Separate the upper layer processing from the lowest layer in __lookup()
in order to make it easier to understand what is going on and allow
compilers to generate better code for the loop.
Signed-off-by: Christoph Lameter [EMAIL PROTECTED]
Index: linux-2.6.13-rc7/lib/radix-tree.c
===
--- linux-2.6.13-rc7.orig/lib/radix-tree.c 2005-08-23 20:39:14.0
-0700
+++ linux-2.6.13-rc7/lib/radix-tree.c 2005-08-26 17:10:54.0 -0700
@@ -1,6 +1,7 @@
/*
* Copyright (C) 2001 Momchil Velikov
* Portions Copyright (C) 2001 Christoph Hellwig
+ * Copyright (C) 2005 SGI, Christoph Lameter [EMAIL PROTECTED]
*
* This program is free software; you can redistribute it and/or
* modify it under the terms of the GNU General Public License as
@@ -51,7 +52,7 @@ struct radix_tree_node {
};
struct radix_tree_path {
- struct radix_tree_node *node, **slot;
+ struct radix_tree_node *node;
int offset;
};
@@ -227,7 +228,7 @@ out:
int radix_tree_insert(struct radix_tree_root *root,
unsigned long index, void *item)
{
- struct radix_tree_node *node = NULL, *tmp, **slot;
+ struct radix_tree_node *node = NULL, *slot;
unsigned int height, shift;
int offset;
int error;
@@ -240,38 +241,42 @@ int radix_tree_insert(struct radix_tree_
return error;
}
- slot = root-rnode;
+ slot = root-rnode;
height = root-height;
shift = (height-1) * RADIX_TREE_MAP_SHIFT;
offset = 0; /* uninitialised var warning */
while (height 0) {
- if (*slot == NULL) {
+ if (slot == NULL) {
/* Have to add a child node. */
- if (!(tmp = radix_tree_node_alloc(root)))
+ if (!(slot = radix_tree_node_alloc(root)))
return -ENOMEM;
- *slot = tmp;
- if (node)
+ if (node) {
+ node-slots[offset] = slot;
node-count++;
+ } else
+ root-rnode = slot;
}
/* Go a level down */
offset = (index shift) RADIX_TREE_MAP_MASK;
- node = *slot;
- slot = (struct radix_tree_node **)(node-slots + offset);
+ node = slot;
+ slot = node-slots[offset];
shift -= RADIX_TREE_MAP_SHIFT;
height--;
}
- if (*slot != NULL)
+ if (slot != NULL)
return -EEXIST;
+
if (node) {
node-count++;
+ node-slots[offset] = item;
BUG_ON(tag_get(node, 0, offset));
BUG_ON(tag_get(node, 1, offset));
- }
+ } else
+ root-rnode = item;
- *slot = item;
return 0;
}
EXPORT_SYMBOL(radix_tree_insert);
@@ -286,27 +291,25 @@ EXPORT_SYMBOL(radix_tree_insert);
void *radix_tree_lookup(struct radix_tree_root *root, unsigned long index)
{
unsigned int height, shift;
- struct radix_tree_node **slot;
+ struct radix_tree_node *slot;
height = root-height;
if (index radix_tree_maxindex(height))
return NULL;
shift = (height-1) * RADIX_TREE_MAP_SHIFT;
- slot = root-rnode;
+ slot = root-rnode;
while (height 0) {
- if (*slot == NULL)
+ if (slot == NULL)
return NULL;
- slot = (struct radix_tree_node **)
- ((*slot)-slots +
- ((index shift) RADIX_TREE_MAP_MASK));
+ slot = slot-slots[(index shift) RADIX_TREE_MAP_MASK];
shift -= RADIX_TREE_MAP_SHIFT;
height--;
}
- return *slot;
+ return slot;
}
EXPORT_SYMBOL(radix_tree_lookup);
@@ -326,27 +329,27 @@ void *radix_tree_tag_set(struct radix_tr
unsigned long
