static char rcsid[] = "$Header: dsort45.c,v 820.1 86/12/04 19:55:13 root Exp $";
static char sccsid[]="%W% %Y% %Q% %G%";

/************************************************************************
*									*
*				Copyright 1984				*
*			VALID LOGIC SYSTEMS INCORPORATED		*
*									*
*	This listing contains confidential proprietary information	*
*	which is not to be disclosed to unauthorized persons without	*
*	written consent of an officer of Valid Logic Systems 		*
*	Incorporated.							*
*									*
*	The copyright notice appearing above is included to provide	*
*	statutory protection in the event of unauthorized or 		*
*	unintentional public disclosure.				*
*									*
************************************************************************/

/*	dsort.c	4.3	81/03/08	*/

/*
 * 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
 * blocks are allocated.
 */

/* 
 * This sorting algorithm has been modified to sort sectors in order
 * using the rimfire/priam as the target disk.
 *
*/

/* NOTE: DANGER most disk drivers may have io in progress
         on the first buffer, pointed to by dp->b_actf. If this is
	 the case DO NOT use this sorting procedure.
*/
#include "../h/param.h"
#include "../h/systm.h"
#include "../h/buf.h"
#include "../s32dev/rim45.h"    

extern Tdkinfo *Rimdrive[];

#define	b_cylin	b_resid

/* 
 * rimsector =  (head number * NSECT)  + sector number
 *
 */
#define rimsector(x) (x->b_dkp.dkp_pblock % CYL(1)) 


dsort45(dp, bp)
	register struct buf *dp, *bp;
{
	register struct buf *ap;
        Tdkinfo  *Rimi;

	Rimi = Rimdrive[bpDRIVE];
	/*
	 * If nothing on the activity queue, then
	 * we become the only thing.
	 */
	ap = dp->b_actf;
	if(ap == NULL) {
		dp->b_actf = bp;
		dp->b_actl = bp;
		bp->av_forw = NULL;
		return;
	}
	/*
	 * 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) {
		while (ap->av_forw) {
			/*
			 * 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.
				 */
				do {
					if (bp->b_cylin <= ap->av_forw->b_cylin)
						goto insert;
					ap = ap->av_forw;
				} while (ap->av_forw);
				goto insert;		/* after last */
			}
			ap = ap->av_forw;
		}
		/*
		 * No inversions... we will go after the last, and
		 * be the first request in the second request list.
		 */
		goto insert;
	}
	/*
	 * Request is at/after the current request...
	 * sort in the first request list.
	 */
	while (ap->av_forw) {
		/*
		 * 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)
			goto insert;
		ap = ap->av_forw;
	}
	/*
	 * 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.
	 */
insert:
	/* Sort blocks in the same cylinder in head/sector order */

        /* Special case */
	if ((ap == dp->b_actf) && (ap->b_cylin == bp->b_cylin) && 
            (rimsector(ap) > rimsector(bp)))
        {
	    /* bp should go before ap */

	    /* NOTE: DANGER most disk drivers may have io in progress
	       on the first buffer, pointed to by dp->b_actf. If this is
	       the case DO NOT use this sorting procedure.
	     */

	    dp->b_actf  = bp;
	    bp->av_forw = ap;

	    return;
	}

        while (ap->av_forw && (ap->av_forw->b_cylin == bp->b_cylin) && 
               (rimsector(ap->av_forw) < rimsector(bp)))
        {
	    ap = ap->av_forw;
        }

        if (((ap->b_cylin == bp->b_cylin) && (rimsector(bp) < rimsector(ap))) ||
             (ap->av_forw && ap->av_forw->b_cylin == bp->b_cylin &&
               (rimsector(bp) > rimsector (ap->av_forw))))
        {
            printf ("dsort Error\n");
            printf ("ap (cyl %d sec %d) ",ap->b_cylin, 
                     rimsector (ap));
            printf ("bp (cyl %d sec %d) ", bp->b_cylin,rimsector(bp));
            if (ap->av_forw)
                printf ("ap->av_forw (cyl %d sec %d)", ap->av_forw->b_cylin,
                        rimsector(ap->av_forw));
            printf ("\n");

        }

	bp->av_forw = ap->av_forw;
	ap->av_forw = bp;
	if (ap == dp->b_actl)
		dp->b_actl = bp;
}
