aboutsummaryrefslogtreecommitdiffstats
path: root/gcc-4.4.3/libcpp/symtab.c
diff options
context:
space:
mode:
Diffstat (limited to 'gcc-4.4.3/libcpp/symtab.c')
-rw-r--r--gcc-4.4.3/libcpp/symtab.c363
1 files changed, 0 insertions, 363 deletions
diff --git a/gcc-4.4.3/libcpp/symtab.c b/gcc-4.4.3/libcpp/symtab.c
deleted file mode 100644
index 086d775d5..000000000
--- a/gcc-4.4.3/libcpp/symtab.c
+++ /dev/null
@@ -1,363 +0,0 @@
-/* Hash tables.
- Copyright (C) 2000, 2001, 2003, 2004, 2008, 2009
- Free Software Foundation, Inc.
-
-This program is free software; you can redistribute it and/or modify it
-under the terms of the GNU General Public License as published by the
-Free Software Foundation; either version 3, or (at your option) any
-later version.
-
-This program is distributed in the hope that it will be useful,
-but WITHOUT ANY WARRANTY; without even the implied warranty of
-MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
-GNU General Public License for more details.
-
-You should have received a copy of the GNU General Public License
-along with this program; see the file COPYING3. If not see
-<http://www.gnu.org/licenses/>.
-
- In other words, you are welcome to use, share and improve this program.
- You are forbidden to forbid anyone else to use, share and improve
- what you give them. Help stamp out software-hoarding! */
-
-#include "config.h"
-#include "system.h"
-#include "symtab.h"
-
-/* The code below is a specialization of Vladimir Makarov's expandable
- hash tables (see libiberty/hashtab.c). The abstraction penalty was
- too high to continue using the generic form. This code knows
- intrinsically how to calculate a hash value, and how to compare an
- existing entry with a potential new one. */
-
-static unsigned int calc_hash (const unsigned char *, size_t);
-static void ht_expand (hash_table *);
-static double approx_sqrt (double);
-
-/* A deleted entry. */
-#define DELETED ((hashnode) -1)
-
-/* Calculate the hash of the string STR of length LEN. */
-
-static unsigned int
-calc_hash (const unsigned char *str, size_t len)
-{
- size_t n = len;
- unsigned int r = 0;
-
- while (n--)
- r = HT_HASHSTEP (r, *str++);
-
- return HT_HASHFINISH (r, len);
-}
-
-/* Initialize an identifier hashtable. */
-
-hash_table *
-ht_create (unsigned int order)
-{
- unsigned int nslots = 1 << order;
- hash_table *table;
-
- table = XCNEW (hash_table);
-
- /* Strings need no alignment. */
- _obstack_begin (&table->stack, 0, 0,
- (void *(*) (long)) xmalloc,
- (void (*) (void *)) free);
-
- obstack_alignment_mask (&table->stack) = 0;
-
- table->entries = XCNEWVEC (hashnode, nslots);
- table->entries_owned = true;
- table->nslots = nslots;
- return table;
-}
-
-/* Frees all memory associated with a hash table. */
-
-void
-ht_destroy (hash_table *table)
-{
- obstack_free (&table->stack, NULL);
- if (table->entries_owned)
- free (table->entries);
- free (table);
-}
-
-/* Returns the hash entry for the a STR of length LEN. If that string
- already exists in the table, returns the existing entry. If the
- identifier hasn't been seen before, and INSERT is CPP_NO_INSERT,
- returns NULL. Otherwise insert and returns a new entry. A new
- string is allocated. */
-hashnode
-ht_lookup (hash_table *table, const unsigned char *str, size_t len,
- enum ht_lookup_option insert)
-{
- return ht_lookup_with_hash (table, str, len, calc_hash (str, len),
- insert);
-}
-
-hashnode
-ht_lookup_with_hash (hash_table *table, const unsigned char *str,
- size_t len, unsigned int hash,
- enum ht_lookup_option insert)
-{
- unsigned int hash2;
- unsigned int index;
- unsigned int deleted_index = table->nslots;
- size_t sizemask;
- hashnode node;
-
- sizemask = table->nslots - 1;
- index = hash & sizemask;
- table->searches++;
-
- node = table->entries[index];
-
- if (node != NULL)
- {
- if (node == DELETED)
- deleted_index = index;
- else if (node->hash_value == hash
- && HT_LEN (node) == (unsigned int) len
- && !memcmp (HT_STR (node), str, len))
- return node;
-
- /* hash2 must be odd, so we're guaranteed to visit every possible
- location in the table during rehashing. */
- hash2 = ((hash * 17) & sizemask) | 1;
-
- for (;;)
- {
- table->collisions++;
- index = (index + hash2) & sizemask;
- node = table->entries[index];
- if (node == NULL)
- break;
-
- if (node == DELETED)
- {
- if (deleted_index != table->nslots)
- deleted_index = index;
- }
- else if (node->hash_value == hash
- && HT_LEN (node) == (unsigned int) len
- && !memcmp (HT_STR (node), str, len))
- return node;
- }
- }
-
- if (insert == HT_NO_INSERT)
- return NULL;
-
- /* We prefer to overwrite the first deleted slot we saw. */
- if (deleted_index != table->nslots)
- index = deleted_index;
-
- node = (*table->alloc_node) (table);
- table->entries[index] = node;
-
- HT_LEN (node) = (unsigned int) len;
- node->hash_value = hash;
-
- if (table->alloc_subobject)
- {
- char *chars = table->alloc_subobject (len + 1);
- memcpy (chars, str, len);
- chars[len] = '\0';
- HT_STR (node) = (const unsigned char *) chars;
- }
- else
- HT_STR (node) = (const unsigned char *) obstack_copy0 (&table->stack,
- str, len);
-
- if (++table->nelements * 4 >= table->nslots * 3)
- /* Must expand the string table. */
- ht_expand (table);
-
- return node;
-}
-
-/* Double the size of a hash table, re-hashing existing entries. */
-
-static void
-ht_expand (hash_table *table)
-{
- hashnode *nentries, *p, *limit;
- unsigned int size, sizemask;
-
- size = table->nslots * 2;
- nentries = XCNEWVEC (hashnode, size);
- sizemask = size - 1;
-
- p = table->entries;
- limit = p + table->nslots;
- do
- if (*p && *p != DELETED)
- {
- unsigned int index, hash, hash2;
-
- hash = (*p)->hash_value;
- index = hash & sizemask;
-
- if (nentries[index])
- {
- hash2 = ((hash * 17) & sizemask) | 1;
- do
- {
- index = (index + hash2) & sizemask;
- }
- while (nentries[index]);
- }
- nentries[index] = *p;
- }
- while (++p < limit);
-
- if (table->entries_owned)
- free (table->entries);
- table->entries_owned = true;
- table->entries = nentries;
- table->nslots = size;
-}
-
-/* For all nodes in TABLE, callback CB with parameters TABLE->PFILE,
- the node, and V. */
-void
-ht_forall (hash_table *table, ht_cb cb, const void *v)
-{
- hashnode *p, *limit;
-
- p = table->entries;
- limit = p + table->nslots;
- do
- if (*p && *p != DELETED)
- {
- if ((*cb) (table->pfile, *p, v) == 0)
- break;
- }
- while (++p < limit);
-}
-
-/* Like ht_forall, but a nonzero return from the callback means that
- the entry should be removed from the table. */
-void
-ht_purge (hash_table *table, ht_cb cb, const void *v)
-{
- hashnode *p, *limit;
-
- p = table->entries;
- limit = p + table->nslots;
- do
- if (*p && *p != DELETED)
- {
- if ((*cb) (table->pfile, *p, v))
- *p = DELETED;
- }
- while (++p < limit);
-}
-
-/* Restore the hash table. */
-void
-ht_load (hash_table *ht, hashnode *entries,
- unsigned int nslots, unsigned int nelements,
- bool own)
-{
- if (ht->entries_owned)
- free (ht->entries);
- ht->entries = entries;
- ht->nslots = nslots;
- ht->nelements = nelements;
- ht->entries_owned = own;
-}
-
-/* Dump allocation statistics to stderr. */
-
-void
-ht_dump_statistics (hash_table *table)
-{
- size_t nelts, nids, overhead, headers;
- size_t total_bytes, longest, deleted = 0;
- double sum_of_squares, exp_len, exp_len2, exp2_len;
- hashnode *p, *limit;
-
-#define SCALE(x) ((unsigned long) ((x) < 1024*10 \
- ? (x) \
- : ((x) < 1024*1024*10 \
- ? (x) / 1024 \
- : (x) / (1024*1024))))
-#define LABEL(x) ((x) < 1024*10 ? ' ' : ((x) < 1024*1024*10 ? 'k' : 'M'))
-
- total_bytes = longest = sum_of_squares = nids = 0;
- p = table->entries;
- limit = p + table->nslots;
- do
- if (*p == DELETED)
- ++deleted;
- else if (*p)
- {
- size_t n = HT_LEN (*p);
-
- total_bytes += n;
- sum_of_squares += (double) n * n;
- if (n > longest)
- longest = n;
- nids++;
- }
- while (++p < limit);
-
- nelts = table->nelements;
- overhead = obstack_memory_used (&table->stack) - total_bytes;
- headers = table->nslots * sizeof (hashnode);
-
- fprintf (stderr, "\nString pool\nentries\t\t%lu\n",
- (unsigned long) nelts);
- fprintf (stderr, "identifiers\t%lu (%.2f%%)\n",
- (unsigned long) nids, nids * 100.0 / nelts);
- fprintf (stderr, "slots\t\t%lu\n",
- (unsigned long) table->nslots);
- fprintf (stderr, "deleted\t\t%lu\n",
- (unsigned long) deleted);
- fprintf (stderr, "bytes\t\t%lu%c (%lu%c overhead)\n",
- SCALE (total_bytes), LABEL (total_bytes),
- SCALE (overhead), LABEL (overhead));
- fprintf (stderr, "table size\t%lu%c\n",
- SCALE (headers), LABEL (headers));
-
- exp_len = (double)total_bytes / (double)nelts;
- exp2_len = exp_len * exp_len;
- exp_len2 = (double) sum_of_squares / (double) nelts;
-
- fprintf (stderr, "coll/search\t%.4f\n",
- (double) table->collisions / (double) table->searches);
- fprintf (stderr, "ins/search\t%.4f\n",
- (double) nelts / (double) table->searches);
- fprintf (stderr, "avg. entry\t%.2f bytes (+/- %.2f)\n",
- exp_len, approx_sqrt (exp_len2 - exp2_len));
- fprintf (stderr, "longest entry\t%lu\n",
- (unsigned long) longest);
-#undef SCALE
-#undef LABEL
-}
-
-/* Return the approximate positive square root of a number N. This is for
- statistical reports, not code generation. */
-static double
-approx_sqrt (double x)
-{
- double s, d;
-
- if (x < 0)
- abort ();
- if (x == 0)
- return 0;
-
- s = x;
- do
- {
- d = (s * s - x) / (2 * s);
- s -= d;
- }
- while (d > .0001);
- return s;
-}
generated by cgit v1.2.3 (git 2.25.1) at 2024-04-30 14:55:49 +0000