diff options
| author | Andrew Morton <akpm@digeo.com> | 2003-02-14 20:24:25 -0800 |
|---|---|---|
| committer | Jens Axboe <axboe@suse.de> | 2003-02-14 20:24:25 -0800 |
| commit | fe2701f1c73e4b98cbe532a02a83e30892d4f4c2 (patch) | |
| tree | 84d4054339d13cf215599001328f205576bf6ee8 /lib | |
| parent | 8042ffff0ac1bd0fc39fe27a26fc272e115afd68 (diff) | |
[PATCH] Use table lookup for radix_tree_maxindex()
Patch from Szabolcs Berecz <szabi@mplayerhq.hu>
With the following patch maxindex is taken from an array instead of
recalculating it all the time.
Diffstat (limited to 'lib')
| -rw-r--r-- | lib/radix-tree.c | 28 |
1 files changed, 22 insertions, 6 deletions
diff --git a/lib/radix-tree.c b/lib/radix-tree.c index e1973ed79a7a..3d0183a4127d 100644 --- a/lib/radix-tree.c +++ b/lib/radix-tree.c @@ -46,6 +46,8 @@ struct radix_tree_path { #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,7 @@ out: */ 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; + return height_to_maxindex[height]; } /* @@ -401,6 +398,24 @@ radix_tree_node_ctor(void *node, kmem_cache_t *cachep, unsigned long flags) 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 < ARRAY_SIZE(height_to_maxindex); i++) + height_to_maxindex[i] = __maxindex(i); +} + void __init radix_tree_init(void) { radix_tree_node_cachep = kmem_cache_create("radix_tree_node", @@ -408,4 +423,5 @@ void __init radix_tree_init(void) 0, radix_tree_node_ctor, NULL); if (!radix_tree_node_cachep) panic ("Failed to create radix_tree_node cache\n"); + radix_tree_init_maxindex(); } |