|
DataMuseum.dkPresents historical artifacts from the history of: RC4000/8000/9000 |
This is an automatic "excavation" of a thematic subset of
See our Wiki for more about RC4000/8000/9000 Excavated with: AutoArchaeologist - Free & Open Source Software. |
top - metrics - download
Length: 31488 (0x7b00) Types: TextFile Names: »tmdsort «
└─⟦01e83a425⟧ Bits:30008166 Bånd med SW8010 og SW8500 source code └─⟦75ff9bef3⟧ └─⟦this⟧ »tmdsort «
mdsort jw 120272.18 changed by jw 18.08.1976 , vnc parameter and ordering of synonyms. changed by jw 21.01.1977 , treatment of parameters, scoping etc. changed by jw 4.11.1977 , abshalf changed by jw 1.01.1979 , spill.no changed by ib 20.07.1978 , sq file handling. begin comment \f Standard program mdsort page 1 Purpose. Mdsort, merge_disc_sort, is a sorting program for fast sorting of one disc file holding records of either fixed or variable length. File format. Records of fixed length are handled by means of inrec6/outrec6, records of variable length are handled by invar/outvar. The number of records of the file is either supplied by the sq system (content = 21) or given in the catalog entry of the input file: inputfile=set <segments> <disc name> <number of records> or by a special end of file record. Method. The program is based upon the external algol procedure mdsortproc. This procedure performs the sort in 2 phases: 1: The input file is read, and sorted strings of the maximum length are output consecutively in one area. 2: The strings generated in phase 1 are merged together in the needed number of passes. The procedure will optimize the sorting by variation of the number of passes, the blocklengths, and the number of shares, and by uti- lization of 2 disc stores if available. The mutual ordering of records with equal values in all keyfields, i.e. synonyms, is not changed by the sorting if the maximum record length is less than 2046. Requirements. The merge technique requires 2 backing storage areas able to hold the data. One of these areas can be the input file if the program is allowed to clear it. The job process must own at least 2 message buffers, but the computer can be utilized harder with a greater number, up to about 20, especially with great core size. The safe minimum core size is given in halfwords by the following expression: 12000 + 512*(inputblocklength + outputblocklength) + 4*maxlength + 48*noofkeys. The blocklengths are given in segments, (512 halfwords), and the maximum recordlength in halfwords. The minimum core size for blocklengths of 2 segments is thus about 15000 halfwords, but it is emphasized that this core size will give a very inefficient sort, 30000 to any size would be more appropriate, depending on the data volume. \f Standard program mdsort page 2 Example of program call. For a more exhaustive definition, see the next section. mdsort in.file1 out.file2 , input and output files block.2 , input and output blocklengths in , segments. var.34 , variable reclength, max 34 halfw. long.8 , first sorting criterion, ascending real.20.d , second, descending abshalf.11.16.d , criterion 3, 6 unsigned halfwords word.10 Program call definition. The program call consists of the following parts: mdsort <sortfiles> <sortspecifikation> Both <sortfiles> and <sortspecifikation> are groups of fp-parameters which will be defined in the sequel. Sortfiles. Fp-parameters defining input and output. <sortfiles>::= in.<input file> (.clear)0/1 out.<output file> (.<output disc> (.<scope>)0/1 )0/1 <input file>, <output file>, and <output disc>::= <name> <scope>::= temp ! login ! user ! project The signature 0/1 means that the preceding quantity can be omit- ted. The clear parameter defines, whether the input file should be cleared or not. The parameter may be necessary in connection with great data volumes. The output file is created by the program, and placed on the output disc, if this parameter is given. If the output disc is specified the scope of the output file will be either temp or the scope specified. If an output disc is not specified the name of the output file is looked up with two possible results: 1. A file with this name does not exist on scope temp to project. In this case the output scope will be temp and the disc for the output file is selected according to the most efficient sorting strategy. 2. A file with this name exists on scope temp to project. The name for the output disc and the scope for the output file is fetched from this file. In any case all files of the name of the output file on scope temp, login, or of a scope not greater than the scope selected for the output file, will be removed with a warning before the sorting starts (or in mdsortproc if it is the input file). \f Standard program mdsort page 3 Sortspecification. Fp-parameters defining the details of the sort. <sortspecification>::= block.<input blocklength>(.<output blocklength>)0/1 <fix or var>.<maxlength> ( eof.<eof 1>.<eof 2> )0/1 ( spill.<yes or no> )0/1 <keyfield> 1/n <input blocklength>, and <output blocklength>::= <integer> Two integers specifying the blocklengths of the input file and the final output file as a number of segments, (512 halfwords). The maximum blocklength is 40 segments. If only one integer is specified, this value is used as both input and output blocklength. <fix or var>::= fix ! var ! vnc Defines whether the records of the input file was created by outrec or by outvar. vnc means invar without checksum. <maxlength>::= <integer> Defines the fixed or the maximum length of a record measured in halfwords. It must be even, and not less than 2. It is important for the efficiency of the sort that maxlength is given as accurate as possible in case of variable record length. <eof 1>, and <eof 2>::= <integer> This parameter is mainly of historical significance and it is not recommendable for new systems. Normally the number of records contained in the input file should be either supplied by the sq system or given in the catalog entry: inputfile=set <segments> <disc> <number of records> But the end of the input file may for a non sq file be specified by a special record having <eof 1>, and <eof 2> as the values of the first 2 words of the user part of the record, i.e., halfword 1 to 4 of fixed length, and halfword 5 to 8 of variable length records. The number of sorted records is inserted in the catalog entry of the output file, and an end of file record is written at the end of the file if eof is used and not sq file. spill.<yes or no> With spill.no the standard check of integer and real overflow is switched off. But note that an overflow in the comparison of keys may yield an invalid sorting. \f Standard program mdsort page 4 <keyfield>::= <type>.<firstaddr> (.<lastaddr>)0/1 (.descending)0/1 This is the specification of one keyfield. The order of specification gives the priority of the keyfields. <type>::= half ! word ! long ! real ! abshalf The types correspond to the types 1 to 5 in the internal sorting system of rc8000 algol. <firstaddr> and <lastaddr>::= <integer> Specifies the position of the keyfield as for a field variable. The keyfield must be entirely within a maximum length record and only a half or abshalf keyfield may have an odd position. The keyfield consists of at least one simple field of the type specified. This field will have <firstaddr> as the field address. If <lastaddr> is used, it must have the value: <lastaddr> = <firstaddr> + (n - 1) * type_length where n is the number of simple keyfields and type_length the length of one simple field, 1, 2, or 4 halfwords. The composite keyfield counts as n in the calculation of number of keys (noofkeys). The maximum value of noofkeys is 50. .descending If the sorting order should be descending, this parameter must be used. Note on the syntax of the fp-parameters. The individual parametergroups may occur in any order. A parametergroup is defined as a sequence of parameters, separated by points. The last occurrence is used except for the keyfields, where all occurrences and their mutual ordering is significant. Only the first 3 characters of the keywords are checked, so for example output can be used instead of out and blok in- stead of block. For in and descending only the 2 first and the first cha- racter is checked, and for out and block the forms ud and segm are allowed. Variable length records. The sum check facility of invar is used during the reading of the input file, unless the parameter vnc is used instead of var. The record length must not excede maxlength, and it must be even. The record length must not be less than 4 and not less than the position of the first keyfield. Some of the keyfields of a short record may in fact be situated outside the record. Such a record is sorted as if all the bits of keyfields outside the record were equal to zero. \f Standard program mdsort page 5 Sq system files. If the content field of the catalog entry of the input file is equal to 21, it is supposed that the file conforms to the conventions of the sq file system. In this case, the block parameter is not necessary, and the eof parameter is irrelevant. The blocklength and number of records of the input file is supplied by the sq system (opensq). The output file will be created as an sq file, either with the same blocklength or with the blocklength specified. Printed output and the execution of the program. 1. The program call is listed on current output. Two different errorindications may be printed among the fp-parameters: <*> the preceding fp-parameter is illegal. <*< the preceding parametergroup is incomplete. 2. Alarms are printed if the accepted fp-parameters are incomplete. 3. The input file is looked up, and the name, the tail of its catalog entry, and its scope is printed. 4. If any errors have been detected up to this point, the run is stopped by a runtime alarm setting the ok-bit false. 5. All files of the name given for the output file which have to be removed before the sorting are looked up and shown in the same way as the input file, just before the removal. The first of these files may actually be the input file, it is not removed at this point but in mdsortproc as if the clear parameter had been used. 6. The text: sort start: is printed just before the call of the sorting procedure mdsortproc. 7. The sorting may be stopped by a runtime alarm from mdsortproc. 8. After return from mdsortproc the text: sort ok: is printed. 9. The output file is scoped and looked up. 10. The number of segments and records produced in the output file and the real time and the cpu time is shown. 11. If any errors occurred at 5. or 9. return is performed by a runtime alarm, otherwise the ok-bit will be true. \f Standard program mdsort page 6 Alarms. The possible alarmsources are multiple, but the user errors should be caught by either mdsort or mdsortproc. These alarms are preceded by the text: ***mdsort alarm: and ***mdsortproc alarm: respectively. ***mdsort alarm: error in fp-parameters: <n> wrong parametergroups in.<inputfile> not given out.<outputfile> not given block.<blocklength> not given fix, var or vnc.<maxlength> not given no keyspecifikation more than 50 keyfields negative number of records from tail(6) inputfile does not exist no resources for scope of outputfile monitor procedure: <n> result: <r> These alarms are supposed to explain themselves. The last one concerns peculiar results from calls of monitor procedures and should not occur. ***mdsortproc alarm: alarm text. alarm integer. comment param 1 wrong input blocklength. 3 wrong output blocklength. 5 wrong maxlength. 6 noofkeys > maxlength. keyfield keyfield no. illegal position of keyfield. infile tail(1) input file is not an area. r.length record length illegal variable length. remove monitor result input file cannot be cleared. size -lacking halfw. the size of the job must be in- creased so much before mdsortproc will do the sorting. disc -lacking entr. too few catalog entries in main catalog. segments not enough segments for one work file of this size. out disc -1 the output disc is not mounted. segments not room for file of this size on the output disc. integer...trap passnumber normally spill in key comparison. In addition alarms from opensq or stderror may occur if file or record formats are strongly illegal. The alarm r.length, and stderror alarms occurring during the reading of the input file are also preceded by a line, spe- cifying the number of input records accepted before the error was detected. \f ; own integer errors; integer content, explanation, noofrecs, outscope, result; integer array base(1:8), keydescr(1:50, 1:2), param(1:8); real cpu, eof, time, time1; real array files(1:6); \f procedure alarm(n); value n; integer n; comment the procedure prints an alarm line on current out and increases errors by one; begin write(out, <:<10>***mdsort alarm: :>); if n > 1000 then write(out, <:monitor procedure::>, n//1000, <: result::>, n mod 1000) else begin if n = 1 then begin write(out, <:error in fp-parameters: :>, errors); errors:= errors - 1; end fp-error; write(out, case n of( <: wrong parametergroups:>, <:in.<inputfile> not given:>, <:out.<outputfile> not given:>, <:block.<blocklength> not given:>, <:fix, var or vnc.<maxlength> not given:>, <:no keyspecifikation:>, <:more than 50 keyfields:>, <:negative number of records from tail(6):>, <:inputfile does not exist:>, <:no resources for scope of outputfile:>) ); end not monitor call error; outchar(out, 10); errors:= errors + 1; end alarm; \f procedure look_remove_scope(situation); value situation; integer situation; comment situation 1 lookup the inputfile, return noofrecs and blocklength if content = 20, bs system, or 21, sq system 2 lookup the outputfile before the sorting. if outscope = 0 then get outdisc and outscope from this file. remove all files of this name with scope temp, login or with scope <= outscope. 3 scope the final output file if outscope > 1 and look it up. ; begin boolean catbase_changed; integer i, i1, i2, look_scope, pos; integer array entry(1:17); long array field disc, name; zone z, znull(1, 1, stderror); catbase_changed:= false; disc:= 16; <* comment discname in entry after lookup head and tail *> name:= if situation = 1 then 0 else 8; <* filename in files *> open(z, 0, files.name, 0); if situation = 3 then begin comment scope the final output file if outscope > temp; if outscope > 1 then begin comment set permanent key to login or perm; i:= monitor(50, z, if outscope = 2 then 2 else 3, entry); if i <> 0 then alarm(if i = 6 then 10 <* no resources *> else 50000 + i) else if outscope > 2 then begin comment set entry base to user or project; for i:= 1 step 1 until 2 do entry(i):= base(if outscope = 3 then i+4 else i+6); i:= monitor(74, z, 0, entry); if i <> 0 then alarm(74000 + i); end set entry base; end scope > temp; end situation = 3, final outputfile; \f lookup: i:= monitor(76, z, 0, entry); if i <> 0 then begin comment file does not exist, only allowed in situation 2; if i = 3 and situation = 1 then alarm(9) <* inputfile not found *> else if i = 3 and situation = 2 then goto return else alarm(76000 + i); end lookup not ok else begin comment lookup ok, find the scope; i1:= entry(2); i2:= entry(3); look_scope:= 6; <* undefined *> case entry(1) extract 3 + 1 of begin <* key 0 *> if i1 = base(3) and i2 = base(4) then look_scope:= 1; <* temp *> <* key 1, not used *> ; <* key 2 *> if i1 = base(3) and i2 = base(4) then look_scope:= 2; <* login *> <* key 3 *> if i1 = base(5) and i2 = base(6) then look_scope:= 3 <* user *> else if i1 = base(7) and i2 = base(8) then look_scope:= 4 <* proj. *> else if i1 <= extend base(7) and i2 >= extend base(8) then look_scope:= 5; <* system *> end case permanent key; if situation = 2 then begin if outscope = 0 <* no outdisc specified *> and look_scope <= 4 <* not scope system *> then begin comment fetch outdisc and outscope from the file; for i:= 1 step 1 until 2 do files(i+4):= real entry.disc(i); outscope:= look_scope; end outdisc not specified; if look_scope > out_scope and look_scope > 2 and look_scope <> 6 <* *** *> then goto return; end outputfile before the sort; \f comment print the filedescriptor; pos:= write(out, case situation of( <:input : :>, <:remove: :>, <:output: :>), files.name); pos:= pos + write(out, false add 32, 19 - pos, <:=set:>, << ddddd>, entry(8), <: :>, entry.disc); pos:= pos + write(out, false add 32, 38 - pos, << dddddd.dddd>, systime(6, entry(13), time1) + time1/1000000, << ddddd>, entry(14), << dddd>, entry(15)) + (if entry(16) <= 4095 then write(out, << dddd>, entry(16)) else write(out, << d>, entry(16) shift(-12), <:.:>, <<d>, entry(16) extract 12)); write(out, false add 32, 62 - pos, << d>, entry(17), <:; :>, case look_scope of( <:temp:>, <:login:>, <:user:>, <:project:>, <:system:>, <:***:>), <:<10>:>); if situation = 1 then begin comment fetch noofrecs etc. from the tail; content:= entry(16) shift(-12); if content <> 20 and content <> 21 then content:= 0; if content = 20 then begin comment fetch blocklength from tail; param(1):= entry(16) extract 12; end content 20, bs system; if content = 21 then noofrecs:= 0 else if content = 20 or noofrecs = 0 then begin comment fetch noofrecs from tail; noofrecs:= entry(13); if noofrecs < 0 then alarm(8); end bs system or not eof; end situation = 1; if situation = 2 then begin comment remove the file and goto lookup; if -,catbase_changed and files(1) = files(3) and files(2) = files(4) then begin comment it is the input file so it must not be removed now; param(2):= 1; <* it is removed in mdsortproc *> if look_scope < outscope then begin comment the lookup must continue with an increased catbase; for i:= 1 step 1 until 2 do entry(i):= base((if look_scope <= 2 then 4 <* user *> else 6 <* proj *>) + i); open(znull, 0, <::>, 0); <* necessary for set catbase *> i:= monitor(72, znull, 0, entry); <* set catalog base *> catbase_changed:= true; if i <> 0 then alarm(72000 + i) else goto lookup; end look_scope < outscope; end the input file has to be removed else begin i:= monitor(48, z, 0, entry); <* remove entry *> if i <> 0 then alarm(48000 + i) else if look_scope < outscope then goto lookup; end remove the file; end situation = 2; end lookup ok; return: if catbase_changed then begin i:= monitor(72, znull, 0, base); <* set catbase back *> if i <> 0 then alarm(72000 + i); end catbase_changed; end look_remove_scope; \f begin comment block for the reading of the fp-parameters; integer firstaddr, i, int, item, keyparamno, lastaddr, noofkeys, paramno, position, separator, type, type_length; real n1; real array name(1:2); procedure alarm_fp; comment prints an error indication after the last fp-parameter, and skips to the beginning of the next parametergroup or to the end of the fp-parameters; begin integer i; errors:= errors + 1; position:= position + write(out, if separator = 1 and item = 2 and paramno > keyparamno then <:<*<60>:> else <:<*>:>); for i:= i while separator <> 4 <* end *> and (separator <> 1 or keyparamno = paramno) do nextfp; goto take_parameter_group; end alarm_fp; \f procedure nextfp; comment the procedure reads and lists the next fp-parameter. global quantities: separator 1: <s>, 2: =, 3: <point>, 4: <end of param>. 0: <newline>. item 1: <integer>, 2: <name>. paramno the number of the preceding parameter, it is in- creased by one in the procedure. int will contain an integer parameter. name will contain a name parameter. n1 n1 = name(1) shift(-24) shift 24. ; begin integer i; paramno:= paramno + 1; i:= system(4, paramno, name); item:= if i extract 12 = 4 then 1 else 2; if item = 1 then int:= name(1); i:= i shift (-12); separator:= if i = 4 then 1 else if i = 6 then 2 else if i = 8 then 3 else if i = 2 then 0 else 4; comment print the separator and the item; if separator <> 4 then begin if position > 59 then position:= write(out, <:,<10> :>) - 2; if separator > 0 then position:= position + write(out, case separator of(<: :>, <:=:>, <:.:>)); i:= 1; case item of begin position:= position + write(out, <<d>, int); position:= position + write(out, string name(increase(i))); end item; n1:= name(1) shift(-24) shift 24; <* only 3 characters *> end some param; end nextfp; \f comment read the parameters by means of procedure nextfp; for i:= 1 step 1 until 7 do param(i):= 0; for i:= 1 step 1 until 6 do files(i):= real<::>; noofrecs:= noofkeys:= outscope:= 0; paramno:= keyparamno:= -1; position:= errors:= 0; outchar(out, 10); nextfp; <* this call takes and lists the programname *> nextfp; <* this call reads the first parameter *> take_parameter_group: if separator = 4 then goto end_reading; keyparamno:= paramno; <* see procedure alarm_fp *> if separator <> 1 or item <> 2 then alarm_fp; if n1 shift(-32) = real<:in:> shift(-32) then begin comment in.<inputfile>(.clear)0/1; nextfp; if separator <> 3 or item <> 2 then alarm_fp; for i:= 1, 2 do files(i):= name(i); param(2):= 0; nextfp; for i:= i while separator = 3 and item = 2 do begin if n1 = real<:cle:> then param(2):= 1 else alarm_fp; nextfp; end; end input file else \f if n1 = real<:out:> or n1 = real<:ud:> then begin comment out.<outputfile>(.<outdisc>(.<outscope>)0/1)0/1; nextfp; if separator <> 3 or item <> 2 then alarm_fp; for i:= 3, 4 do files(i):= name(i-2); comment <.<output disc> >0/1; nextfp; files(5):= real <::>; outscope:= 0; <* temp, outdisc not specified *> if separator = 3 then begin if item <> 2 then alarm_fp; for i:= 5, 6 do files(i):= name(i-4); nextfp; outscope:= 1; <* temp, outdisc specified *> if separator = 3 and item = 2 then begin outscope:=if n1 = real<:tem:> then 1 else if n1 = real<:log:> then 2 else if n1 = real<:use:> then 3 else if n1 = real<:pro:> then 4 else -1; if outscope < 0 then alarm_fp; nextfp; end take scope; end output disc; end out else if n1 = real<:blo:> or n1 = real<:seg:> then begin comment take block.<inputbl.length>.<outputbl.length>0/1; nextfp; if separator <> 3 or item <> 1 then alarm_fp; param(1):= param(3):= int; nextfp; if separator = 3 and item = 1 then begin param(3):= int; nextfp; end output blocklength; end block else \f if n1 = real<:fix:> or n1 = real<:var:> or n1 = real<:vnc:> then begin comment <fix or var>.<maxlength>; if n1 = real <:fix:> then param(4):= 1 else if n1 = real <:var:> then param(4):= 0 else param(4):= 2; comment .<maxlength>; nextfp; if separator <> 3 or item <> 1 then alarm_fp; param(5):= int; nextfp; end record format else if n1 = real<:eof:> then begin comment eof.<eof 1>.<eof 2> ; for i:= 1, 2 do begin nextfp; if separator <> 3 or item <> 1 then alarm_fp; eof:= eof shift 24 add int; end eof 1, eof 2; nextfp; noofrecs:= -1; end eof else if n1 = real<:spi:> then begin nextfp; if separator <> 3 or item <> 2 then alarm_fp; if n1 = real<:yes:> then else if n1 = real<:no:> then begin spill_no; overflows:= underflows:= 0; end else alarm_fp; nextfp; end spill else if n1 = real<:hal:> or n1 = real<:byt:> then begin type:= 1; goto key end else if n1 = real<:wor:> then begin type:= 2; goto key end else if n1 = real<:lon:> then begin type:= 3; goto key end else \f if n1 = real<:rea:> then begin type:= 4; goto key end else if n1 = real<:abs:> then begin type:= 5; key: type_length:= case type of(1, 2, 4, 4, 1); comment .<firstaddr> (.<lastaddr>)0/1; nextfp; if separator <> 3 or item <> 1 then alarm_fp; firstaddr:= lastaddr:= int; nextfp; if separator = 3 and item = 1 then begin lastaddr:= int; i:= lastaddr - firstaddr; if i < 0 or i mod type_length <> 0 then alarm_fp; nextfp; end lastaddr; comment <.d>0/1; if separator = 3 then begin if item <> 2 or n1 shift(-40) shift 40 <> real <:d:> then alarm_fp; type:= -type; nextfp; end; for firstaddr:= firstaddr, firstaddr + type_length while firstaddr <= lastaddr do begin noofkeys:= noofkeys + 1; if noofkeys <= 50 then begin keydescr(noofkeys, 1):= type; keydescr(noofkeys, 2):= firstaddr; end; end for firstaddr; end keyspecifikation else \f if n1 = real<:tes:> then begin nextfp; param(8):= int; nextfp; end test else alarm_fp; goto take_parameter_group; endreading: write(out, <:<10>:>); param(6):= noofkeys; end block for reading of fp-parameters; \f comment fetch catalog bases for proc. look_remove_scope; system(11, 0, base); comment check that the parameters are sufficient; if errors > 0 then alarm(1); if files(1) = real<::> then alarm(2); if files(3) = real<::> then alarm(3); <* param(1) cannot be checked before lookup of inputfile *> if param(5) = 0 then alarm(5); if param(6) = 0 then alarm(6); if param(6) > 50 then alarm(7); if files(1) <> real<::> then look_remove_scope(1); if param(1) = 0 and content <> 21 then alarm(4); <* note that param(1) may be fetched from the inputfile *> comment now the parameters have been read, the final checking is done in mdsortproc; if errors > 0 then system(9, errors, <:<10>errors :>); \f param(7):= 1; <* makes mdsortproc return with ok result only *> look_remove_scope(2); write(out, <:sort start:<10>:>); cpu:= systime(1, 0, time); mdsortproc(param, keydescr, files, eof, noofrecs, result, explanation); cpu:= systime(1, time, time) - cpu; write(out, <:sort ok:<10>:>); look_remove_scope(3); comment sort was ok, print end report; write(out, <:sorted: segments::>, << ddddd>, explanation, <: records::>, << dddddd>, noofrecs, <:<10>seconds: real::>, << ddddd>, time, <: cpu::>, << dddddd>, cpu, <:<10>:>); if errors > 0 then system(9, errors, <:<10>errors: :>); end ▶EOF◀