From aece3d1f40879759f641dfbfdbb9e2593adeb43c Mon Sep 17 00:00:00 2001 From: Sandeep K Sinha Date: Tue, 16 Jun 2009 16:57:08 +1000 Subject: md: Binary search in linear raid Replace the linear search with binary search in which_dev. Signed-off-by: Sandeep K Sinha Signed-off-by: NeilBrown --- drivers/md/linear.c | 22 +++++++++++++++++----- 1 file changed, 17 insertions(+), 5 deletions(-) (limited to 'drivers/md') diff --git a/drivers/md/linear.c b/drivers/md/linear.c index 529a3d37e3fe..9b02a73fbc6b 100644 --- a/drivers/md/linear.c +++ b/drivers/md/linear.c @@ -27,14 +27,26 @@ */ static inline dev_info_t *which_dev(mddev_t *mddev, sector_t sector) { - dev_info_t *hash; + int lo, mid, hi; linear_conf_t *conf = mddev->private; - hash = conf->disks; + lo = 0; + hi = mddev->raid_disks - 1; - while (sector >= hash->end_sector) - hash++; - return hash; + /* + * Binary Search + */ + + while (hi > lo) { + + mid = (hi + lo) / 2; + if (sector < conf->disks[mid].end_sector) + hi = mid; + else + lo = mid + 1; + } + + return conf->disks + lo; } /** -- cgit v1.2.3