X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Fcpphash.c;h=9e15ab48f03080192cdaa1f46ee21cfd74d384e9;hb=665617504a0de369ff5c0fd45add7a09e021f462;hp=c26f7b54c4c2e2995e704fe2ec626d7cb17cb160;hpb=69461e0d90d5ee950b9e0b8ba60d4bbf3299f472;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/cpphash.c b/gcc/cpphash.c index c26f7b54c4c..9e15ab48f03 100644 --- a/gcc/cpphash.c +++ b/gcc/cpphash.c @@ -1,4 +1,4 @@ -/* Part of CPP library. (Identifier and string tables.) +/* Hash tables for the CPP library. Copyright (C) 1986, 1987, 1989, 1992, 1993, 1994, 1995, 1996, 1998, 1999, 2000 Free Software Foundation, Inc. Written by Per Bothner, 1994. @@ -27,252 +27,96 @@ Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. #include "system.h" #include "cpplib.h" #include "cpphash.h" -#include "obstack.h" -#define obstack_chunk_alloc xmalloc -#define obstack_chunk_free free +static cpp_hashnode *alloc_node PARAMS ((hash_table *)); -/* Initial hash table size. (It can grow if necessary.) This is the - largest prime number smaller than 2**12. */ -#define HASHSIZE 4093 +/* Return an identifier node for hashtable.c. Used by cpplib except + when integrated with the C front ends. */ -/* This is the structure used for the hash table. */ -struct htab +static cpp_hashnode * +alloc_node (table) + hash_table *table; { - struct cpp_hashnode **entries; - size_t size; - size_t nelts; -}; - -static void expand_hash PARAMS ((struct htab *)); -static unsigned long higher_prime_number PARAMS ((unsigned long)); - -/* Set up and tear down internal structures for macro expansion. */ -void -_cpp_init_macros (pfile) - cpp_reader *pfile; -{ - pfile->hash_ob = xnew (struct obstack); - obstack_init (pfile->hash_ob); - - pfile->hashtab = xobnew (pfile->hash_ob, struct htab); - - pfile->hashtab->nelts = 0; - pfile->hashtab->size = HASHSIZE; - pfile->hashtab->entries = xcnewvec (cpp_hashnode *, HASHSIZE); + cpp_hashnode *node; + + node = (cpp_hashnode *) obstack_alloc (&table->pfile->hash_ob, + sizeof (cpp_hashnode)); + memset ((PTR) node, 0, sizeof (cpp_hashnode)); + return node; } +/* Set up the identifier hash table. Use TABLE if non-null, otherwise + create our own. */ + void -_cpp_cleanup_macros (pfile) +_cpp_init_hashtable (pfile, table) cpp_reader *pfile; + hash_table *table; { - cpp_hashnode **p, **limit; - - p = pfile->hashtab->entries; - limit = p + pfile->hashtab->size; - do + if (table == NULL) { - if (*p) - { - _cpp_free_definition (*p); - (*p)->fe_value = 0; /* expose the node to GC */ - } + pfile->our_hashtable = 1; + table = ht_create (13); /* 8K (=2^13) entries. */ + table->alloc_node = (hashnode (*) PARAMS ((hash_table *))) alloc_node; + gcc_obstack_init (&pfile->hash_ob); } - while (++p < limit); - free (pfile->hashtab->entries); - obstack_free (pfile->hash_ob, 0); - free (pfile->hash_ob); + table->pfile = pfile; + pfile->hash_table = table; } -/* 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. Also, the ability to - delete members from the table has been removed. */ +/* Tear down the identifier hash table. */ -cpp_hashnode * -cpp_lookup (pfile, name, len) +void +_cpp_destroy_hashtable (pfile) cpp_reader *pfile; - const U_CHAR *name; - size_t len; { - size_t n = len; - unsigned int r = 0; - const U_CHAR *str = name; - - do + if (pfile->our_hashtable) { - r = HASHSTEP (r, str); - str++; + free (pfile->hash_table); + obstack_free (&pfile->hash_ob, 0); } - while (--n); - - return _cpp_lookup_with_hash (pfile, name, len, r); } +/* Returns the hash entry for the STR of length LEN, creating one + if necessary. */ + cpp_hashnode * -_cpp_lookup_with_hash (pfile, name, len, hash) +cpp_lookup (pfile, str, len) cpp_reader *pfile; - const U_CHAR *name; - size_t len; - unsigned int hash; -{ - unsigned int index; - unsigned int hash2; - size_t size; - cpp_hashnode *entry; - cpp_hashnode **entries; - - entries = pfile->hashtab->entries; - size = pfile->hashtab->size; - - hash += len; - index = hash % size; - - entry = entries[index]; - if (entry == NULL) - goto insert; - if (entry->hash == hash && entry->length == len - && !memcmp (entry->name, name, len)) - return entry; - - hash2 = 1 + hash % (size - 2); - - for (;;) - { - index += hash2; - if (index >= size) - index -= size; - entry = entries[index]; - - if (entry == NULL) - goto insert; - if (entry->hash == hash && entry->length == len - && !memcmp (entry->name, name, len)) - return entry; - } - - insert: - pfile->hashtab->nelts++; - - /* Create a new hash node. */ - { - U_CHAR *p = obstack_alloc (pfile->hash_ob, sizeof (cpp_hashnode) + len); - entry = (cpp_hashnode *)p; - p += offsetof (cpp_hashnode, name); - - entry->type = T_VOID; - entry->fe_value = 0; - entry->length = len; - entry->hash = hash; - entry->value.expansion = NULL; - memcpy (p, name, len); - p[len] = 0; - - entries[index] = entry; - } - - if (size * 3 <= pfile->hashtab->nelts * 4) - expand_hash (pfile->hashtab); - - return entry; -} - -static void -expand_hash (htab) - struct htab *htab; + const unsigned char *str; + unsigned int len; { - cpp_hashnode **oentries; - cpp_hashnode **olimit; - cpp_hashnode **p; - size_t size; - - oentries = htab->entries; - olimit = oentries + htab->size; - - htab->size = size = higher_prime_number (htab->size * 2); - htab->entries = xcnewvec (cpp_hashnode *, size); - - for (p = oentries; p < olimit; p++) - { - if (*p != NULL) - { - unsigned int index; - unsigned int hash, hash2; - cpp_hashnode *entry = *p; - - hash = entry->hash; - index = hash % size; - - if (htab->entries[index] == NULL) - { - insert: - htab->entries[index] = entry; - continue; - } - - hash2 = 1 + hash % (size - 2); - for (;;) - { - index += hash2; - if (index >= size) - index -= size; - - if (htab->entries[index] == NULL) - goto insert; - } - } - } - - free (oentries); + /* ht_lookup cannot return NULL. */ + return CPP_HASHNODE (ht_lookup (pfile->hash_table, str, len, HT_ALLOC)); } -/* The following function returns the nearest prime number which is - greater than a given source number, N. */ +/* Determine whether the str STR, of length LEN, is a defined macro. */ -static unsigned long -higher_prime_number (n) - unsigned long n; +int +cpp_defined (pfile, str, len) + cpp_reader *pfile; + const unsigned char *str; + int len; { - unsigned long i; - - /* Ensure we have a larger number and then force to odd. */ - n++; - n |= 0x01; + cpp_hashnode *node; - /* All odd numbers < 9 are prime. */ - if (n < 9) - return n; + node = CPP_HASHNODE (ht_lookup (pfile->hash_table, str, len, HT_NO_INSERT)); - /* Otherwise find the next prime using a sieve. */ - - next: - for (i = 3; i * i <= n; i += 2) - if (n % i == 0) - { - n += 2; - goto next; - } - - return n; + /* If it's of type NT_MACRO, it cannot be poisoned. */ + return node && node->type == NT_MACRO; } +/* For all nodes in the hashtable, callback CB with parameters PFILE, + the node, and V. */ + void -cpp_forall_identifiers (pfile, cb) +cpp_forall_identifiers (pfile, cb, v) cpp_reader *pfile; - int (*cb) PARAMS ((cpp_reader *, cpp_hashnode *)); + cpp_cb cb; + PTR v; { - cpp_hashnode **p, **limit; - - p = pfile->hashtab->entries; - limit = p + pfile->hashtab->size; - do - { - if (*p) - if ((*cb) (pfile, *p) == 0) - break; - } - while (++p < limit); + /* We don't need a proxy since the hash table's identifier comes + first in cpp_hashnode. */ + ht_forall (pfile->hash_table, (ht_cb) cb, v); }