* binary search in ext4_ext_binsearch_idx()
@ 2010-04-08 3:26 minskey
0 siblings, 0 replies; only message in thread
From: minskey @ 2010-04-08 3:26 UTC (permalink / raw)
To: linux-ext4
in ext4_ext_binsearch_idx() routine, there is the following code:
while (l <= r) {
m = l + (r - l) / 2;
if (block < le32_to_cpu(m->ei_block))
r = m - 1;
else
l = m + 1;
}
path->p_idx = l - 1;
The code always runs logN iterations to get the expected extent,
if 3-way comparison is used, we can save some iterations when
(block == le32_to_cpu(m->ei_block)) at the first iteration.
some other routines, such as ext4_ext_binsearch() etc, use the
same algorithm (2-way comparison), Is there any special goal ?
thanks,
-minskey
^ permalink raw reply [flat|nested] only message in thread
only message in thread, other threads:[~2010-04-08 3:38 UTC | newest]
Thread overview: (only message) (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2010-04-08 3:26 binary search in ext4_ext_binsearch_idx() minskey
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).