/* ufs_disksubr.c 4.3 81/03/09 */
* Seek sort for disks. We depend on the driver
* which calls us using b_resid as the current cylinder number.
* The argument dp structure holds a b_actf activity chain pointer
* on which we keep two queues, sorted in ascending cylinder order.
* The first queue holds those requests which are positioned after
* the current cylinder (in the first request); the second holds
* requests which came in after their cylinder number was passed.
* Thus we implement a one way scan, retracting after reaching the
* end of the drive to the first request on the second queue,
* at which time it becomes the first queue.
* A one-way scan is natural because of the way UNIX read-ahead
register struct buf
*dp
, *bp
;
* If nothing on the activity queue, then
* we become the only thing.
* If we lie after the first (currently active)
* request, then we must locate the second request list
* and add ourselves to it.
if (bp
->b_cylin
< ap
->b_cylin
) {
* Check for an ``inversion'' in the
* normally ascending cylinder numbers,
* indicating the start of the second request list.
if (ap
->av_forw
->b_cylin
< ap
->b_cylin
) {
* Search the second request list
* for the first request at a larger
* cylinder number. We go before that;
* if there is no such request, we go at end.
if (bp
->b_cylin
< ap
->av_forw
->b_cylin
)
goto insert
; /* after last */
* No inversions... we will go after the last, and
* be the first request in the second request list.
* Request is at/after the current request...
* sort in the first request list.
* We want to go after the current request
* if there is an inversion after it (i.e. it is
* the end of the first request list), or if
* the next request is a larger cylinder than our request.
if (ap
->av_forw
->b_cylin
< ap
->b_cylin
||
bp
->b_cylin
< ap
->av_forw
->b_cylin
)
* Neither a second list nor a larger
* request... we go at the end of the first list,
* which is the same as the end of the whole schebang.
bp
->av_forw
= ap
->av_forw
;