summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--drivers/ras/cec.c34
1 files changed, 20 insertions, 14 deletions
diff --git a/drivers/ras/cec.c b/drivers/ras/cec.c
index 88e4f3ff0cb8..dbfe3e61d2c2 100644
--- a/drivers/ras/cec.c
+++ b/drivers/ras/cec.c
@@ -183,32 +183,38 @@ static void cec_timer_fn(struct timer_list *unused)
*/
static int __find_elem(struct ce_array *ca, u64 pfn, unsigned int *to)
{
+ int min = 0, max = ca->n - 1;
u64 this_pfn;
- int min = 0, max = ca->n;
- while (min < max) {
- int tmp = (max + min) >> 1;
+ while (min <= max) {
+ int i = (min + max) >> 1;
- this_pfn = PFN(ca->array[tmp]);
+ this_pfn = PFN(ca->array[i]);
if (this_pfn < pfn)
- min = tmp + 1;
+ min = i + 1;
else if (this_pfn > pfn)
- max = tmp;
- else {
- min = tmp;
- break;
+ max = i - 1;
+ else if (this_pfn == pfn) {
+ if (to)
+ *to = i;
+
+ return i;
}
}
+ /*
+ * When the loop terminates without finding @pfn, min has the index of
+ * the element slot where the new @pfn should be inserted. The loop
+ * terminates when min > max, which means the min index points to the
+ * bigger element while the max index to the smaller element, in-between
+ * which the new @pfn belongs to.
+ *
+ * For more details, see exercise 1, Section 6.2.1 in TAOCP, vol. 3.
+ */
if (to)
*to = min;
- this_pfn = PFN(ca->array[min]);
-
- if (this_pfn == pfn)
- return min;
-
return -ENOKEY;
}