Google
 

Trailing-Edge - PDP-10 Archives - BB-T573C-DD_1986 - 10,7/whosrt.mac
There are 3 other files named whosrt.mac in the archive. Click here to see a list.
	TITLE	WHOSRT --SORT ROUTINES

	SEARCH	WHOMAC

	$SETUP	(WHOSRT)

SUBTTL	.SORT2 - USE QUICKSORT TO SORT TWO WORD PAIRS


;
; SOME NON-STANDARD AC DEFINITIONS
;
	I=T3		;INDEX TO LOW END OF SWAP LIST
	J=T4		;INDEX TO HIGH END OF SWAP LIST
	L=P1		;POINTER TO LEFT END OF LIST TO SORT
	R=P2		;POINTER TO RIGHT END OF LIST TO SORT
	X1=P3		;HIGH ORDER VALUE TO SPLIT WITH
	X2=P4		;LOW ORDER VALUE TO SPLIT WITH
	Q==16		;FORTRAN ARG POINTER

;	PURGE T3,T4,P1,P2,P3,P4	;NOT NEEDED

; .SORT2 - SORT TWO WORD PAIRS INTO ASCENDING ORDER
;	INPUT:	T1/ AOBJN POINTER TO LIST TO BE SORTED
;		    MUST BE EVEN NUMBER OF WORDS
;		T2/ FLAGS,,SORT CODE
;			FLAGS ARE 400000 FOR UNSIGNED SORT
;			  	  200000 FOR DESCENDING SORT
;			SORT CODE IS
;				0 NONE
;				1 NONE
;				2 KEY IS 1234
;				3 KEY IS 3124
;				4 KEY IS 4123
;				WHERE HALF WORDS ARE NUMBERED 1-4 FOR
;				THE TWO WORD PAIR
;	CALL:	PUSHJ P,.SORT2##
;	RETURN:	NON-SKIP
;	OUTPUT:	NONE
;	USES:	T1-4
;
	SUBTTL	ENTRY	AND INITIALIZATION CODE

	ENTRY	SORT2,.SORT2
SORT2:	SKIPA				;THIS WILL BOMB IN THE HIGH SEG
	PUSH	P,[[JRA	Q,3(Q)]]
	HRRZ	T1,@(Q)			;GET THE LENGTH OF THE ARG LIST
	MOVN	T1,T1			;MAKE IT NEGATIVE
	HRLI	T1,(T1)			;AND PUT IT IN THE LEFT HALF
	HRRI	T1,@1(Q)	;PUT ADDRRESS IN RIGHT HALF
	MOVE	T2,@2(Q)

	SUBTTL	ENTRANCE AND INITIALIZATION CODE
.SORT2::PUSHJ P,.SAVE4##	;GET SOME ACS
	JUMPGE	T1,.POPJ##	;RETURN IF LIST EMPTY
	MOVEI	T3,(T2)		;GET JUST TYPE OF SORT
	CAIG	T3,1		;SEE IF ANYTHING TO DO
	 POPJ	P,		;NO--RETURN
	DMOVEM	T1,USRARG	;SAVE USERS ARGS
	HLRE	R,T1		;GET -LENGTH IN R
	MOVM	R,R		;MAKE +LENGTH
	SUBI	R,1		;SUBTRACT ONE, SO POINTING TO LAST PAIR
	CAIE	R,1		;SEE IF ONLY 1
	 TRNN	R,1B35		;ENSURE AN ODD COUNT NOW
	  POPJ	P,		;JUST RETURN
	MOVE	P1,USRARG	;GET IOWD POINTER
	PUSHJ	P,@INISRT-2(T2)	;DO INITIAL SETUP
	MOVE	P1,USRARG	;PICKUP IOWD POINTER AGAIN
	MOVE	T2,USRARG+1	;PICKUP USER FLAGS
	TLNE	T2,200000	;DESCENDING ORDER?
	 PUSHJ	P,NEGSRT	;YES--FIX UP
	MOVE	P1,USRARG	;PICKUP IOWD POINTER AGAIN
	MOVE	T2,USRARG+1	;PICKUP USER FLAGS
	TLNE	T2,400000	;USER WANT UNSIGNED?
	 PUSHJ	P,FLPSRT	;YES--FIX UP
	MOVE	T1,USRARG	;GET IOWD PNTR
	ADDI	R,-1(T1)	;ADD IN BASE ADR, GET ADR OF RIGHT END
	MOVEI	L,(T1)		;GET BASE ADR IN L, ADR OF LEFT END
	MOVEM	P,SAVPDP	;STORE P FOR TERMINATION CHECK
	JRST	SOR.02		;JUMP INTO "SORT THIS L,R PAIR"
	SUBTTL	SORT A PARTITION
