10/06/86 hash_ The hash_ subroutine is used to maintain a hash table. It contains entry points that initialize a hash table and insert, delete, and search for entries in the table. A hash table is used to locate entries in another data table when the length of the data table or the frequency with which its entries are referenced makes linear searching uneconomical. A hash table entry contains a name and a value. The name is a character string (of up to 32 characters) that is associated in some way with a data table entry. The value is a fixed binary number that can be used to locate that data table entry (for example, an array index or an offset within a segment). The entries in the hash table are arranged so that the location of any entry can be computed by applying a hash function to the corresponding name. It is possible for several names to hash to the same location. When this occurs, a linear search from the hash location to the first free entry is required, to find a place for a new entry (if adding), or to find out whether an entry corresponding to the name exists (if searching). The more densely packed the hash table, the more likely this occurrence is. To maintain a balance between efficiency and table size, hash_ keeps a hash table approximately 75 percent full, by rehashing it (i.e. rebuilding it in a larger space) when it becomes too full. The number of entries is limited only by the available space. The table uses eight words per entry plus ten words for a header. If an entire segment is available to hold the table, it can have over 32,000 entries. Entry points in hash_: (List is generated by the help command) :Entry: in: 10/06/86 hash_$in Function: This entry point adds an entry to a hash table. If the additional entry makes the table too full, the table is rehashed before the new entry is added (see the description of the rehash_ subroutine). Syntax: declare hash_$in entry (ptr, char(*), bit(36) aligned, fixed bin(35)); call hash_$in (table_ptr, name, value, code); Arguments: table_ptr is a pointer to the hash table. (Input) name is a name associated with a data table entry. It can be up to 32 characters long. (Input) value is the locator (e.g., index or offset) of the data table entry associated with name. (Input) code is a standard system error code with the following values: (Output) 0 entry added successfully. error_table_$segnamdup entry already exists, with same value. error_table_$namedup entry already exists, with different values. error_table_$full_hashtbl hash table is full and there is no room to rehash it into a larger space. :Entry: inagain: 10/06/86 hash_$inagain Function: This entry point adds an entry to a hash table. It is identical to the hash_$in entry except that it never tries to rehash the table. The new entry is added unless the table is completely full. This entry point is used by the rehash_ subroutine to avoid loops. It can also be used by an application that has a hash table embedded in a larger data base, where automatic rehashing would damage the data base. Syntax: declare hash_$inagain entry (ptr, char(*), bit(36) aligned, fixed bin(35)); call hash_$inagain (table_ptr, name, value, code); Arguments: table_ptr is a pointer to the hash table. (Input) name is a name associated with a data table entry. It can be up to 32 characters long. (Input) value is the locator (e.g., index or offset) of the data table entry associated with name. (Input) code is a standard system error code with the following values: (Output) 0 entry added successfully. error_table_$segnamdup entry already exists, with same value. error_table_$namedup entry already exists, with different values. error_table_$full_hashtbl hash table is full and there is no room to rehash it into a larger space. :Entry: make: 02/02/83 hash_$make Function: initializes an empty hash table. The caller must provide a segment to hold it, and must specify its initial size (see hash_$opt_size). Syntax: declare hash_$make entry (ptr, fixed bin, fixed bin(35)); call hash_$make (table_ptr, size, code); Arguments: table_ptr is a pointer to the table to be initialized. (Input) size is the initial number of entries. (Input). It is recommended that the value returned by hash_$opt_size be used. code is a standard status code. (Output). It can be: 0 if there is no error. error_table_$invalid_elsize if size is too large. :Entry: opt_size: 02/02/83 hash_$opt_size Function: This entry point, given the number of entries to be placed in a new hash table initially, returns the optimal size for the new table. This function is used when rehashing a full hash table, and should be used when making a new hash table. Syntax: declare hash_$opt_size entry (fixed bin) returns (fixed bin); size=hash_$opt_size (n_entries); Arguments: n_entries is the number of entries to be added. (Input) size is the optimal table size for that number of entries. (Output) :Entry: out: 10/06/86 hash_$out Function: This entry point deletes a name from the hash table. Syntax: declare hash_$out entry (ptr, char(*), bit(36) aligned, fixed bin(35)); call hash_$out (table_ptr, name, value, code); Arguments: table_ptr is a pointer to the hash table. (Input) name is the name to be deleted. (Input). Its maximum length is 32 characters. value is the locator value corresponding to name. (Input) code is a standard status code. (Output). It can be: 0 name was found and deleted. error_table_$noentry name was not found in the hash table. :Entry: search: 10/06/86 hash_$search Function: This entry point searches a hash table for a given name and returns the corresponding locator value. Syntax: declare hash_$search entry (ptr, char(*), bit(36) aligned, fixed bin(35)); call hash_$search (table_ptr, name, value, code); Arguments: table_ptr is a pointer to the hash table. (Input) name is the name to be searched for. (Input). It can be up to 32 characters long. value is the locator value corresponding to name. (Output) code is a standard status code. (Output). It can be: 0 name was found. error_table_$noentry name was not found in the hash table. ----------------------------------------------------------- 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