COMPILATION LISTING OF SEGMENT speedtype_sort_ Compiled by: Multics PL/I Compiler, Release 26a, of September 3, 1980 Compiled at: Honeywell LISD Phoenix, System M Compiled on: 01/06/81 1250.0 mst Tue Options: optimize map 1 /* ****************************************************** 2* * * 3* * * 4* * Copyright, (C) Honeywell Information Systems * 5* * Inc., 1980. * 6* * * 7* * * 8* ****************************************************** */ 9 10 speedtype_sort_: procedure (arg_vector_ptr, arg_vector_size, arg_string_len); 11 12 /* This program is an internal interface of the Speedtype subsystem. 13* * Changed on 10/21/75 by Bill Silver to notescript_sort_. 14* * Changed on 06/13/77 by Bill Silver to speedtype_sort_. 15* * 16* * This program sorts symbols and expansions. 17* * It was taken from "sort_strings_". 18* * Algorithm 347 19* * AN EFFICIENT ALGORITHM FOR SORTING WITH MINIMAL STORAGE 20* * Richard C. Singleton 21* * CACM 12, Number 3, March 1969, pp. 185-7 22**/ 23 24 dcl arg_vector_ptr ptr; /* Pointer to array of string pointers. */ 25 dcl arg_vector_size fixed bin; /* Number of symbols to sort. */ 26 dcl arg_string_len fixed bin; /* Length of sort strings. */ 27 28 dcl vector_ptr ptr; /* Pointer to vector of pointers. */ 29 dcl vector_size fixed bin; /* Number of symbols. */ 30 dcl string_len fixed bin; /* Length of sort strings. */ 31 32 dcl 1 temp like vector_entry aligned; /* Work entry. */ 33 dcl 1 swap_temp like vector_entry aligned; /* Work entry. */ 34 35 dcl (depth, first, last, median, low, high) fixed bin; 36 37 dcl 1 stack (0:20) aligned, 38 2 first fixed bin, 39 2 last fixed bin; 40 41 dcl 1 vector (vector_size) based (vector_ptr) like vector_entry aligned; 42 43 dcl 1 vector_entry based aligned, 44 2 string_ptr ptr, 45 2 sbx fixed bin, 46 2 pad bit (36); 47 48 dcl string char (string_len) based; /* Template to reference strings. */ 49 50 dcl (divide) builtin; 51 /* */ 52 vector_ptr = arg_vector_ptr; /* Copy arguments. */ 53 vector_size = arg_vector_size; 54 string_len = arg_string_len; 55 56 depth = 0; 57 first = 1; 58 last = vector_size; 59 go to L4; 60 61 62 L1: median = divide (first + last, 2, 17, 0); 63 temp = vector (median); 64 low = first; 65 high = last; 66 67 if vector (first).string_ptr -> string > vector (median).string_ptr -> string 68 then do; 69 vector (median) = vector (first); 70 vector (first) = temp; 71 temp = vector (median); 72 end; 73 74 if vector (last).string_ptr -> string < vector (median).string_ptr -> string 75 then do; 76 vector (median) = vector (last); 77 vector (last) = temp; 78 temp = vector (median); 79 if vector (first).string_ptr -> string > vector (median).string_ptr -> string 80 then do; 81 vector (median) = vector (first); 82 vector (first) = temp; 83 temp = vector (median); 84 end; 85 end; 86 87 L2: do high = (high -1) by -1 while (vector (high).string_ptr -> string > temp.string_ptr -> string); 88 end; 89 90 do low = (low + 1) by 1 while (vector (low).string_ptr -> string < temp.string_ptr -> string); 91 end; 92 93 if low <= high 94 then do; 95 swap_temp = vector (high); 96 vector (high) = vector (low); 97 vector (low) = swap_temp; 98 go to L2; 99 end; 100 101 if (high - first) > (last - low) 102 then do; 103 stack.first (depth) = first; 104 stack.last (depth) = high; 105 first = low; 106 end; 107 else do; 108 stack.first (depth) = low; 109 stack.last (depth) = last; 110 last = high; 111 end; 112 113 depth = depth + 1; 114 115 L4: if (last - first) > 10 116 then goto L1; 117 118 if first = 1 119 then if first < last 120 then goto L1; 121 122 do first = (first + 1) to last; 123 temp = vector (first); 124 do low = first -1 by -1 while (vector (low).string_ptr -> string > temp.string_ptr -> string); 125 vector (low + 1) = vector (low); 126 end; 127 vector (low + 1) = temp; 128 end; 129 130 depth = depth - 1; 131 if depth >= 0 132 then do; 133 first = stack.first (depth); 134 last = stack.last (depth); 135 go to L4; 136 end; 137 138 end speedtype_sort_; SOURCE FILES USED IN THIS COMPILATION. LINE NUMBER DATE MODIFIED NAME PATHNAME 0 01/06/81 1247.6 speedtype_sort_.pl1 >spec>on>speed>speedtype_sort_.pl1 NAMES DECLARED IN THIS COMPILATION. IDENTIFIER OFFSET LOC STORAGE CLASS DATA TYPE ATTRIBUTES AND REFERENCES (* indicates a set context) NAMES DECLARED BY DECLARE STATEMENT. arg_string_len parameter fixed bin(17,0) dcl 26 ref 10 54 arg_vector_ptr parameter pointer dcl 24 ref 10 52 arg_vector_size parameter fixed bin(17,0) dcl 25 ref 10 53 depth 000114 automatic fixed bin(17,0) dcl 35 set ref 56* 103 104 108 109 113* 113 130* 130 131 133 134 divide builtin function dcl 50 ref 62 first 000122 automatic fixed bin(17,0) array level 2 in structure "stack" dcl 37 in procedure "speedtype_sort_" set ref 103* 108* 133 first 000115 automatic fixed bin(17,0) dcl 35 in procedure "speedtype_sort_" set ref 57* 62 64 67 69 70 79 81 82 101 103 105* 115 118 118 122* 122* 123 124* 133* high 000121 automatic fixed bin(17,0) dcl 35 set ref 65* 87* 87 87* 93 95 96 101 104 110 last 1 000122 automatic fixed bin(17,0) array level 2 in structure "stack" dcl 37 in procedure "speedtype_sort_" set ref 104* 109* 134 last 000116 automatic fixed bin(17,0) dcl 35 in procedure "speedtype_sort_" set ref 58* 62 65 74 76 77 101 109 110* 115 118 122 134* low 000120 automatic fixed bin(17,0) dcl 35 set ref 64* 90* 90 90* 93 96 97 101 105 108 124* 124* 125 125* 127 median 000117 automatic fixed bin(17,0) dcl 35 set ref 62* 63 67 69 71 74 76 78 79 81 83 stack 000122 automatic structure array level 1 dcl 37 string based char unaligned dcl 48 ref 67 67 74 74 79 79 87 87 90 90 124 124 string_len 000103 automatic fixed bin(17,0) dcl 30 set ref 54* 67 67 74 74 79 79 87 87 90 90 124 124 string_ptr based pointer array level 2 in structure "vector" dcl 41 in procedure "speedtype_sort_" set ref 67 67 74 74 79 79 87 90 124 string_ptr 000104 automatic pointer level 2 in structure "temp" dcl 32 in procedure "speedtype_sort_" set ref 87 90 124 swap_temp 000110 automatic structure level 1 dcl 33 set ref 95* 97 temp 000104 automatic structure level 1 dcl 32 set ref 63* 70 71* 77 78* 82 83* 123* 127 vector based structure array level 1 dcl 41 set ref 63 69* 69 70* 71 76* 76 77* 78 81* 81 82* 83 95 96* 96 97* 123 125* 125 127* vector_entry based structure level 1 dcl 43 vector_ptr 000100 automatic pointer dcl 28 set ref 52* 63 67 67 69 69 70 71 74 74 76 76 77 78 79 79 81 81 82 83 87 90 95 96 96 97 123 124 125 125 127 vector_size 000102 automatic fixed bin(17,0) dcl 29 set ref 53* 58 NAMES DECLARED BY EXPLICIT CONTEXT. L1 000031 constant label dcl 62 ref 115 118 L2 000153 constant label dcl 87 ref 98 L4 000270 constant label dcl 115 ref 59 135 speedtype_sort_ 000006 constant entry external dcl 10 THERE WERE NO NAMES DECLARED BY CONTEXT OR IMPLICATION. STORAGE REQUIREMENTS FOR THIS PROGRAM. Object Text Link Symbol Defs Static Start 0 0 416 426 370 426 Length 566 370 10 124 25 0 BLOCK NAME STACK SIZE TYPE WHY NONQUICK/WHO SHARES STACK FRAME speedtype_sort_ 128 external procedure is an external procedure. STORAGE FOR AUTOMATIC VARIABLES. STACK FRAME LOC IDENTIFIER BLOCK NAME speedtype_sort_ 000100 vector_ptr speedtype_sort_ 000102 vector_size speedtype_sort_ 000103 string_len speedtype_sort_ 000104 temp speedtype_sort_ 000110 swap_temp speedtype_sort_ 000114 depth speedtype_sort_ 000115 first speedtype_sort_ 000116 last speedtype_sort_ 000117 median speedtype_sort_ 000120 low speedtype_sort_ 000121 high speedtype_sort_ 000122 stack speedtype_sort_ THE FOLLOWING EXTERNAL OPERATORS ARE USED BY THIS PROGRAM. return ext_entry NO EXTERNAL ENTRIES ARE CALLED BY THIS PROGRAM. NO EXTERNAL VARIABLES ARE USED BY THIS PROGRAM. LINE LOC LINE LOC LINE LOC LINE LOC LINE LOC LINE LOC LINE LOC 10 000002 52 000013 53 000017 54 000021 56 000023 57 000024 58 000026 59 000030 62 000031 63 000035 64 000044 65 000046 67 000050 69 000064 70 000071 71 000075 74 000101 76 000112 77 000117 78 000123 79 000127 81 000137 82 000143 83 000147 87 000153 88 000170 90 000173 91 000207 93 000211 95 000214 96 000223 97 000230 98 000234 101 000235 103 000244 104 000251 105 000253 106 000255 108 000256 109 000263 110 000265 113 000267 115 000270 118 000274 122 000301 123 000307 124 000316 125 000335 126 000342 127 000345 128 000352 130 000354 131 000356 133 000360 134 000364 135 000366 138 000367 ----------------------------------------------------------- Historical Background This edition of the Multics software materials and documentation is provided and donated to Massachusetts Institute of Technology by Group BULL including BULL HN Information Systems Inc. as a contribution to computer science knowledge. This donation is made also to give evidence of the common contributions of Massachusetts Institute of Technology, Bell Laboratories, General Electric, Honeywell Information Systems Inc., Honeywell BULL Inc., Groupe BULL and BULL HN Information Systems Inc. to the development of this operating system. Multics development was initiated by Massachusetts Institute of Technology Project MAC (1963-1970), renamed the MIT Laboratory for Computer Science and Artificial Intelligence in the mid 1970s, under the leadership of Professor Fernando Jose Corbato. Users consider that Multics provided the best software architecture for managing computer hardware properly and for executing programs. Many subsequent operating systems incorporated Multics principles. Multics was distributed in 1975 to 2000 by Group Bull in Europe , and in the U.S. by Bull HN Information Systems Inc., as successor in interest by change in name only to Honeywell Bull Inc. and Honeywell Information Systems Inc. . ----------------------------------------------------------- Permission to use, copy, modify, and distribute these programs and their documentation for any purpose and without fee is hereby granted,provided that the below copyright notice and historical background appear in all copies and that both the copyright notice and historical background and this permission notice appear in supporting documentation, and that the names of MIT, HIS, BULL or BULL HN not be used in advertising or publicity pertaining to distribution of the programs without specific prior written permission. Copyright 1972 by Massachusetts Institute of Technology and Honeywell Information Systems Inc. Copyright 2006 by BULL HN Information Systems Inc. Copyright 2006 by Bull SAS All Rights Reserved