.TITLE SORTER .IDENT /290482/ .ENABL LC ; ; Written by Ray Di Marco ; 29-Apr-82. ; ; ; Version 290482/01. ; ; ;---------------------------------------------------------------------------- ; ; This is the main module for the database management program SORTER, that ; allows the user to sort information extracted from a database with the ; SELECT cusp. This is very useful as such a (sorted) file may be used as ; input to other database CUSPS such as the report writer (REPORT) or the on- ; line retriver (INSPECT). The program requests the user to specify the name ; of the file to be sorted when first run, after which it will proceed to ; sort the records, outputing a message at the start of each pass. ; ; The program can be envoked as a CUSP from a menu program, and will accept ; the name of the file to be sorted, as well as the name of the cusp to ; chain to after sorting is complete via core common. Refer to the MENU and ; CONIO modules for information on how this is achieved. ; ; This module must be linked with the data base object library, DBSLIB, to ; create the SORTER program. This program can be used to sort any correctly ; formatted data file; unlike some other CUSPs that are customized for a ; particular database, only one copy of SORTER.SAV is needed on the sytem. ; ; ; ***** Performance indication ****** ; *********************************** ; ; Sorting 1350 entries, each of 50 bytes, required two passes (of 52 and 25 ; seconds respectively). The machine used was a PDP11/29 operating under ; TSX-plus. The sort file was placed on a private RK05 disk pack for the ; test, and the program was allocated 56k of memory. During the test the ; system was simultaneously servicing three KED users and one DBSEDT user. ; .SBTTL Documentation .IF EQ,-1 The fuction of SORTER is to arrange the entries of a data file into ascending order. SORTER may be used on any file that is of the following format Block 0 .Word SIZENT ; number of bytes in an entry .Word NUMENT ; number of entries in data file .BLKW 254. ; contents of rest of block irrelavent Block 1 .Blkb SIZENT ; Entry #1 2 ; More .... . ; .... entries . .Blkb SIZENT ; Entry #NUMENT (last entry) The format of all entries are identical, and consists of a two byte header that is used by the database CUSPs to record the number of the database record from which the data was extracted, followed by bytes containing the data extracted. Note that SIZENT is the total number of bytes in an entry, and must be at least three (ie 2 header bytes and at least 1 data byte). The function of sorter is to rearrange the file such that the first byte in an entry that is not equal to its equivalent byte in the next entry is smaller than it. This means that if the entries hold names, the names will be sorted in ascending alphabetic order. The sort algorithm used is relatively simple. Upon activation, the sorter obtains as much memory as it can from the monitor, and proceeds to divide this memory into queue elements. Each queue element consists of a forward and backward pointer. In a typical enviroment approximately 500 elements will be available. The program then reads in data from the sort file, and stores it in a queue element. As each queue element is loaded with data, it is linked into an order queue. If the program runs out of queue elements (ie there is not enough memory to hold all the entries at once), the program has to remove an element from one end of the ordered queue and write out its contents before it can process the next entry from the file. In this case another sorting pass will be needed if a subsequent entry is inserted at the end of the queue from which element are being removed. User application programs may make use of the SORTER to sort data. The SRTFOR module may be used by FORTRAN programs to load data into a SORTER format data file, envoke the sorter and then retrieve the data. MACRO programs may append the SFLEIO module to their programs to simplify I/O operations to the sort file. .ENDC .SBTTL DECLARTIONS .ENABL LC ; ; .MCALL .PRINT,.EXIT ; Error Reporting .MCALL .PUSH,.POP ; Stacking .MCALL CNAF ; Numeric IO ; .GLOBL CON.EX,CON.ST ; CONIO entries .GLOBL SFLINT,SFLINP,SFLOUT,SFLRST,SFLEND ; SRTFIO entries .GLOBL SFLNME,SFLPAR ; SRTFIO name of sort file ; ; .PSECT CODE ; open code section ; ------ ---- ; ; .SBTTL Macro Definitions ; .MACRO PRINT STR=R0 .GLOBL CON.LO MOV STR,R0 CALL CON.LO .ENDM PRINT ; .MACRO GTLIN BUF=R0,STR .IF NB,STR .GLOBL CON.LO MOV STR,R0 CALL CON.LO .ENDC MOV BUF,R0 .GLOBL CON.LI CALL CON.LI .ENDM GTLIN ; .MACRO FATAL STR,?A,?B .PRINT #'B .EXIT B': .ASCIZ |'STR'| .EVEN .ENDM FATAL ; .SBTTL INITIALIZATION SECTION ; ; ; Initialize console interface and then get name of file to be ; sorted. Then is time to initialize file stream and queues. ; START: CALL CON.ST ; initialize TTY interface PRINT #7000$ ; identify self GTLIN #SFLNME,#7100$ ; get name of 'SFL' file CALL SFLINT ; initialize sort file CALL QUEINT ; initilize queues JMP LOOP ; enter sort loop ; ; .NLIST BIN 7000$: .ASCIZ /Sorter RDM290482/ 7100$: .ASCII / Sorter File: /<200> .EVEN .LIST BIN ; ; .SBTTL Sorting Loop Manager ; ; ; Register R5 is used as a loop counter. This is initialized on first ; entering the loop to zero. On starting a new pass, we increment the ; counter and output the pass number. ; LOOP: CLR R5 ; R5 = pass counter, initialize 1000$: INC R5 ; start of another pass CNAF SSSD,STRING=#7010$,NUMBER=R5 PRINT #7000$ ; print pass number ; ; Use register R1 as record size and R2 as count of number of records to ; sort in pass. Reset the F.RSRT prior to entering loop; then enter sorting ; loop, which consists of read in records and storing then in an ordered ; queue. Once all records have been input, we empty out the records in the ; queue and initiate another pass if F.RSRT became set during the sorting ; (as this means could not fit all of records in memory simultaneously. ; MOV SFLPAR,R1 ; R1 = entry size MOV SFLPAR+2,R2 ; R2 = number records CLR F.RSRT ; reset done flag CLR F.OUTP ; reset Have Output Flag 1100$: CALL GETELM ; get an element CALL INPUT ; fill it with data CALL INSERT ; insert in queue SOB R2,1100$ ; loop till out of elements CALL EMPTY ; empty queue contents CALL SFLRST ; empty file buffers TST F.RSRT ; another pass wanted? BNE 1000$ ; yes -> loop ; ; After closing out file exit via CON.EX routine. ; CALL SFLEND ; Close out file PRINT #7100$ ; indicate done JMP CON.EX ; exit ; .NLIST BIN 7000$: .ASCII / Pass: / 7010$: .ASCIZ /..../ 7100$: .ASCIZ / Done/ .EVEN .LIST BIN ; .SBTTL ROUTINE - 'GETELM' ... return address of free elem in R0 ; ; ; This routine returns the address of a free element in R0. It first attempts ; to get an element off the free queue. If it cannot, it removes the first ; element off the active queue, empties it and returns its address. Note that ; the F.OUTP becomes set if an active queue element had to be used. ; ; GETELM: CALL QUEOFF ; get element off free queue BCC 1000$ ; got one -> skip CALL QUEOF ; remove first element of queue BCS 6000$ ; cannot -> trouble .PUSH R0 ; save element address ADD #4,R0 ; R0 -> data CALL SFLOUT ; write it out .POP R0 ; R0 -> Queue Element MOV #1,F.OUTP ; indicate had to output elem 1000$: RETURN ; all done 6000$: FATAL ; ; .SBTTL ROUTINE - 'INPUT' ... Load next record into Elem @R0 ; ; ; This routine is called to input the next record (size in R1) into the queue ; element whose address is in R0. ; INPUT: .PUSH R0 ; save element address ADD #4,R0 ; R0 -> data CALL SFLINP ; read data .POP R0 ; R0 -> Queue Element RETURN ; EXIT ; ; ; .SBTTL ROUTINE - 'INSERT' ... INSERT ELEMENT R0 INTO ACTIVE QUEUE ; ; ; We are here to insert the element @R0 onto the active queue. Elements are ; ordered such that those with the highest data are at the head of the queue. ; If the new element is inserted at the head of the queue, all is well. If it ; is not, then may need another pass, depending on whether the new element is ; the smallest on the queue and if some elements have already been output. ; INSERT: .PUSH ; save ADD #6,R0 ; R0 -> data area (ignore RECNUM) MOV R0,10010$ ; SAVE FOR '10000$' LOOP SUB #2,R1 ; R1 = record size (ignore RECNUM) MOV R1,10020$ ; SET UP FOR LOOP ; MOV #QUEHDR,R5 ; R5 -> PARENT MOV (R5),R4 ; R4 -> CHILD BEQ 2000$ ; at eoq -> exit CALL 10000$ ; ok to insert here? BHIS 2000$ ; yes -> exit 1000$: MOV R4,R5 ; CHILD is now PARENT MOV (R5),R4 ; R4 -> new CHILD BEQ 1400$ ; at eoq -> exit CALL 10000$ ; at right place? BLO 1000$ ; no -> loop BR 2000$ ; go insert element 1400$: MOV F.OUTP,F.RSRT ; insert at end of queue **** ; 2000$: MOV R5,R1 ; R1 -> PARENT .POP R0 ; R0 -> Element CALL QUEJN ; insert Element on queue .POP ; restore registers RETURN ; exit ; ; This routine compares the data sections of the new element and element R4 ; byte by byte, start at record byte 2 (bytes 0,1 are the record number). In ; other words, this routine does a ; CMP E0,E4 ; 10000$: MOV (PC)+,R0 ; R0 -> E0 data 10010$: .WORD 0 ; *** patched by INSERT *** MOV (PC)+,R3 ; R3 = number bytes in E0 10020$: .WORD 0 ; *** patched by INSERT *** MOV R4,R2 ; R2 -> E4 ADD #6,R2 ; R2 -> E4 data 10100$: CMPB (R0)+,(R2)+ ; Compare elements untill ... BNE 10200$ ; ... find difference or ... SOB R3,10100$ ; ... run out of bytes 10200$: RETURN ; all done ; .SBTTL ROUTINE - 'EMPTY' ... empty out active queue ; ; ; This routine when called will deactivate all elements currently on the ; active queue. Elements are removed sequently, their data writtern out and ; the elements are returned to the free queue. ; EMPTY: CALL QUEOF ; get an element BCS 100$ ; done -> 100$ .PUSH R0 ; save address ADD #4,R0 ; point to data CALL SFLOUT ; output it .POP R0 ; restore CALL QUEJNF ; return element to free list BR EMPTY ; loop 100$: RETURN ; exit ; ; ; .SBTTL VARIABLES/MESSAGES ; ; ; F.RSRT: .WORD 0 ; 1 -> another sort pass needed INSERT F.OUTP: .WORD 0 ; 1 -> had to write out data GETELM ; ; .SBTTL Module QUEMNG .SBTTL ************* ; ; ; The function of this module is to provide support for the manipulation of ; queue elements. The routines in the module are- ; ; QUEINT initialize the queues. This routine must be called at ; initialization time. It issues a '.SETTOP' to obtain ; all available memory above the program high limit. It ; then uses this memory to form as many queue elements ; as possible, which it links the the 'FREHDR' word. ; ; QUEOFF returns the address of a queue element which is currently ; free to the user in R0. The 'C' flag is set iff no ; element is currently free. ; ; QUEJNF returns element R0 the the free queue ; ; QUEOF returns the address of the last element in the active ; queue in R0, after freeing the element from the queue. ; The 'C' flag is set on exit iff no active element was ; found. ; ; QUEJN inserts element R0 in the active queue after parent R1. ; ; ; The following variables are used by the module. The user should access only ; those marked with a '**' symbol- ; ; LIMIT holds program limits; set up by LINK.SAV ; ; MEMTOP holds highest address obtained with '.SETTOP' ; ; NUMELM holds number queue elements created ; ; FREHDR head of free queue ; ; QUEHDR ** head of active queue ; ; QUEEND points to last element on active queue ; ; .SBTTL Documentation - QUEMNG element structure ; ; ; The size of the data to be stored in the queue element is stored in the ; first word of the 'SFLPAR' block. The initialization routine adds 4 (there ; are two link/words per element) to this number, and then rounds it up to ; make it an even number of bytes. The format of an element is- ; ; ELEM N - .WORD FRWPNT ; .WORD BCKPNT ; .BLKW N ; ; where FRWPNT holds the adress of the next element on the queue ; BCKPNT holds the adress of the previous element on the queue ; N is the contents of 'SFLPAR' word plus 1 divided by 2. ; ; ; .SBTTL Documentation - QUEMNG free queue ; ; The FREHDR word points to the first element on the free queue. The eoq is ; marked by a link pointer of zero. The back pointer and data areas of the ; elements are ignored. ; ; ; .SBTTL Documentation - QUEMNG active queue ; ; ; The QUEHDR word points to the first element on the queue. The QUEEND ; word points to the last element on the queue. Both these words are zero when ; there are no elements on the queue. The queue can be traversed in both the ; forward and backward dirrection. The last element in either the forward or ; back dirrection has its forward/backword point set to zero ; ; .SBTTL DECLARTIONS ; ; .MCALL .EXIT,.SETTOP,.PRINT ; RT11 .MCALL .PUSH,.POP ; STACKING ; ; .PSECT CODE ; OPEN CODE SECTION ; ------ ---- ; .MACRO ERRON CND,MES,?X,?Y,?Z B'CND X BR Y X: .PRINT #'Z .EXIT Z: .ASCII /QUEMNG-fatal-/ .ASCIZ /MES/ .EVEN Y: .ENDM ERRON ; ; .SBTTL Routine - 'QUEINT' ... queue initialization ; ; QUEINT: .SETTOP #-2 ; GET ALL OF MEMORY MOV R0,MEMTOP ; SAVE ALL OF MEMORY MOV SFLPAR,R1 ; RECORD SIZE -> R1 CMP R1,#3 ; MUST BE 3 BYTES AT LEAST ERRON EQ,<'QUEINT' RECORD TO SMALL> ADD #5,R1 ; ALLOW FOR LINK POINTERS BIC #1,R1 ; ENSURE EVEN NUM BYTES ; CLR QUEHDR ; CLEAR FRONT HEADER CLR QUEEND ; CLEAR BACK HEADER CLR R2 ; COUNT OF ELEMENTS ; MOV #FREHDR,R5 ; R5 --> LAST ELEMENT MOV LIMIT+2,R4 ; R4 --> NEXT ELEMENT 1000$: MOV R4,R3 ; POINT R3 ... ADD R1,R3 ; ... TO NEXT CMP R3,MEMTOP ; IN MEMORY RANGE BHIS 2000$ ; NO -> EXIT MOV R4,(R5) ; LINK THIS ELEMENT TO FREE QUEUE MOV R4,R5 ; MAKE THIS ELEMENT NEW HEAD MOV R3,R4 ; MAKE NEXT ELEMENT NEW NEXT INC R2 ; INCREMENT COUNT BR 1000$ ; LOOP ; 2000$: CLR (R5) ; MARK EOQ CMP R2,#4 ; NEED AT LEAST 4 ELEMENTS ERRON LOS,<'QUEINT' NOT ENOUGH MEMORY> MOV R2,NUMELM ; SAVE NUMBER OF ELEMENTS RETURN ; EXIT ; ; .SBTTL ROUTINES - 'QUEOFF'/'QUEJNF' ... FREE QUEUE SUPPORT ; ; ; QUEOFF: MOV FREHDR,R0 ; GET ADDRESS NEXT ELEMENT BEQ 100$ ; NONE -> SKIP MOV (R0),FREHDR ; DELINK CLR (R0) ;; CLEAR FORWARD POINTER CLR 2(R0) ;; clear back pointer TST (PC)+ ; CLEAR FAIL FLAG (SKIP NEXT) 100$: SEC ; SET FAILED RETURN ; EXIT ; ; QUEJNF: MOV FREHDR,(R0) ; LINK ... MOV R0,FREHDR ; ... TO QUEUE RETURN ; EXIT ; ; .SBTTL ROUTINE - 'QUEJN' ... JOIN ACTIVE QUEUE ; ; ; QUEJN: MOV (R1),(R0) ; POINT ELEMENT TO NEXT BEQ 100$ ; NO MORE -> 100$ .PUSH R1 ; SAVE PARENT ADDRESS MOV R0,(R1) ; POINT PARENT TO ELEMENT MOV (R0),R1 ; R1 --> NEXT MOV 2(R1),2(R0) ; POINT ELEMENT TO PARENT MOV R0,2(R1) ; POINT NEXT BACK TO ELEMENT .POP R1 ; RESTORE RETURN ; EXIT ; 100$: MOV R1,2(R0) ; POINT BACK TO PARENT CMP R1,#QUEHDR ; IS PARENT HEAD OF QUEUE BNE 110$ ; NO SKIP CLR 2(R0) ; NO BACK POINTER 110$: MOV R0,(R1) ; SET UP HEADER MOV R0,QUEEND ; SET UP BACK POINTER HEADER RETURN ; EXIT ; ; .SBTTL ROUTINE - 'QUEOF' ... TAKE ELEM OFF ACTIVE QUEUE ; ; QUEOF: MOV QUEEND,R0 ; GET ADDRESS OF ELEMENT BEQ 1000$ ; NONE -> EXIT MOV 2(R0),QUEEND ; DELINK ELEMENT BNE 100$ ; NOT AT EOQ -> SKIP CMP R0,QUEHDR ; ONLY ONE ON QUEUE! ERRON NE,<'QUEOF' - QUEUE CORRUPTED!> CLR QUEHDR ; CLEAR FRONT POINTER BR 200$ ;; complete delinking 100$: CLR @2(R0) ;; last element now EOQ 200$: CLR (R0) ;; clear front pointer CLR 2(R0) ;; clear back pointer RETURN ; EXIT ; 1000$: TST QUEHDR ; SHOULD BE ZERO ERRON NE,<'QUEOF' - QUEHDR CORRUPTED!> SEC ; SET FAILED RETURN ; EXIT ; ; .SBTTL DATA AREA FOR 'QUEMNG' ; ; ; .PSECT DATA ; OPEN DATA AREA ; ------ ---- ; ; LIMIT: .LIMIT ; LIMITS MEMTOP: .WORD 0 ; TOP OF MEMORY NUMELM: .WORD 0 ; NUMBER ELEMENTS FREHDR: .WORD 0 ; HEAD FREE QUEUE QUEHDR: .WORD 0,0 ; HEAD FORWARD QUEUE QUEEND: .WORD 0,0 ; HEAD BACK QUEUE ; ; .END START