1 10/06/86  hash_
  2 
  3 
  4 The hash_ subroutine is used to maintain a hash table.  It contains
  5 entry points that initialize a hash table and insert, delete, and
  6 search for entries in the table.
  7 
  8 A hash table is used to locate entries in another data table when the
  9 length of the data table or the frequency with which its entries are
 10 referenced makes linear searching uneconomical.
 11 
 12 A hash table entry contains a name and a value.  The name is a
 13 character string (of up to 32 characters) that is associated in some
 14 way with a data table entry.  The value is a fixed binary number that
 15 can be used to locate that data table entry (for example, an array
 16 index or an offset within a segment).  The entries in the hash table
 17 are arranged so that the location of any entry can be computed by
 18 applying a hash function to the corresponding name.
 19 
 20 
 21 It is possible for several names to hash to the same location.  When
 22 this occurs, a linear search from the hash location to the first free
 23 entry is required, to find a place for a new entry (if adding), or to
 24 find out whether an entry corresponding to the name exists (if
 25 searching).  The more densely packed the hash table, the more likely
 26 this occurrence is.  To maintain a balance between efficiency and table
 27 size, hash_ keeps a hash table approximately 75 percent full, by
 28 rehashing it (i.e.  rebuilding it in a larger space) when it becomes
 29 too full.
 30 
 31 The number of entries is limited only by the available space.  The
 32 table uses eight words per entry plus ten words for a header.  If an
 33 entire segment is available to hold the table, it can have over 32,000
 34 entries.
 35 
 36 
 37 Entry points in hash_:
 38    (List is generated by the help command)
 39 
 40 
 41 :Entry:  in:  10/06/86 hash_$in
 42 
 43 
 44 Function:  This entry point adds an entry to a hash table.  If the
 45 additional entry makes the table too full, the table is rehashed before
 46 the new entry is added (see the description of the rehash_ subroutine).
 47 
 48 
 49 Syntax:
 50 declare hash_$in entry (ptr, char(*), bit(36) aligned, fixed bin(35));
 51 call hash_$in (table_ptr, name, value, code);
 52 
 53 
 54 Arguments:
 55 table_ptr
 56    is a pointer to the hash table.  (Input)
 57 name
 58    is a name associated with a data table entry.  It can be up to 32
 59    characters long.  (Input)
 60 value
 61    is the locator (e.g., index or offset) of the data table entry
 62    associated with name.  (Input)
 63 
 64 
 65 code
 66    is a standard system error code with the following values:  (Output)
 67    0
 68       entry added successfully.
 69    error_table_$segnamdup
 70       entry already exists, with same value.
 71    error_table_$namedup
 72       entry already exists, with different values.
 73    error_table_$full_hashtbl
 74       hash table is full and there is no room to rehash it into a
 75       larger space.
 76 
 77 
 78 :Entry:  inagain:  10/06/86 hash_$inagain
 79 
 80 
 81 Function:  This entry point adds an entry to a hash table.  It is
 82 identical to the hash_$in entry except that it never tries to rehash
 83 the table.  The new entry is added unless the table is completely full.
 84 This entry point is used by the rehash_ subroutine to avoid loops.  It
 85 can also be used by an application that has a hash table embedded in a
 86 larger data base, where automatic rehashing would damage the data base.
 87 
 88 
 89 Syntax:
 90 declare hash_$inagain entry (ptr, char(*), bit(36) aligned,
 91    fixed bin(35));
 92 call hash_$inagain (table_ptr, name, value, code);
 93 
 94 
 95 Arguments:
 96 table_ptr
 97    is a pointer to the hash table.  (Input)
 98 name
 99    is a name associated with a data table entry.  It can be up to 32
100    characters long.  (Input)
101 value
102    is the locator (e.g., index or offset) of the data table entry
103    associated with name.  (Input)
104 
105 
106 code
107    is a standard system error code with the following values:  (Output)
108 
109    0
110       entry added successfully.
111    error_table_$segnamdup
112       entry already exists, with same value.
113    error_table_$namedup
114       entry already exists, with different values.
115    error_table_$full_hashtbl
116       hash table is full and there is no room to rehash it into a
117       larger space.
118 
119 
120 :Entry:  make:  02/02/83 hash_$make
121 
122 
123 Function: initializes an empty hash table.  The caller must
124 provide a segment to hold it, and must specify its initial size (see
125 hash_$opt_size).
126 
127 
128 Syntax:
129 declare hash_$make entry (ptr, fixed bin, fixed bin(35));
130 call hash_$make (table_ptr, size, code);
131 
132 
133 Arguments:
134 table_ptr
135    is a pointer to the table to be initialized.  (Input)
136 size
137    is the initial number of entries.  (Input).  It is recommended that
138    the value returned by hash_$opt_size be used.
139 code
140    is a standard status code.  (Output).  It can be:
141    0
142       if there is no error.
143    error_table_$invalid_elsize
144       if size is too large.
145 
146 
147 :Entry:  opt_size:  02/02/83 hash_$opt_size
148 
149 
150 Function:  This entry point, given the number of entries to be placed
151 in a new hash table initially, returns the optimal size for the new
152 table.  This function is used when rehashing a full hash table, and
153 should be used when making a new hash table.
154 
155 
156 Syntax:
157 declare hash_$opt_size entry (fixed bin) returns (fixed bin);
158 size=hash_$opt_size (n_entries);
159 
160 
161 Arguments:
162 n_entries
163    is the number of entries to be added.  (Input)
164 size
165    is the optimal table size for that number of entries.  (Output)
166 
167 
168 :Entry:  out:  10/06/86 hash_$out
169 
170 
171 Function:  This entry point deletes a name from the hash table.
172 
173 
174 Syntax:
175 declare hash_$out entry (ptr, char(*), bit(36) aligned, fixed bin(35));
176 call hash_$out (table_ptr, name, value, code);
177 
178 
179 Arguments:
180 table_ptr
181    is a pointer to the hash table.  (Input)
182 name
183    is the name to be deleted.  (Input).  Its maximum length is 32
184    characters.
185 value
186    is the locator value corresponding to name.  (Input)
187 code
188    is a standard status code.  (Output).  It can be:
189    0
190       name was found and deleted.
191    error_table_$noentry
192       name was not found in the hash table.
193 
194 
195 :Entry:  search:  10/06/86 hash_$search
196 
197 
198 Function:  This entry point searches a hash table for a given name and
199 returns the corresponding locator value.
200 
201 
202 Syntax:
203 declare hash_$search entry (ptr, char(*), bit(36) aligned,
204    fixed bin(35));
205 call hash_$search (table_ptr, name, value, code);
206 
207 
208 Arguments:
209 table_ptr
210    is a pointer to the hash table.  (Input)
211 name
212    is the name to be searched for.  (Input).  It can be up to 32
213    characters long.
214 value
215    is the locator value corresponding to name.  (Output)
216 code
217    is a standard status code.  (Output).  It can be:
218    0
219       name was found.
220    error_table_$noentry
221       name was not found in the hash table.