linux-ext4.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
* 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).