-/* 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.
#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);
}
OSDN Git Service
