COMPILATION LISTING OF SEGMENT strm_hash_ Compiled by: Multics PL/I Compiler, Release 28e, of February 14, 1985 Compiled at: Honeywell Multics Op. - System M Compiled on: 07/16/86 0854.1 mst Wed Options: optimize map 1 /****^ *********************************************************** 2* * * 3* * Copyright, (C) Honeywell Information Systems Inc., 1982 * 4* * * 5* * Copyright (c) 1978 by Massachusetts Institute of * 6* * Technology and Honeywell Information Systems, Inc. * 7* * * 8* * Copyright (c) 1972 by Massachusetts Institute of * 9* * Technology and Honeywell Information Systems, Inc. * 10* * * 11* *********************************************************** */ 12 13 14 15 /****^ HISTORY COMMENTS: 16* 1) change(85-09-24,Elhard), approve(85-09-24,MCR7198), 17* audit(86-06-30,Weaver), install(86-07-16,MR12.0-1094): 18* Improved documentation. 19* END HISTORY COMMENTS */ 20 21 22 /* External procedures to implement hash-coded lookup of 23* the STRINGMAP table (strm). 24* 25* Sept 1978, David Spector. */ 26 27 /* format: style3,^indnoniterdo */ 28 29 make_entry: 30 procedure (new_string, entry_nr); 31 32 /**********************************************************************/ 33 /* */ 34 /* Name: strm_hash_$make_entry */ 35 /* Input: new_string, entry_nr */ 36 /* Function: stores a new entry into the strm hash table. */ 37 /* Given a string (in ACC format) and the entry */ 38 /* number in the hash table, calculate the hash */ 39 /* function to determine the bucket and thread the */ 40 /* new entry into the appropriate bucket. */ 41 /* Each entry is a bit (18) relative offset in the */ 42 /* definition section of the new object segment */ 43 /* of a string (ACC format) being used in some */ 44 /* definition. The hash table (strm.hash_table) */ 45 /* contains fixed bin(17) array subscripts which */ 46 /* point to the first strm.entry in the particular */ 47 /* hash bucket of entries. Empty buckets are */ 48 /* represented by zeros in the hash table. Each */ 49 /* bucket contains a list of entries; the forward */ 50 /* thread for the list is an array subscript */ 51 /* (fixed bin(17)) in strm.entry.hash_thread for */ 52 /* each entry in the bucket. The end of the list */ 53 /* (or chain) of entries is marked by a hash thread */ 54 /* of zero. */ 55 /* Output: none */ 56 /* */ 57 /**********************************************************************/ 58 59 declare new_string char (*); /* new entry's string */ 60 declare trial_string char (*); 61 declare entry_nr fixed binary (17); /* array subscript (location) of new entry */ 62 63 declare hash_index fixed binary (34); /* array subscript of bucket in hash table */ 64 65 declare bx_$strmp external ptr; /* global base of strm */ 66 declare bx_$tdefp external ptr; /* global base of def section */ 67 68 declare p ptr; 69 declare defbase ptr; 70 71 declare (addrel, length, substr) 72 builtin; 73 74 declare acc_string char (257) based; 75 1 1 /* Include file bndtbl.incl.pl1 */ 1 2 1 3 1 4 /****^ HISTORY COMMENTS: 1 5* 1) change(85-09-24,Elhard), approve(85-09-24,MCR7198), 1 6* audit(86-06-30,Weaver), install(86-07-16,MR12.0-1094): 1 7* Added link_regeneration_table and eliminated the use of "p" as a pointer 1 8* to base structures on.. 1 9* END HISTORY COMMENTS */ 1 10 1 11 /* DIVERSE BINDER TABLES */ 1 12 1 13 /* Modified Oct 1978 by David Spector for hash coding snt and strm */ 1 14 /* Modified Dec 1978 by David Spector for making repatch table 1 15* automatically extensible */ 1 16 1 17 declare (sntp, adnp, odnp, rptp, rptep, strmp, lrtp) pointer; 1 18 1 19 /* The SEGNAME table - segnames and synonyms of all components */ 1 20 1 21 declare 1 snt aligned based(sntp), 1 22 2 hash_table (0:210) unaligned ptr, /* prime length */ 1 23 2 max_size fixed bin, /* size limit of allocated segname table */ 1 24 2 n_names fixed bin, /* number of segname-table entries used */ 1 25 2 entry(1000) like seg; 1 26 1 27 /* declaration of a SEGNAME entry */ 1 28 1 29 declare 1 seg aligned based, /* redeclaration of a single segname */ 1 30 2 name char(33) aligned, /* segname in ACC string format */ 1 31 2 lng fixed bin, /* length of segname, incl ACC count */ 1 32 2 addname fixed bin, /* 1-> add name to bound segment */ 1 33 2 defrel bit(18), /* offset in defs of new definition */ 1 34 2 comp pointer, /* pointer to associated component table */ 1 35 2 hash_thread ptr; /* thread to next "seg" in bucket */ 1 36 1 37 1 38 /* the ADDNAME table - list of names specified by "Addname" statement */ 1 39 1 40 declare 1 an aligned based(adnp), 1 41 2 max_size fixed bin, /* size limit of addname table */ 1 42 2 n_an fixed bin, /* number of names to add */ 1 43 2 syn(1000) char(32) aligned; /* contains the names to be added */ 1 44 1 45 1 46 /* The ODDNAME table - scratchpad memory to suppress redundant error messages */ 1 47 1 48 declare 1 od aligned based(odnp), 1 49 2 max_size fixed bin, /* max size of table */ 1 50 2 n_odds fixed bin, /* current size of table */ 1 51 2 entry(1000), 1 52 3 name char(289) aligned; 1 53 1 54 1 55 /* The REPATCH table - of halfwords to be relocated at a later time */ 1 56 1 57 declare 1 rpt aligned based(rptp), 1 58 2 thread unaligned ptr, /* To next rpt (null at end) */ 1 59 2 npt fixed bin, 1 60 2 entry(1000) like rpte aligned; 1 61 1 62 1 63 declare 1 rpte aligned based(rptep), /* declaration of single repatch table entry */ 1 64 2 poffset bit(18) unaligned, /* offset into text of word to be patched */ 1 65 2 pexpr bit(18) unaligned, /* value to add to patched halfword */ 1 66 2 halfword char(3) aligned, /* designates wordhalf to be patched */ 1 67 2 pbase char(1) unaligned, /* section designator of word to be patched */ 1 68 2 code char(1) unaligned; /* code of section base to be used as patch value */ 1 69 1 70 1 71 /* The STRINGMAP table - to avoid redundant strings in definition section */ 1 72 1 73 declare 1 strm aligned based(strmp), 1 74 2 hash_table (0:862) fixed bin(17), /* prime length */ 1 75 2 max_size fixed bin, 1 76 2 nstr fixed bin, 1 77 2 entry(2048) unaligned, 1 78 3 map bit(18), /* rel pointer to string in def section */ 1 79 3 hash_thread fixed bin(17); /* index of next strm.entry in hash bucket */ 1 80 1 81 /* The LINK_REGENERATION table - to flag links which have and */ 1 82 /* have not been regenerated to insure generation of all links */ 1 83 1 84 declare 1 lrt aligned based (lrtp), 1 85 2 count fixed bin, 1 86 2 start_offset fixed bin (18) unsigned, 1 87 2 regenerated (0 refer (lrt.count)) 1 88 bit (18) unaligned; 1 89 1 90 declare UNRESOLVED bit (18) static options (constant) init ("000000"b3); 1 91 declare INTERNALLY_RESOLVED bit (18) static options (constant) init ("777777"b3); 76 77 78 strmp = bx_$strmp; /* locate STRINGMAP table */ 79 call hash_code (new_string, hash_index); /* hash code the string */ 80 strm.entry (entry_nr).hash_thread = strm.hash_table (hash_index); 81 /* push new entry into hash-code bucket */ 82 strm.hash_table (hash_index) = entry_nr; 83 return; 84 85 lookup: 86 entry (trial_string, entry_nr); 87 88 /**********************************************************************/ 89 /* */ 90 /* Name: strm_hash_$lookup */ 91 /* Input: trial_string */ 92 /* Function: Given a string (trial_string) in ACC format, */ 93 /* compute the hash function on it, and compare the */ 94 /* trial string with each string in the bucket until */ 95 /* a match is found or the bucket is exhausted. If */ 96 /* the string is found, return the array subscript */ 97 /* of the strm.entry. If not found, return zero. */ 98 /* Output: entry_nr */ 99 /* */ 100 /**********************************************************************/ 101 102 strmp = bx_$strmp; /* locate STRINGMAP table */ 103 defbase = bx_$tdefp; /* locate base of def section */ 104 call hash_code (trial_string, hash_index); /* hash code the string */ 105 do entry_nr = strm.hash_table (hash_index) repeat strm.entry (entry_nr).hash_thread while (entry_nr ^= 0); 106 /* search the hash-code bucket for the string */ 107 p = addrel (defbase, strm.entry (entry_nr).map); 108 /* locate strm string */ 109 if substr (p -> acc_string, 1, length (trial_string)) = trial_string 110 then return; /* success: entry_nr is non-zero */ 111 end; /* continue scanning this bucket */ 112 return; /* failure: entry_nr is zero */ 113 114 hash_code: 115 procedure (char_string, hash_index); 116 117 /**********************************************************************/ 118 /* */ 119 /* Name: hash_code */ 120 /* Input: char_string */ 121 /* Function: given a character string, calculates the hash */ 122 /* function and returns the array index of the first */ 123 /* strm hash_table entry in the resulting bucket. */ 124 /* Output: hash_index */ 125 /* */ 126 /**********************************************************************/ 127 128 declare char_string char (*); /* input: string */ 129 declare hash_index fixed binary (34); /* output: subscript of hash bucket */ 130 131 declare pos fixed binary; 132 133 declare (bin, hbound, length, min, mod, unspec) 134 builtin; 135 136 hash_index = 0; 137 do pos = 1 to min (length (char_string), 24); /* prevent overflow of hash_index */ 138 hash_index = 2 * hash_index + bin (unspec (substr (char_string, pos, 1)), 9); 139 end; 140 hash_index = mod (hash_index, hbound (strm.hash_table, 1) + 1); 141 return; 142 end; /* end of hash_code */ 143 144 end; /* end of make_entry */ SOURCE FILES USED IN THIS COMPILATION. LINE NUMBER DATE MODIFIED NAME PATHNAME 0 07/16/86 0846.5 strm_hash_.pl1 >spec>install>1094>strm_hash_.pl1 76 1 07/16/86 0845.5 bndtbl.incl.pl1 >spec>install>1094>bndtbl.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. acc_string based char(257) unaligned dcl 74 ref 109 addrel builtin function dcl 71 ref 107 bin builtin function dcl 133 ref 138 bx_$strmp 000010 external static pointer dcl 65 ref 78 102 bx_$tdefp 000012 external static pointer dcl 66 ref 103 char_string parameter char unaligned dcl 128 ref 114 137 138 defbase 000104 automatic pointer dcl 69 set ref 103* 107 entry 1541 based structure array level 2 packed unaligned dcl 1-73 entry_nr parameter fixed bin(17,0) dcl 61 set ref 29 80 82 85 105* 105* 107* 111 hash_index 000100 automatic fixed bin(34,0) dcl 63 in procedure "make_entry" set ref 79* 80 82 104* 105 hash_index parameter fixed bin(34,0) dcl 129 in procedure "hash_code" set ref 114 136* 138* 138 140* 140 hash_table based fixed bin(17,0) array level 2 dcl 1-73 set ref 80 82* 105 140 hash_thread 1541(18) based fixed bin(17,0) array level 3 packed unaligned dcl 1-73 set ref 80* 111 hbound builtin function dcl 133 ref 140 length builtin function dcl 71 in procedure "make_entry" ref 109 length builtin function dcl 133 in procedure "hash_code" ref 137 map 1541 based bit(18) array level 3 packed unaligned dcl 1-73 ref 107 min builtin function dcl 133 ref 137 mod builtin function dcl 133 ref 140 new_string parameter char unaligned dcl 59 set ref 29 79* p 000102 automatic pointer dcl 68 set ref 107* 109 pos 000116 automatic fixed bin(17,0) dcl 131 set ref 137* 138* rpte based structure level 1 dcl 1-63 seg based structure level 1 dcl 1-29 strm based structure level 1 dcl 1-73 strmp 000106 automatic pointer dcl 1-17 set ref 78* 80 80 82 102* 105 107 111 140 substr builtin function dcl 71 ref 109 138 trial_string parameter char unaligned dcl 60 set ref 85 104* 109 109 unspec builtin function dcl 133 ref 138 NAMES DECLARED BY DECLARE STATEMENT AND NEVER REFERENCED. INTERNALLY_RESOLVED internal static bit(18) initial unaligned dcl 1-91 UNRESOLVED internal static bit(18) initial unaligned dcl 1-90 adnp automatic pointer dcl 1-17 an based structure level 1 dcl 1-40 lrt based structure level 1 dcl 1-84 lrtp automatic pointer dcl 1-17 od based structure level 1 dcl 1-48 odnp automatic pointer dcl 1-17 rpt based structure level 1 dcl 1-57 rptep automatic pointer dcl 1-17 rptp automatic pointer dcl 1-17 snt based structure level 1 dcl 1-21 sntp automatic pointer dcl 1-17 NAMES DECLARED BY EXPLICIT CONTEXT. hash_code 000150 constant entry internal dcl 114 ref 79 104 lookup 000056 constant entry external dcl 85 make_entry 000007 constant entry external dcl 29 THERE WERE NO NAMES DECLARED BY CONTEXT OR IMPLICATION. STORAGE REQUIREMENTS FOR THIS PROGRAM. Object Text Link Symbol Defs Static Start 0 0 274 310 224 304 Length 472 224 14 146 47 0 BLOCK NAME STACK SIZE TYPE WHY NONQUICK/WHO SHARES STACK FRAME make_entry 96 external procedure is an external procedure. hash_code internal procedure shares stack frame of external procedure make_entry. STORAGE FOR AUTOMATIC VARIABLES. STACK FRAME LOC IDENTIFIER BLOCK NAME make_entry 000100 hash_index make_entry 000102 p make_entry 000104 defbase make_entry 000106 strmp make_entry 000116 pos hash_code THE FOLLOWING EXTERNAL OPERATORS ARE USED BY THIS PROGRAM. return mod_fx1 ext_entry_desc NO EXTERNAL ENTRIES ARE CALLED BY THIS PROGRAM. THE FOLLOWING EXTERNAL VARIABLES ARE USED BY THIS PROGRAM. bx_$strmp bx_$tdefp LINE LOC LINE LOC LINE LOC LINE LOC LINE LOC LINE LOC LINE LOC 29 000003 78 000022 79 000025 80 000042 82 000051 83 000053 85 000054 102 000071 103 000075 104 000100 105 000116 107 000125 109 000133 111 000141 112 000147 114 000150 136 000161 137 000163 138 000175 139 000212 140 000214 141 000223 ----------------------------------------------------------- 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