COMPILATION LISTING OF SEGMENT sort_branches Compiled by: Multics PL/I Compiler, Release 27d, of October 11, 1982 Compiled at: Honeywell LISD Phoenix, System M Compiled on: 11/15/82 1634.3 mst Mon Options: optimize map 1 /* *********************************************************** 2* * * 3* * Copyright, (C) Honeywell Information Systems Inc., 1982 * 4* * * 5* * Copyright (c) 1972 by Massachusetts Institute of * 6* * Technology and Honeywell Information Systems, Inc. * 7* * * 8* *********************************************************** */ 9 10 11 sort_branches: procedure(root, a_count); /* Procedure to sort branches in order of thier primary names. */ 12 13 /* This proc uses a singleton sort. It should be able to sort about 2**18 items . 14*If it bombs out on a lesser number there is a programming error. 15**/ 16 17 18 dcl 19 root ptr, 20 pp ptr, 21 (i, j, k, l, m, n, q, xi, xj, 22 xk, xl, xq) fixed bin, 23 (vxi, vxj, vxk, vxq, bp) ptr, 24 Cut fixed bin int static init(12), 25 stacki(18) fixed bin, 26 stackj(18) fixed bin, 27 a_count fixed bin, 28 count fixed bin; 29 1 1 /* include backup_dir_list */ 1 2 /* Created by R H Campbell. */ 1 3 /* Modified 15 June 1970, R H Campbell, 30 March l971, R A Tilden. */ 1 4 /* Last modified by Kobziar 2/10/75 to add access_class */ 1 5 /* Last modified by Greenberg 11/4/76 for vtoc_error bit */ 1 6 dcl 1 br (1000) based aligned, /* branch array returned by list_dir */ 1 7 2 (vtoc_error bit (1), /* Vtoc error on this entry */ 1 8 pad1 bit (1), uid bit (70), 1 9 pad2 bit (20), dtu bit (52), 1 10 pad3 bit (20), dtm bit (52), 1 11 pad4 bit (20), dtd bit (52), 1 12 pad5 bit (20), dtbm bit (52), 1 13 access_class bit (72), 1 14 dirsw bit (1), optionsw bit (2), bc bit (24), consistsw bit (2), mode bit (5), usage bit (2), 1 15 usagect bit (17), nomore bit (1), (cl, ml) bit (9), 1 16 acct bit (36), 1 17 (hlim, llim) bit (17), 1 18 multiple_class bit (1), pad7 bit (1), 1 19 (rb1, rb2, rb3) bit (6), pad8 bit (18), 1 20 (pad9, namerp) bit (18), 1 21 ix bit (18), dump_me bit (1), nnames bit (17)) unaligned; /* ix is pointer to i'th (sorted) entry. */ 1 22 1 23 dcl nnames fixed bin; /* Number of elements in name array. */ 1 24 1 25 dcl 1 name (1000 /* nnames */) based aligned, 1 26 2 size bit (17), 1 27 2 string character (32); 1 28 1 29 dcl 1 lk (1) based aligned, /* link array returned by list_dir */ 1 30 2 (pad1 bit (2), uid bit (70), 1 31 pad2 bit (20), dtu bit (52), 1 32 pad3 bit (20), dtm bit (52), 1 33 pad4 bit (20), dtd bit (52), 1 34 (pathnamerp, namerp) bit (18), 1 35 ix bit (18), dump_me bit (1), nnames bit (17)) unaligned; /* ix is pointer to i'th (sorted) entry. */ 1 36 1 37 dcl 1 path based (pp) aligned, /* path name structure from list_dir (one per link) */ 1 38 2 size bit (17), 1 39 2 author character(32), /* author of link, and */ 1 40 2 name character (168); /* path name. */ 1 41 1 42 dcl 1 old_path based (pp) aligned, /* path name as it existed prior to inclusion of author */ 1 43 2 size bit (17), 1 44 2 name character (168); 1 45 /* end backup_dir_list */ 30 31 32 33 dcl (addr, divide, null, ptr, rel) builtin; 34 35 36 /* Set up arrays of pointers to names and indices of pointers */ 37 38 if root = null then go to sort_ret; 39 40 bp = root; /* get pointer to first branch structure */ 41 count = a_count; /* copy the count of branches */ 42 43 begin; 44 dcl x (count) fixed bin; 45 46 do n = 1 to count; 47 x(n) = n; /* place index into index list */ 48 end; 49 50 n = n - 1; 51 52 i, m = 1; 53 j = n; 54 55 /* Now sort */ 56 57 /* Start by getting and ordering first middle and last elements in current list */ 58 /* Arrange indices accordingly since only they get sorted and set test value to middle value */ 59 60 sloop: 61 k = i; 62 l = j; 63 q = divide(i+j, 2, 17, 0); 64 65 xi = x(i); 66 xj = x(j); 67 xq = x(q); 68 69 vxi = ptr(bp, bp->br(xi).namerp); 70 vxj = ptr(bp, bp->br(xj).namerp); 71 vxq = ptr(bp, bp->br(xq).namerp); 72 73 74 75 if vxq->name(1).string < vxi->name(1).string then 76 77 if vxj->name(1).string < vxi->name(1).string then 78 79 if vxq->name(1).string < vxj->name(1).string then do; 80 x(i) = xq; 81 x(q) = xj; 82 x(j) = xi; 83 vxq = vxj; 84 end; 85 86 else do; 87 x(i) = xj; 88 x(j) = xi; 89 end; 90 91 else do; 92 x(i) = xq; 93 x(q) = xi; 94 vxq = vxi; 95 end; 96 97 else if vxj->name(1).string < vxq->name(1).string then 98 99 if vxi->name(1).string < vxj->name(1).string then do; 100 x(q) = xj; 101 x(j) = xq; 102 vxq = vxj; 103 end; 104 105 else do; 106 x(q) = xi; 107 x(i) = xj; 108 x(j) = xq; 109 vxq = vxi; 110 end; 111 112 /* Now order into lists above and below the test value */ 113 114 lloop: 115 l = l - 1; 116 xl = x(l); 117 118 119 120 if ptr(bp, bp->br(xl).namerp)->name(1).string > vxq->name(1).string then go to lloop; 121 122 kloop: 123 k = k + 1; 124 xk = x(k); 125 126 127 128 if ptr(bp, bp->br(xk).namerp)->name(1).string < vxq->name(1).string then go to kloop; 129 130 131 132 if k<=l then do; 133 x(k) = xl; 134 x(l) = xk; 135 go to lloop; 136 end; 137 138 139 140 /* now put the longer list on the stack, and try to sort the smaller.*/ 141 if l-iCut then go to sloop; 159 160 161 162 if i=1 then if ibr(xk).namerp); 171 bubble: l = k - 1; 172 xl = x(l); 173 if ptr(bp, bp->br(xl).namerp)->name(1).string <= vxk->name(1).string then go to ok; 174 x(k) = xl; 175 x(l) = xk; 176 k = l; 177 go to bubble; 178 ok: end; 179 180 /* Start work on the next list */ 181 182 183 m = m - 1; 184 185 186 if m=0 then go to thread; 187 188 189 i = stacki(m); 190 191 j = stackj(m); 192 193 194 195 go to test; 196 197 198 199 thread: /* store branch pointers in the store of the sorted primary names */ 200 do i = 1 to count; /* loop over all branches */ 201 xi = x(i); /* get index to next branch ordered by name */ 202 bp->br(i).ix = rel(addr(bp->br(xi))); /* place rel pointer in appropriate branch */ 203 end; 204 205 end; /* end begin block in which x array is declared */ 206 207 sort_ret: 208 return; 209 210 end; SOURCE FILES USED IN THIS COMPILATION. LINE NUMBER DATE MODIFIED NAME PATHNAME 0 11/15/82 1505.3 sort_branches.pl1 >dumps>old>recomp>sort_branches.pl1 30 1 12/07/76 1740.3 backup_dir_list.incl.pl1 >ldd>include>backup_dir_list.incl.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. Cut constant fixed bin(17,0) initial dcl 18 ref 156 a_count parameter fixed bin(17,0) dcl 18 ref 11 41 addr builtin function dcl 33 ref 202 bp 000124 automatic pointer dcl 18 set ref 40* 69 69 70 70 71 71 120 120 128 128 170 170 173 173 202 202 br based structure array level 1 dcl 1-6 set ref 202 count 000172 automatic fixed bin(17,0) dcl 18 set ref 41* 44 46 199 divide builtin function dcl 33 ref 63 i 000100 automatic fixed bin(17,0) dcl 18 set ref 52* 60 63 65 80 87 92 107 141 148 150* 156 162 162 167* 167 167* 168* 189* 199* 201 202* ix 22 based bit(18) array level 2 packed unaligned dcl 1-6 set ref 202* j 000101 automatic fixed bin(17,0) dcl 18 set ref 53* 62 63 66 82 88 101 108 141 143 144* 156 162 167 191* k 000102 automatic fixed bin(17,0) dcl 18 set ref 60* 122* 122 124 132 133 141 142 150 168* 169 171 174 176* l 000103 automatic fixed bin(17,0) dcl 18 set ref 62* 114* 114 116 132 134 141 144 149 171* 172 175 176 m 000104 automatic fixed bin(17,0) dcl 18 set ref 52* 142 143 148 149 153* 153 183* 183 186 189 191 n 000105 automatic fixed bin(17,0) dcl 18 set ref 46* 47 47* 50* 50 53 name based structure array level 1 dcl 1-25 namerp 21(18) based bit(18) array level 2 packed unaligned dcl 1-6 set ref 69 70 71 120 128 170 173 null builtin function dcl 33 ref 38 ptr builtin function dcl 33 ref 69 70 71 120 128 170 173 q 000106 automatic fixed bin(17,0) dcl 18 set ref 63* 67 81 93 100 106 rel builtin function dcl 33 ref 202 root parameter pointer dcl 18 ref 11 38 40 stacki 000126 automatic fixed bin(17,0) array dcl 18 set ref 142* 148* 189 stackj 000150 automatic fixed bin(17,0) array dcl 18 set ref 143* 149* 191 string 1 based char(32) array level 2 dcl 1-25 ref 75 75 75 75 75 75 97 97 97 97 120 120 128 128 173 173 vxi 000114 automatic pointer dcl 18 set ref 69* 75 75 94 97 109 vxj 000116 automatic pointer dcl 18 set ref 70* 75 75 83 97 97 102 vxk 000120 automatic pointer dcl 18 set ref 170* 173 vxq 000122 automatic pointer dcl 18 set ref 71* 75 75 83* 94* 97 102* 109* 120 128 x 000100 automatic fixed bin(17,0) array dcl 44 set ref 47* 65 66 67 80* 81* 82* 87* 88* 92* 93* 100* 101* 106* 107* 108* 116 124 133* 134* 169 172 174* 175* 201 xi 000107 automatic fixed bin(17,0) dcl 18 set ref 65* 69 82 88 93 106 201* 202 xj 000110 automatic fixed bin(17,0) dcl 18 set ref 66* 70 81 87 100 107 xk 000111 automatic fixed bin(17,0) dcl 18 set ref 124* 128 134 169* 170 175 xl 000112 automatic fixed bin(17,0) dcl 18 set ref 116* 120 133 172* 173 174 xq 000113 automatic fixed bin(17,0) dcl 18 set ref 67* 71 80 92 101 108 NAMES DECLARED BY DECLARE STATEMENT AND NEVER REFERENCED. lk based structure array level 1 dcl 1-29 nnames automatic fixed bin(17,0) dcl 1-23 old_path based structure level 1 dcl 1-42 path based structure level 1 dcl 1-37 pp automatic pointer dcl 18 NAMES DECLARED BY EXPLICIT CONTEXT. bubble 000362 constant label dcl 171 ref 177 kloop 000247 constant label dcl 122 ref 128 lloop 000224 constant label dcl 114 ref 120 135 ok 000416 constant label dcl 178 ref 173 sloop 000062 constant label dcl 60 ref 156 162 sort_branches 000010 constant entry external dcl 11 sort_ret 000462 constant label dcl 207 ref 38 test 000330 constant label dcl 156 ref 195 thread 000432 constant label dcl 199 ref 186 THERE WERE NO NAMES DECLARED BY CONTEXT OR IMPLICATION. STORAGE REQUIREMENTS FOR THIS PROGRAM. Object Text Link Symbol Defs Static Start 0 0 510 520 463 520 Length 676 463 10 142 25 0 BLOCK NAME STACK SIZE TYPE WHY NONQUICK/WHO SHARES STACK FRAME sort_branches 123 external procedure is an external procedure. begin block on line 43 71 begin block uses auto adjustable storage. STORAGE FOR AUTOMATIC VARIABLES. STACK FRAME LOC IDENTIFIER BLOCK NAME begin block on line 43 000100 x begin block on line 43 sort_branches 000100 i sort_branches 000101 j sort_branches 000102 k sort_branches 000103 l sort_branches 000104 m sort_branches 000105 n sort_branches 000106 q sort_branches 000107 xi sort_branches 000110 xj sort_branches 000111 xk sort_branches 000112 xl sort_branches 000113 xq sort_branches 000114 vxi sort_branches 000116 vxj sort_branches 000120 vxk sort_branches 000122 vxq sort_branches 000124 bp sort_branches 000126 stacki sort_branches 000150 stackj sort_branches 000172 count sort_branches THE FOLLOWING EXTERNAL OPERATORS ARE USED BY THIS PROGRAM. enter_begin leave_begin return alloc_auto_adj 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 000004 38 000015 40 000022 41 000025 43 000027 44 000032 46 000037 47 000047 48 000051 50 000053 52 000055 53 000060 60 000062 62 000065 63 000067 65 000072 66 000076 67 000101 69 000104 70 000114 71 000123 75 000132 80 000147 81 000152 82 000154 83 000156 84 000157 87 000160 88 000163 89 000165 92 000166 93 000171 94 000173 95 000174 97 000175 100 000205 101 000210 102 000212 103 000213 106 000214 107 000217 108 000221 109 000223 114 000224 116 000227 120 000233 122 000247 124 000251 128 000255 132 000270 133 000273 134 000275 135 000300 141 000301 142 000310 143 000313 144 000315 145 000317 148 000320 149 000323 150 000325 153 000327 156 000330 162 000335 167 000342 168 000347 169 000350 170 000353 171 000362 172 000366 173 000371 174 000405 175 000410 176 000413 177 000415 178 000416 183 000420 186 000422 189 000424 191 000426 195 000431 199 000432 201 000442 202 000445 203 000457 205 000461 207 000462 ----------------------------------------------------------- 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