.; DECUS Sort Utility 24-Jul-83 - Edit for DECUS Release .Title SORT - DECUS Sorting Utility .subtitlechapter .uspace .ps 60,72 .nhy .figure 10 .c;SORT .c;---- .s 2 .c;A General Purpose Sorting Utility for RT11 .c;------------------------------------------ .s 2 SORT is a general purpose RT11 utility sorting programme, capable of coping with files as large as RT11 can deal with. Sorting may be ASCII or alphanumeric, and considerable trouble was taken by the author to enhance the speed of the sorting. It sorts large volume files rapidly, requiring typically only 2 or 3 merge passes for sorts of two megabytes or more. It is device independent, running on a system with any configuration of devices. Input and output may use any RT11 device, but scratch files must be on disc. SORT may be used directly from RT11, or chained to from a programme. .s Records must be terminated by a carriage return character. Other control characters except tab (and control-Z in Dibol files) are ignored. .s 3 SORT was written by Darrell Whimp during his student days at St Peter's Lutheran College, Brisbane. It has been given to DECUS with the kind permission of himself and the computing department at St Peter's. It has been modified and submitted to DECUS by Chester Wilson, who is willing to provide support for it, and will welcome any suggestions, bug reports and ideas generally (to 71 Galatea St, Charleville, 4470, Australia). .s General permission is given to copy, use, and modify, but not to sell for profit. .page .fg 10 .c;Table of Contents .c;----------------- .s 3 .lm +10 .nf a) Update History .S 1. General Ideas Re Sorting What is Sorting? Multi-line Records Sorting Patterns 2. Using SORT 3. Scratch Files 4. Tag Sorting 5. Chaining to SORT 6. Error Messages 7. Assembling SORT 8. Distribution .s Appendix A: ASCII sequence Appendix I: Index .lm 0 .page .fg 10 .c;Update History .c;-------------- .s 3 .c;July 1983: Release to DECUS - V2A .ch General Ideas re Sorting .X General Ideas re Sorting .x Keys - ideas on .x Records - ideas on .hl 1;What is Sorting? Sorting is the technique of getting a collection of anything, in this case information stored on a computer, into a desired sequence. The information is divided up into RECORDS, which for the purpose of this sorting programme are restricted to a line of text within a file. This is an ordinary text file, such as that created by KED, EDIT, or TECO. .s Each record comprises a string of characters (terminated with a carriage return and a line feed character) which were typed in to the computer, or generated by a programme. Groups of these characters may be related - for example one group may be a surname, another a street address, another a town, and another an examination result. .s To allow this information to be processed for different purposes it is useful to gather together related pieces of this information. For example, for a mailing list it may be useful to have the information in alphabetical order of surnames (and for people with the same surname then in alphabetical order of first names - something like an elementary phone book). For determining the honours list we need the information in order of the examination results, and to determine the most convenient transport arrangements for people in the list we may need our list in order of towns or suburbs. .s The particular piece of information which we desire to sort our records on is a KEY. We may have but one key, or we may have several keys, to be taken in order (such as surname, then, for each group with a common surname, the Christian name, etc). We may wish our list to be in ascending order, or we may wish it in descending order. It is possible to specify to a sorting programme what the desired sorted order is to be. .hl 1;Multi-line Records .x Multi-line records A file of information may consist of several lines for each record. For example, the name may be on the first line, the address on the second and third, and more information on the fourth or fifth lines. Alternatively the data may be stored in a Fortran random-access file, which is in a format where it cannot be easily read by ordinary text editors (eg KED). .s SORT can only cope with single line records of text. If you wish to sort information from a file in another format, you will need to write a programme to convert it into a text file with a single line to each record (albeit a very long line), and another to convert the data back to the original format after it has been sorted. .hl 1;Sorting Patterns .x ASCII codes _& sorting Characters in PDP-11 computers are stored using the ASCII (American Standard Code for Information Interchange). Sorting directly upon these codes leads to the following sequence: .nf .s ! " _# $ % _& ' ( ) * + , - . / 0 1 2 3 4 5 6 7 8 9 : ; .s < = > ? @ A B C D E F G H I J K L M N O P Q R S T U V W X Y Z .s [ _\ ] _^ __ ` a b c d e f g h i j k l m n o p q r s t u v w x y z .s { | } ~ .s;.f Thus capital letters sort before lower case letters (eg "ZULU" will come before "apple"), and non-alphabetics will be scattered about the list. Providing all the fields used as keys for sorting are all the same case or numeric information only this should provide no problems, but for mixed fields it can be a nuisance. .s SORT can sort things according to the ASCII codes, in either ascending or descending order. It can also sort according to an alphanumeric technique which does two things: (1) case is ignored, so "apple" will come before "ZULU", and (2) leading non-alphanumeric characters are ignored (providing that there are SOME alphanumeric characters in the record!). The following are some results using the test file provided SORT.DAT: .tp 20 .s .x Examples of Sorting THE DATA FILE ITSELF: .S .LIT _.TYPE SORT.DAT DOG TAGS c i flag waving n S c Goanna, Sand s e d goanna oil g A o Goanna, other c d r Charlie Sand e a /delete option S n b Dog food a s e dog leg i C t word C i billy goat d I p Billy the Kid I n h _# of eggs in the basket. A g e aaron alphabeticus n I l Aaron _& Moses I d A Rhubarb e . r .END LITERAL .tp 23 .S 3 ASCENDING ASCII SORT: .S .lit _.R SORT *TT:=CTEST.DAT _# of eggs in the basket. A g e /delete option S n b word C i Aaron _& Moses I d A Billy the Kid I n h Charlie Sand e a DOG TAGS c i Dog food a s e Goanna, Sand s e d Goanna, other c d r Rhubarb e . r aaron alphabeticus n I l billy goat d I p dog leg i C t flag waving n S c goanna oil g A o .end literal .tp 23 .s 3 DESCENDING ASCII SORT: .S .LIT _.R SORT *TT:=CTEST.DAT/K:D:1:80. goanna oil g A o flag waving n S c dog leg i C t billy goat d I p aaron alphabeticus n I l Rhubarb e . r Goanna, other c d r Goanna, Sand s e d Dog food a s e DOG TAGS c i Charlie Sand e a Billy the Kid I n h Aaron _& Moses I d A word C i /delete option S n b _# of eggs in the basket. A g e .end literal .tp 23 .s 3 ALPHANUMERIC SORT: .S .lit _.R SORT *TT:/A=CTEST.DAT Aaron _& Moses I d A aaron alphabeticus n I l billy goat d I p Billy the Kid I n h Charlie Sand e a /delete option S n b Dog food a s e dog leg i C t DOG TAGS c i flag waving n S c word C i goanna oil g A o Goanna, other c d r Goanna, Sand s e d _# of eggs in the basket. A g e Rhubarb e . r .END LITERAL .ch Using SORT .x Running SORT .x SORT Commands .x Commands for SORT SORT is run using the command: .s .i 10;_.R SORT .br .ts 10 or _.RUN dev:SORT .s SORT responds with an asterisk, expecting a normal RT11 command string in the form .s *,,=/switches .s Default input and output extensions are ".DAT". .s [An exclamation mark "!" preceding the file specification has special significance - see the chapter on Chaining to SORT.] .s The scratch files are optional, and as many scratch files as may be needed (up to 2) will be allocated on device DK: if required. The output file will normally be used as a scratch file (if on disc), and for applications where disc space is critical, it is possible to use the input file as a scratch file also (thereby destroying it, however!). .s Switches available for SORT are: .s .lm 10 .i -10;/K /K:[type:]start:length<:[type:]start:length> .s Where .s .nf type may be A for ascending ASCII D for descending ASCII or ALP for alphanumeric. .s .lm +10 .f If type be omitted, it defaults to the previous type specification. This is initially set to "A". .lm -10;.nf;.s start is the character on which this sorting key starts [needs a decimal point to be taken as decimal - eg "10." for the tenth character in the line.] .s length is the number of characters in this sorting key. [again, it needs a decimal point] .s;.f /K defines the keys to be used for sorting. Keys may be ascending ASCII, descending ASCII, or alphanumeric (always ascending). They must be specified in pairs - with the starting column (the first column is column 1) followed by the length (in bytes) of that particular key. .s The ASCII code has some traps for the unwary when it comes to sorting (See previous chapter). Unlike a dictionary, the capital and lower case letters are treated completely differently. Thus all records with keys commencing with "Z" will come before any records with keys commencing with "a" in an ascending ASCII sort. This is often no problem where everything is in capital letters, but can be a nuisance otherwise. The ASCII code is listed in the appendix for reference. An alphanumeric sort on the other hand treats capital and small letters the same, and ignores any leading non-alphanumeric characters, so that "dog", "Dog", and "/DOG" will all come together on sorting this way. .s /K:A:1:10. .s will sort in ascending ASCII order on the first ten columns (note the decimal point - if omitted, the RT11 command string interpreter will assume OCTAL). .s .tp 5 /K:D:20.:15. .s will sort in descending ASCII order on the fifteen columns commencing at column 20 (decimal). .s .tp 4 /K:A:1:10.:D:20.:15. .s combines the two examples above, sorting first in ascending Ascii order on the first ten columns, then in descending ascii on the fifteen columns starting on column 20. .s .tp 5 /K:1:10.:30.:10. .s sorts in ascending ASCII order on the first ten columns first, then on the ten columns starting at column 30. .s .tp 8 /K:ALP:1:80. .s will sort in alphanumeric (or "dictionary") order on the first eighty columns. .x Alphanumeric order sort .x Dictionary order sort In this sort, upper and lower case are taken as equals, and any leading non-alphanumeric characters in the field specified will be ignored (unless there are no alphanumeric characters in the field). Thus "fred", "Fred", "FRED", and "*** Fred" will be treated as equal. .s .x Number of keys Up to ten keys may be used in any one sort (this is an assembly parameter in SORT.MAC, and can be extended if necessary - see later chapter). They may not overlap. Each key requires two values: the starting column, and the number of bytes in the key. An odd number of values specified will cause a key error. .s .x Default keys Should /K be omitted, the sort will be performed on the whole length of the record in ascending ASCII sequence. The length of the record is set using the /L switch, and defaults to 80 characters if /L is not used either. The default can be changed to alphanumeric sorting by using the /A switch. .s The default for /K alone is "/K:A:1:80.". .s If /K is used but /L is not used, the output records will be truncated after the end of the highest key, or column 80, whichever is the greater. .s 2 .i -10 /L:n Sets the maximum length of the records to be sorted. This is the .x Record Length number of bytes of DATA which will be read from the record (and therefore found in the output file), not counting the terminating and at the end of each record. Should /L be omitted, it defaults to the maximum column specified in a /K specification or 80, whichever is the lesser. .s .x Algorithm for SORT .x Sorting Algorithm [The sorting technique used by SORT, a replacement/selection algorithm, is excellent for speed, especially with double-buffering. However it is necessary for this type of sort to have a fixed space allocated in memory for each record, hence the maximum record size. Variable length records will however remain at their original length (except as per /P - see below) throughout the sorting process unless they exceed this specified maximum, in which case they will be truncated. Specifying /L in excess of what may be required will do no harm, though it may slow down the sort a little. If tag sorting be used (again see below) it is strongly recommended that /L be as accurate as possible, as otherwise the scratch files can be rather large!] .s 2 .tp 4 .x Assume alphabetic - /A .i -10;/A If no /K switch be specified, assume alphanumeric sort with default field specifications (/K:ALP:1:80. unless /L specified, when the "80." will take on the /L value). .s 2 .tp 8 .x Tagsort - /T .i -10;/T Performs a tag sort (see chapter 3) - a sort in which only the keys specified are relevant and the remainder of the record is discarded. The output file may contain the keys, or a sequence number (or both). The sequence number may either be a six digit number denoting which record in the input file should be in this position in that file if sorted, or a nine digit number denoting the starting position (six digits for block number, three digits for byte number) of the relevant input record. .s .tp 8 .ts 10,20,30 .x Tagsort - /T:S /T:type .s where .s type may be S, to output sequence numbers P, to output file position numbers or K, to output keys. .s S and K may be specified together (/T:S:K). The default for /T alone is /T:S. .s /T:S sequence numbers .br .x Tagsort - /T:P /T:P file position numbers .br .x Tagsort - /T:K /T:K keys .br /T:S:K - both sequence numbers _& keys .s 2 .x Input file as Scratch file .x Scratch file - use Input file .i -10;/R Use the input file as a scratch file, destroying it in the process and deleting it at the finish of the sort. This minimizes scratch file requirements, at the risk of destroying the input file if it has not been suitably backed up before the sort. A warning message will be typed, and the sort will not proceed unless the user confirms his intentions of using the input file as a scratch file. .s If the scratch space is insufficient (eg a tagsort putting sequence numbers plus the complete record as a key to the output file, generating a file larger than the original input file), it is possible for the sort to die partly completed, with the input file destroyed. Be warned! (In a normal non-tag sort, it is not possible to generate an output file larger than the input file.) .s 2 .tp 5 .i -10;/P Pad the records as they are read to be sorted with blanks to make each record the same length (/L value). .s 2 .x Dibol File Format .i -10;/D Use Dibol input _& output files. [You will only encounter these if you are an inveterate Dibol language user!] In this format the input data will be terminated by either the end of file or by a control-Z (sub, octal 32) character. The output file will be terminated by a control-Z. If a value be specified with this switch (/D:m, eg /D:1000.) the specified value will be the number of records to be sorted from the input file. Excess will be ignored. There is no support for multi-volume files. .s 2 .i -10;/H Type a HELP text of these switches. .ch Scratch Files .x Scratch File Allocation In the command string there are two positions available for scratch files. In any sort, up to two scratch files may be required. It is recommended that scratch files be placed on the fastest discs available to enhance the speed of the sort. The names of files provided as scratch files will not be used (the dummy names "#S1" and "#S2" are used - note the space in the name to prevent inadvertent scrubbing of any normal user files), and the files will be deleted at the end of the sort. Any size specifications used for these files will however be used, overriding the size calculated by SORT. Thus should the error message "Insufficient Disc Space Allocated" occur, larger scratch files can be allocated. .s If two scratch files are specified, SORT will use them if needed. No more than two sorting scratch files is ever needed. (Another temporary index file can be produced, but it is generally insignificant as regards size and speed.) If only one scratch file is specified, SORT will additionally use either the output file as a scratch file (if it be on a disc), or the input file if /R was specified. If needed, another scratch file will be allocated on device DK:. .s If no scratch file is specified, depending upon whether output and/or input files are available for scratch use, up to two scratch files will be allocated on device DK:. (eg TT:=SRC.TXT will allocate two scratch files as neither input nor output file is available for scratch use.) .s Tag sorts appear to require two scratch files in addition to the output file. .s It is a good idea to use the output file for scratch space, by having it on a disc, and by allocating only 1 other scratch file. This conserves storage and may increase the speed of the sort as if on the final merge the data is all in the output file as a scratch file, there is no need for a copy from a (different) scratch file. .ch Tag Sorting .x Tagsorts Sorting is usually performed using partial records ("keys") for the sorting, although most commonly inserting each complete input record in the output file. This is not always necessary. Sometimes it is useful to have the keys alone extracted and sorted, or merely a sequence indicating which input records would be in which position in a sorted file. .s Examples of the use of tag sorting (excuse my lack of imagination!): .s .lm +4 If you have a list of people occupying a building, and you wish to find unoccupied rooms. You are not interested in who is allocated to which room, just interested in finding unallocated rooms. Using a tag sort sorting on the room number as the key, and providing only the keys in the output (/T:K), you can go through the output looking for rooms which are missing from the list. .s If you have a large data file and you wish to be able to access it randomly (but it is a text file, not a Fortran random access file), you need an index with pointers to the information contained in it. Using a tag sort you can create a list of pointers to information in the file as though it had been sorted without actually producing a sorted version of it. Indeed using different keys it is possible to produce several indices for accessing the one file. Here the output from the tag sort could be merely a record sequence number (if all records are the same length, so a programme can calculate where in the file a particular record commences) using /T:S, or, if records differ in length, /T:P to give an actual starting position within the file. .lm -4 .s There are three options for the output from a tagsort. The output file may contain: .list .lm 4 .le;The keys on which the sorting was performed. The switch for this is /T:K. .le;A sequence number (seven digits) corresponding to the position of the record in the input file (first record 1, second record 2, etc). The switch for this is /T:S. .le;A sequence number (nine digits) corresponding to the position of the start of the record in the input file (six octal digits for block number, three for the byte on which the record starts). The switch for this is /T:P. .end list .lm 0 A combination of either of the sequence numbers and the keys is possible (eg /T:S:K - see the /T switch specification above). .s 2 .c;[Difficult bit!] .s During the sorting the sequence numbers and the keys are combined in the scratch files. To calculate the size required for scratch files, SORT uses the record length and the size of the input file. Should the input file consist of a large number of variable-length records such that there is a larger number of records than expected, this space reserved may be inadequate. This will require allocation of more scratch space by explicit inclusion of this with the scratch files in the command string. .ch;Chaining to SORT .x Chaining to SORT SORT may be chained to (and from), providing a facility for programmes requiring sorted data. .s If SORT has been chained to, it will take its commands from locations 510-777(octal). Each command must be terminated by a null (or a backslash - see below), and an extra null must follow the last command. In this mode the /R switch does not cause a warning message to be printed. .s To cause SORT to chain to another programme, use a command in the form .s .i 10;*!filename .s (default DK:filename.SAV). This should be the last specification in the list of commands passed in the chain area to SORT. On a normal return from SORT after a chain, location 510 will still contain the start of the command string passed to SORT. If it contain zero, an error has occurred, and the error message commences in location 512 (null terminated). .s For convenience of use from Fortran, the command string passed in a chain to SORT may have backslashes separating the lines of command. A double backslash terminates the list. .s Example: .br ------- .s This FORTRAN program is supplied on the distribution disc. It chains to SORT to produce the examples found earlier in this manual (chapter 1), then prints the sorted data. It also demonstrates the technique for error detection passed back from SORT. .s .nf c Demonstration Fortran Programme for SORT c c This programme is designed to be run from a copy of the SORT c distribution disc, with that disc assigned as device DK: c double precision area byte cmd(200),crlf(4) data area/12RDK SORT SAV/ if(ipeek("44).and."400)go to 100 c c Here we were not chained to. Commence generation of the data c Generate three files from SORT.DAT - FTN2.DAT, FTN3.DAT, and c FTN4.DAT. These units correspond to the Fortran DK: units. c type 1 1 format(' Generating Data'// *' In this demonstration SORT should produce an error,'/ *' as there is no file ERROR.DAT provided on the SORT'/ *' distribution disc.'//) c call scopy('ftn2=sort_\ftn3=sort/k:d:1:80._\ftn4=sort/a_\ *tt:=error_\!dk:demo_\_\',cmd) call chain(area,cmd,(len(cmd)+1)/2) stop 'Chain to SORT failed' c c Here we were chained to - ie return from SORT c 100 if(ipeek("510).ne.0)go to 200 c c Error returned from SORT c c Read the bytes returned commencing at location 510, c null terminated. type 101 101 format('0Error reported from SORT:') i="512 ii=1 102 j=ipeekb(i) if(j.eq.0)go to 120 cmd(ii)=j i=i+1 ii=ii+1 go to 102 120 type 121,(cmd(i),i=1,ii) 121 format(x80a1) type 122 122 format(/) c c c Type the sorted files c 200 type 2 2 format('0Ascending Sort:'//) call filprn(2) type 3 3 format('0Descending Sort:'//) call filprn(3) type 4 4 format('0Alphabetic Sort:'//) call filprn(4) call exit end .s Subroutine filprn(ifile) c Print the contents of a file on unit IFILE c byte line(82) data ispace/' '/ c 10 read(ifile,20,end=30)line 20 format(82a1) line(82)=0 call trim(line) type 20,ispace,(line(i),i=1,len(line)) go to 10 c 30 type 40 40 format(/) return end .f .Ch Error Messages .lm 10 .i -10;Illegal switch or value - Type /H for help. .i -10;No Input File .i -10;No Output File .br;SORT requires both an input and an output file. Only one input file (the first in a file spec) will be used. .i -10;File not found .i -10;Scratch Files must be on Discs .i -10;Chain File not found .i -10;Illegal Device .i -10;Command Syntax Error .br;Although it may not be reported, remember that any numbers specified for values with switches must have a decimal point following them if they are to be taken as decimal. .i -10;Key Error .i -10;Keys Overlap .i -10;Too Many Keys .br;SORT.SAV provided allows for up to ten sets of keys. .i -10;Insufficient memory .i -10;Fetch Error .i -10;Input Error .i -10;Output Error .i -10;Run-index file Input Error .br;An additional file may be used for storing internal information in particularly lengthy sorts. .i -10;Insufficient Disc Space .br;Not enough room to enter the scratch or output files. .i -10;Insufficient Disc Space Allocated .br;You will need to allocate additional scratch or output file space. .lm 0 .s [The following errors should not occur unless something is very wrong:] .lm 10 .i -10;Buffering Error .i -10;Records lost in Merge .i -10;Error deleting Input File .i -10;Error renaming Scratch File .i -10;Too Many Runs .s .i -10;/R will destroy your Input File. Are you sure? .br;This is not an error - it is what SORT types in response to the /R switch if SORT is being driven from a terminal (ie not chained to). It gives the user a chance to make sure he really means to destroy his input file. .lm 0 .Ch Assembling SORT .x Assembling SORT The command file SORT.COM is provided, and may be used by typing .s .i 10;_.ASSIGN dev1 LST .i 10;_.ASSIGN dev2 MAP .i 10;_.@SORT .s Where and are devices for the listing and map files respectively. .s A runnable version of SORT (SORT.SAV) is provided, and should be adequate for most sorting purposes. Different flavours of SORT can be produced should the user so desire. One parameter may be varied by prefixing SORT with a macro prefix file (DEFLEN), but changes to any other parameters require modifications to SORT.MAC. .s The parameters which may be varied are: .s .lm 10 .nf DEFLEN MAXMRG MAXKEY LEEWAY .f .x Assembly Parameters .x Parameters for Assembly .lm 5 .x DEFLEN - default /L .i -5;DEFLEN=80. .br is the default value for /L should /L not be specified by the user. .s .x MAXMRG - maximum order of merge .i -5;MAXMRG=30. .br is the default value for MAXMRG. It indicates the highest order order of merge of which SORT is capable. The maximum possible order of merge is 70. .s .x MAXKEY - maximum number of keys .x Keys - maximum number of - MAXKEY .x Number of keys, maximum - MAXKEY .i -5;MAXKEY=10. .br is the default value for MAXKEY. MAXKEY indicates the highest number of keys on which SORT can process a file. There is no upper limit to the number of keys which may be specified. .s .x LEEWAY - scratch file size .x Scratch file size - LEEWAY .i -5;LEEWAY=5. .br is the default value for LEEWAY. This is the most important parameter. SORT calculates the number of records in a file using the file-size from a .LOOKUP and the length of the records. From this it calculates the size of the scratch files and then increases the size of these by a certain percentage. LEEWAY is this percentage. Scratch files and output files are allocated LEEWAY percent oversize. .lm 0 .Ch Distribution The following files should be on the RT-11 distribution disk: .lm 5 .nf .s SORT .ABS (Abstract) SORT .RNO (RUNOFF Source for SORT.DOC) SORT .DOC (This document) .s SORT .MAC (Source files) DBIOR .MAC (Double buffered I/O routines) DBIOM. MAC (Macros for above) .s SORT .SAV (Executable program) .s DEMO .COM (Demonstration command file) SORT .DAT (Using this demo file) DEMO .FOR (Fortran demo programme - run DEMO .SAV from copy of distribution disc assigned as device DK:) .S SORT .DIS (Distribution command file) .lm 0 .ax .c;Ascii Codes .c;----------- .s 3 .lm 15 .ts 35,55 .nf space ! A a " B b _# C c $ D d % E e _& F f ' G g ( H h ) I i * J j + K k , L l - M m _. N n / O o 0 P p 1 Q q 2 R r 3 S s 4 T t 5 U u 6 V v 7 W w 8 X x 9 Y y : Z z ; [ { < _\ | = ] } > _^ ~ ? __ @ ` .number appendix I .ax .c;Index .c;----- .s 3 .lm 10;.rm +40 .print index