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 (HT_LEN (node
) == len
&& !memcmp (HT_STR (node
), str
, len
))
126 if (insert
== HT_ALLOCED
)
127 /* The string we search for was placed at the end of the
128 obstack. Release it. */
129 obstack_free (&table
->stack
, (PTR
) str
);
133 index
= (index
+ hash2
) & sizemask
;
137 if (insert
== HT_NO_INSERT
)
140 node
= (*table
->alloc_node
) (table
);
141 table
->entries
[index
] = node
;
144 if (insert
== HT_ALLOC
)
145 HT_STR (node
) = obstack_copy0 (&table
->stack
, str
, len
);
149 if (++table
->nelements
* 4 >= table
->nslots
* 3)
150 /* Must expand the string table. */
156 /* Double the size of a hash table, re-hashing existing entries. */
162 hashnode
*nentries
, *p
, *limit
;
163 unsigned int size
, sizemask
;
165 size
= table
->nslots
* 2;
166 nentries
= (hashnode
*) xcalloc (size
, sizeof (hashnode
));
170 limit
= p
+ table
->nslots
;
174 unsigned int index
, hash
, hash2
;
176 hash
= calc_hash (HT_STR (*p
), HT_LEN (*p
));
177 hash2
= ((hash
* 17) & sizemask
) | 1;
178 index
= hash
& sizemask
;
182 if (! nentries
[index
])
184 nentries
[index
] = *p
;
188 index
= (index
+ hash2
) & sizemask
;
193 free (table
->entries
);
194 table
->entries
= nentries
;
195 table
->nslots
= size
;
198 /* For all nodes in TABLE, callback CB with parameters TABLE->PFILE,
201 ht_forall (table
, cb
, v
)
209 limit
= p
+ table
->nslots
;
213 if ((*cb
) (table
->pfile
, *p
, v
) == 0)
219 /* Dump allocation statistics to stderr. */
222 ht_dump_statistics (table
)
225 size_t nelts
, nids
, overhead
, headers
;
226 size_t total_bytes
, longest
, sum_of_squares
;
227 double exp_len
, exp_len2
, exp2_len
;
230 #define SCALE(x) ((unsigned long) ((x) < 1024*10 \
232 : ((x) < 1024*1024*10 \
234 : (x) / (1024*1024))))
235 #define LABEL(x) ((x) < 1024*10 ? ' ' : ((x) < 1024*1024*10 ? 'k' : 'M'))
237 total_bytes
= longest
= sum_of_squares
= nids
= 0;
239 limit
= p
+ table
->nslots
;
243 size_t n
= HT_LEN (*p
);
246 sum_of_squares
+= n
* n
;
253 nelts
= table
->nelements
;
254 overhead
= obstack_memory_used (&table
->stack
) - total_bytes
;
255 headers
= table
->nslots
* sizeof (hashnode
);
257 fprintf (stderr
, "\nString pool\nentries\t\t%lu\n",
258 (unsigned long) nelts
);
259 fprintf (stderr
, "identifiers\t%lu (%.2f%%)\n",
260 (unsigned long) nids
, nids
* 100.0 / nelts
);
261 fprintf (stderr
, "slots\t\t%lu\n",
262 (unsigned long) table
->nslots
);
263 fprintf (stderr
, "bytes\t\t%lu%c (%lu%c overhead)\n",
264 SCALE (total_bytes
), LABEL (total_bytes
),
265 SCALE (overhead
), LABEL (overhead
));
266 fprintf (stderr
, "table size\t%lu%c\n",
267 SCALE (headers
), LABEL (headers
));
269 exp_len
= (double)total_bytes
/ (double)nelts
;
270 exp2_len
= exp_len
* exp_len
;
271 exp_len2
= (double) sum_of_squares
/ (double) nelts
;
273 fprintf (stderr
, "coll/search\t%.4f\n",
274 (double) table
->collisions
/ (double) table
->searches
);
275 fprintf (stderr
, "ins/search\t%.4f\n",
276 (double) nelts
/ (double) table
->searches
);
277 fprintf (stderr
, "avg. entry\t%.2f bytes (+/- %.2f)\n",
278 exp_len
, approx_sqrt (exp_len2
- exp2_len
));
279 fprintf (stderr
, "longest entry\t%lu\n",
280 (unsigned long) longest
);
285 /* Return the approximate positive square root of a number N. This is for
286 statistical reports, not code generation. */
301 d
= (s
* s
- x
) / (2 * s
);