The patch regmap: rbtree: When adding a reg do a bsearch for target node
has been applied to the regmap tree at git://git.kernel.org/pub/scm/linux/kernel/git/broonie/regmap.git All being well this means that it will be integrated into the linux-next tree (usually sometime in the next 24 hours) and sent to Linus during the next merge window (or sooner if it is a bug fix), however if problems are discovered then the patch may be dropped or reverted. You may get further e-mails resulting from automated or manual testing and review of the tree, please engage with people reporting problems and send followup patches addressing any issues that are reported if needed. If any updates are required or you are submitting further changes they should be sent as incremental updates against current git, existing patches will not be replaced. Please add any relevant lists and maintainers to the CCs when replying to this mail. Thanks, Mark >From c164cfba7c6569d01a83cb6fdde0cb1cadf72cf8 Mon Sep 17 00:00:00 2001 From: Nikesh Oswal <[email protected]> Date: Wed, 21 Oct 2015 14:16:14 +0100 Subject: [PATCH] regmap: rbtree: When adding a reg do a bsearch for target node A binary search is much more efficient rather than iterating over the rbtree in ascending order which the current code is doing. During initialisation the reg defaults are written to the cache in a large chunk and these are always sorted in the ascending order so for this situation ideally we should have iterated the rbtree in descending order. But at runtime the drivers may write into the cache in any random order so this patch selects to use a bsearch to give an optimal runtime performance and also at initialisation time when reg defaults are written the performance of binary search would be much better than iterating in ascending order which the current code was doing. Signed-off-by: Nikesh Oswal <[email protected]> Signed-off-by: Mark Brown <[email protected]> --- drivers/base/regmap/regcache-rbtree.c | 9 +++++++-- 1 file changed, 7 insertions(+), 2 deletions(-) diff --git a/drivers/base/regmap/regcache-rbtree.c b/drivers/base/regmap/regcache-rbtree.c index 56486d9..353f602 100644 --- a/drivers/base/regmap/regcache-rbtree.c +++ b/drivers/base/regmap/regcache-rbtree.c @@ -413,8 +413,8 @@ static int regcache_rbtree_write(struct regmap *map, unsigned int reg, max = reg + max_dist; /* look for an adjacent register to the one we are about to add */ - for (node = rb_first(&rbtree_ctx->root); node; - node = rb_next(node)) { + node = rbtree_ctx->root.rb_node; + while (node) { rbnode_tmp = rb_entry(node, struct regcache_rbtree_node, node); @@ -425,6 +425,11 @@ static int regcache_rbtree_write(struct regmap *map, unsigned int reg, new_base_reg = min(reg, base_reg); new_top_reg = max(reg, top_reg); } else { + if (max < base_reg) + node = node->rb_left; + else + node = node->rb_right; + continue; } -- 2.6.1 -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/

