ASMB NAM QSORT,7 92069-16061 REV.1912 781012 * * ************************************************************** * (C) COPYRIGHT HEWLETT-PACKARD COMPANY 1979. ALL RIGHTS * * RESERVED. NO PART OF THIS PROGRAM MAY BE PHOTOCOPIED, RE- * * PRODUCED, OR TRANSLATED TO ANOTHER PROGRAM LANGUAGE WITH- * * OUT THE PRIOR WRITTEN CONSENT OF HEWLETT-PACKARD COMPANY. * ************************************************************** * * * SOURCE: 92069-18102 * RELOC: 92069-16060 * * ************************************************************* * * * * OVERALL STRATEGY: * * QSORT IS A MODIFICATION OF A QUICK SORT AS DOCUMENTED IN KNUTH VOLUME III. * * THE OBJECT IS TO RECURSIVELY PARTITION THE RECORDS TO BE SORTED INTO * TWO PARTITIONS, EVERYTHING IN THE LEFT PARTITION SHOULD BE LESS THAN * EVERYTHING IN THE RIGHT PARTITION, AND EVERY RECORD IN THE LEFT PARTITION * SHOULD BE LESS THAN THE LAST RECORD IN THE PARTITION AND EVERY RECORD * IN THE RIGHT PARTITION SHOULD BE GREATER THAN THE FIRST RECORD IN THE * PARTITION. ALSO IT MUST BE INSURED THAT THE LAST RECORD OF THE LEFT * PARTITION IS LESS THAN THE FIRST RECORD OF THE RIGHT PARTITION. * * * * ---------------------------------------------------- * ! ! !! ! ! * ! LEFT PARTITION !X !!Z ! RIGHT PARTITION ! * ! ! !! ! ! * ---------------------------------------------------- * * EVERY RECORD .LE. X EVERY RECORD .GE. Z * * AND X .LT. Z * * * * IF ALL THE ABOVE CRITERIA IS MEET X AND Z ARE IN THEIR FINAL * POSITIONS AND NEED NOT BE EXAMINED IN FUTURE PASSES. THEREFORE * THE ALGORITHM CAN BE USED RECURSIVELY ON THE SMALLER * OF THE LEFT AND RIGHT PARTITIONS, * THEN RECURSIVELY ON THE LARGER PARTITIONS UNTIL THE ENTIRE BUFFER * IS SORTED. * * WHEN THIS ALGORITHM IS USED WITH QS05 THE PERFORMANCE CAN BE MEASURED * AS FOLLOWS, * * W = # BYTES IN CORE * B = # BYTES PER RECORD * N = # RECORDS PER FILE * * # OF I/O REQUESTS = (2B/W)2 - 2BN/W+2 * * * SKP * * * * * VARIABLES AND THEIR MEANINGS * * * * XX - CONTAINS AN UPPER LIMIT VALUE FOR THE LEFT PARTITION * ZZ - CONTAINS A LOWER LIMIT VALUE FOR THE RIGHT PARTITION * X - CONTAINS A CURRENT VALUE FROM THE LEFT PARTITION. ALL * VALUES TO THE LEFT OF X MUST BE LESS THAN/ EQUAL TO XX. * Z - CONTAINS A CURRENT VALUE FROM THE RIGHT PARTITION. ALL * VALUES TO THE RIGHT OF Z MUST BE GREATER THAN/ EQUAL TO * ZZ. * P - POINTS TO THE PLACE X CAME FROM * Q - POINTS TO THE PLACE ZERO CAME FROM * IZ - POINTS TO THE PLACE ZZ CAME FROM * IX - POINTS TO THE PLACE XX CAME FROM * L - POINTS TO THE LOW END OF THE LEFT PARTITION * U - POINTS TO THE HIGH END OF THE LEFT PARTITION * L1 - POINTS TO THE LOW END OF THE RIGHT PARTITION * U1 - POINTS TO THE HIGH END OF THE RIGHT PARTITION * * * * * ALGORITHM * * * STEP 1. * EXAMINE THE LOWEST AND THE HIGHEST RECORDS AND PUT THE LESSER * IN THE FIRST RECORD. PUT THE GREATER IN THE LAST * RECORD. * X FIRST RECORD * Z LAST RECORD * * STEP 2. * SET THE LEFT LIMIT (XX) TO X * SET THE RIGHT LIMIT(ZZ) TO Z * * STEP 3. * SCAN FROM LEFT TO RIGHT UNTIL A RECORD IS FOUND THAT IS GREATER * THAN/ EQUAL TO THE LEFT LIMIT. PUT THIS RECORD IN X. * * STEP 4. * SCAN RIGHT END TO THE LEFT UNTIL A RECORD IS FOUND LESS THAN/ EQUAL * TO THE RIGHT LIMIT. PUT THIS RECORD IN Z. * * STEP 5. * INSURE X < Z * * STEP 6. * INSURE XX .LE. X AND ZZ .LE. Z * * STEP 7. * CONTINUE EXECUTING STEPS 3 THROUGH 6 UNTIL THE RECORDS IN X AND * Z ARE ADJACENT IN THE BUFFER. * * STEP 8. * AT THIS TIME X AND Z WILL BE IN THEIR FINAL POSITIONS SINCE * EVERY RECORD TO THE RIGHT OF Z IS GREATER THAN Z. AND EVERY RECORD * TO THE LEFT OF X IS LESS THAN X, AND X < Z. * * STEP 9. * DIVID THE BUFFER INTO 2 PARTITIONS. THE LEFT PARTITION IS FROM THE * FIRST RECORD UPTO BUT NOT INCLUDING X. THE SECOND PARTITION IS * FROM THE LAST RECORD DOWN TO BUT NOT INCLUDING Z. * * STEP 10. * DECIDE WHICH PARTITION IS SMALLER AND STACK ITS UPPER AND LOWER LIMITS. * * STEP 11. * EXECUTE STEPS 1-10 UNTIL ALL RECORDS ARE SORTED IN THAT PARTITION. * * STEP 12. * POP THE STACK * * STEP 13. * EXECUTE STEPS 1-12 UNTIL EVERYTHING IS SORTED. * * * * * SKP ENT QSORT EXT .ENTR EXT CMP,.MVW AA BSS 1 BUFFER ADDRESS L1 BSS 1 LOWER LIMIT OF THE BUFFER U1 BSS 1 UPPER RECORD LIMIT OF THE BUFFER KEY BSS 1 SIZE OF KEY IN BYTES REC BSS 1 SIZE OF RECORD IN BYTES LIST BSS 1 ADDRESS OF LIST ARRAY STAT BSS 1 STATUS RETURN QSORT NOP JSB .ENTR DEF AA LDA REC,I ARS STA REC REC = SIZE OF RECORD LDA L1,I ADA NEG1 MPY REC ADA AA STA L1 L1 = BASE ADDRESS FOR LOWER RECORD LDA U1,I ADA NEG1 MPY REC ADA AA STA U1 U1 = BASE ADDRES FOR UPPER RECORD LDA REC CMA,INA STA RECN NEGETIVE RECORD SIZE LDA KEY,I ARS CMA,INA STA KEY CLA STA STAT,I STA K REENT ISZ K LDA L1 STA L LDA U1 STA U * * * PART *************** * PART LDA L STA P P = LOWER ADDRESS LDA U U = LEFT LOWER LIMIT STA Q Q = UPPER ADDRESS LDB Z PUT HIGH RECORD IN Z JSB MOVE LDA P LDB X JSB MOVE LDB AA ADB RECN STB II LDA P CMA,INA ADA Q ADA RECN STA JJ LDA X LDB Z JSB COMP JMP LA60 X = Z JMP LA60 X < Z LDA Q X > Z STA M M = UPPER ADDRESS LDA P STA J J = LOWER ADDRESS LDA X LDB Z JSB SWICH LA60 LDA L CMA,INA ADA U ADA RECN ADA NEG1 SSA ARE X AND Z BUFFERS ADJACENT IN THE BUFFER JMP LA370 YES LDA X NO, SET XX = X LDB XX JSB MOVE LDA Z LDB ZZ SET ZZ = Z JSB MOVE LDA P STA IX IX = POINTS TO XX BUFFER LDA Q STA IZ IZ POINTS TO ZZ * * * LEFT *************** * SCAN FROM LEFT TO RIGHT UNTIL A RECORD IS FOUND .GE. X * LEFT LDA P ADA REC STA P LDA Q CMA,INA ADA P SSA,RSS JMP LA100 LDA P LDB X JSB MOVE LDA X LDB XX JSB COMP RSS X = XX JMP LEFT X < XX * X > XX * * RIGHT *************** * SCAN FROM RIGHT TO LEFT UNTIL A RECORD IS FOUND .LE. Z * RIGHT LDA Q ADA RECN STA Q CMA,INA ADA P SSA,RSS JMP LA140 LDA Q LDB Z JSB MOVE LDA Z LDB ZZ JSB COMP JMP DIST Z = ZZ JMP DIST Z < ZZ JMP RIGHT Z > ZZ LA140 LDA P LEFT AND RIGHT HAVE RUN INTO EACH OTHER STA Q ADA RECN BACK LEFT OFF BY ONE STA P LDA X LDB Z JSB MOVE LDA P LDB X JSB MOVE * * * DIST *************** * DIST LDA X LDB Z JSB COMP JMP LA200 X = Z JMP LA200 X < Z LDA Q X > Z STA M LDA P STA J LDA X LDB Z JSB SWICH LA200 LDA X INSURE XX .LE. X LDB XX JSB COMP JMP LA240 X = XX JMP LA240 X < XX LDA X X > XX LDB XX JSB MOVE LDA II ADA REC STA II LDA P STA IX LA240 LDA ZZ INSURE THAT ZZ .LE. Z LDB Z JSB COMP JMP LEFT ZZ = Z JMP LEFT ZZ < Z LDA Z ZZ > Z LDB ZZ JSB MOVE LDA II ADA REC STA II LDA Q STA IZ JMP LEFT LA100 LDA Q X AND Z ARE ADJACENT ADA RECN STA P * * * OUT *************** * OUT LDA P CPA IX JMP LA320 LDA X LDB XX JSB CHECK JMP LA320 X = XX LDA XX X # XX LDB P JSB MOVE LDA X LDB IX JSB MOVE LA320 LDA Q CPA IZ JMP LA348 LDA Z LDB ZZ JSB CHECK JMP LA348 Z = ZZ LDA ZZ Z # ZZ LDB Q JSB MOVE LDA Z LDB IZ JSB MOVE LA348 LDA Q CMA,INA ADA U CMA,INA ADA P DECIDE WHICH BUFFER IS SMALLER AND LDB L PUT THE UPPER AND LOWER BOUNDS CMB,INB ON THE STACK ADA B SSA,RSS JMP LA350 LDA L STA L1 LDA P ADA RECN STA U1 LDA Q ADA REC STA L JMP LA360 LA350 LDA U STA U1 LDA Q ADA REC STA L1 LDA P ADA RECN STA U LA360 LDA II CPA JJ JMP LA370 LDB U1 CMB,INB ADB L1 SSB JMP RECUR POP LDA U POP THE STACK CMA,INA ADA L SSA JMP PART LA370 LDA K DONE WITH STACK? CPA ONE JMP QSORT,I YES, EXIT ADA NEG1 STA K ADA BA LDB A,I STB L LDA K ADA CA LDB A,I STB U JMP POP RECUR LDA K NO, GO DO IT AGAIN ADA BA LDB L STB A,I LDA K ADA CA LDB U STB A,I JMP REENT * * * SUBROUTINES FOLLOW. * SKP * * * * MOVE NOP JSB .MVW DEF REC NOP JMP MOVE,I * COMP NOP STA TEMP1 STB TEMP2 JSB CMP DEF *+4 DEF LIST,I DEF TEMP1,I DEF TEMP2,I SZA,RSS JMP COMPX SSA,RSS ISZ COMP ISZ COMP COMPX JMP COMP,I SKP * CHECK NOP JSB COMP JMP CHCKX NOP ISZ CHECK CHCKX JMP CHECK,I * SKP * * * * * * ABSTRACT: * * SWITCH INTERCHANGES 2 RECORDS ADDRESSED BY THE A AND B REGISTERS * A COPY OF THE A-REG IS MOVED TO M * A COPY OF THE B-REG IS MOVED TO J * * CALLING SEQUENCE: * * A-REG - RECORD ADDRESS * B-REG - RECORD ADDRESS * J - LOWER ADDRESS * M - UPPER ADDRESS * * SWICH NOP STA TEMP1 STB TEMP2 LDB RECN LOOPD LDA TEMP1,I STA Y LDA TEMP2,I STA J,I STA TEMP1,I LDA Y STA M,I STA TEMP2,I ISZ TEMP1 ISZ TEMP2 ISZ J ISZ M INB,SZB JMP LOOPD JMP SWICH,I SKP * * * BUFFER AREA. * X DEF XM Z DEF ZM XX DEF XXM ZZ DEF ZZM XM BSS 42 ZM BSS 42 XXM BSS 42 ZZM BSS 42 I BSS 1 J BSS 1 L BSS 1 M BSS 1 P BSS 1 Q BSS 1 U BSS 1 Y BSS 1 II BSS 1 IX BSS 1 JJ BSS 1 IZ BSS 1 TEMP1 BSS 1 TEMP2 BSS 1 RECN BSS 1 K BSS 1 CA DEF * CC BSS 30 BA DEF * BB BSS 30 NEG1 DEC -1 ONE DEC 1 A EQU 0 B EQU 1 END