diff options
| author | Linus Torvalds <torvalds@linux-foundation.org> | 2011-04-19 13:02:08 -0700 |
|---|---|---|
| committer | Christopher Li <sparse@chrisli.org> | 2011-04-19 13:02:08 -0700 |
| commit | 52df775e6235b81ddb44f885214f40ea562a61ea (patch) | |
| tree | c0362ece9476706bb527ad498d323c229b61fa5f | |
| parent | aaff080449ebcb66553ebf5b512f737b6191f339 (diff) | |
| download | sparse-dev-52df775e6235b81ddb44f885214f40ea562a61ea.tar.gz | |
Add new streams to a hash-list based on their names
This trivially creates a small (currently 64-entry) hash table for
stream numbers, so that you can look up a stream by its name.
Nothing currently uses it, but the next commit will teach
"already_tokenized()" to look up the stream by name, allowing us to
avoid the "walk over each stream we've seen" loop. The silly string
compare in that loop can take a lot of CPU time.
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
Signed-off-by: Christopher Li <sparse@chrisli.org>
| -rw-r--r-- | token.h | 3 | ||||
| -rw-r--r-- | tokenize.c | 25 |
2 files changed, 26 insertions, 2 deletions
@@ -40,7 +40,7 @@ struct stream { /* Use these to check for "already parsed" */ enum constantfile constant; - int dirty; + int dirty, next_stream; struct ident *protect; struct token *ifndef; struct token *top_if; @@ -49,6 +49,7 @@ struct stream { extern int input_stream_nr; extern struct stream *input_streams; extern unsigned int tabstop; +extern int *hash_stream(const char *name); struct ident { struct ident *next; /* Hash chain of identifiers */ @@ -14,6 +14,7 @@ #include <string.h> #include <ctype.h> #include <unistd.h> +#include <stdint.h> #include "lib.h" #include "allocate.h" @@ -179,9 +180,28 @@ const char *show_token(const struct token *token) } } +#define HASHED_INPUT_BITS (6) +#define HASHED_INPUT (1 << HASHED_INPUT_BITS) +#define HASH_PRIME 0x9e370001UL + +static int input_stream_hashes[HASHED_INPUT] = { [0 ... HASHED_INPUT-1] = -1 }; + +int *hash_stream(const char *name) +{ + uint32_t hash = 0; + unsigned char c; + + while ((c = *name++) != 0) + hash = (hash + (c << 4) + (c >> 4)) * 11; + + hash *= HASH_PRIME; + hash >>= 32 - HASHED_INPUT_BITS; + return input_stream_hashes + hash; +} + int init_stream(const char *name, int fd, const char **next_path) { - int stream = input_stream_nr; + int stream = input_stream_nr, *hash; struct stream *current; if (stream >= input_streams_allocated) { @@ -199,6 +219,9 @@ int init_stream(const char *name, int fd, const char **next_path) current->path = NULL; current->constant = CONSTANT_FILE_MAYBE; input_stream_nr = stream+1; + hash = hash_stream(name); + current->next_stream = *hash; + *hash = stream; return stream; } |