SOR.01:	POP P,T1		;TAKE OFF TOP REQUEST
	HRRZI	R,(T1)		;EXTRACT RIGHT END ADR
	HLRZ	L,T1		;EXTRACT LEFT END ADR
SOR.02:	MOVEI I,(L)		;SET UP POINTERS FOR THIS
	MOVEI	J,(R)		; SCAN AND SWAP SEQUENCE
	MOVE	X1,(L)		;USE FIRST PAIR FOR SCAN AND SWAP
	MOVE	X2,1(L)		; SO GET FIRST AND SECOND WORDS
	JRST	SOR.06		;AND SKIP TO CHECK RIGHT,SINCE LEFT .EQ.

SOR.03:	CAME X1,(I)		;SEE IF HIGH ORDER MATCH
	JRST	SOR.05		;NO, USE THAT TO DECIDE
	CAMG	X2,1(I)		;YES, CHECK NEXT WORD
	JRST	SOR.06		;WE FOUND AN I ENTRY LESS THAN X
SOR.04:	ADDI I,2		;MOVE UP TO NEXT SPOT
	JRST	SOR.03		;BACK TO FIND A SWAPPABLE ENTRY

SOR.05:	CAML X1,(I)		;CHECK FIRST WORD AGAIN
	JRST	SOR.04		;NO SWAP, BACK TO INCREMENT AND LOOP
SOR.06:	CAME X1,(J)		;NOW SAME PROCEDURE FOR RIGHT END
	JRST	SOR.08		;DON'T HAVE TO CHECK X2
	CAML	X2,1(J)		;CHECK LOW ORDER WORD
	JRST	SOR.09		;YES, MAKE A SWAP
SOR.07:	SUBI J,2		;ELSE DECREMENT J
	JRST	SOR.06		;AND BACK TO FIND A SWAPPABLE ENTRY

SOR.08:	CAMG X1,(J)		;CHECK FIRST ENTRY AGAIN, SINCE .NE.
	JRST	SOR.07		;NO SWAP, BACK TO DECREMENT AND LOOP
SOR.09:	CAILE I,(J)		;CHECK IF POINTERS HAVE SWAPPED
	JRST	SOR.10		;YES, THIS SWAP AND SCAN COMPLETE
	DMOVE	T1,(I)		;NO, MAKE A SWAP
	EXCH	T1,(J)		;EXCH EACH WORD
	EXCH	T2,1(J)		; ...
	DMOVEM	T1,(I)		;FINISH THE EXCHANGE
	ADDI	I,2		;MOVE THE POINTERS
	SUBI	J,2		; TOWARD EACH OTHER
	CAILE I,(J)		;CHECK IF POINTERS HAVE SWAPPED
	JRST	SOR.10		;YES, THIS SWAP AND SCAN COMPLETE
	JRST	SOR.03		;AND BACK TO CONTINUE
	SUBTTL	SELECT NEXT PARTITION FOR SORT
SOR.10:	MOVEI T1,(J)		;CALCULATE J-L
	SUBI	T1,(L)		; ...
	MOVEI	T2,(R)		;AND CALCULATE R-I
	SUBI	T2,(I)		; ...
	CAML	T1,T2		;SEE WHICH IS LONGER
	JRST	SOR.11		;(J-L) .GE. (R-I)
	CAIL	I,(R)		;IS I .LT. R? (IE, MORE TO SORT?)
	JRST	SOR.12		;NO, CHECK IF OTHER SIDE NEEDS
	MOVEI	T1,(R)		;STACK REQUEST TO SORT THIS
	HRLI	T1,(I)		;T1/ XWD I,R
	PUSH	P,T1		;STICK IT ON THE STACK
SOR.12:	MOVEI R,(J)		;AND MOVE DOWN THE R POINTER
	JRST	SOR.13		;THEN GO CHECK IF DONE

