| /* Part of CPP library. (Identifier and string tables.) |
| Copyright (C) 1986, 1987, 1989, 1992, 1993, 1994, 1995, 1996, 1998, |
| 1999, 2000 Free Software Foundation, Inc. |
| Written by Per Bothner, 1994. |
| Based on CCCP program by Paul Rubin, June 1986 |
| Adapted to ANSI C, Richard Stallman, Jan 1987 |
| |
| 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 2, 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; if not, write to the Free Software |
| Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. |
| |
| 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 "cpplib.h" |
| #include "cpphash.h" |
| #include "obstack.h" |
| |
| #define obstack_chunk_alloc xmalloc |
| #define obstack_chunk_free free |
| |
| /* Initial hash table size. (It can grow if necessary.) This is the |
| largest prime number smaller than 2**12. */ |
| #define HASHSIZE 4093 |
| |
| /* This is the structure used for the hash table. */ |
| struct htab |
| { |
| 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_hashtable (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); |
| } |
| |
| void |
| _cpp_cleanup_hashtable (pfile) |
| cpp_reader *pfile; |
| { |
| cpp_hashnode **p, **limit; |
| |
| p = pfile->hashtab->entries; |
| limit = p + pfile->hashtab->size; |
| do |
| { |
| if (*p) |
| _cpp_free_definition (*p); |
| } |
| while (++p < limit); |
| |
| free (pfile->hashtab->entries); |
| obstack_free (pfile->hash_ob, 0); |
| free (pfile->hash_ob); |
| } |
| |
| /* 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. */ |
| |
| cpp_hashnode * |
| cpp_lookup (pfile, name, len) |
| cpp_reader *pfile; |
| const U_CHAR *name; |
| size_t len; |
| { |
| size_t n = len; |
| unsigned int r = 0; |
| const U_CHAR *str = name; |
| U_CHAR *dest = _cpp_pool_reserve (&pfile->ident_pool, len + 1); |
| |
| do |
| { |
| r = HASHSTEP (r, *str); |
| *dest++ = *str++; |
| } |
| while (--n); |
| *dest = '\0'; |
| |
| return _cpp_lookup_with_hash (pfile, len, r); |
| } |
| |
| /* NAME is a null-terminated identifier of length len. It is assumed |
| to have been placed at the front of the identifier pool. */ |
| cpp_hashnode * |
| _cpp_lookup_with_hash (pfile, len, hash) |
| cpp_reader *pfile; |
| size_t len; |
| unsigned int hash; |
| { |
| unsigned int index; |
| size_t size; |
| cpp_hashnode *entry; |
| cpp_hashnode **entries; |
| unsigned char *name = POOL_FRONT (&pfile->ident_pool); |
| |
| entries = pfile->hashtab->entries; |
| size = pfile->hashtab->size; |
| |
| hash += len; |
| index = hash % size; |
| |
| entry = entries[index]; |
| if (entry) |
| { |
| unsigned int hash2; |
| |
| 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) |
| break; |
| if (entry->hash == hash && entry->length == len |
| && !memcmp (entry->name, name, len)) |
| return entry; |
| } |
| } |
| |
| /* Commit the memory for the identifier. */ |
| POOL_COMMIT (&pfile->ident_pool, len + 1); |
| |
| /* Create a new hash node and insert it in the table. */ |
| entries[index] = obstack_alloc (pfile->hash_ob, sizeof (cpp_hashnode)); |
| |
| entry = entries[index]; |
| entry->type = NT_VOID; |
| entry->flags = 0; |
| entry->directive_index = 0; |
| entry->arg_index = 0; |
| entry->length = len; |
| entry->hash = hash; |
| entry->name = name; |
| entry->value.macro = 0; |
| |
| pfile->hashtab->nelts++; |
| if (size * 3 <= pfile->hashtab->nelts * 4) |
| expand_hash (pfile->hashtab); |
| |
| return entry; |
| } |
| |
| static void |
| expand_hash (htab) |
| struct htab *htab; |
| { |
| 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); |
| } |
| |
| /* The following function returns the nearest prime number which is |
| greater than a given source number, N. */ |
| |
| static unsigned long |
| higher_prime_number (n) |
| unsigned long n; |
| { |
| unsigned long i; |
| |
| /* Ensure we have a larger number and then force to odd. */ |
| n++; |
| n |= 0x01; |
| |
| /* All odd numbers < 9 are prime. */ |
| if (n < 9) |
| return n; |
| |
| /* 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; |
| } |
| |
| void |
| cpp_forall_identifiers (pfile, cb, v) |
| cpp_reader *pfile; |
| int (*cb) PARAMS ((cpp_reader *, cpp_hashnode *, void *)); |
| void *v; |
| { |
| cpp_hashnode **p, **limit; |
| |
| p = pfile->hashtab->entries; |
| limit = p + pfile->hashtab->size; |
| do |
| { |
| if (*p) |
| if ((*cb) (pfile, *p, v) == 0) |
| break; |
| } |
| while (++p < limit); |
| } |
| |
| /* Determine whether the identifier ID, of length LEN, is a defined macro. */ |
| int |
| cpp_defined (pfile, id, len) |
| cpp_reader *pfile; |
| const U_CHAR *id; |
| int len; |
| { |
| cpp_hashnode *hp = cpp_lookup (pfile, id, len); |
| |
| /* If it's of type NT_MACRO, it cannot be poisoned. */ |
| return hp->type == NT_MACRO; |
| } |