summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDimitris Papastamos <dp@opensource.wolfsonmicro.com>2011-10-03 10:50:14 +0100
committerMark Brown <broonie@opensource.wolfsonmicro.com>2011-10-03 11:50:53 +0100
commitc08604b8ae72b4fa1843a76fc7b403ddec49f8f4 (patch)
tree64de79de1019dbc3fd7862693a245bb29bf25e4b
parentac77a765cb6e3b5aa41c186ad9f37db7fdad7dbe (diff)
downloadlinux-c08604b8ae72b4fa1843a76fc7b403ddec49f8f4.tar.bz2
regmap: Optimize the lookup path to use binary search
Since there are more lookups than insertions in a typical scenario, optimize the linear search into a binary search. For this to work, we need to keep reg_defaults sorted upon insertions, for now be lazy and use sort(). Signed-off-by: Dimitris Papastamos <dp@opensource.wolfsonmicro.com> Signed-off-by: Mark Brown <broonie@opensource.wolfsonmicro.com>
-rw-r--r--drivers/base/regmap/regcache.c29
1 files changed, 24 insertions, 5 deletions
diff --git a/drivers/base/regmap/regcache.c b/drivers/base/regmap/regcache.c
index 2d55b261f1c5..e1846eb2f171 100644
--- a/drivers/base/regmap/regcache.c
+++ b/drivers/base/regmap/regcache.c
@@ -12,6 +12,7 @@
#include <linux/slab.h>
#include <trace/events/regmap.h>
+#include <linux/sort.h>
#include "internal.h"
@@ -356,14 +357,30 @@ unsigned int regcache_get_val(const void *base, unsigned int idx,
int regcache_lookup_reg(struct regmap *map, unsigned int reg)
{
- unsigned int i;
-
- for (i = 0; i < map->num_reg_defaults; i++)
- if (map->reg_defaults[i].reg == reg)
- return i;
+ unsigned int min, max, index;
+
+ min = 0;
+ max = map->num_reg_defaults - 1;
+ do {
+ index = (min + max) / 2;
+ if (map->reg_defaults[index].reg == reg)
+ return index;
+ if (map->reg_defaults[index].reg < reg)
+ min = index + 1;
+ else
+ max = index;
+ } while (min <= max);
return -1;
}
+static int regcache_insert_cmp(const void *a, const void *b)
+{
+ const struct reg_default *_a = a;
+ const struct reg_default *_b = b;
+
+ return _a->reg - _b->reg;
+}
+
int regcache_insert_reg(struct regmap *map, unsigned int reg,
unsigned int val)
{
@@ -378,5 +395,7 @@ int regcache_insert_reg(struct regmap *map, unsigned int reg,
map->num_reg_defaults++;
map->reg_defaults[map->num_reg_defaults - 1].reg = reg;
map->reg_defaults[map->num_reg_defaults - 1].def = val;
+ sort(map->reg_defaults, map->num_reg_defaults,
+ sizeof(struct reg_default), regcache_insert_cmp, NULL);
return 0;
}