COMPILATION LISTING OF SEGMENT hash_table Compiled by: Multics PL/I Compiler, Release 27d, of October 11, 1982 Compiled at: Honeywell LISD Phoenix, System M Compiled on: 11/12/82 1305.0 mst Fri Options: optimize map 1 /* *********************************************************** 2* * * 3* * Copyright, (C) Honeywell Information Systems Inc., 1982 * 4* * * 5* *********************************************************** */ 6 7 /* ****************************************************** 8* * * 9* * * 10* * Copyright (c) 1972 by Massachusetts Institute of * 11* * Technology and Honeywell Information Systems, Inc. * 12* * * 13* * * 14* ****************************************************** */ 15 16 hash_table: proc; /* originally coded by k.willis 2/71 */ 17 18 19 1 1 /* BEGIN INCLUDE FILE ... hashst.incl.pl1 */ 1 2 /* format: style4 */ 1 3 1 4 /* General Utility hash table */ 1 5 1 6 dcl 1 htable based (htp) aligned, /* hash table entries of level 2 are statistical info */ 1 7 2 nb fixed bin, /* number of buckets in hash table */ 1 8 2 ni fixed bin, /* number of entries used */ 1 9 2 np fixed bin, /* number of times hash_ called referincing this table */ 1 10 2 tnt fixed bin, /* total # of tries to find, enter, or delete an entry */ 1 11 2 id char (4), /* ht01 version 1 of hash_ */ 1 12 2 gnt fixed bin, /* greatest number of tries for search etc. */ 1 13 2 loht fixed bin (18) unsigned, /* length of hash table in words */ 1 14 2 pad bit (36) aligned, /* padding */ 1 15 2 buckets (1:hash_table_size_ refer (htable.nb)), /* 26111=((1024*255)/10 words per entry)-1 (8-word header) */ 1 16 3 name char (32) unaligned, /* identifier of entry */ 1 17 3 value bit (36) aligned, /* value corresponding to name */ 1 18 3 flags aligned, 1 19 4 ds bit (1) unal, /* deleted switch="1"b if deleted */ 1 20 4 empty bit (1) unal, 1 21 4 pad bit (34) unal, /* empty switch="1"b if empty */ 1 22 2 end_of_table bit (0) aligned; /* to get address */ 1 23 1 24 declare MAX_HT_BUCKETS_IN_SEG fixed bin init (26111) int static options (constant); 1 25 declare hash_table_size_ fixed bin; 1 26 1 27 /* END INCLUDE FILE ... hashst.incl.pl1 */ 20 21 22 23 24 dcl htp pointer; /* hash table pointer */ 25 dcl buffer char (152), /* input buffer string */ 26 1 input based (ip), /* input character array-overlays buffer */ 27 2 line (0: 151) char (1) unaligned, 28 (ip, q, ap) pointer, 29 abuffer char (152) aligned, 30 bit_count fixed bin (24), /* number of bits in hash table */ 31 len fixed bin, /* length of argument from console */ 32 more_needed bit (1), /* switch that indicates expected argument when on */ 33 (val, i, j, count, ec, al, buckets) fixed bin, 34 bc fixed bin init (152), /* number of characters in input line */ 35 hash_$in entry (ptr, char (*) aligned, fixed bin, fixed bin), 36 hash_$out entry (ptr, char (*) aligned, fixed bin, fixed bin), 37 hash_$search entry (ptr, char (*) aligned, fixed bin, fixed bin), 38 hash_$make entry (ptr, fixed bin, fixed bin), 39 ios_$read_ptr entry (ptr, fixed bin (17), fixed bin (17)), 40 cu_$arg_ptr entry (fixed bin, ptr, fixed bin, fixed bin), 41 aa fixed bin (35), 42 bchr char (al) based (ap) unaligned, /* character string for command args */ 43 (error_table_$segknown, error_table_$namedup, error_table_$noarg, error_table_$invalid_elsize) ext fixed bin (17), 44 error_table_$full_hashtbl ext fixed bin (17), 45 path char (168) aligned, 46 expand_path_ entry (ptr, fixed bin (17), ptr, ptr, fixed bin (17)), 47 com_err_ entry options (variable), 48 ioa_ entry options (variable), 49 hcs_$make_seg entry (char (*) aligned, char (*) aligned, char (*) aligned, fixed bin (5), 50 ptr, fixed bin), 51 hcs_$set_bc entry (char (*) aligned, char (*) aligned, fixed bin (24), fixed bin), 52 term_ entry (char (*) aligned, char (*) aligned, fixed bin), 53 cv_dec_ entry (char (*) aligned) returns (fixed bin (35)), 54 dn char (168) aligned, /* directory name */ 55 en char (32) aligned, /* entry name */ 56 chr char (1) aligned, /* request code */ 57 getback label local, 58 (srchname, addname) char (32) aligned; /* entry name and value to be passed to hash_ */ 59 dcl default fixed bin init (995), /* size of hash table if none given */ 60 max fixed bin init (6552); /* max number of buckets that will fit in one segment */ 61 62 dcl (substr, null, addr) builtin; 63 64 65 66 67 68 69 70 71 72 /* the hash_table command is used to create a hash table and to insert, delete, and search for entries in it. 73* 74* usage: hash_table path -nb- 75* where "path" specifies the name of an existing hash table or the name to be given to the hash table 76* created with "nb" buckets or entries. if "nb" is not specifiedor not within bounds(0 bchr, 1, al)); /* convert the decimal number to binary */ 114 if aa <= 0 then buckets = default; /* check range of buckets */ 115 else if aa>max then do; 116 buckets = max; /* buckets cannot be more than will fit in 1 segment */ 117 call ioa_ ("too many buckets: ^d maximum", max); /* print console message */ 118 end; 119 else buckets = aa; /* change precision of valid number of buckets */ 120 end; 121 bit_count = 36* (buckets*10+8); /* there are 36 bits in each word and 10 words in each bucket with 8 at top */ 122 call hcs_$set_bc (dn, en, bit_count, ec); /* set the bit count of segment created */ 123 if ec ^= 0 then go to err; 124 call hash_$make (q, buckets, ec); /* this entry initializes the created hash table */ 125 if ec ^= 0 then go to err; 126 end; 127 ip = addr (buffer); /* common to existing and new hash tables */ 128 129 130 131 132 next: 133 call ios_$read_ptr (ip, bc, count); /* get request */ 134 if count = 1 then go to next; /* nl character-try again */ 135 abuffer = buffer; /* align input */ 136 chr = substr (abuffer, 1, 1); /* treat first character as request code */ 137 138 139 140 141 if chr = "q" then do; /* quit */ 142 call term_ (dn, en, ec); /* remove segment from address space */ 143 if ec ^= 0 then go to err; 144 return; /* return to caller */ 145 end; 146 147 148 149 150 j = 1; /* the next char examined in input will be the second(input.line(j)) */ 151 more_needed = "1"b; /* 1 argument must be present */ 152 153 154 155 156 if chr = "s" then do; /* search */ 157 getback = s; /* set return label to s */ 158 go to getarg; /* get first argument */ 159 s: more_needed = "0"b; /* any further arguments are optional */ 160 call hash_$search (q, srchname, val, ec); /* entry point to find val of srchname */ 161 if ec ^= 0 then go to err2; /* could not find it */ 162 call ioa_ ("'^a' has value ^d", srchname, val); /* print the value */ 163 go to getarg; /* repeat the process if more arguments */ 164 end; 165 166 167 168 169 if chr = "d" then do; /* delete */ 170 getback = d; /* set ruturn label to d */ 171 go to getarg; /* get first argument */ 172 d: more_needed = "0"b; /* any further arguments are optional */ 173 call hash_$out (q, srchname, val, ec); /* entry point to delete srchname */ 174 if ec ^= 0 then go to err2; /* could not find it */ 175 else call ioa_ ("'^a' deleted with value ^d", srchname, val); /* print console message */ 176 go to getarg; /* repeat the process for any remaining arguments */ 177 end; 178 179 180 181 182 if chr = "a" then do; /* insert */ 183 getback = a; /* set return label to a */ 184 go to getarg; /* get first argument */ 185 a: more_needed = "1"b; /* two arguments are required for "a" and others must be in pairs */ 186 addname = srchname; /* save entry name in addname */ 187 getback = a2; /* set return label to a2 */ 188 go to getarg; /* get value corresponding to addname */ 189 a2: more_needed = "0"b; /* another argument is not required */ 190 aa = cv_dec_ (srchname); /* convert value to binary */ 191 val = aa; /* change the precision */ 192 call hash_$in (q, addname, val, ec); /* entry point to insert the entry and value in hash table */ 193 getback = a; 194 if ec = 0 then go to getarg; /* get any remaining arguments */ 195 go to err2; 196 end; 197 198 199 200 201 call ioa_ ("'^a' not a hash_table request", chr); /* invalid request */ 202 go to next; /* try again */ 203 204 205 206 207 208 209 getarg: do i = j to count-2 while (ip -> input.line (i) = " "); /* set i to point to first char in name and j to blank after */ 210 end; /* i points to first nonblank character */ 211 if i>count-2 then do; /* no argument existed */ 212 if more_needed then go to err1; /* print error message if argument expected */ 213 else go to next; /* otherwise get next request */ 214 end; 215 else do j = i+1 to count-2 while (ip -> input.line (j) ^= " "); 216 end; /* j now points to blank after name or nl character */ 217 if j-i>32 then do; /* maximum length of name is 32 characters */ 218 call ioa_ ("'^a' truncated to 32 characters", substr (abuffer, i+1, j-i)); /* print message */ 219 len = 32; /* continue the process with 32 characters */ 220 end; 221 else len = j-i; /* assign len the actual length if <32 characters */ 222 srchname = substr (abuffer, i+1, len); /* put name in srchname */ 223 go to getback; /* return to routine to process srchname */ 224 225 226 227 228 229 230 err1: ec = error_table_$noarg; /* expected argument missing */ 231 call com_err_ (ec, "hash_table", ""); /* common error message routine */ 232 go to next; /* get next request */ 233 err2: if ec = error_table_$full_hashtbl then go to err; /* if hash table was full or inefficient */ 234 call com_err_ (ec, "hash_table", ""); /* print message for all other errors */ 235 go to getarg; /* get any remaining arguments for request */ 236 end hash_table; SOURCE FILES USED IN THIS COMPILATION. LINE NUMBER DATE MODIFIED NAME PATHNAME 0 11/12/82 1045.5 hash_table.pl1 >spec>on>11/12/82>hash_table.pl1 20 1 04/21/82 1211.8 hashst.incl.pl1 >ldd>include>hashst.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. aa 000235 automatic fixed bin(35,0) dcl 25 set ref 113* 114 115 119 190* 191 abuffer 000154 automatic char(152) dcl 25 set ref 135* 136 218 218 222 addname 000410 automatic char(32) dcl 25 set ref 186* 192* addr builtin function dcl 62 ref 105 105 105 105 105 105 127 al 000232 automatic fixed bin(17,0) dcl 25 set ref 99* 104 105* 110* 113 113 113 113 ap 000152 automatic pointer dcl 25 set ref 99* 104 110* 113 113 bc 000234 automatic fixed bin(17,0) initial dcl 25 set ref 25* 132* bchr based char unaligned dcl 25 ref 104 113 113 bit_count 000222 automatic fixed bin(24,0) dcl 25 set ref 121* 122* buckets 000233 automatic fixed bin(17,0) dcl 25 set ref 111* 114* 116* 119* 121 124* buffer 000100 automatic char(152) unaligned dcl 25 set ref 127 135 chr 000372 automatic char(1) dcl 25 set ref 136* 141 156 169 182 201* com_err_ 000032 constant entry external dcl 25 ref 101 231 234 count 000230 automatic fixed bin(17,0) dcl 25 set ref 132* 134 209 211 215 cu_$arg_ptr 000022 constant entry external dcl 25 ref 99 110 cv_dec_ 000044 constant entry external dcl 25 ref 113 190 default 000420 automatic fixed bin(17,0) initial dcl 59 set ref 59* 111 114 dn 000310 automatic char(168) dcl 25 set ref 105 105 107* 122* 142* ec 000231 automatic fixed bin(17,0) dcl 25 set ref 99* 100 101* 105* 106 107* 109 110* 111 122* 123 124* 125 142* 143 160* 161 173* 174 192* 194 230* 231* 233 234* en 000362 automatic char(32) dcl 25 set ref 105 105 107* 122* 142* error_table_$full_hashtbl 000026 external static fixed bin(17,0) dcl 25 ref 233 error_table_$noarg 000024 external static fixed bin(17,0) dcl 25 ref 230 expand_path_ 000030 constant entry external dcl 25 ref 105 getback 000374 automatic label variable local dcl 25 set ref 157* 170* 183* 187* 193* 223 hash_$in 000010 constant entry external dcl 25 ref 192 hash_$make 000016 constant entry external dcl 25 ref 124 hash_$out 000012 constant entry external dcl 25 ref 173 hash_$search 000014 constant entry external dcl 25 ref 160 hcs_$make_seg 000036 constant entry external dcl 25 ref 107 hcs_$set_bc 000040 constant entry external dcl 25 ref 122 i 000226 automatic fixed bin(17,0) dcl 25 set ref 209* 209* 211 215 217 218 218 218 218 221 222 input based structure level 1 packed unaligned dcl 25 ioa_ 000034 constant entry external dcl 25 ref 117 162 175 201 218 ios_$read_ptr 000020 constant entry external dcl 25 ref 132 ip 000146 automatic pointer dcl 25 set ref 127* 132* 209 215 j 000227 automatic fixed bin(17,0) dcl 25 set ref 150* 209 215* 215* 217 218 218 221 len 000223 automatic fixed bin(17,0) dcl 25 set ref 219* 221* 222 line based char(1) array level 2 packed unaligned dcl 25 ref 209 215 max 000421 automatic fixed bin(17,0) initial dcl 59 set ref 59* 115 116 117* more_needed 000224 automatic bit(1) unaligned dcl 25 set ref 151* 159* 172* 185* 189* 212 null builtin function dcl 62 ref 108 path 000236 automatic char(168) dcl 25 set ref 104* 105 105 q 000150 automatic pointer dcl 25 set ref 107* 108 124* 160* 173* 192* srchname 000400 automatic char(32) dcl 25 set ref 160* 162* 173* 175* 186 190* 222* substr builtin function dcl 62 ref 113 113 136 218 218 222 term_ 000042 constant entry external dcl 25 ref 142 val 000225 automatic fixed bin(17,0) dcl 25 set ref 160* 162* 173* 175* 191* 192* NAMES DECLARED BY DECLARE STATEMENT AND NEVER REFERENCED. MAX_HT_BUCKETS_IN_SEG internal static fixed bin(17,0) initial dcl 1-24 error_table_$invalid_elsize external static fixed bin(17,0) dcl 25 error_table_$namedup external static fixed bin(17,0) dcl 25 error_table_$segknown external static fixed bin(17,0) dcl 25 hash_table_size_ automatic fixed bin(17,0) dcl 1-25 htable based structure level 1 dcl 1-6 htp automatic pointer dcl 24 NAMES DECLARED BY EXPLICIT CONTEXT. a 000702 constant label dcl 185 ref 183 193 a2 000713 constant label dcl 189 ref 187 d 000620 constant label dcl 172 ref 170 err 000141 constant label dcl 101 ref 106 108 123 125 143 233 err1 001125 constant label dcl 230 ref 212 err2 001155 constant label dcl 233 ref 161 174 195 getarg 001006 constant label dcl 209 ref 158 163 171 176 184 188 194 235 hash_table 000102 constant entry external dcl 16 ht 000112 constant entry external dcl 98 next 000450 constant label dcl 132 ref 134 202 213 232 s 000536 constant label dcl 159 ref 157 THERE WERE NO NAMES DECLARED BY CONTEXT OR IMPLICATION. STORAGE REQUIREMENTS FOR THIS PROGRAM. Object Text Link Symbol Defs Static Start 0 0 1372 1440 1206 1402 Length 1646 1206 46 171 163 0 BLOCK NAME STACK SIZE TYPE WHY NONQUICK/WHO SHARES STACK FRAME hash_table 336 external procedure is an external procedure. STORAGE FOR AUTOMATIC VARIABLES. STACK FRAME LOC IDENTIFIER BLOCK NAME hash_table 000100 buffer hash_table 000146 ip hash_table 000150 q hash_table 000152 ap hash_table 000154 abuffer hash_table 000222 bit_count hash_table 000223 len hash_table 000224 more_needed hash_table 000225 val hash_table 000226 i hash_table 000227 j hash_table 000230 count hash_table 000231 ec hash_table 000232 al hash_table 000233 buckets hash_table 000234 bc hash_table 000235 aa hash_table 000236 path hash_table 000310 dn hash_table 000362 en hash_table 000372 chr hash_table 000374 getback hash_table 000400 srchname hash_table 000410 addname hash_table 000420 default hash_table 000421 max hash_table THE FOLLOWING EXTERNAL OPERATORS ARE USED BY THIS PROGRAM. alloc_cs call_ext_out_desc call_ext_out return shorten_stack ext_entry THE FOLLOWING EXTERNAL ENTRIES ARE CALLED BY THIS PROGRAM. com_err_ cu_$arg_ptr cv_dec_ expand_path_ hash_$in hash_$make hash_$out hash_$search hcs_$make_seg hcs_$set_bc ioa_ ios_$read_ptr term_ THE FOLLOWING EXTERNAL VARIABLES ARE USED BY THIS PROGRAM. error_table_$full_hashtbl error_table_$noarg LINE LOC LINE LOC LINE LOC LINE LOC LINE LOC LINE LOC LINE LOC 25 000071 59 000073 16 000101 98 000110 99 000120 100 000137 101 000141 102 000166 104 000167 105 000174 106 000221 107 000223 108 000262 109 000266 110 000270 111 000307 113 000314 114 000341 115 000347 116 000351 117 000353 118 000373 119 000374 121 000375 122 000402 123 000427 124 000431 125 000444 127 000446 132 000450 134 000463 135 000466 136 000471 141 000474 142 000476 143 000517 144 000521 150 000522 151 000524 156 000526 157 000532 158 000535 159 000536 160 000537 161 000563 162 000565 163 000611 169 000612 170 000614 171 000617 172 000620 173 000621 174 000645 175 000647 176 000673 182 000674 183 000676 184 000701 185 000702 186 000704 187 000707 188 000712 189 000713 190 000714 191 000731 192 000733 193 000757 194 000762 195 000764 201 000765 202 001005 209 001006 210 001023 211 001025 212 001031 213 001033 215 001034 216 001052 217 001054 218 001057 219 001111 220 001114 221 001115 222 001120 223 001124 230 001125 231 001130 232 001154 233 001155 234 001160 235 001204 ----------------------------------------------------------- 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