simplify disksort, please review.

[Antoine Brodin]

Jeff Roberson <jroberson at chesapeake.net> wrote:
> http://www.chesapeake.net/~jroberson/disksort.diff
> 
> Our disksort algorithm used to be complicated by the BIO_ORDERED flag,
> which could cause us to make some exceptions in the sorting.  When the
> ordered support was removed we never simplified the algorithm.  The patch
> above gets rid of the switch point and associated logic.  It's now a
> simple hinted insertion sort with a one way scan.  Since it's a fairly
> central algorithm, I'd appreciate a review.

Sorry for the late review, but there's perhaps a problem:

If you have this situation:

queue:------------ 5 - 6 - 7
last_offset: 4     |
insert_point:------+

And you bioq_disksort a bio with an offset of 1:

queue:------------ 5 - 1 - 6 - 7
last_offset: 4     |
insert_point:------+

It looks weirdly sorted.

IIRC, the previous algorithm gave:

queue:------------ 5 - 6 - 7 - 1

Looking at revision 1.83, it looks like insert_point was useless, not
switch_point.

I can't test this change since disksort doesn't seem to be used by 
ata(4) anymore (is there any reason ?).

Cheers,

Antoine