1/* Hash tables.
2   Copyright (C) 2000, 2001, 2003, 2004 Free Software Foundation, Inc.
3
4This program is free software; you can redistribute it and/or modify it
5under the terms of the GNU General Public License as published by the
6Free Software Foundation; either version 2, or (at your option) any
7later version.
8
9This program is distributed in the hope that it will be useful,
10but WITHOUT ANY WARRANTY; without even the implied warranty of
11MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12GNU General Public License for more details.
13
14You should have received a copy of the GNU General Public License
15along with this program; if not, write to the Free Software
16Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17
18 In other words, you are welcome to use, share and improve this program.
19 You are forbidden to forbid anyone else to use, share and improve
20 what you give them.   Help stamp out software-hoarding!  */
21
22#include "config.h"
23#include "system.h"
24#include "symtab.h"
25
26/* The code below is a specialization of Vladimir Makarov's expandable
27   hash tables (see libiberty/hashtab.c).  The abstraction penalty was
28   too high to continue using the generic form.  This code knows
29   intrinsically how to calculate a hash value, and how to compare an
30   existing entry with a potential new one.  Also, the ability to
31   delete members from the table has been removed.  */
32
33static unsigned int calc_hash (const unsigned char *, size_t);
34static void ht_expand (hash_table *);
35static double approx_sqrt (double);
36
37/* Calculate the hash of the string STR of length LEN.  */
38
39static unsigned int
40calc_hash (const unsigned char *str, size_t len)
41{
42  size_t n = len;
43  unsigned int r = 0;
44
45  while (n--)
46    r = HT_HASHSTEP (r, *str++);
47
48  return HT_HASHFINISH (r, len);
49}
50
51/* Initialize an identifier hashtable.  */
52
53hash_table *
54ht_create (unsigned int order)
55{
56  unsigned int nslots = 1 << order;
57  hash_table *table;
58
59  table = XCNEW (hash_table);
60
61  /* Strings need no alignment.  */
62  _obstack_begin (&table->stack, 0, 0,
63		  (void *(*) (long)) xmalloc,
64		  (void (*) (void *)) free);
65
66  obstack_alignment_mask (&table->stack) = 0;
67
68  table->entries = XCNEWVEC (hashnode, nslots);
69  table->entries_owned = true;
70  table->nslots = nslots;
71  return table;
72}
73
74/* Frees all memory associated with a hash table.  */
75
76void
77ht_destroy (hash_table *table)
78{
79  obstack_free (&table->stack, NULL);
80  if (table->entries_owned)
81    free (table->entries);
82  free (table);
83}
84
85/* Returns the hash entry for the a STR of length LEN.  If that string
86   already exists in the table, returns the existing entry, and, if
87   INSERT is CPP_ALLOCED, frees the last obstack object.  If the
88   identifier hasn't been seen before, and INSERT is CPP_NO_INSERT,
89   returns NULL.  Otherwise insert and returns a new entry.  A new
90   string is alloced if INSERT is CPP_ALLOC, otherwise INSERT is
91   CPP_ALLOCED and the item is assumed to be at the top of the
92   obstack.  */
93hashnode
94ht_lookup (hash_table *table, const unsigned char *str, size_t len,
95	   enum ht_lookup_option insert)
96{
97  return ht_lookup_with_hash (table, str, len, calc_hash (str, len),
98			      insert);
99}
100
101hashnode
102ht_lookup_with_hash (hash_table *table, const unsigned char *str,
103		     size_t len, unsigned int hash,
104		     enum ht_lookup_option insert)
105{
106  unsigned int hash2;
107  unsigned int index;
108  size_t sizemask;
109  hashnode node;
110
111  sizemask = table->nslots - 1;
112  index = hash & sizemask;
113  table->searches++;
114
115  node = table->entries[index];
116
117  if (node != NULL)
118    {
119      if (node->hash_value == hash
120	  && HT_LEN (node) == (unsigned int) len
121	  && !memcmp (HT_STR (node), str, len))
122	{
123	  if (insert == HT_ALLOCED)
124	    /* The string we search for was placed at the end of the
125	       obstack.  Release it.  */
126	    obstack_free (&table->stack, (void *) str);
127	  return node;
128	}
129
130      /* hash2 must be odd, so we're guaranteed to visit every possible
131	 location in the table during rehashing.  */
132      hash2 = ((hash * 17) & sizemask) | 1;
133
134      for (;;)
135	{
136	  table->collisions++;
137	  index = (index + hash2) & sizemask;
138	  node = table->entries[index];
139	  if (node == NULL)
140	    break;
141
142	  if (node->hash_value == hash
143	      && HT_LEN (node) == (unsigned int) len
144	      && !memcmp (HT_STR (node), str, len))
145	    {
146	      if (insert == HT_ALLOCED)
147	      /* The string we search for was placed at the end of the
148		 obstack.  Release it.  */
149		obstack_free (&table->stack, (void *) str);
150	      return node;
151	    }
152	}
153    }
154
155  if (insert == HT_NO_INSERT)
156    return NULL;
157
158  node = (*table->alloc_node) (table);
159  table->entries[index] = node;
160
161  HT_LEN (node) = (unsigned int) len;
162  node->hash_value = hash;
163  if (insert == HT_ALLOC)
164    HT_STR (node) = (const unsigned char *) obstack_copy0 (&table->stack,
165                                                           str, len);
166  else
167    HT_STR (node) = str;
168
169  if (++table->nelements * 4 >= table->nslots * 3)
170    /* Must expand the string table.  */
171    ht_expand (table);
172
173  return node;
174}
175
176/* Double the size of a hash table, re-hashing existing entries.  */
177
178static void
179ht_expand (hash_table *table)
180{
181  hashnode *nentries, *p, *limit;
182  unsigned int size, sizemask;
183
184  size = table->nslots * 2;
185  nentries = XCNEWVEC (hashnode, size);
186  sizemask = size - 1;
187
188  p = table->entries;
189  limit = p + table->nslots;
190  do
191    if (*p)
192      {
193	unsigned int index, hash, hash2;
194
195	hash = (*p)->hash_value;
196	index = hash & sizemask;
197
198	if (nentries[index])
199	  {
200	    hash2 = ((hash * 17) & sizemask) | 1;
201	    do
202	      {
203		index = (index + hash2) & sizemask;
204	      }
205	    while (nentries[index]);
206	  }
207	nentries[index] = *p;
208      }
209  while (++p < limit);
210
211  if (table->entries_owned)
212    free (table->entries);
213  table->entries_owned = true;
214  table->entries = nentries;
215  table->nslots = size;
216}
217
218/* For all nodes in TABLE, callback CB with parameters TABLE->PFILE,
219   the node, and V.  */
220void
221ht_forall (hash_table *table, ht_cb cb, const void *v)
222{
223  hashnode *p, *limit;
224
225  p = table->entries;
226  limit = p + table->nslots;
227  do
228    if (*p)
229      {
230	if ((*cb) (table->pfile, *p, v) == 0)
231	  break;
232      }
233  while (++p < limit);
234}
235
236/* Restore the hash table.  */
237void
238ht_load (hash_table *ht, hashnode *entries,
239	 unsigned int nslots, unsigned int nelements,
240	 bool own)
241{
242  if (ht->entries_owned)
243    free (ht->entries);
244  ht->entries = entries;
245  ht->nslots = nslots;
246  ht->nelements = nelements;
247  ht->entries_owned = own;
248}
249
250/* Dump allocation statistics to stderr.  */
251
252void
253ht_dump_statistics (hash_table *table)
254{
255  size_t nelts, nids, overhead, headers;
256  size_t total_bytes, longest;
257  double sum_of_squares, exp_len, exp_len2, exp2_len;
258  hashnode *p, *limit;
259
260#define SCALE(x) ((unsigned long) ((x) < 1024*10 \
261		  ? (x) \
262		  : ((x) < 1024*1024*10 \
263		     ? (x) / 1024 \
264		     : (x) / (1024*1024))))
265#define LABEL(x) ((x) < 1024*10 ? ' ' : ((x) < 1024*1024*10 ? 'k' : 'M'))
266
267  total_bytes = longest = sum_of_squares = nids = 0;
268  p = table->entries;
269  limit = p + table->nslots;
270  do
271    if (*p)
272      {
273	size_t n = HT_LEN (*p);
274
275	total_bytes += n;
276	sum_of_squares += (double) n * n;
277	if (n > longest)
278	  longest = n;
279	nids++;
280      }
281  while (++p < limit);
282
283  nelts = table->nelements;
284  overhead = obstack_memory_used (&table->stack) - total_bytes;
285  headers = table->nslots * sizeof (hashnode);
286
287  fprintf (stderr, "\nString pool\nentries\t\t%lu\n",
288	   (unsigned long) nelts);
289  fprintf (stderr, "identifiers\t%lu (%.2f%%)\n",
290	   (unsigned long) nids, nids * 100.0 / nelts);
291  fprintf (stderr, "slots\t\t%lu\n",
292	   (unsigned long) table->nslots);
293  fprintf (stderr, "bytes\t\t%lu%c (%lu%c overhead)\n",
294	   SCALE (total_bytes), LABEL (total_bytes),
295	   SCALE (overhead), LABEL (overhead));
296  fprintf (stderr, "table size\t%lu%c\n",
297	   SCALE (headers), LABEL (headers));
298
299  exp_len = (double)total_bytes / (double)nelts;
300  exp2_len = exp_len * exp_len;
301  exp_len2 = (double) sum_of_squares / (double) nelts;
302
303  fprintf (stderr, "coll/search\t%.4f\n",
304	   (double) table->collisions / (double) table->searches);
305  fprintf (stderr, "ins/search\t%.4f\n",
306	   (double) nelts / (double) table->searches);
307  fprintf (stderr, "avg. entry\t%.2f bytes (+/- %.2f)\n",
308	   exp_len, approx_sqrt (exp_len2 - exp2_len));
309  fprintf (stderr, "longest entry\t%lu\n",
310	   (unsigned long) longest);
311#undef SCALE
312#undef LABEL
313}
314
315/* Return the approximate positive square root of a number N.  This is for
316   statistical reports, not code generation.  */
317static double
318approx_sqrt (double x)
319{
320  double s, d;
321
322  if (x < 0)
323    abort ();
324  if (x == 0)
325    return 0;
326
327  s = x;
328  do
329    {
330      d = (s * s - x) / (2 * s);
331      s -= d;
332    }
333  while (d > .0001);
334  return s;
335}
336