Commit | Line | Data |
---|---|---|
01395141 C |
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 | } |