.TITLE SRDSRT-SORT THE DIRECTRY .IDENT -6.6- ; Jun-85 .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.) ; ;= ; ;+ ; ; **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 ;DJS001 .IF IDN DIR ASC ; Is the order ascending? ;DJS001 CMP ARG(R3),ARG(R4) ; SEE WHICH IS BIGGER ;DJS001 BHI EXCHNG ; IF HI EXCHANGE POINTERS ;DJS001 BLO CONTINUE ; IF LO, CONTINUE ;DJS001 .IFF ; Else... ;DJS001 .IF IDN DIR DSC ; Is the order descending? ;DJS001 CMP ARG(R3),ARG(R4) ; SEE WHICH IS SMALLER ;DJS001 BLO EXCHNG ; IF LO EXCHANGE POINTERS ;DJS001 BHI CONTINUE ; IF HI, CONTINUE ;DJS001 .IFF ; Else... ;DJS001 .ERROR ; Illegal value for direction argument. ;DJS001 .ENDC ;DJS001 .ENDC ;DJS001 .ENDM ;DJS001 ; ;BT003 READAT: QIOW$ IO.RAT,HDRLUN,EFN1,,IOSB$,,<0,ATTLST> ;BT003 ATTLST: .BYTE -15,43 ; Read creation date ;BT003 .WORD DTBUF ; Buffer to receive date/time ;BT003 .WORD 0 ; End of attribute list ;BT003 DTBUF: ;BT003 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 ; ;BT003 .PSECT SRDCOD,I,RO,LCL,CON,REL ;BT003 ; ;BT003 ; SRDSRT:: ;BT003 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 ; ;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$: ;BT003 ; ;WG6.6 ; All sort information is now set up - ready to sort ;WG6.6 ; ;WG6.6 ; First we do a modified shell sort: ;WG6.6 ; 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, ;WG6.6 ; 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 ; ;WG6.6 ; Complete the sort with a shuttle sort: ;WG6.6 ; Loop through the whole table, starting with i=1. ;WG6.6 ; B: Compare entry i with entry i+1. ;WG6.6 ; 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 ; ;WG6.6 ; First do a modified shell sort ;WG6.6 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 ;WG6.6 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 ;WG6.6 563$: ;WG6.6 MOV (SP)+,R0 ; Restore R0 ;WG6.6 BR WBACK ; Continue ;WG6.6 ; ;WG6.6 ; COMPARE SUBROUTINE ;WG6.6 ; ;WG6.6 COMPAR: ;WG6.6 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 ; ;WG6.6 ; Field compare modules ;WG6.6 ; ;WG6.6 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 ; Ascending date ;BT003 BR NXTFLD ; Proceed to next sort key ;BT003 SDD: C$MP D.FLEV,DSC ; 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$: ;BT003 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 ; ;BT003 ;+ ;BT003 ; 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 ;- ;BT003 GETDAT: MOV R0,-(SP) ; Save registers ;BT003 MOV R1,-(SP) ; ... ;BT003 MOV R2,-(SP) ; ... ;BT003 MOV R2,R3 ; Point to start of directory ;BT003 10$: CMP R3,R1 ; At end yet ? ;BT003 BHIS 90$ ; HIS - then all thru ;BT003 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$: CALL CVDATE ; Convert date (return value in R2) ;BT003 BCC 30$ ; CC - then read OK ;BT003 DIAG BADDS ; File header date corrupt ;BT003 CLR R2 ; Set to zero ;BT003 30$: MOV R2,D.FLEV(R3) ; Insert date into directory ;BT003 MOV (SP)+,R1 ; Restore pointer ;BT003 ADD #D.SIZ,R3 ; Point to next entry ;BT003 BR 10$ ; And loop ;BT003 90$: MOV (SP)+,R2 ; Restore registers ;BT003 MOV (SP)+,R1 ; ... ;BT003 MOV (SP)+,R0 ; ... ;BT003 RETURN ;BT003 ; ;BT003 ;+ ;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 ;- ;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 ;BT003 ;BT003 .END