From 625cbc8522ee1850a3ea70fb121e5a7db1739d00 Mon Sep 17 00:00:00 2001 From: Ali Gholami Rudi Date: Thu, 31 Oct 2013 16:11:24 +0330 Subject: [PATCH] cpp: use a simple hash table instead of tab struct --- Makefile | 4 ++-- cpp.c | 54 ++++++++++++++++++++++++++++++------------------------ tab.c | 55 ------------------------------------------------------- tab.h | 14 -------------- 4 files changed, 32 insertions(+), 95 deletions(-) delete mode 100644 tab.c delete mode 100644 tab.h diff --git a/Makefile b/Makefile index d98848f..451d7db 100644 --- a/Makefile +++ b/Makefile @@ -17,9 +17,9 @@ LDFLAGS = all: ncc npp %.o: %.c ncc.h $(CC) -c $(CFLAGS) $< -ncc: ncc.o tok.o out.o cpp.o tab.o gen.o reg.o mem.o $(GEN) +ncc: ncc.o tok.o out.o cpp.o gen.o reg.o mem.o $(GEN) $(CC) -o $@ $^ $(LDFLAGS) -npp: npp.o cpp.o tab.o +npp: npp.o cpp.o $(CC) -o $@ $^ $(LDFLAGS) clean: diff --git a/cpp.c b/cpp.c index b42e362..9419a9e 100644 --- a/cpp.c +++ b/cpp.c @@ -10,7 +10,6 @@ #include #include "mem.h" #include "ncc.h" -#include "tab.h" #include "tok.h" static char *buf; @@ -18,15 +17,16 @@ static int len; static int cur; static struct macro { - char name[NAMELEN]; - char def[MDEFLEN]; + char name[NAMELEN]; /* macro name */ + char def[MDEFLEN]; /* macro definition */ char args[NARGS][NAMELEN]; - int nargs; - int isfunc; + int nargs; /* number of arguments */ + int isfunc; /* macro is a function */ + int undef; /* macro is removed */ } macros[NDEFS]; -static int nmacros; -/* macro hash table */ -static struct tab mtab; +static int mcount = 1; /* number of macros */ +static int mhead[256]; /* macro hash table heads */ +static int mnext[NDEFS]; /* macro hash table next entries */ #define BUF_FILE 0 #define BUF_MACRO 1 @@ -270,31 +270,37 @@ static void readarg(char *s) } } -static int macro_find(char *name) +/* find a macro; if undef is nonzero, search #undef-ed macros too */ +static int macro_find(char *name, int undef) { - char *n = tab_get(&mtab, name); - if (!n) - return -1; - return container(n, struct macro, name) - macros; + int i = mhead[(unsigned char) name[0]]; + while (i > 0) { + if (!strcmp(name, macros[i].name)) + if (!macros[i].undef || undef) + return i; + i = mnext[i]; + } + return -1; } static void macro_undef(char *name) { - int i = macro_find(name); + int i = macro_find(name, 0); if (i >= 0) - tab_del(&mtab, macros[i].name); + macros[i].undef = 1; } static int macro_new(char *name) { - int i = macro_find(name); + int i = macro_find(name, 1); if (i >= 0) return i; - if (nmacros >= NDEFS) + if (mcount >= NDEFS) die("nomem: NDEFS reached!\n"); - i = nmacros++; + i = mcount++; strcpy(macros[i].name, name); - tab_add(&mtab, macros[i].name); + mnext[i] = mhead[(unsigned char) name[0]]; + mhead[(unsigned char) name[0]] = i; return i; } @@ -406,8 +412,8 @@ static int cpp_cmd(void) if (cmd[2]) { int not = cmd[2] == 'n'; read_word(name); - matched = not ? macro_find(name) < 0 : - macro_find(name) >= 0; + matched = not ? macro_find(name, 0) < 0 : + macro_find(name, 0) >= 0; } else { matched = cpp_eval(); } @@ -470,7 +476,7 @@ static void macro_expand(char *name) buf_arg(dat, mbuf); return; } - m = ¯os[macro_find(name)]; + m = ¯os[macro_find(name, 0)]; if (!m->isfunc) { buf_macro(m); return; @@ -517,7 +523,7 @@ static int expandable(char *word) return 1; if (buf_expanding(word)) return 0; - i = macro_find(word); + i = macro_find(word, 0); return i >= 0 ? macros[i].isfunc + 1 : 0; } @@ -711,7 +717,7 @@ static long evalatom(void) int parens = !eval_jmp('('); long ret; eval_expect(TOK_NAME); - ret = macro_find(eval_id()) >= 0; + ret = macro_find(eval_id(), 0) >= 0; if (parens) eval_expect(')'); return ret; diff --git a/tab.c b/tab.c deleted file mode 100644 index c7bb02d..0000000 --- a/tab.c +++ /dev/null @@ -1,55 +0,0 @@ -#include -#include "tab.h" - -static int hash(char *s) -{ - unsigned h = 0x12345678; - while (*s) { - h ^= (h >> ((h & 0xf) + 1)); - h += *s++; - h ^= (h << ((h & 0xf) + 5)); - } - h &= (TABITEMS - 1); - return h ? h : 1; -} - -void tab_add(struct tab *t, char *s) -{ - int h = hash(s); - int i = t->n++; - if (!i) - i = t->n++; - t->next[i] = t->head[h]; - t->head[h] = i; - t->data[i] = s; -} - -char *tab_get(struct tab *t, char *s) -{ - int h = t->head[hash(s)]; - while (h && t->data[h]) { - if (!strcmp(s, t->data[h])) - return t->data[h]; - h = t->next[h]; - } - return NULL; -} - -void tab_del(struct tab *t, char *s) -{ - int h = t->head[hash(s)]; - int prev = 0; - while (h && t->data[h]) { - if (!strcmp(s, t->data[h])) { - if (prev) - t->next[prev] = t->next[h]; - else - t->head[h] = t->next[h]; - t->next[h] = 0; - t->data[h] = NULL; - return; - } - prev = h; - h = t->next[h]; - } -} diff --git a/tab.h b/tab.h deleted file mode 100644 index 889f020..0000000 --- a/tab.h +++ /dev/null @@ -1,14 +0,0 @@ -#define TABITEMS (1 << 12) -#define container(ptr, type, field) ((type *) ((void *) (ptr) - \ - offsetof(type, field))) - -struct tab { - int head[TABITEMS]; - char *data[TABITEMS]; - int next[TABITEMS]; - int n; -}; - -void tab_add(struct tab *t, char *s); -void tab_del(struct tab *t, char *s); -char *tab_get(struct tab *t, char *s); -- 2.11.4.GIT