lkml.org 
[lkml]   [2003]   [Feb]   [14]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
Patch in this message
/
Date
From
Subject[PATCH][RFC] radix-tree.c

With the following patch maxindex is taken from an array instead of
recalculating it all the time.

Comments?

Bye,
Szabi


--- linux-2.5.60/lib/radix-tree.c.orig Sat Jan 25 19:28:22 2003
+++ linux-2.5.60/lib/radix-tree.c Fri Feb 14 22:16:34 2003
@@ -46,6 +46,8 @@
#define RADIX_TREE_INDEX_BITS (8 /* CHAR_BIT */ * sizeof(unsigned long))
#define RADIX_TREE_MAX_PATH (RADIX_TREE_INDEX_BITS/RADIX_TREE_MAP_SHIFT + 2)

+static unsigned long height_to_maxindex[RADIX_TREE_MAX_PATH];
+
/*
* Radix tree node cache.
*/
@@ -126,12 +128,9 @@
*/
static inline unsigned long radix_tree_maxindex(unsigned int height)
{
- unsigned int tmp = height * RADIX_TREE_MAP_SHIFT;
- unsigned long index = (~0UL >> (RADIX_TREE_INDEX_BITS - tmp - 1)) >> 1;
-
- if (tmp >= RADIX_TREE_INDEX_BITS)
- index = ~0UL;
- return index;
+ if (unlikely(height >= RADIX_TREE_MAX_PATH))
+ return ~0UL;
+ return height_to_maxindex[height];
}

/*
@@ -402,6 +401,24 @@
memset(node, 0, sizeof(struct radix_tree_node));
}

+static __init unsigned long __maxindex(unsigned int height)
+{
+ unsigned int tmp = height * RADIX_TREE_MAP_SHIFT;
+ unsigned long index = (~0UL >> (RADIX_TREE_INDEX_BITS - tmp - 1)) >> 1;
+
+ if (tmp >= RADIX_TREE_INDEX_BITS)
+ index = ~0UL;
+ return index;
+}
+
+static __init void radix_tree_init_maxindex(void)
+{
+ unsigned int i;
+
+ for (i = 0; i < RADIX_TREE_MAX_PATH; i++)
+ height_to_maxindex[i] = __maxindex(i);
+}
+
void __init radix_tree_init(void)
{
radix_tree_node_cachep = kmem_cache_create("radix_tree_node",
@@ -409,4 +426,5 @@
0, radix_tree_node_ctor, NULL);
if (!radix_tree_node_cachep)
panic ("Failed to create radix_tree_node cache\n");
+ radix_tree_init_maxindex();
}
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

\
 
 \ /
  Last update: 2005-03-22 13:33    [W:0.095 / U:0.372 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site