SOR.11:	CAIL L,(J)		;IS L .LT. J?
	JRST	SOR.14		;NO, GO MOVE UP THE L POINTER
	MOVEI	T1,(J)		;YES, STACK REQUEST TO SORT THIS
	HRLI	T1,(L)		;FROM L TO J
	PUSH	P,T1		;STACK IT
SOR.14:	MOVEI L,(I)		;MOVE UP L, SINCE ALL BELOW SORTED
SOR.13:	CAIGE L,(R)		;ARE WE DONE WITH THIS PARTITION?
	JRST	SOR.02		;NO, BACK TO REPEAT THE WHOLE MESS
	CAME	P,SAVPDP	;YES, IS THE PARTITION THE WHOLE LIST?
	JRST	SOR.01		;NO, LOOP TO PICK NEXT REQUEST
	MOVE	P1,USRARG	;GET IOWD POINTER
	MOVE	T2,USRARG+1	;GET SORT TYPE
	TLNE	T2,400000	;USER WANT UNSIGNED?
	 PUSHJ	P,FLPSRT	;YES--FIX BACK
	MOVE	P1,USRARG	;GET IOWD POINTER
	MOVE	T2,USRARG+1	;GET SORT TYPE
	TLNE	T2,200000	;DESCENDING?
	 PUSHJ	P,NEGSRT	;YES--FIX BACK
	MOVE	P1,USRARG	;GET IOWD POINTER
	MOVE	T2,USRARG+1	;GET SORT TYPE
	PUSHJ	P,@FINSRT-2(T2)	;FINISH UP
	POPJ	P,		;AND RETURN
	SUBTTL	INITIAL/FINAL SORT ARRANGING ROUTINES

INISRT:	I1234
	I3124
	I4123

FINSRT:	F1234
	F3124
	F4123

I1234:
F1234:	POPJ	P,		;T1/ 1,,2  T2/ 3,,4

I3124:	DMOVE	T1,(P1)		;T1/ 1,,2  T2/ 3,,4
	MOVSS	T2		;T1/ 1,,2  T2/ 4,,3
	ROTC	T1,-^D18	;T1/ 3,,1  T2/ 2,,4
	DMOVEM	T1,(P1)		;STORE
	AOBJN	P1,.+1
	AOBJN	P1,I3124	;AND LOOP FOR ALL
	POPJ	P,

F3124:	DMOVE	T1,(P1)		;T1/ 3,,1  T2/ 2,,4
	ROTC	T1,^D18		;T1/ 1,,2  T2/ 4,,3
	MOVSS	T2		;T1/ 1,,2  T2/ 3,,4
	DMOVEM	T1,(P1)		;STORE
	AOBJN	P1,.+1
	AOBJN	P1,F3124	;AND LOOP FOR ALL
	POPJ	P,

I4123:	DMOVE	T1,(P1)		;T1/ 1,,2  T2/ 3,,4
	ROTC	T1,-^D18	;T1/ 4,,1  T2/ 2,,3
	DMOVEM	T1,(P1)		;STORE
	AOBJN	P1,.+1
	AOBJN	P1,I4123	;AND LOOP FOR ALL
	POPJ	P,

F4123:	DMOVE	T1,(P1)		;T1/ 4,,1  T2/ 2,,3
	ROTC	T1,^D18		;T1/ 1,,2  T2/ 3,,4
	DMOVEM	T1,(P1)		;STORE
	AOBJN	P1,.+1
	AOBJN	P1,F4123	;AND LOOP FOR ALL
	POPJ	P,

FLPSRT:	MOVSI	T1,(1B0)	;GET THE SIGN BIT
FLPS.1:	XORM	T1,(P1)		;TOGGLE SIGN BIT
	AOBJN	P1,.+1
	AOBJN	P1,FLPS.1	;AND LOOP FOR ALL
	POPJ	P,

NEGSRT:	SETCMM	(P1)		;NEGATE
	AOBJN	P1,.+1
	AOBJN	P1,NEGSRT	;AND LOOP FOR ALL
	POPJ	P,
	SUBTTL	STORAGE

	$LOW
SAVPDP:	BLOCK 1
USRARG:	BLOCK	2


	END