This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
convert cpplib to use libiberty's hash tables
- To: gcc-patches at gcc dot gnu dot org
- Subject: convert cpplib to use libiberty's hash tables
- From: Zack Weinberg <zack at wolery dot cumb dot org>
- Date: Sun, 12 Mar 2000 15:44:23 -0800
Right, I've been sitting on this long enough. It could undoubtedly be
polished a bit more, but it's already a huge improvement in code
simplicity. Performance on this box is a wash; when I tried it on my
old slow machine several months ago, I got a 25% speedup.
One annoyance with hashtab.c is you have to create a dummy hash node
in order to look anything up. This complicates some of the code a
bit.
I took advantage of the opportunity to tidy up the include-file search
algorithm. It's now a lot easier to understand what's going on.
Further improvements are possible, but I'm going to shelve them for
the moment and focus on the parser rewrite (which should have been
done weeks ago...)
zw
Convert cpplib to use libiberty/hashtab.c.
* cpplib.h (struct cpp_reader): Make hashtab and
all_include_files of type 'struct htab *'. Delete HASHSIZE
and ALL_INCLUDE_HASHSIZE macros.
* cpphash.h: Update prototypes.
(struct hashnode): Remove next, prev, and bucket_hdr members.
Make length a size_t. Add hash member.
(struct ihash): Remove next member. Add hash member. Make
name a flexible array member.
* cppfiles.c: Include hashtab.h.
(include_hash): Delete.
(IHASHSIZE): New macro.
(hash_IHASH, eq_IHASH, _cpp_init_include_hash): New functions.
(cpp_included): Do the hash lookup here.
(_cpp_find_include_file): Rewrite.
(cpp_read_file): Put the "fake" hash entry into the hash
table. Honor the control_macro, if it turns out we've seen
the file before. Don't push the buffer here.
(_cpp_read_include_file): Push the buffer here.
(OMODES): New macro. Use it whenever we call open(2).
* cpphash.c: Include hashtab.h.
(hash_HASHNODE, eq_HASHNODE, del_HASHNODE, dump_hash_helper,
_cpp_init_macro_hash, _cpp_dump_macro_hash, _cpp_make_hashnode,
_cpp_lookup_slot): New functions.
(HASHSIZE): new macro.
(hashf, _cpp_install, _cpp_delete_macro): Delete.
(_cpp_lookup): Use hashtab.h routines.
* cppinit.c: Include hashtab.h.
(cpp_reader_init): Call _cpp_init_macro_hash and
_cpp_init_include_hash. Don't allocate hashtab directly.
(cpp_cleanup): Just call htab_delete on pfile->hashtab and
pfile->all_include_files.
(initialize_builtins): Use _cpp_make_hashnode and
htab_find_slot to add hash entries.
(cpp_finish): Just call _cpp_dump_macro_hash.
* cpplib.c: Include hashtab.h.
(do_define): Use _cpp_lookup_slot and _cpp_make_hashnode to
create hash entries.
(do_pragma_poison, do_assert): Likewise.
(do_include): Don't push the buffer here. Don't increment
system_include_depth unless _cpp_read_include_file succeeds.
(do_undef, do_unassert): Use _cpp_lookup_slot and htab_clear_slot
or htab_remove_elt.
(do_pragma_implementation): Use alloca to create copy.
* Makefile.in: Update dependencies.
===================================================================
Index: cppfiles.c
--- cppfiles.c 2000/03/11 00:49:44 1.44
+++ cppfiles.c 2000/03/12 23:26:41
@@ -28,9 +28,9 @@ Foundation, 59 Temple Place - Suite 330,
#include "system.h"
#include "cpplib.h"
#include "cpphash.h"
+#include "hashtab.h"
#include "intl.h"
-static IHASH *include_hash PARAMS ((cpp_reader *, const char *, int));
static IHASH *redundant_include_p PARAMS ((cpp_reader *, IHASH *,
struct file_name_list *));
static struct file_name_map *read_name_map
@@ -42,6 +42,10 @@ static long read_and_prescan PARAMS ((cp
int, size_t));
static struct file_name_list *actual_directory
PARAMS ((cpp_reader *, const char *));
+
+static unsigned int hash_IHASH PARAMS ((const void *));
+static int eq_IHASH PARAMS ((const void *, const void *));
+
static void init_input_buffer PARAMS ((cpp_reader *, int, struct stat *));
static int file_cleanup PARAMS ((cpp_buffer *, cpp_reader *));
static U_CHAR *find_position PARAMS ((U_CHAR *, U_CHAR *, unsigned long *));
@@ -50,50 +54,57 @@ static U_CHAR *find_position PARAMS ((U_
static void hack_vms_include_specification PARAMS ((char *));
#endif
+/* Initial size of include hash table. */
+#define IHASHSIZE 50
+
#ifndef INCLUDE_LEN_FUDGE
#define INCLUDE_LEN_FUDGE 0
#endif
-/* Look up or add an entry to the table of all includes. This table
- is indexed by the name as it appears in the #include line. The
- ->next_this_file chain stores all different files with the same
- #include name (there are at least three ways this can happen). The
- hash function could probably be improved a bit. */
+/* Open files in nonblocking mode, so we don't get stuck if someone
+ clever has asked cpp to process /dev/rmt0. _cpp_read_include_file
+ will check that we have a real file to work with. Also take care
+ not to acquire a controlling terminal by mistake (this can't happen
+ on sane systems, but paranoia is a virtue). */
+#define OMODES O_RDONLY|O_NONBLOCK|O_NOCTTY
+
+/* Calculate hash of an IHASH entry. */
+static unsigned int
+hash_IHASH (x)
+ const void *x;
+{
+ IHASH *i = (IHASH *)x;
+ unsigned int r = 0, len = 0;
+ const U_CHAR *s = i->nshort;
+
+ if (i->hash != (unsigned long)-1)
+ return i->hash;
+
+ do
+ len++, r = r * 67 + (*s++ - 113);
+ while (*s && *s != '.');
+ i->hash = r + len;
+ return r + len;
+}
-static IHASH *
-include_hash (pfile, fname, add)
- cpp_reader *pfile;
- const char *fname;
- int add;
+/* Compare an existing IHASH structure with a potential one. */
+static int
+eq_IHASH (x, y)
+ const void *x;
+ const void *y;
{
- unsigned int hash = 0;
- IHASH *l, *m;
- const char *f = fname;
-
- while (*f)
- hash += *f++;
-
- l = pfile->all_include_files[hash % ALL_INCLUDE_HASHSIZE];
- m = 0;
- for (; l; m = l, l = l->next)
- if (!strcmp (l->nshort, fname))
- return l;
+ const U_CHAR *a = ((const IHASH *)x)->nshort;
+ const U_CHAR *b = ((const IHASH *)y)->nshort;
+ return !strcmp (a, b);
+}
- if (!add)
- return 0;
-
- l = (IHASH *) xmalloc (sizeof (IHASH));
- l->next = NULL;
- l->next_this_file = NULL;
- l->foundhere = NULL;
- l->buf = NULL;
- l->limit = NULL;
- if (m)
- m->next = l;
- else
- pfile->all_include_files[hash % ALL_INCLUDE_HASHSIZE] = l;
-
- return l;
+/* Init the hash table. In here so it can see the hash and eq functions. */
+void
+_cpp_init_include_hash (pfile)
+ cpp_reader *pfile;
+{
+ pfile->all_include_files
+ = htab_create (IHASHSIZE, hash_IHASH, eq_IHASH, free);
}
/* Return 0 if the file pointed to by IHASH has never been included before,
@@ -152,9 +163,10 @@ cpp_included (pfile, fname)
cpp_reader *pfile;
const char *fname;
{
- IHASH *ptr;
-
- ptr = include_hash (pfile, fname, 0);
+ IHASH dummy, *ptr;
+ dummy.nshort = fname;
+ dummy.hash = -1;
+ ptr = htab_find (pfile->all_include_files, (const void *)&dummy);
return (ptr != NULL);
}
@@ -164,10 +176,7 @@ file_cleanup (pbuf, pfile)
cpp_reader *pfile;
{
if (pbuf->buf)
- {
- free ((PTR) pbuf->buf);
- pbuf->buf = 0;
- }
+ free ((PTR) pbuf->buf);
if (pfile->system_include_depth)
pfile->system_include_depth--;
return 0;
@@ -178,7 +187,7 @@ file_cleanup (pbuf, pfile)
(because it was included already and it's marked idempotent),
-1 if an error occurred, or a file descriptor open on the file.
*IHASH is set to point to the include hash entry for this file, and
- *BEFORE is 1 if the file was included before (but needs to be read
+ *BEFORE is set to 1 if the file was included before (but needs to be read
again). */
int
_cpp_find_include_file (pfile, fname, search_start, ihash, before)
@@ -188,97 +197,82 @@ _cpp_find_include_file (pfile, fname, se
IHASH **ihash;
int *before;
{
- struct file_name_list *l;
- IHASH *ih, *jh;
- int f, len;
+ struct file_name_list *path;
+ IHASH *ih, **slot;
+ IHASH dummy;
+ int f;
char *name;
-
- ih = include_hash (pfile, fname, 1);
- jh = redundant_include_p (pfile, ih,
- fname[0] == '/' ? ABSOLUTE_PATH : search_start);
- if (jh != 0)
- {
- *before = 1;
- *ihash = jh;
-
- if (jh == (IHASH *)-1)
- return -2;
- else
- return open (jh->name, O_RDONLY, 0666);
- }
+ dummy.hash = -1;
+ dummy.nshort = fname;
+ path = (fname[0] == '/') ? ABSOLUTE_PATH : search_start;
+ slot = (IHASH **) htab_find_slot (pfile->all_include_files,
+ (const void *)&dummy, 1);
- if (ih->foundhere)
- /* A file is already known by this name, but it's not the same file.
- Allocate another include_hash block and add it to the next_this_file
- chain. */
+ if (*slot && (ih = redundant_include_p (pfile, *slot, path)))
{
- jh = (IHASH *) xmalloc (sizeof (IHASH));
- while (ih->next_this_file) ih = ih->next_this_file;
-
- ih->next_this_file = jh;
- jh = ih;
- ih = ih->next_this_file;
+ if (ih == (IHASH *)-1)
+ return -2;
- ih->next = NULL;
- ih->next_this_file = NULL;
- ih->buf = NULL;
- ih->limit = NULL;
+ *before = 1;
+ *ihash = ih;
+ return open (ih->name, OMODES);
}
- *before = 0;
- *ihash = ih;
- ih->name = NULL;
- ih->nshort = xstrdup (fname);
- ih->control_macro = NULL;
-
- /* If the pathname is absolute, just open it. */
- if (fname[0] == '/')
+
+ if (path == ABSOLUTE_PATH)
{
- ih->foundhere = ABSOLUTE_PATH;
- ih->name = ih->nshort;
- return open (ih->name, O_RDONLY, 0666);
+ name = (char *) fname;
+ f = open (name, OMODES);
}
-
- /* Search directory path, trying to open the file. */
-
- len = strlen (fname);
- name = xmalloc (len + pfile->max_include_len + 2 + INCLUDE_LEN_FUDGE);
-
- for (l = search_start; l; l = l->next)
+ else
{
- memcpy (name, l->name, l->nlen);
- name[l->nlen] = '/';
- strcpy (&name[l->nlen+1], fname);
- _cpp_simplify_pathname (name);
- if (CPP_OPTIONS (pfile)->remap)
- name = remap_filename (pfile, name, l);
+ /* Search directory path, trying to open the file. */
+ name = alloca (strlen (fname) + pfile->max_include_len
+ + 2 + INCLUDE_LEN_FUDGE);
+ do
+ {
+ memcpy (name, path->name, path->nlen);
+ name[path->nlen] = '/';
+ strcpy (&name[path->nlen+1], fname);
+ _cpp_simplify_pathname (name);
+ if (CPP_OPTIONS (pfile)->remap)
+ name = remap_filename (pfile, name, path);
- f = open (name, O_RDONLY|O_NONBLOCK|O_NOCTTY, 0666);
+ f = open (name, OMODES);
#ifdef EACCES
- if (f == -1 && errno == EACCES)
- {
- cpp_error(pfile, "included file `%s' exists but is not readable",
- name);
- return -1;
- }
+ if (f == -1 && errno == EACCES)
+ {
+ cpp_error (pfile,
+ "included file `%s' exists but is not readable",
+ name);
+ return -1;
+ }
#endif
-
- if (f >= 0)
- {
- ih->foundhere = l;
- ih->name = xrealloc (name, strlen (name) + 1);
- return f;
- }
+ if (f >= 0)
+ break;
+ path = path->next;
+ }
+ while (path);
}
-
- if (jh)
- {
- jh->next_this_file = NULL;
- free (ih);
- }
- free (name);
- *ihash = (IHASH *)-1;
+ if (f == -1)
return -1;
+
+ ih = (IHASH *) xmalloc (sizeof (IHASH) + strlen (name));
+ strcpy ((char *)ih->name, name);
+ ih->foundhere = path;
+ if (path == ABSOLUTE_PATH)
+ ih->nshort = ih->name;
+ else
+ ih->nshort = strstr (ih->name, fname);
+ ih->control_macro = NULL;
+ ih->hash = dummy.hash;
+
+ ih->next_this_file = *slot;
+ *slot = ih;
+
+ *before = 0;
+ *ihash = ih;
+ return f;
}
/* The file_name_map structure holds a mapping of file names for a
@@ -482,54 +476,41 @@ cpp_read_file (pfile, fname)
cpp_reader *pfile;
const char *fname;
{
- IHASH *ih_fake;
+ IHASH *ih, **slot;
+ IHASH dummy;
int f;
- if (fname == NULL || *fname == 0)
- {
- fname = "";
- f = 0;
- }
+ if (fname == NULL)
+ fname = "";
- /* Open the file in nonblocking mode, so we don't get stuck if
- someone clever has asked cpp to process /dev/rmt0.
- _cpp_read_include_file will check that we have a real file to
- work with. Also take care not to acquire a controlling terminal
- by mistake (this can't happen on sane systems, but paranoia is a
- virtue). */
- else if ((f = open (fname, O_RDONLY|O_NONBLOCK|O_NOCTTY, 0666)) < 0)
+ dummy.hash = -1;
+ dummy.nshort = fname;
+ slot = (IHASH **) htab_find_slot (pfile->all_include_files,
+ (const void *) &dummy, 1);
+ if (*slot && (ih = redundant_include_p (pfile, *slot, ABSOLUTE_PATH)))
{
- cpp_notice_from_errno (pfile, fname);
- return 0;
+ if (ih == (IHASH *)-1)
+ return 1; /* Already included. */
}
-
- /* Push the buffer. */
- if (!cpp_push_buffer (pfile, NULL, 0))
- goto failed_push;
-
- /* Gin up an include_hash structure for this file and feed it
- to finclude. */
+ else
+ {
+ ih = (IHASH *) xmalloc (sizeof (IHASH) + strlen (fname));
+ ih->control_macro = 0;
+ ih->foundhere = ABSOLUTE_PATH; /* well sort of ... */
+ ih->hash = dummy.hash;
+ strcpy ((char *)ih->name, fname);
+ ih->nshort = ih->name;
- ih_fake = (IHASH *) xmalloc (sizeof (IHASH));
- ih_fake->next = 0;
- ih_fake->next_this_file = 0;
- ih_fake->foundhere = ABSOLUTE_PATH; /* well sort of ... */
- ih_fake->name = fname;
- ih_fake->control_macro = 0;
- ih_fake->buf = (char *)-1;
- ih_fake->limit = 0;
- if (!_cpp_read_include_file (pfile, f, ih_fake))
- goto failed_finclude;
+ ih->next_this_file = *slot;
+ *slot = ih;
+ }
- return 1;
+ if (*fname == '\0')
+ f = 0;
+ else
+ f = open (fname, OMODES);
- failed_finclude:
- /* If finclude fails, it pops the buffer. */
- free (ih_fake);
- failed_push:
- if (f)
- close (f);
- return 0;
+ return _cpp_read_include_file (pfile, f, ih);
}
/* Read the contents of FD into the buffer on the top of PFILE's stack.
@@ -549,13 +530,16 @@ _cpp_read_include_file (pfile, fd, ihash
long length;
cpp_buffer *fp;
+ fp = cpp_push_buffer (pfile, NULL, 0);
+
+ if (fp == 0)
+ goto push_fail;
+
if (fstat (fd, &st) < 0)
goto perror_fail;
if (fcntl (fd, F_SETFL, 0) == -1) /* turn off nonblocking mode */
goto perror_fail;
- fp = CPP_BUFFER (pfile);
-
/* If fd points to a plain file, we know how big it is, so we can
allocate the buffer all at once. If fd is a pipe or terminal, we
can't. Most C source files are 4k or less, so we guess that. If
@@ -632,12 +616,14 @@ _cpp_read_include_file (pfile, fd, ihash
fp->actual_dir = actual_directory (pfile, ihash->name);
pfile->input_stack_listing_current = 0;
+ pfile->only_seen_white = 2;
return 1;
perror_fail:
cpp_error_from_errno (pfile, ihash->name);
fail:
cpp_pop_buffer (pfile);
+ push_fail:
close (fd);
return 0;
}
@@ -1485,7 +1471,7 @@ hack_vms_include_specification (fullname
if (check_filename_before_returning)
{
- f = open (fullname, O_RDONLY, 0666);
+ f = open (fullname, OMODES);
if (f >= 0)
{
/* The file name is OK as it is, so return it as is. */
===================================================================
Index: cpphash.c
--- cpphash.c 2000/03/11 00:49:44 1.52
+++ cpphash.c 2000/03/12 23:26:43
@@ -27,10 +27,15 @@ Foundation, 59 Temple Place - Suite 330,
#include "system.h"
#include "cpplib.h"
#include "cpphash.h"
+#include "hashtab.h"
#include "version.h"
#undef abort
-static unsigned int hashf PARAMS ((const U_CHAR *, int));
+static unsigned int hash_HASHNODE PARAMS ((const void *));
+static int eq_HASHNODE PARAMS ((const void *, const void *));
+static void del_HASHNODE PARAMS ((void *));
+static int dump_hash_helper PARAMS ((void *, void *));
+
static int comp_def_part PARAMS ((int, U_CHAR *, int, U_CHAR *,
int, int));
static void push_macro_expansion PARAMS ((cpp_reader *,
@@ -45,6 +50,9 @@ static void special_symbol PARAMS ((HAS
#define FORWARD(N) CPP_FORWARD (CPP_BUFFER (pfile), (N))
#define PEEKC() CPP_BUF_PEEK (CPP_BUFFER (pfile))
+/* Initial hash table size. (It can grow if necessary - see hashtab.c.) */
+#define HASHSIZE 500
+
/* The arglist structure is built by create_definition to tell
collect_expansion where the argument names begin. That
is, for a define like "#define f(x,y,z) foo+x-bar*y", the arglist
@@ -91,29 +99,82 @@ struct argdata
int raw_length, expand_length;
int stringified_length;
};
-
-/* Calculate hash function on a string. */
-
+/* Calculate hash of a HASHNODE structure. */
static unsigned int
-hashf (s, len)
- register const U_CHAR *s;
- register int len;
+hash_HASHNODE (x)
+ const void *x;
{
- unsigned int n = len;
- unsigned int r = 0;
+ HASHNODE *h = (HASHNODE *)x;
+ const U_CHAR *s = h->name;
+ unsigned int len = h->length;
+ unsigned int n = len, r = 0;
+ if (h->hash != (unsigned long)-1)
+ return h->hash;
+
do
r = r * 67 + (*s++ - 113);
while (--n);
+ h->hash = r + len;
return r + len;
}
-/* Find the most recent hash node for name "name" (ending with first
- non-identifier char) installed by cpp_install
+/* Compare two HASHNODE structures. */
+static int
+eq_HASHNODE (x, y)
+ const void *x;
+ const void *y;
+{
+ const HASHNODE *a = (const HASHNODE *)x;
+ const HASHNODE *b = (const HASHNODE *)y;
+
+ return (a->length == b->length
+ && !strncmp (a->name, b->name, a->length));
+}
+/* Destroy a HASHNODE. */
+static void
+del_HASHNODE (x)
+ void *x;
+{
+ HASHNODE *h = (HASHNODE *)x;
+
+ if (h->type == T_MACRO)
+ _cpp_free_definition (h->value.defn);
+ free ((void *) h->name);
+ free (h);
+}
+
+/* Allocate and initialize a HASHNODE structure.
+ Caller must fill in the value field. */
+
+HASHNODE *
+_cpp_make_hashnode (name, len, type, hash)
+ const U_CHAR *name;
+ size_t len;
+ enum node_type type;
+ unsigned long hash;
+{
+ HASHNODE *hp = (HASHNODE *) xmalloc (sizeof (HASHNODE));
+ U_CHAR *p = xmalloc (len + 1);
+
+ hp->type = type;
+ hp->length = len;
+ hp->name = p;
+ hp->hash = hash;
+
+ memcpy (p, name, len);
+ p[len] = 0;
+
+ return hp;
+}
+
+/* Find the hash node for name "name", which ends at the first
+ non-identifier char.
+
If LEN is >= 0, it is the length of the name.
- Otherwise, compute the length by scanning the entire name. */
+ Otherwise, compute the length now. */
HASHNODE *
_cpp_lookup (pfile, name, len)
@@ -121,28 +182,60 @@ _cpp_lookup (pfile, name, len)
const U_CHAR *name;
int len;
{
- register const U_CHAR *bp;
- register HASHNODE *bucket;
- register unsigned int hash;
+ const U_CHAR *bp;
+ HASHNODE dummy;
if (len < 0)
{
for (bp = name; is_idchar (*bp); bp++);
len = bp - name;
}
+
+ dummy.name = name;
+ dummy.length = len;
+ dummy.hash = -1;
+
+ return (HASHNODE *) htab_find (pfile->hashtab, (void *)&dummy);
+}
- hash = hashf (name, len) % HASHSIZE;
+/* Find the hashtable slot for name "name". Used to insert or delete. */
+HASHNODE **
+_cpp_lookup_slot (pfile, name, len, insert, hash)
+ cpp_reader *pfile;
+ const U_CHAR *name;
+ int len;
+ int insert;
+ unsigned long *hash;
+{
+ const U_CHAR *bp;
+ HASHNODE dummy;
+ HASHNODE **slot;
- bucket = pfile->hashtab[hash];
- while (bucket)
+ if (len < 0)
{
- if (bucket->length == len && strncmp (bucket->name, name, len) == 0)
- return bucket;
- bucket = bucket->next;
+ for (bp = name; is_idchar (*bp); bp++);
+ len = bp - name;
}
- return (HASHNODE *) 0;
+
+ dummy.name = name;
+ dummy.length = len;
+ dummy.hash = -1;
+
+ slot = (HASHNODE **) htab_find_slot (pfile->hashtab, (void *)&dummy, insert);
+ if (insert)
+ *hash = dummy.hash;
+ return slot;
}
+/* Init the hash table. In here so it can see the hash and eq functions. */
+void
+_cpp_init_macro_hash (pfile)
+ cpp_reader *pfile;
+{
+ pfile->hashtab = htab_create (HASHSIZE, hash_HASHNODE,
+ eq_HASHNODE, del_HASHNODE);
+}
+
/* Free a DEFINITION structure. Used by delete_macro, and by
do_define when redefining macros. */
@@ -162,86 +255,6 @@ _cpp_free_definition (d)
free (d);
}
-/*
- * Delete a hash node. Some weirdness to free junk from macros.
- * More such weirdness will have to be added if you define more hash
- * types that need it.
- */
-
-void
-_cpp_delete_macro (hp)
- HASHNODE *hp;
-{
- if (hp->prev != NULL)
- hp->prev->next = hp->next;
- if (hp->next != NULL)
- hp->next->prev = hp->prev;
-
- /* make sure that the bucket chain header that
- the deleted guy was on points to the right thing afterwards. */
- if (hp == *hp->bucket_hdr)
- *hp->bucket_hdr = hp->next;
-
- if (hp->type == T_MACRO)
- _cpp_free_definition (hp->value.defn);
-
- free (hp);
-}
-
-/* Install a name in the main hash table, even if it is already there.
- Name stops with first non alphanumeric, except leading '#'.
- Caller must check against redefinition if that is desired.
- delete_macro () removes things installed by cpp_install () in fifo order.
- this is important because of the `defined' special symbol used
- in #if, and also if pushdef/popdef directives are ever implemented.
-
- If LEN is >= 0, it is the length of the name.
- Otherwise, compute the length by scanning the entire name.
-
- If HASH is >= 0, it is the precomputed hash code.
- Otherwise, compute the hash code. */
-
-HASHNODE *
-_cpp_install (pfile, name, len, type, value)
- cpp_reader *pfile;
- const U_CHAR *name;
- int len;
- enum node_type type;
- const char *value;
-{
- register HASHNODE *hp;
- register int i, bucket;
- register const U_CHAR *p;
- unsigned int hash;
-
- if (len < 0)
- {
- p = name;
- while (is_idchar(*p))
- p++;
- len = p - name;
- }
-
- hash = hashf (name, len) % HASHSIZE;
-
- i = sizeof (HASHNODE) + len + 1;
- hp = (HASHNODE *) xmalloc (i);
- bucket = hash;
- hp->bucket_hdr = &pfile->hashtab[bucket];
- hp->next = pfile->hashtab[bucket];
- pfile->hashtab[bucket] = hp;
- hp->prev = NULL;
- if (hp->next != NULL)
- hp->next->prev = hp;
- hp->type = type;
- hp->length = len;
- hp->value.cpval = value;
- hp->name = ((U_CHAR *) hp) + sizeof (HASHNODE);
- memcpy (hp->name, name, len);
- hp->name[len] = 0;
- return hp;
-}
-
static int
macro_cleanup (pbuf, pfile)
cpp_buffer *pbuf;
@@ -255,7 +268,6 @@ macro_cleanup (pbuf, pfile)
return 0;
}
-
/* Read a replacement list for a macro, and build the DEFINITION
structure. ARGLIST specifies the formal parameters to look for in
the text of the definition. If ARGLIST is null, this is an
@@ -503,7 +515,6 @@ collect_expansion (pfile, arglist)
while (here > last && is_hspace (pfile->token_buffer [here-1]))
here--;
CPP_SET_WRITTEN (pfile, here);
-
CPP_NUL_TERMINATE (pfile);
len = CPP_WRITTEN (pfile) - start + 1;
/* space for no-concat markers at either end */
@@ -1666,8 +1677,27 @@ _cpp_dump_definition (pfile, sym, len, d
if (*x == '\r') x += 2, i -= 2;
if (i > 0) CPP_PUTS (pfile, x, i);
}
-
if (pfile->lineno == 0)
CPP_PUTC (pfile, '\n');
CPP_NUL_TERMINATE (pfile);
+}
+
+/* Dump out the hash table. */
+static int
+dump_hash_helper (h, p)
+ void *h;
+ void *p;
+{
+ HASHNODE *hp = (HASHNODE *)h;
+ cpp_reader *pfile = (cpp_reader *)p;
+
+ _cpp_dump_definition (pfile, hp->name, hp->length, hp->value.defn);
+ return 1;
+}
+
+void
+_cpp_dump_macro_hash (pfile)
+ cpp_reader *pfile;
+{
+ htab_traverse (pfile->hashtab, dump_hash_helper, pfile);
}
===================================================================
Index: cpphash.h
--- cpphash.h 2000/03/08 23:35:18 1.20
+++ cpphash.h 2000/03/12 23:26:43
@@ -132,15 +132,11 @@ union hashval
typedef struct hashnode HASHNODE;
struct hashnode
{
- struct hashnode *next; /* double links for easy deletion */
- struct hashnode *prev;
- struct hashnode **bucket_hdr; /* also, a back pointer to this node's hash
- chain is kept, in case the node is the head
- of the chain and gets deleted. */
- enum node_type type; /* type of special token */
- int length; /* length of token, for quick comparison */
- U_CHAR *name; /* the actual name */
+ const U_CHAR *name; /* the actual name */
+ size_t length; /* length of token, for quick comparison */
+ unsigned long hash; /* cached hash value */
union hashval value; /* pointer to expansion, or whatever */
+ enum node_type type; /* type of special token */
};
/* List of directories to look for include files in. */
@@ -169,7 +165,6 @@ struct file_name_list
#include statement) which is stored in *nshort. */
struct ihash
{
- struct ihash *next;
/* Next file with the same short name but a
different (partial) pathname). */
struct ihash *next_this_file;
@@ -177,12 +172,13 @@ struct ihash
/* Location of the file in the include search path.
Used for include_next */
struct file_name_list *foundhere;
- const char *name; /* (partial) pathname of file */
- const char *nshort; /* name of file as referenced in #include */
+
+ unsigned long hash; /* save hash value for future reference */
+ const char *nshort; /* name of file as referenced in #include;
+ points into name[] */
const U_CHAR *control_macro; /* macro, if any, preventing reinclusion -
see redundant_include_p */
- char *buf, *limit; /* for file content cache,
- not yet implemented */
+ const char name[1]; /* (partial) pathname of file */
};
typedef struct ihash IHASH;
@@ -247,19 +243,23 @@ extern unsigned char _cpp_IStable[256];
(CPP_OPTIONS (PFILE)->pedantic && !CPP_BUFFER (pfile)->system_header_p)
/* In cpphash.c */
-extern HASHNODE *_cpp_install PARAMS ((cpp_reader *, const U_CHAR *, int,
- enum node_type, const char *));
-extern HASHNODE *_cpp_lookup PARAMS ((cpp_reader *, const U_CHAR *, int));
-extern void _cpp_free_definition PARAMS ((DEFINITION *));
-extern void _cpp_delete_macro PARAMS ((HASHNODE *));
-
-extern DEFINITION *_cpp_create_definition
- PARAMS ((cpp_reader *, int));
-extern int _cpp_compare_defs PARAMS ((cpp_reader *, DEFINITION *,
- DEFINITION *));
-extern void _cpp_macroexpand PARAMS ((cpp_reader *, HASHNODE *));
-extern void _cpp_dump_definition PARAMS ((cpp_reader *, const U_CHAR *, long,
- DEFINITION *));
+extern HASHNODE *_cpp_make_hashnode PARAMS ((const U_CHAR *, size_t,
+ enum node_type,
+ unsigned long));
+extern HASHNODE *_cpp_lookup PARAMS ((cpp_reader *,
+ const U_CHAR *, int));
+extern HASHNODE **_cpp_lookup_slot PARAMS ((cpp_reader *,
+ const U_CHAR *, int, int,
+ unsigned long *));
+extern void _cpp_free_definition PARAMS ((DEFINITION *));
+extern DEFINITION *_cpp_create_definition PARAMS ((cpp_reader *, int));
+extern void _cpp_dump_definition PARAMS ((cpp_reader *, const U_CHAR *,
+ long, DEFINITION *));
+extern int _cpp_compare_defs PARAMS ((cpp_reader *, DEFINITION *,
+ DEFINITION *));
+extern void _cpp_macroexpand PARAMS ((cpp_reader *, HASHNODE *));
+extern void _cpp_init_macro_hash PARAMS ((cpp_reader *));
+extern void _cpp_dump_macro_hash PARAMS ((cpp_reader *));
/* In cppfiles.c */
extern void _cpp_simplify_pathname PARAMS ((char *));
@@ -267,6 +267,7 @@ extern int _cpp_find_include_file PARAMS
struct file_name_list *,
IHASH **, int *));
extern int _cpp_read_include_file PARAMS ((cpp_reader *, int, IHASH *));
+extern void _cpp_init_include_hash PARAMS ((cpp_reader *));
/* In cppexp.c */
extern int _cpp_parse_expr PARAMS ((cpp_reader *));
===================================================================
Index: cppinit.c
--- cppinit.c 2000/03/12 13:55:52 1.61
+++ cppinit.c 2000/03/12 23:26:43
@@ -28,6 +28,7 @@ Foundation, 59 Temple Place - Suite 330,
#include "prefix.h"
#include "intl.h"
#include "version.h"
+#include "hashtab.h"
#include "mkdeps.h"
/* Predefined symbols, built-in macros, and the default include path. */
@@ -554,7 +555,8 @@ cpp_reader_init (pfile)
pfile->token_buffer = (U_CHAR *) xmalloc (pfile->token_buffer_size);
CPP_SET_WRITTEN (pfile, 0);
- pfile->hashtab = (HASHNODE **) xcalloc (HASHSIZE, sizeof (HASHNODE *));
+ _cpp_init_macro_hash (pfile);
+ _cpp_init_include_hash (pfile);
}
/* Free resources used by PFILE.
@@ -563,7 +565,6 @@ void
cpp_cleanup (pfile)
cpp_reader *pfile;
{
- int i;
while (CPP_BUFFER (pfile) != NULL)
cpp_pop_buffer (pfile);
@@ -584,25 +585,8 @@ cpp_cleanup (pfile)
if (pfile->deps)
deps_free (pfile->deps);
- for (i = ALL_INCLUDE_HASHSIZE; --i >= 0; )
- {
- IHASH *imp, *next;
- for (imp = pfile->all_include_files[i]; imp; imp = next)
- {
- next = imp->next;
- free ((PTR) imp->name);
- free ((PTR) imp->nshort);
- free (imp);
- }
- pfile->all_include_files[i] = 0;
- }
-
- for (i = HASHSIZE; --i >= 0;)
- {
- while (pfile->hashtab[i])
- _cpp_delete_macro (pfile->hashtab[i]);
- }
- free (pfile->hashtab);
+ htab_delete (pfile->hashtab);
+ htab_delete (pfile->all_include_files);
}
@@ -654,7 +638,6 @@ static const struct builtin builtin_arra
/* Subroutine of cpp_start_read; reads the builtins table above and
enters the macros into the hash table. */
-
static void
initialize_builtins (pfile)
cpp_reader *pfile;
@@ -662,6 +645,7 @@ initialize_builtins (pfile)
int len;
const struct builtin *b;
const char *val;
+ HASHNODE *hp;
for(b = builtin_array; b->name; b++)
{
if ((b->flags & STDC) && CPP_TRADITIONAL (pfile))
@@ -669,8 +653,11 @@ initialize_builtins (pfile)
val = (b->flags & ULP) ? user_label_prefix : b->value;
len = strlen (b->name);
+
+ hp = _cpp_make_hashnode (b->name, len, b->type, -1);
+ hp->value.cpval = val;
+ *(htab_find_slot (pfile->hashtab, (void *)hp, 1)) = hp;
- _cpp_install (pfile, b->name, len, b->type, val);
if ((b->flags & DUMP) && CPP_OPTIONS (pfile)->debug_output)
dump_special_to_buffer (pfile, b->name);
}
@@ -1015,20 +1002,7 @@ cpp_finish (pfile)
}
if (opts->dump_macros == dump_only)
- {
- int i;
- HASHNODE *h;
- for (i = HASHSIZE; --i >= 0;)
- {
- for (h = pfile->hashtab[i]; h; h = h->next)
- if (h->type == T_MACRO)
- {
- _cpp_dump_definition (pfile, h->name, h->length,
- h->value.defn);
- CPP_PUTC (pfile, '\n');
- }
- }
- }
+ _cpp_dump_macro_hash (pfile);
}
static void
===================================================================
Index: cpplib.c
--- cpplib.c 2000/03/11 00:49:44 1.130
+++ cpplib.c 2000/03/12 23:26:43
@@ -24,6 +24,7 @@ Foundation, 59 Temple Place - Suite 330,
#include "cpplib.h"
#include "cpphash.h"
+#include "hashtab.h"
#include "intl.h"
#include "mkdeps.h"
@@ -659,9 +660,10 @@ do_define (pfile, keyword)
cpp_reader *pfile;
const struct directive *keyword ATTRIBUTE_UNUSED;
{
- HASHNODE *hp;
+ HASHNODE **slot;
DEFINITION *def;
long here;
+ unsigned long hash;
int len, c;
int funlike = 0;
U_CHAR *sym;
@@ -692,9 +694,11 @@ do_define (pfile, keyword)
if (def == 0)
return 0;
- if ((hp = _cpp_lookup (pfile, sym, len)) != NULL)
+ slot = _cpp_lookup_slot (pfile, sym, len, 1, &hash);
+ if (*slot)
{
int ok;
+ HASHNODE *hp = *slot;
/* Redefining a macro is ok if the definitions are the same. */
if (hp->type == T_MACRO)
@@ -729,7 +733,11 @@ do_define (pfile, keyword)
}
}
else
- _cpp_install (pfile, sym, len, T_MACRO, (char *) def);
+ {
+ HASHNODE *hp = _cpp_make_hashnode (sym, len, T_MACRO, hash);
+ hp->value.defn = def;
+ *slot = hp;
+ }
if (CPP_OPTIONS (pfile)->debug_output
|| CPP_OPTIONS (pfile)->dump_macros == dump_definitions)
@@ -1260,21 +1268,12 @@ do_include (pfile, keyword)
if (importing)
ihash->control_macro = (const U_CHAR *) "";
- if (cpp_push_buffer (pfile, NULL, 0) == NULL)
- {
- close (fd);
- return 0;
- }
-
- if (angle_brackets)
- pfile->system_include_depth++; /* Decremented in file_cleanup. */
-
if (_cpp_read_include_file (pfile, fd, ihash))
{
output_line_command (pfile, enter_file);
- pfile->only_seen_white = 2;
+ if (angle_brackets)
+ pfile->system_include_depth++; /* Decremented in file_cleanup. */
}
-
return 0;
}
@@ -1435,7 +1434,7 @@ do_undef (pfile, keyword)
const struct directive *keyword;
{
int len;
- HASHNODE *hp;
+ HASHNODE **slot;
U_CHAR *buf, *name, *limit;
int c;
long here = CPP_WRITTEN (pfile);
@@ -1468,8 +1467,10 @@ do_undef (pfile, keyword)
}
CPP_SET_WRITTEN (pfile, here);
- while ((hp = _cpp_lookup (pfile, name, len)) != NULL)
+ slot = _cpp_lookup_slot (pfile, name, len, 0, 0);
+ if (slot)
{
+ HASHNODE *hp = *slot;
/* If we are generating additional info for debugging (with -g) we
need to pass through all effective #undef commands. */
if (CPP_OPTIONS (pfile)->debug_output && keyword)
@@ -1480,7 +1481,8 @@ do_undef (pfile, keyword)
{
if (hp->type != T_MACRO)
cpp_warning (pfile, "undefining `%s'", hp->name);
- _cpp_delete_macro (hp);
+
+ htab_clear_slot (pfile->hashtab, (void **)slot);
}
}
@@ -1692,6 +1694,7 @@ do_pragma_implementation (pfile)
long written = CPP_WRITTEN (pfile);
U_CHAR *name;
U_CHAR *copy;
+ size_t len;
token = get_directive_token (pfile);
if (token == CPP_VSPACE)
@@ -1703,14 +1706,15 @@ do_pragma_implementation (pfile)
}
name = pfile->token_buffer + written + 1;
- copy = (U_CHAR *) xstrdup (name);
- copy[strlen(copy)] = '\0'; /* trim trailing quote */
-
+ len = strlen (name);
+ copy = (U_CHAR *) alloca (len);
+ memcpy (copy, name, len - 1);
+ copy[len] = '\0'; /* trim trailing quote */
+
if (cpp_included (pfile, copy))
cpp_warning (pfile,
"`#pragma implementation' for `%s' appears after file is included",
copy);
- free (copy);
return 0;
}
@@ -1721,11 +1725,13 @@ do_pragma_poison (pfile)
/* Poison these symbols so that all subsequent usage produces an
error message. */
U_CHAR *p;
- HASHNODE *hp;
+ HASHNODE **slot;
long written;
size_t len;
enum cpp_token token;
int writeit;
+ unsigned long hash;
+
/* As a rule, don't include #pragma poison commands in output,
unless the user asks for them. */
writeit = (CPP_OPTIONS (pfile)->debug_output
@@ -1747,8 +1753,10 @@ do_pragma_poison (pfile)
p = pfile->token_buffer + written;
len = strlen (p);
- if ((hp = _cpp_lookup (pfile, p, len)))
+ slot = _cpp_lookup_slot (pfile, p, len, 1, &hash);
+ if (*slot)
{
+ HASHNODE *hp = *slot;
if (hp->type != T_POISON)
{
cpp_warning (pfile, "poisoning existing macro `%s'", p);
@@ -1759,7 +1767,11 @@ do_pragma_poison (pfile)
}
}
else
- _cpp_install (pfile, p, len, T_POISON, 0);
+ {
+ HASHNODE *hp = _cpp_make_hashnode (p, len, T_POISON, hash);
+ hp->value.cpval = 0;
+ *slot = hp;
+ }
if (writeit)
CPP_PUTC (pfile, ' ');
}
@@ -3025,7 +3037,9 @@ do_assert (pfile, keyword)
U_CHAR *sym;
int ret, c;
HASHNODE *base, *this;
- int baselen, thislen;
+ HASHNODE **bslot, **tslot;
+ size_t blen, tlen;
+ unsigned long bhash, thash;
if (CPP_PEDANTIC (pfile) && CPP_OPTIONS (pfile)->done_initializing)
cpp_pedwarn (pfile, "ANSI C does not allow `#assert'");
@@ -3049,27 +3063,30 @@ do_assert (pfile, keyword)
goto error;
}
- thislen = strlen (sym);
- baselen = (U_CHAR *) strchr (sym, '(') - sym;
- this = _cpp_lookup (pfile, sym, thislen);
- if (this)
+ tlen = strlen (sym);
+ blen = (U_CHAR *) strchr (sym, '(') - sym;
+ tslot = _cpp_lookup_slot (pfile, sym, tlen, 1, &thash);
+ if (*tslot)
{
cpp_warning (pfile, "`%s' re-asserted", sym);
goto error;
}
- base = _cpp_lookup (pfile, sym, baselen);
- if (! base)
- base = _cpp_install (pfile, sym, baselen, T_ASSERT, 0);
- else if (base->type != T_ASSERT)
- {
- /* Token clash - but with what?! */
- cpp_ice (pfile, "base->type != T_ASSERT in do_assert");
- goto error;
- }
-
- this = _cpp_install (pfile, sym, thislen, T_ASSERT,
- (char *)base->value.aschain);
+ bslot = _cpp_lookup_slot (pfile, sym, blen, 1, &bhash);
+ if (! *bslot)
+ *bslot = base = _cpp_make_hashnode (sym, blen, T_ASSERT, bhash);
+ else
+ {
+ base = *bslot;
+ if (base->type != T_ASSERT)
+ {
+ /* Token clash - but with what?! */
+ cpp_ice (pfile, "base->type != T_ASSERT in do_assert");
+ goto error;
+ }
+ }
+ *tslot = this = _cpp_make_hashnode (sym, tlen, T_ASSERT, thash);
+ this->value.aschain = base->value.aschain;
base->value.aschain = this;
pfile->limit = sym; /* Pop */
@@ -3118,9 +3135,9 @@ do_unassert (pfile, keyword)
for (this = base->value.aschain; this; this = next)
{
next = this->value.aschain;
- _cpp_delete_macro (this);
+ htab_remove_elt (pfile->hashtab, this);
}
- _cpp_delete_macro (base);
+ htab_remove_elt (pfile->hashtab, base);
}
else
{
@@ -3135,10 +3152,11 @@ do_unassert (pfile, keyword)
next = next->value.aschain;
next->value.aschain = this->value.aschain;
- _cpp_delete_macro (this);
+ htab_remove_elt (pfile->hashtab, this);
if (base->value.aschain == NULL)
- _cpp_delete_macro (base); /* Last answer for this predicate deleted. */
+ /* Last answer for this predicate deleted. */
+ htab_remove_elt (pfile->hashtab, base);
}
pfile->limit = sym; /* Pop */
===================================================================
Index: cpplib.h
--- cpplib.h 2000/03/11 00:49:44 1.69
+++ cpplib.h 2000/03/12 23:26:43
@@ -121,6 +121,7 @@ struct cpp_buffer
};
struct file_name_map_list;
+struct htab;
/* Maximum nesting of cpp_buffers. We use a static limit, partly for
efficiency, and partly to limit runaway recursion. */
@@ -155,12 +156,10 @@ struct cpp_reader
int buffer_stack_depth;
/* Hash table of macros and assertions. See cpphash.c */
-#define HASHSIZE 1403
- struct hashnode **hashtab;
+ struct htab *hashtab;
/* Hash table of other included files. See cppfiles.c */
-#define ALL_INCLUDE_HASHSIZE 71
- struct ihash *all_include_files[ALL_INCLUDE_HASHSIZE];
+ struct htab *all_include_files;
/* Chain of `actual directory' file_name_list entries,
for "" inclusion. */
@@ -502,7 +501,6 @@ extern void output_line_command PARAMS
/* In cppfiles.c */
extern int cpp_included PARAMS ((cpp_reader *, const char *));
extern int cpp_read_file PARAMS ((cpp_reader *, const char *));
-
#ifdef __cplusplus
}
===================================================================
Index: Makefile.in
--- Makefile.in 2000/03/10 08:16:55 1.396
+++ Makefile.in 2000/03/12 23:42:57
@@ -2029,6 +2029,7 @@ LIBCPP_OBJS = cpplib.o cpphash.o cpperro
prefix.o version.o mbchar.o @extra_cpp_objs@
LIBCPP_DEPS = cpplib.h cpphash.h intl.h system.h
+HASHTAB_H = $(srcdir)/../include/hashtab.h
# All the other archives built/used by this makefile are for targets. This
# one is strictly for the host.
@@ -2042,17 +2043,17 @@ cppmain$(exeext): cppmain.o intl.o libcp
$(CC) $(ALL_CFLAGS) $(LDFLAGS) -o cppmain$(exeext) cppmain.o \
intl.o libcpp.a $(LIBS)
-cppmain.o: cppmain.c $(CONFIG_H) cpplib.h intl.h system.h
+cppmain.o: cppmain.c $(CONFIG_H) cpplib.h intl.h system.h
-cppulp.o: cppulp.c $(CONFIG_H) system.h output.h
-cpplib.o: cpplib.c $(CONFIG_H) $(LIBCPP_DEPS) mkdeps.h
-cpphash.o: cpphash.c $(CONFIG_H) $(LIBCPP_DEPS) version.h
+cppulp.o: cppulp.c $(CONFIG_H) system.h output.h
cpperror.o: cpperror.c $(CONFIG_H) $(LIBCPP_DEPS)
cppexp.o: cppexp.c $(CONFIG_H) $(LIBCPP_DEPS)
-cppfiles.o: cppfiles.c $(CONFIG_H) $(LIBCPP_DEPS)
+cppfiles.o: cppfiles.c $(CONFIG_H) $(LIBCPP_DEPS) $(HASHTAB_H)
+cpphash.o: cpphash.c $(CONFIG_H) $(LIBCPP_DEPS) $(HASHTAB_H) version.h
+cpplib.o: cpplib.c $(CONFIG_H) $(LIBCPP_DEPS) $(HASHTAB_H) mkdeps.h
-cppinit.o: cppinit.c $(CONFIG_H) cpplib.h intl.h system.h \
- cpphash.h prefix.h output.h Makefile version.h mkdeps.h
+cppinit.o: cppinit.c $(CONFIG_H) $(LIBCPP_DEPS) $(HASHTAB_H) mkdeps.h \
+ prefix.h output.h Makefile version.h
$(CC) $(ALL_CFLAGS) $(ALL_CPPFLAGS) $(INCLUDES) \
$(PREPROCESSOR_DEFINES) \
-c `echo $(srcdir)/cppinit.c | sed 's,^\./,,'`