2 Copyright (C) 2000, 2001 Free Software Foundation, Inc.
4 This program is free software; you can redistribute it and/or modify it
5 under the terms of the GNU General Public License as published by the
6 Free Software Foundation; either version 2, or (at your option) any
9 This program is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 GNU General Public License for more details.
14 You should have received a copy of the GNU General Public License
15 along with this program; if not, write to the Free Software
16 Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
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! */
24 #include "coretypes.h"
26 #include "hashtable.h"
28 /* The code below is a specialization of Vladimir Makarov's expandable
29 hash tables (see libiberty/hashtab.c). The abstraction penalty was
30 too high to continue using the generic form. This code knows
31 intrinsically how to calculate a hash value, and how to compare an
32 existing entry with a potential new one. Also, the ability to
33 delete members from the table has been removed. */
35 static unsigned int calc_hash
PARAMS ((const unsigned char *, unsigned int));
36 static void ht_expand
PARAMS ((hash_table
*));
38 /* Calculate the hash of the string STR of length LEN. */
42 const unsigned char *str
;
47 #define HASHSTEP(r, c) ((r) * 67 + ((c) - 113));
50 r
= HASHSTEP (r
, *str
++);
56 /* Initialize an identifier hashtable. */
62 unsigned int nslots
= 1 << order
;
65 table
= (hash_table
*) xmalloc (sizeof (hash_table
));
66 memset (table
, 0, sizeof (hash_table
));
68 /* Strings need no alignment. */
69 gcc_obstack_init (&table
->stack
);
70 obstack_alignment_mask (&table
->stack
) = 0;
72 table
->entries
= (hashnode
*) xcalloc (nslots
, sizeof (hashnode
));
73 table
->nslots
= nslots
;
77 /* Frees all memory associated with a hash table. */
83 obstack_free (&table
->stack
, NULL
);
84 free (table
->entries
);
88 /* Returns the hash entry for the a STR of length LEN. If that string
89 already exists in the table, returns the existing entry, and, if
90 INSERT is CPP_ALLOCED, frees the last obstack object. If the
91 identifier hasn't been seen before, and INSERT is CPP_NO_INSERT,
92 returns NULL. Otherwise insert and returns a new entry. A new
93 string is alloced if INSERT is CPP_ALLOC, otherwise INSERT is
94 CPP_ALLOCED and the item is assumed to be at the top of the
97 ht_lookup (table
, str
, len
, insert
)
99 const unsigned char *str
;
101 enum ht_lookup_option insert
;
103 unsigned int hash
= calc_hash (str
, len
);
109 sizemask
= table
->nslots
- 1;
110 index
= hash
& sizemask
;
112 /* hash2 must be odd, so we're guaranteed to visit every possible
113 location in the table during rehashing. */
114 hash2
= ((hash
* 17) & sizemask
) | 1;
119 node
= table
->entries
[index
];
124 if (node
->hash_value
== hash
&& HT_LEN (node
) == len
125 && !memcmp (HT_STR (node
), str
, len
))
127 if (insert
== HT_ALLOCED
)
128 /* The string we search for was placed at the end of the
129 obstack. Release it. */
130 obstack_free (&table
->stack
, (void *) str
);
134 index
= (index
+ hash2
) & sizemask
;
138 if (insert
== HT_NO_INSERT
)
141 node
= (*table
->alloc_node
) (table
);
142 table
->entries
[index
] = node
;
145 node
->hash_value
= hash
;
146 if (insert
== HT_ALLOC
)
147 HT_STR (node
) = obstack_copy0 (&table
->stack
, str
, len
);
151 if (++table
->nelements
* 4 >= table
->nslots
* 3)
152 /* Must expand the string table. */
158 /* Double the size of a hash table, re-hashing existing entries. */
164 hashnode
*nentries
, *p
, *limit
;
165 unsigned int size
, sizemask
;
167 size
= table
->nslots
* 2;
168 nentries
= (hashnode
*) xcalloc (size
, sizeof (hashnode
));
172 limit
= p
+ table
->nslots
;
176 unsigned int index
, hash
, hash2
;
178 hash
= (*p
)->hash_value
;
179 hash2
= ((hash
* 17) & sizemask
) | 1;
180 index
= hash
& sizemask
;
184 if (! nentries
[index
])
186 nentries
[index
] = *p
;
190 index
= (index
+ hash2
) & sizemask
;
195 free (table
->entries
);
196 table
->entries
= nentries
;
197 table
->nslots
= size
;
200 /* For all nodes in TABLE, callback CB with parameters TABLE->PFILE,
203 ht_forall (table
, cb
, v
)
211 limit
= p
+ table
->nslots
;
215 if ((*cb
) (table
->pfile
, *p
, v
) == 0)
221 /* Dump allocation statistics to stderr. */
224 ht_dump_statistics (table
)
227 size_t nelts
, nids
, overhead
, headers
;
228 size_t total_bytes
, longest
, sum_of_squares
;
229 double exp_len
, exp_len2
, exp2_len
;
232 #define SCALE(x) ((unsigned long) ((x) < 1024*10 \
234 : ((x) < 1024*1024*10 \
236 : (x) / (1024*1024))))
237 #define LABEL(x) ((x) < 1024*10 ? ' ' : ((x) < 1024*1024*10 ? 'k' : 'M'))
239 total_bytes
= longest
= sum_of_squares
= nids
= 0;
241 limit
= p
+ table
->nslots
;
245 size_t n
= HT_LEN (*p
);
248 sum_of_squares
+= n
* n
;
255 nelts
= table
->nelements
;
256 overhead
= obstack_memory_used (&table
->stack
) - total_bytes
;
257 headers
= table
->nslots
* sizeof (hashnode
);
259 fprintf (stderr
, "\nString pool\nentries\t\t%lu\n",
260 (unsigned long) nelts
);
261 fprintf (stderr
, "identifiers\t%lu (%.2f%%)\n",
262 (unsigned long) nids
, nids
* 100.0 / nelts
);
263 fprintf (stderr
, "slots\t\t%lu\n",
264 (unsigned long) table
->nslots
);
265 fprintf (stderr
, "bytes\t\t%lu%c (%lu%c overhead)\n",
266 SCALE (total_bytes
), LABEL (total_bytes
),
267 SCALE (overhead
), LABEL (overhead
));
268 fprintf (stderr
, "table size\t%lu%c\n",
269 SCALE (headers
), LABEL (headers
));
271 exp_len
= (double)total_bytes
/ (double)nelts
;
272 exp2_len
= exp_len
* exp_len
;
273 exp_len2
= (double) sum_of_squares
/ (double) nelts
;
275 fprintf (stderr
, "coll/search\t%.4f\n",
276 (double) table
->collisions
/ (double) table
->searches
);
277 fprintf (stderr
, "ins/search\t%.4f\n",
278 (double) nelts
/ (double) table
->searches
);
279 fprintf (stderr
, "avg. entry\t%.2f bytes (+/- %.2f)\n",
280 exp_len
, approx_sqrt (exp_len2
- exp2_len
));
281 fprintf (stderr
, "longest entry\t%lu\n",
282 (unsigned long) longest
);
287 /* Return the approximate positive square root of a number N. This is for
288 statistical reports, not code generation. */
303 d
= (s
* s
- x
) / (2 * s
);