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     ! 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.