COMPILATION LISTING OF SEGMENT sort_strings_ Compiled by: Multics PL/I Compiler, Release 27d, of October 11, 1982 Compiled at: Honeywell LISD Phoenix, System M Compiled on: 11/18/82 1647.8 mst Thu Options: optimize map 1 /* *********************************************************** 2* * * 3* * Copyright, (C) Honeywell Information Systems Inc., 1981 * 4* * * 5* * Copyright (c) 1972 by Massachusetts Institute of * 6* * Technology and Honeywell Information Systems, Inc. * 7* * * 8* *********************************************************** */ 9 10 11 sort_strings_: proc (pm_Ap, pm_count); 12 13 /* 14* Algorithm 347 15* AN EFFICIENT ALGORITHM FOR SORTING WITH MINIMAL STORAGE 16* Richard C. Singleton 17* CACM 12, Number 3, March 1969, pp. 185-7 18* 19* Converted to Multics PL/I by Paul A. Green - April 6, 1974 20* 21* Modified to sort adjustable character strings instead of fixed binary numbers 22* by Jerry Stern - May 30, 1974 23* 24* Modified 10/19/77 by J. Stern to add $indirect entry 25**/ 26 27 /* Parameters */ 28 29 dcl pm_Ap ptr; /* ptr to array of string descriptors */ 30 dcl pm_count fixed bin (24); /* number of strings to sort */ 31 dcl pm_Ip ptr; /* ptr to array of "indirect" data */ 32 33 34 /* Automatic */ 35 36 dcl ind_sw bit (1) aligned; 37 dcl (Ap, Ip) ptr; 38 dcl (first, last, median, low, high) fixed bin (24); 39 dcl depth fixed bin; 40 41 dcl 1 stack (0:20) aligned, 42 2 first fixed bin (24), 43 2 last fixed bin (24); 44 45 dcl 1 A_temp aligned like A_entry; 46 47 dcl I_temp fixed bin (71); 48 49 50 /* Based */ 51 52 dcl cstring char (262144) based; 53 54 dcl 1 A_entry aligned based, 55 2 p ptr unal, 56 2 l fixed bin; 57 58 dcl 1 A (pm_count) aligned based (Ap) like A_entry; 59 60 dcl I (pm_count) fixed bin (71) based (Ip); 61 62 63 /* Builtins */ 64 65 dcl (divide, substr) builtin; 66 67 ind_sw = "0"b; 68 go to join; 69 70 71 indirect: entry (pm_Ap, pm_count, pm_Ip); 72 73 ind_sw = "1"b; 74 Ip = pm_Ip; 75 76 join: Ap = pm_Ap; 77 depth = 0; 78 first = 1; 79 last = pm_count; 80 go to L4; 81 82 83 L1: median = divide (first + last, 2, 24, 0); 84 low = first; 85 high = last; 86 87 if substr (A (first).p -> cstring, 1, A (first).l) > substr (A (median).p -> cstring, 1, A (median).l) 88 then call swap (first, median); 89 90 if substr (A (last).p -> cstring, 1, A (last).l) < substr (A (median).p -> cstring, 1, A (median).l) 91 then do; 92 call swap (last, median); 93 94 if substr (A (first).p -> cstring, 1, A (first).l) > substr (A (median).p -> cstring, 1, A (median).l) 95 then call swap (first, median); 96 97 end; 98 99 A_temp = A (median); 100 101 L2: do high = high -1 by -1 102 while (substr (A (high).p -> cstring, 1, A (high).l) > substr (A_temp.p -> cstring, 1, A_temp.l)); 103 end; 104 105 do low = low +1 by 1 106 while (substr (A (low).p -> cstring, 1, A (low).l) < substr (A_temp.p -> cstring, 1, A_temp.l)); 107 end; 108 109 if low <= high then do; 110 call swap (high, low); 111 go to L2; 112 end; 113 114 if (high - first) > (last - low) then do; 115 stack.first (depth) = first; 116 stack.last (depth) = high; 117 first = low; 118 end; 119 120 else do; 121 stack.first (depth) = low; 122 stack.last (depth) = last; 123 last = high; 124 end; 125 126 depth = depth +1; 127 128 L4: if (last - first) > 10 then go to L1; 129 130 if first = 1 then 131 if first < last then go to L1; 132 133 do first = first +1 to last; 134 A_temp = A (first); 135 if ind_sw then I_temp = I (first); 136 do low = first -1 by -1 137 while (substr (A (low).p -> cstring, 1, A (low).l) > substr (A_temp.p -> cstring, 1, A_temp.l)); 138 A (low +1) = A (low); 139 if ind_sw then I (low +1) = I (low); 140 end; 141 A (low +1) = A_temp; 142 if ind_sw then I (low +1) = I_temp; 143 end; 144 145 146 depth = depth -1; 147 if depth >= 0 then do; 148 first = stack.first (depth); 149 last = stack.last (depth); 150 go to L4; 151 end; 152 return; 153 154 155 swap: proc (i, j); 156 157 dcl (i, j) fixed bin (24); 158 dcl 1 A_swap aligned like A_entry; 159 dcl I_swap fixed bin (71); 160 161 162 A_swap = A (i); 163 A (i) = A (j); 164 A (j) = A_swap; 165 166 if ind_sw 167 then do; 168 I_swap = I (i); 169 I (i) = I (j); 170 I (j) = I_swap; 171 end; 172 173 end swap; 174 175 176 end sort_strings_; SOURCE FILES USED IN THIS COMPILATION. LINE NUMBER DATE MODIFIED NAME PATHNAME 0 11/18/82 1629.3 sort_strings_.pl1 >dumps>old>recomp>sort_strings_.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. A based structure array level 1 dcl 58 set ref 99 134 138* 138 141* 162 163* 163 164* A_entry based structure level 1 dcl 54 A_swap 000202 automatic structure level 1 dcl 158 set ref 162* 164 A_temp 000166 automatic structure level 1 dcl 45 set ref 99* 134* 141 Ap 000102 automatic pointer dcl 37 set ref 76* 87 87 87 87 90 90 90 90 94 94 94 94 99 101 101 105 105 134 136 136 138 138 141 162 163 163 164 I based fixed bin(71,0) array dcl 60 set ref 135 139* 139 142* 168 169* 169 170* I_swap 000204 automatic fixed bin(71,0) dcl 159 set ref 168* 170 I_temp 000170 automatic fixed bin(71,0) dcl 47 set ref 135* 142 Ip 000104 automatic pointer dcl 37 set ref 74* 135 139 139 142 168 169 169 170 cstring based char(262144) unaligned dcl 52 ref 87 87 90 90 94 94 101 101 105 105 136 136 depth 000113 automatic fixed bin(17,0) dcl 39 set ref 77* 115 116 121 122 126* 126 146* 146 147 148 149 divide builtin function dcl 65 ref 83 first 000106 automatic fixed bin(24,0) dcl 38 in procedure "sort_strings_" set ref 78* 83 84 87 87 87* 94 94 94* 114 115 117* 128 130 130 133* 133* 134 135 136* 148* first 000114 automatic fixed bin(24,0) array level 2 in structure "stack" dcl 41 in procedure "sort_strings_" set ref 115* 121* 148 high 000112 automatic fixed bin(24,0) dcl 38 set ref 85* 101* 101 101 101* 109 110* 114 116 123 i parameter fixed bin(24,0) dcl 157 ref 155 162 163 168 169 ind_sw 000100 automatic bit(1) dcl 36 set ref 67* 73* 135 139 142 166 j parameter fixed bin(24,0) dcl 157 ref 155 163 164 169 170 l 1 000166 automatic fixed bin(17,0) level 2 in structure "A_temp" dcl 45 in procedure "sort_strings_" set ref 101 105 136 l 1 based fixed bin(17,0) array level 2 in structure "A" dcl 58 in procedure "sort_strings_" set ref 87 87 90 90 94 94 101 105 136 last 000107 automatic fixed bin(24,0) dcl 38 in procedure "sort_strings_" set ref 79* 83 85 90 90 92* 114 122 123* 128 130 133 149* last 1 000114 automatic fixed bin(24,0) array level 2 in structure "stack" dcl 41 in procedure "sort_strings_" set ref 116* 122* 149 low 000111 automatic fixed bin(24,0) dcl 38 set ref 84* 105* 105 105 105* 109 110* 114 117 121 136* 136 136* 138 138 139 139* 141 142 median 000110 automatic fixed bin(24,0) dcl 38 set ref 83* 87 87 87* 90 90 92* 94 94 94* 99 p based pointer array level 2 in structure "A" packed unaligned dcl 58 in procedure "sort_strings_" set ref 87 87 90 90 94 94 101 105 136 p 000166 automatic pointer level 2 in structure "A_temp" packed unaligned dcl 45 in procedure "sort_strings_" set ref 101 105 136 pm_Ap parameter pointer dcl 29 ref 11 71 76 pm_Ip parameter pointer dcl 31 ref 71 74 pm_count parameter fixed bin(24,0) dcl 30 ref 11 71 79 stack 000114 automatic structure array level 1 dcl 41 substr builtin function dcl 65 ref 87 87 90 90 94 94 101 101 105 105 136 136 NAMES DECLARED BY EXPLICIT CONTEXT. L1 000046 constant label dcl 83 ref 128 130 L2 000155 constant label dcl 101 ref 111 L4 000257 constant label dcl 128 ref 80 150 indirect 000021 constant entry external dcl 71 join 000034 constant label dcl 76 ref 68 sort_strings_ 000006 constant entry external dcl 11 swap 000376 constant entry internal dcl 155 ref 87 92 94 110 THERE WERE NO NAMES DECLARED BY CONTEXT OR IMPLICATION. STORAGE REQUIREMENTS FOR THIS PROGRAM. Object Text Link Symbol Defs Static Start 0 0 514 524 460 524 Length 666 460 10 126 33 0 BLOCK NAME STACK SIZE TYPE WHY NONQUICK/WHO SHARES STACK FRAME sort_strings_ 137 external procedure is an external procedure. swap internal procedure shares stack frame of external procedure sort_strings_. STORAGE FOR AUTOMATIC VARIABLES. STACK FRAME LOC IDENTIFIER BLOCK NAME sort_strings_ 000100 ind_sw sort_strings_ 000102 Ap sort_strings_ 000104 Ip sort_strings_ 000106 first sort_strings_ 000107 last sort_strings_ 000110 median sort_strings_ 000111 low sort_strings_ 000112 high sort_strings_ 000113 depth sort_strings_ 000114 stack sort_strings_ 000166 A_temp sort_strings_ 000170 I_temp sort_strings_ 000202 A_swap swap 000204 I_swap swap 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 11 000002 67 000013 68 000014 71 000015 73 000026 74 000030 76 000034 77 000040 78 000041 79 000043 80 000045 83 000046 84 000052 85 000054 87 000056 90 000101 92 000121 94 000123 99 000146 101 000155 103 000174 105 000177 107 000214 109 000216 110 000221 111 000223 114 000224 115 000233 116 000240 117 000242 118 000244 121 000245 122 000252 123 000254 126 000256 128 000257 130 000263 133 000270 134 000276 135 000304 136 000312 138 000333 139 000340 140 000345 141 000350 142 000354 143 000360 146 000362 147 000364 148 000366 149 000372 150 000374 152 000375 155 000376 162 000400 163 000407 164 000416 166 000421 168 000425 169 000430 170 000432 173 000434 ----------------------------------------------------------- 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