Return to dsort.c CVS log

Up to [CSRG BSD Unix] / 41BSD / 4.0.upgrade / sys / dev

Annotation of 41BSD/4.0.upgrade/sys/dev/dsort.c, revision 1.1.1.1

1.1       root        1: /*     dsort.c 4.3     81/03/08        */
                      2: 
                      3: /*
                      4:  * Seek sort for disks.  We depend on the driver
                      5:  * which calls us using b_resid as the current cylinder number.
                      6:  *
                      7:  * The argument dp structure holds a b_actf activity chain pointer
                      8:  * on which we keep two queues, sorted in ascending cylinder order.
                      9:  * The first queue holds those requests which are positioned after
                     10:  * the current cylinder (in the first request); the second holds
                     11:  * requests which came in after their cylinder number was passed.
                     12:  * Thus we implement a one way scan, retracting after reaching the
                     13:  * end of the drive to the first request on the second queue,
                     14:  * at which time it becomes the first queue.
                     15:  *
                     16:  * A one-way scan is natural because of the way UNIX read-ahead
                     17:  * blocks are allocated.
                     18:  */
                     19: 
                     20: #include "../h/param.h"
                     21: #include "../h/systm.h"
                     22: #include "../h/buf.h"
                     23: 
                     24: #define        b_cylin b_resid
                     25: 
                     26: disksort(dp, bp)
                     27:        register struct buf *dp, *bp;
                     28: {
                     29:        register struct buf *ap;
                     30: 
                     31:        /*
                     32:         * If nothing on the activity queue, then
                     33:         * we become the only thing.
                     34:         */
                     35:        ap = dp->b_actf;
                     36:        if(ap == NULL) {
                     37:                dp->b_actf = bp;
                     38:                dp->b_actl = bp;
                     39:                bp->av_forw = NULL;
                     40:                return;
                     41:        }
                     42:        /*
                     43:         * If we lie after the first (currently active)
                     44:         * request, then we must locate the second request list
                     45:         * and add ourselves to it.
                     46:         */
                     47:        if (bp->b_cylin < ap->b_cylin) {
                     48:                while (ap->av_forw) {
                     49:                        /*
                     50:                         * Check for an ``inversion'' in the
                     51:                         * normally ascending cylinder numbers,
                     52:                         * indicating the start of the second request list.
                     53:                         */
                     54:                        if (ap->av_forw->b_cylin < ap->b_cylin) {
                     55:                                /*
                     56:                                 * Search the second request list
                     57:                                 * for the first request at a larger
                     58:                                 * cylinder number.  We go before that;
                     59:                                 * if there is no such request, we go at end.
                     60:                                 */
                     61:                                do {
                     62:                                        if (bp->b_cylin < ap->av_forw->b_cylin)
                     63:                                                goto insert;
                     64:                                        ap = ap->av_forw;
                     65:                                } while (ap->av_forw);
                     66:                                goto insert;            /* after last */
                     67:                        }
                     68:                        ap = ap->av_forw;
                     69:                }
                     70:                /*
                     71:                 * No inversions... we will go after the last, and
                     72:                 * be the first request in the second request list.
                     73:                 */
                     74:                goto insert;
                     75:        }
                     76:        /*
                     77:         * Request is at/after the current request...
                     78:         * sort in the first request list.
                     79:         */
                     80:        while (ap->av_forw) {
                     81:                /*
                     82:                 * We want to go after the current request
                     83:                 * if there is an inversion after it (i.e. it is
                     84:                 * the end of the first request list), or if
                     85:                 * the next request is a larger cylinder than our request.
                     86:                 */
                     87:                if (ap->av_forw->b_cylin < ap->b_cylin ||
                     88:                    bp->b_cylin < ap->av_forw->b_cylin)
                     89:                        goto insert;
                     90:                ap = ap->av_forw;
                     91:        }
                     92:        /*
                     93:         * Neither a second list nor a larger
                     94:         * request... we go at the end of the first list,
                     95:         * which is the same as the end of the whole schebang.
                     96:         */
                     97: insert:
                     98:        bp->av_forw = ap->av_forw;
                     99:        ap->av_forw = bp;
                    100:        if (ap == dp->b_actl)
                    101:                dp->b_actl = bp;
                    102: }

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.