.TITLE SRDSRT-SORT THE DIRECTRY .IDENT -6.7- ; Jan-97 .ENABL LC ; ; MODIFICATIONS: ; ; CEF001 -- 1-June-83 ; ADD .PSECTS ; ; ; VERSION 6.4 - 07-Nov-83 (;BT003 and ;DJS001) ; ; Bob Turkelson ; SRD Working Group ; ; Use additional LUN for reading headers. For directories too ; large to fit into memory, the directory is kept open while ; processing it in pieces. Thus the directory LUN can not be ; re-used for reading the headers. ; Issue a fatal message if write-back is specified and the ; directory is too large to fit into memory. Determined before ; any directory sorting is done, to save the sorting time. ; (Previously a directory write-back cancelled warning was ; issued, but the last piece of the directory was written ; anyway, wiping out most of the directory.) ; Add sort by date capability. Merged from Henry Tumblin's ; version of SRD (which does not appear on the SIG tapes). ; Allow specification of major and minor sort keys in any order ; in the /SR:x:x:x switch, also allowing the sort to be either ; ascending or descending for any key (file name, type, version ; date). Ascending and descending capability adopted from ; changes by Dave Sides (Sachs/Freeman Assoc., Inc., c/o ; JHU/Applied Physics Laboratory)(;DJS001). Ideas for ; specifying sort keys came from the version of SRD in the ; U. S. Forest Service collection of programs appearing on the ; Spring 1982 SIG tape. The implementation here is quite ; different. ; ; ; Version 6.6 - 12-Jun-85 (;WG6.6) ; ; SRD Working Group ; ; Modify the sort algorithm for improved performance. ; (Thanks to Jim DeMange and Tony Gandy of Systeme ; Corporation, Orlando, FL.) ; ; Version 6.7 - 27-Jan-97 ; ; Johnny Billquist ; ; Added support for the next millenium. ; ;= ; ;+ ; ; **SRD--SORT DIRECTORY ; ; THIS MODULE SORTS THE DIRECTORY ; ; ; DUKE001 -- 19-NOV-79,-5.0-, HENRY R. TUMBLIN ; MOVED COMPRESS INTO SRDSUB AS A SUBROUTINE ; ; THIS TASK WILL SORT A RSX11/IAS DIRECTORY ; THEN CREATE A LISTING WITH SEVERAL SELECTION OPTIONS ; ; ; ;- ; .PSECT SRDATA,D,RW,LCL,REL,CON ;BT003 ; SYSTEM MACRO CALLS ; .MCALL CALLR,WRITE$,WAIT$,CLOSE$,QIOW$,DIR$ ;BT003 ; ; LOCAL MACRO ; .MACRO C$MP ARG,DIR,IND,?EX,?NEX,?NN .IF IDN DIR ASC ; Is the order ascending? ;DJS001 .IF NB IND MOV R3,-(SP) MOV R4,-(SP) MOV ARG(R3),R3 BEQ NN MOV ARG(R4),R4 BEQ NN CMP (R3),(R4) BHI EX BLO NEX CMP 2(R3),2(R4) BHI EX BLO NEX CMP 4(R3),4(R4) BHI EX BLO NEX BR NN .IFF CMP ARG(R3),ARG(R4) ; SEE WHICH IS BIGGER ;DJS00 BHI EXCHNG ; IF HI EXCHANGE POINTERS ;DJS001 BLO CONTINUE ; IF LO, CONTINUE ;DJS001 .ENDC .IFF ; Else... ;DJS001 .IF IDN DIR DSC ; Is the order descending? ;DJS001 .IF NB IND MOV R3,-(SP) MOV R4,-(SP) MOV ARG(R3),R3 BEQ NN MOV ARG(R4),R4 BEQ NN CMP (R3),(R4) BHI NEX BLO EX CMP 2(R3),2(R4) BHI NEX BLO EX CMP 4(R3),4(R4) BHI NEX BLO EX BR NN .IFF CMP ARG(R3),ARG(R4) ; SEE WHICH IS SMALLER ;DJS001 BLO EXCHNG ; IF LO EXCHANGE POINTERS ;DJS001 BHI CONTINUE ; IF HI, CONTINUE ;DJS001 .ENDC .IFF ; Else... ;DJS001 .ERROR ; Illegal value for direction argument. ;DJS001 .ENDC ;DJS001 .ENDC ;DJS001 .IF NB IND EX: MOV (SP)+,R4 MOV (SP)+,R3 BR EXCHNG NEX: MOV (SP)+,R4 MOV (SP)+,R3 BR CONTINUE NN: MOV (SP)+,R4 MOV (SP)+,R3 .ENDC .ENDM ;DJS001 ; ; READAT: QIOW$ IO.RAT,HDRLUN,EFN1,,IOSB$,,<0,ATTLST> ;BT ATTLST: .BYTE -15,43 ; Read creation date ;BT003 .WORD DTBUF ; Buffer to receive date/time ;BT003 .WORD 0 ; End of attribute list ;BT003 DTBUF: ; RVNO: .BLKW 1 ; Revision number ;BT003 RVDATE: .BLKB 7 ; Revision date ;BT003 .BLKB 6 ; Revision time ;BT003 CRDATE: .BLKB 7 ; Creation date ;BT003 .BLKB 6 ; Creation time ;BT003 .BLKB 7 ; Expiration date ;BT003 .EVEN ;BT003 SRTORD: .BLKW 6 ; Addresses for ordered sort ;BT003 ; DATBUF: .BLKW <2048.>*3 DBEND: ; .PSECT SRDCOD,I,RO,LCL,CON,REL ;BT003 ; ; ; SRDSRT:: ; BIT #WBSW,SWMS2$ ; Requested to write back directory? ;BT003 BEQ 5$ ; EQ - no, proceed ;BT003 CMPB #IE.EOF,F.ERR+UFDFDB ; Has entire directory been read? ;BT003 BEQ 5$ ; EQ - yes, proceed ;BT003 FERR WBCAN ; Issue fatal error (without sorting) to ;BT003 ; ; prevent last piece of directory being ;BT003 ; ; written later ;BT003 5$: MOV F.BKDS+2+UFDFDB,R1 ; Point at end of buffer ;BT003 MOV DIRBF$,R2 ; POINT AT TOP OF DIRECTORY CALL SRDCOM ; COMPRESS WHAT WE HAVE. .ENABL LSB BIT #DATSRT,FLAGS$ ; Sorting by date? ;BT003 BEQ 10$ ; EQ - no ;BT003 CALL GETDAT ; Read in file headers to get dates ;BT003 ; ; ; AT THIS POINT, THE DIRECTORY IS DENSE, AND ; R1=LOGICAL END OF DIRECTORY ; R2=FIRST ENTRY ; ; NOW WE SORT THE ENTRIES ; 10$: BIT #SRSW,SWMS2$ ; SORT IT ??? BNE 100$ ; NE - yes ;BT003 JMP WBACK ; Otherwise, check for write-back ;BT003 100$: MOV #SRTORD,R3 ; Point to table to put sort code addresses ;BT003 MOV #SKBUF$,R5 ; Point to start of sort key buffer ;BT003 110$: CMPB (R5),#'T ; Sort on file type? ;BT003 BNE 130$ ; NE - no ;BT003 TSTB (R5)+ ; Point to field for descending ;BT003 CMPB (R5)+,#'D ; Descending file type? ;BT003 BEQ 120$ ; EQ - yes ;BT003 MOV #STA,(R3)+ ; Ascending file type ;BT003 BR 250$ ; Proceed to next sort key ;BT003 120$: MOV #STD,(R3)+ ; Descending file type ;BT003 BR 250$ ; Proceed to next sort key ;BT003 130$: CMPB (R5),#'N ; Sort on file name? ;BT003 BNE 150$ ; NE - no ;BT003 TSTB (R5)+ ; Point to field for descending ;BT003 CMPB (R5)+,#'D ; Descending file type? ;BT003 BEQ 140$ ; EQ - yes ;BT003 MOV #SNA,(R3)+ ; Ascending file name ;BT003 BR 250$ ; Proceed to next sort key ;BT003 140$: MOV #SND,(R3)+ ; Descending file name ;BT003 BR 250$ ; Proceed to next sort key ;BT003 150$: CMPB (R5),#'V ; Sort on file version? ;BT003 BNE 170$ ; NE - no ;BT003 TSTB (R5)+ ; Point to field for descending ;BT003 CMPB (R5)+,#'D ; Descending file version? ;BT003 BEQ 160$ ; EQ - yes ;BT003 MOV #SVA,(R3)+ ; Ascending file version ;BT003 BIS #ASCVER,FLAGS$ ; Set ascending version flag ;BT003 BIT #PUSW,SWMSK$ ; Selecting obsolete versions? ;BT003 BNE 250$ ; NE - yes ;BT003 BIS #OVDSVA,FLAGS$ ; No, set for ascending, highest versions ;BT003 BR 250$ ; Proceed to next sort key ;BT003 160$: MOV #SVD,(R3)+ ; Descending file version ;BT003 BIT #PUSW,SWMSK$ ; Selecting obsolete versions? ;BT003 BEQ 250$ ; EQ - no ;BT003 BIS #OVDSVA,FLAGS$ ; No, set for descending, lowest versions ;BT003 BR 250$ ; Proceed to next sort key ;BT003 170$: CMPB (R5),#'D ; Sort on file date? ;BT003 BNE 190$ ; NE - no ;BT003 TSTB (R5)+ ; Point to field for descending ;BT003 CMPB (R5)+,#'D ; Descending date? ;BT003 BEQ 180$ ; EQ - yes ;BT003 MOV #SDA,(R3)+ ; Ascending date ;BT003 BR 250$ ; Proceed to next sort key ;BT003 180$: MOV #SDD,(R3)+ ; Descending date ;BT003 BR 250$ ; Proceed to next sort key ;BT003 190$: TST (R5)+ ; Future ;BT003 250$: TST (R5) ; At end of sort keys? ;BT003 BNE 110$ ; No, process next one ;BT003 CLR (R3) ; Signal end of address table ;BT003 15$: ; ; ; ; All sort information is now set up - ready to sort ; ; ; ; First we do a modified shell sort: ; ; An intial offset is calculated as m=(N+1)/2, that is, as ;WG6.6 ; 1/2 the total number of entries in the table (rounded up). ;WG6.6 ; A: Then loop with i=1 to N-m, comparing entry i with entry i+m, ;W ; swapping any entries found to be out of order. ;WG6.6 ; Calculate a new value for the offset m as 1/2 the previous ;WG6.6 ; value (rounded up). When this value reaches 1, go on to the ;WG6.6 ; shuttle sort. Otherwise, go to A: above. ;WG6.6 ; A shell sort tends to get the entries into the correct area of ;WG6.6 ; the table with minimal swapping of entries. ;WG6.6 ; ; ; Complete the sort with a shuttle sort: ; ; Loop through the whole table, starting with i=1. ;WG6.6 ; B: Compare entry i with entry i+1. ;W ; If the entries are in order, increment i and goto B: above. ;WG6.6 ; If they are out of order, we know that the previous entries are ;WG6.6 ; all sorted, so we need to find where to insert entry i+1. ;WG6.6 ; Store entry i+1 on the stack. ;WG6.6 ; Search backward (watching for the start of the table) starting at ;WG6.6 ; entry i-1 to find an entry j where entry j and entry i+1 are in ;WG6.6 ; order. When found, that means that entry i+1 should go where entry ;WG6.6 ; j+1 is, after entries j+1 through i are each moved one entry towards ;WG6.6 ; the end of the table. Accomplish this by moving entry i to i+1, ;WG6.6 ; i-1 to i, ..., until j+1 is moved to j+2. ;WG6.6 ; Move the entry on the stack to j+1 to complete the insert. ;WG6.6 ; Increment i to the next entry and continue with the loop. ;WG6.6 ; ; ; First do a modified shell sort ; MOV R0,-(SP) ; Save R0 ;WG6.6 MOV R1,R5 ; Get address of end of table ;WG6.6 SUB R2,R5 ; Compute table size in bytes ;WG6.6 CLR R4 ; Prepare for double register shift ;WG6.6 ASHC #-4,R4 ; Divide by 16. to get number of entries ;WG6.6 ; (Here we are assuming D.SIZ is 16.) ;WG6.6 MOV R5,R0 ; Save total number of entries ;WG6.6 511$: INC R0 ; Inc current entry offset number (to round up) ;WG6.6 ASR R0 ; Divide by 2 to calculate new offset number ;WG6.6 CMP R0,#1 ; Test for Shell sort completion ;WG6.6 BLE 518$ ; LE - Shell sort completed ;WG6.6 MOV R2,R3 ; Get start of table address (1st entry to cmp) ;WG6.6 MOV R0,R4 ; Get entry offset number ;WG6.6 ASH #4,R4 ; Multiply by 16. to convert to byte offset ;WG6.6 ADD R2,R4 ; Compute address of entry at offset ;WG6.6 512$: CALL COMPAR ; Compare entries pointed to by R3 and R4 ;WG6.6 BNE 515$ ; NE - swap required ;WG6.6 ADD #D.SIZ,R3 ; Step to next entry ;WG6.6 ADD #D.SIZ,R4 ;WG6.6 513$: CMP R4,R1 ; Have we reached the end of the table? ;WG6.6 BLO 512$ ; LO - no ;WG6.6 BR 511$ ; Go start next loop ;WG6.6 515$: MOV #D.SIZ/2,R5 ; Set up loop count to swap entries ;WG6.6 516$: MOV (R3),-(SP) ; Swap entries ;WG6.6 MOV (R4),(R3)+ ;WG6.6 MOV (SP)+,(R4)+ ;WG6.6 SOB R5,516$ ;WG6.6 BR 513$ ; Continue, pointing at next entries ;WG6.6 ; Now do shuttle sort ; 518$: MOV R2,R3 ; Get address of beginning of table ;WG6.6 520$: MOV R3,R4 ; Copy address of current entry ;WG6.6 ADD #D.SIZ,R4 ; Point at next entry ;WG6.6 CMP R4,R1 ; Have we reached the end of the table? ;WG6.6 BHIS 563$ ; HIS - yes, sort completed ;WG6.6 CALL COMPAR ; Compare entries pointed to by R3 and R4 ;WG6.6 BEQ 540$ ; EQ - entries are in order ;WG6.6 MOV R4,R0 ; Save pointer to current position ;WG6.6 525$: SUB #D.SIZ,R3 ; Back up through table ;WG6.6 CMP R3,R2 ; Have we gone beyond the start of the table? ;WG6.6 BLO 527$ ; LO - at start of table - entry should go here ;WG6.6 CALL COMPAR ; Compare entries ;WG6.6 BNE 525$ ; NE - have not yet found where entry should go ;WG6.6 527$: MOV R0,-(SP) ; Save entry address ;WG6.6 ; Here the (R4) entry should go AFTER the (R3) entry ;WG6.6 .REPT D.SIZ/2 ;WG6.6 MOV (R4)+,-(SP) ; Save swap entry ;WG6.6 .ENDR ;WG6.6 ADD #D.SIZ*2,R3 ; Go back past entry to swap ;WG6.6 530$: MOV -(R0),-(R4) ; Move all entries up in table ;WG6.6 CMP R4,R3 ; Test for all entries moved ;WG6.6 BHI 530$ ; HI - all entries have not yet been moved ;WG6.6 .REPT D.SIZ/2 ;WG6.6 MOV (SP)+,-(R3) ; Insert swap entry in its proper location ;WG6.6 .ENDR ;WG6.6 MOV (SP)+,R3 ; Point back to position to restart ;WG6.6 BR 520$ ; Continue comparisons from this point ;WG6.6 540$: ADD #D.SIZ,R3 ; Point to next entry ;WG6.6 BR 520$ ; Continue comparisons ;WG6.6 ; All data sorted ; 563$: ; MOV (SP)+,R0 ; Restore R0 ;WG6.6 JMP WBACK ; Continue ;WG6.6 ; ; ; COMPARE SUBROUTINE ; ; ; COMPAR: ; MOV #SRTORD,R5 ; Point to table of addresses of sort code ;**-5 JMP @(R5)+ ; Check the first field for sorting ;BT003 NXTFLD: TST (R5) ; Are we at the end of the table? ;BT003 BEQ CONTINUE ; EQ - yes ;BT003 JMP @(R5)+ ; Check the next field for sorting ;BT003 EXCHNG: CLZ ; Clear Z-bit to indicate NE ;WG6.6 RETURN ; Return ;WG6.6 CONTINUE: SEZ ; Set Z-bit to indicate EQ ;WG6.6 RETURN ; Return ;WG6.6 ; ; ; Field compare modules ; ; ; STA: C$MP D.TYP,ASC ; Ascending file type ;**-2 BR NXTFLD ; Proceed to next sort key ;BT003 STD: C$MP D.TYP,DSC ; Descending file type ;BT003 BR NXTFLD ; Proceed to next sort key ;BT003 SNA: C$MP D.FNAM,ASC ; Ascending file name ;BT003 C$MP D.FNAM+2,ASC ;BT003 C$MP D.FNAM+4,ASC ;BT003 BR NXTFLD ; Proceed to next sort key ;BT003 SND: C$MP D.FNAM,DSC ; Descending file name ;BT003 C$MP D.FNAM+2,DSC ;BT003 C$MP D.FNAM+4,DSC ;BT003 BR NXTFLD ; Proceed to next sort key ;BT003 SVA: C$MP D.VER,ASC ; Ascending file version ;BT003 BR NXTFLD ; Proceed to next sort key ;BT003 SVD: C$MP D.VER,DSC ; Descending file version ;BT003 BR NXTFLD ; Proceed to next sort key ;BT003 SDA: C$MP D.FLEV,ASC,IND ; Ascending date ;BT003 BR NXTFLD ; Proceed to next sort key ;BT003 SDD: C$MP D.FLEV,DSC,IND ; Descending date ;BT003 BR NXTFLD ; Proceed to next sort key ;BT003 ; .DSABL LSB ;**-13 ; ; DIRECTORY IS SORTED, NOW WRITE BACK ; WBACK: MOV #WBTRY,R4 ; Re-try loop count ;BT003 CLR R5 BIT #WBSW,SWMS2$ ;WRITE-BACK REQUESTED? BEQ 90$ ;BR IF NO 65$: CMP DIRBF$,R1 ; DOES THE DIRECTORY HAVE ANYTHING IN IT? BHIS 100$ ; NO -- DON'T WRITE. BIT #DATSRT,FLAGS$ ; Doing a date sort? ;BT003 BEQ 68$ ; EQ - no ;BT003 CALL CLRDAT ; Clear temporary dates out of header ;BT003 68$: ; CLR R5 MOV #1,F.EFBK+2+UFDFDB ;RESET END-OF-FILE MOV DIRBF$,F.BKDS+2+UFDFDB ;POINT I-O BUFFER TO TOP MOV #1,F.VBN+2+UFDFDB ;AND ALSO VIRT. BLK NUMBER 70$: WRITE$ #UFDFDB ;WRITE OUT A BLOCK BCS 85$ ; ERROR WAIT$ #UFDFDB ; WAIT FOR COMPLETION BCS 85$ 75$: ADD #512.,F.BKDS+2+UFDFDB ;ADJ. BUFFER TO NEXT BLK CMP F.BKDS+2+UFDFDB,R1 ;SEE IF WE'RE PAST END OF DATA BLO 70$ ; CHECK FOR ERROR & RETRY IF NEEDED TST R5 BEQ 100$ ; NO ERRORS THIS TIME SOB R4,65$ BR 100$ ; Close UFD & return 85$: DIAG WBERR INC R5 BR 75$ 90$: CMPB #IE.EOF,F.ERR+UFDFDB ; DONE WITH DIRECTORY ?? BNE 110$ ; If NE no - just return ; 100$: CLOSE$ #UFDFDB ; Close the UFD ; 110$: MOV R1,F.BKDS+2+UFDFDB ; POINT AT END OF BUFFER RETURN ; and return ; ; ;+ ; ; This routine will fill in the file date in ;BT003 ; the file system level location in the file ID in ;BT003 ; the directory entry. On ODS-1 systems, this location ;BT003 ; is always zero. ;BT003 ;- ; GETDAT: MOV R0,-(SP) ; Save registers ;BT003 MOV R1,-(SP) ; ... ;BT003 MOV R2,-(SP) ; ... ;BT003 MOV R4,-(SP) MOV R5,-(SP) MOV #DATBUF,R5 MOV R2,R3 ; Point to start of directory ;BT003 10$: CMP R3,R1 ; At end yet ? ;BT003 BHIS 90$ ; HIS - then all thru ;BT003 CMP R5,#DBEND ; End of date buffer? BEQ 90$ ; Yes. No use to do more. MOV R1,-(SP) ; Save pointer ;BT003 MOV R3,READAT+Q.IOPL ; Set file ID pointer ;BT003 DIR$ #READAT ; Read attributes ;BT003 CMPB IOSB$,#IS.SUC ; Did it succeed ? ;BT003 BEQ 20$ ; EQ - yes ;BT003 DIAG BADDS ; Unable to read file dates ;BT003 CLR R2 ; Set to zero ;BT003 BR 30$ ;BT003 20$: MOV #CRDATE,R1 ; Point to creation date string ;BT003 BIT #RDSW,SWMS2$ ; Use revision date? ;BT003 BEQ 25$ ; EQ - no ;BT003 TST RVNO ; Ever revised? ;BT003 BEQ 25$ ; EQ - no, use creation date ;BT003 MOV #RVDATE,R1 ; Point to revision date string ;BT003 25$: MOV R5,D.FLEV(R3) ; Save pointer. MOV R3,-(SP) CALL CVFDAT ; Convert date (return value in R2,R3) ;BT003 BCC 30$ ; CC - then read OK ;BT003 DIAG BADDS ; File header date corrupt ;BT003 CLR R2 ; Set to zero ;BT003 CLR R3 30$: CALL CVTIME ; And time... BCC 31$ DIAG BADDS CLR R4 BR 32$ 31$: ASL R4 ASL R4 ASL R4 ASL R4 ASL R4 CLR -(SP) MOVB (R1)+,(SP) SUB #'0,(SP) ADD (SP),R4 ASL (SP) ASL (SP) ADD (SP),R4 MOVB (R1)+,(SP) SUB #'0,(SP) ASR (SP) ADD (SP)+,R4 32$: MOV R2,(R5)+ MOV R3,(R5)+ MOV R4,(R5)+ MOV (SP)+,R3 MOV (SP)+,R1 ; Restore pointer ;BT003 ADD #D.SIZ,R3 ; Point to next entry ;BT003 BR 10$ ; And loop ;BT003 90$: MOV (SP)+,R5 MOV (SP)+,R4 MOV (SP)+,R2 ; Restore registers ;BT003 MOV (SP)+,R1 ; ... ;BT003 MOV (SP)+,R0 ; ... ;BT003 RETURN ;BT003 ; ; ;+ ; ; This routine will zero the file level number in the ;BT003 ; directory entry. This is required before the directory is ;BT003 ; written back to disk. ;BT003 ;- ; CLRDAT: MOV DIRBF$,R3 ; Point to start ;BT003 10$: CMP R3,R1 ; At end of buffer ? ;BT003 BHIS 90$ ; HIS - then all thru ;BT003 CLR D.FLEV(R3) ; Reset file level # ;BT003 ADD #D.SIZ,R3 ; Point to next entry ;BT003 BR 10$ ; And loop ;BT003 90$: RETURN ;BT0 ; .END