summaryrefslogtreecommitdiffabout
authorSergey Poznyakoff <gray@gnu.org.ua>2009-06-28 23:15:52 (GMT)
committer Sergey Poznyakoff <gray@gnu.org.ua>2009-06-28 23:16:56 (GMT)
commit23abfa7a31bf5dedd09cd0963da7dc4a291631eb (patch) (side-by-side diff)
treef6b892f1b0c2932bacea14e6ff92529f2f8bbfd0
parenteb6e7c7cee0c998f5b403074201992c22383a553 (diff)
downloadcflow-23abfa7a31bf5dedd09cd0963da7dc4a291631eb.tar.gz
cflow-23abfa7a31bf5dedd09cd0963da7dc4a291631eb.tar.bz2
Use doubly-linked lists to keep statics and autos.
* src/Makefile.am (cflow_SOURCES): Order sources. * src/cflow.h (struct linked_list_entry): Add new member: list. (struct symbol): New members: owner, entry (install_ident, ident_change_storage): New prototypes. (linked_list_iterate, linked_list_unlink) (data_in_list): New prototypes. * src/linked-list.c (linked_list_append) (linked_list_iterate): Update for doubly-linked lists. (linked_list_unlink): New function. (linked_list_prepend): Comment out: not used this far. * src/parser.c: Use install_ident and ident_change_storage. * src/symbol.c: Keep information about automatic variables/parameters (on a per-function basis) and static identifiers (on a per-module basis) in two separate linked lists. This speeds up cleanup procedures.
Diffstat (more/less context) (ignore whitespace changes)
-rw-r--r--src/Makefile.am15
-rw-r--r--src/cflow.h15
-rw-r--r--src/linked-list.c148
-rw-r--r--src/parser.c44
-rw-r--r--src/symbol.c312
5 files changed, 329 insertions, 205 deletions
diff --git a/src/Makefile.am b/src/Makefile.am
index 2ca13e5..7252ff8 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -22,16 +22,17 @@ INCLUDES = -I$(top_srcdir)/lib -I../ -I../lib
bin_PROGRAMS = cflow
cflow_SOURCES = \
- main.c\
- rc.c\
- parser.c\
c.l\
- output.c\
- symbol.c\
cflow.h\
- parser.h\
gnu.c\
- posix.c
+ linked-list.c\
+ main.c\
+ output.c\
+ parser.c\
+ parser.h\
+ posix.c\
+ rc.c\
+ symbol.c
localedir = $(datadir)/locale
diff --git a/src/cflow.h b/src/cflow.h
index c6712c9..d933750 100644
--- a/src/cflow.h
+++ b/src/cflow.h
@@ -46,7 +46,8 @@
#define NUMITEMS(a) sizeof(a)/sizeof((a)[0])
struct linked_list_entry {
- struct linked_list_entry *next;
+ struct linked_list_entry *next, *prev;
+ struct linked_list *list;
void *data;
};
@@ -88,7 +89,10 @@ enum symbol_flag {
typedef struct symbol Symbol;
struct symbol {
+ struct table_entry *owner;
Symbol *next; /* Next symbol with the same hash */
+ struct linked_list_entry *entry;
+
enum symtype type; /* Type of the symbol */
char *name; /* Identifier */
enum symbol_flag flag; /* Specific flag */
@@ -162,6 +166,8 @@ extern unsigned input_file_count;
Symbol *lookup(char*);
Symbol *install(char*);
+Symbol *install_ident(char *name, enum storage storage);
+void ident_change_storage(Symbol *sp, enum storage storage);
void delete_autos(int level);
void delete_statics(void);
void delete_parms(int level);
@@ -171,7 +177,12 @@ struct linked_list *linked_list_create(linked_list_free_data_fp fun);
void linked_list_destroy(struct linked_list **plist);
void linked_list_append(struct linked_list **plist, void *data);
void linked_list_prepend(struct linked_list **plist, void *data);
-int symbol_in_list(Symbol *sym, struct linked_list *list);
+void linked_list_iterate(struct linked_list **plist,
+ int (*itr) (void *, void *), void *data);
+void linked_list_unlink(struct linked_list *list,
+ struct linked_list_entry *ent);
+
+int data_in_list(void *data, struct linked_list *list);
int get_token(void);
int source(char *name);
diff --git a/src/linked-list.c b/src/linked-list.c
new file mode 100644
index 0000000..b7266ad
--- a/dev/null
+++ b/src/linked-list.c
@@ -0,0 +1,148 @@
+/* This file is part of GNU cflow
+ Copyright (C) 1997, 2005, 2006, 2007, 2009 Sergey Poznyakoff
+
+ GNU cflow 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 3 of the License, or
+ (at your option) any later version.
+
+ GNU cflow 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 GNU cflow; if not, write to the Free Software
+ Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
+ MA 02110-1301 USA */
+
+#include <cflow.h>
+
+static struct linked_list *
+deref_linked_list (struct linked_list **plist)
+{
+ if (!*plist) {
+ struct linked_list *list = xmalloc(sizeof(*list));
+ list->free_data = NULL;
+ list->head = list->tail = NULL;
+ *plist = list;
+ }
+ return *plist;
+}
+
+
+struct linked_list *
+linked_list_create(linked_list_free_data_fp fun)
+{
+ struct linked_list *list = xmalloc(sizeof(*list));
+ list->free_data = fun;
+ list->head = list->tail = NULL;
+ return list;
+}
+
+void
+linked_list_append(struct linked_list **plist, void *data)
+{
+ struct linked_list *list = deref_linked_list (plist);
+ struct linked_list_entry *entry = xmalloc(sizeof(*entry));
+
+ entry->list = list;
+ entry->data = data;
+ entry->next = NULL;
+ entry->prev = list->tail;
+ if (list->tail)
+ list->tail->next = entry;
+ else
+ list->head = entry;
+ list->tail = entry;
+}
+
+#if 0
+void
+linked_list_prepend(struct linked_list **plist, void *data)
+{
+ struct linked_list *list = deref_linked_list (plist);
+ struct linked_list_entry *entry = xmalloc(sizeof(*entry));
+
+ entry->list = list;
+ entry->data = data;
+ if (list->head)
+ list->head->prev = entry;
+ entry->next = list->head;
+ entry->prev = NULL;
+ list->head = entry;
+ if (!list->tail)
+ list->tail = entry;
+}
+#endif
+
+void
+linked_list_destroy(struct linked_list **plist)
+{
+ if (plist && *plist) {
+ struct linked_list *list = *plist;
+ struct linked_list_entry *p;
+
+ for (p = list->head; p; ) {
+ struct linked_list_entry *next = p->next;
+ if (list->free_data)
+ list->free_data(p->data);
+ free(p);
+ p = next;
+ }
+ free(list);
+ *plist = NULL;
+ }
+}
+
+void
+linked_list_unlink(struct linked_list *list, struct linked_list_entry *ent)
+{
+ struct linked_list_entry *p;
+
+ if (p = ent->prev)
+ p->next = ent->next;
+ else
+ list->head = ent->next;
+
+ if (p = ent->next)
+ p->prev = ent->prev;
+ else
+ list->tail = ent->prev;
+ if (list->free_data)
+ list->free_data(ent->data);
+ free(ent);
+}
+
+void
+linked_list_iterate(struct linked_list **plist,
+ int (*itr) (void *, void *), void *data)
+{
+ struct linked_list *list;
+ struct linked_list_entry *p;
+
+ if (!*plist)
+ return;
+ list = *plist;
+ for (p = linked_list_head(list); p; ) {
+ struct linked_list_entry *next = p->next;
+
+ if (itr(p->data, data))
+ linked_list_unlink(list, p);
+ p = next;
+ }
+ if (!list->head)
+ linked_list_destroy(&list);
+ *plist = list;
+}
+
+int
+data_in_list(void *data, struct linked_list *list)
+{
+ struct linked_list_entry *p;
+
+ for (p = linked_list_head(list); p; p = p->next)
+ if (p->data == data)
+ return 1;
+ return 0;
+}
diff --git a/src/parser.c b/src/parser.c
index 26ac25d..c918b43 100644
--- a/src/parser.c
+++ b/src/parser.c
@@ -43,7 +43,6 @@ int parmdcl(Ident*);
int dirdcl(Ident*);
void skip_struct();
Symbol *get_symbol(char *name);
-Symbol *install_ident(char *name);
void maybe_parm_list(int *parm_cnt_return);
void call(char*, int);
@@ -956,9 +955,7 @@ declare(Ident *ident, int maybe_knr)
if (ident->storage == AutoStorage) {
undo_save_stack();
- sp = install(ident->name);
- sp->type = SymIdentifier;
- sp->storage = ident->storage;
+ sp = install_ident(ident->name, ident->storage);
if (parm_level) {
sp->level = parm_level;
sp->flag = symbol_parm;
@@ -981,7 +978,7 @@ declare(Ident *ident, int maybe_knr)
if (sp->source) {
if (ident->storage == StaticStorage
&& (sp->storage != StaticStorage || level > 0)) {
- sp = install_ident(ident->name);
+ sp = install_ident(ident->name, ident->storage);
} else {
error_at_line(0, 0, filename, ident->line,
_("%s/%d redefined"),
@@ -993,8 +990,9 @@ declare(Ident *ident, int maybe_knr)
sp->type = SymIdentifier;
sp->arity = ident->parmcnt;
- sp->storage = (ident->storage == ExplicitExternStorage) ?
- ExternStorage : ident->storage;
+ ident_change_storage(sp,
+ (ident->storage == ExplicitExternStorage) ?
+ ExternStorage : ident->storage);
sp->decl = finish_save_stack(ident->name);
sp->source = filename;
sp->def_line = ident->line;
@@ -1032,29 +1030,11 @@ declare_type(Ident *ident)
}
Symbol *
-install_ident(char *name)
-{
- Symbol *sp;
-
- sp = install(name);
- sp->type = SymIdentifier;
- sp->arity = -1;
- sp->storage = ExternStorage;
- sp->decl = NULL;
- sp->source = NULL;
- sp->def_line = -1;
- sp->ref_line = NULL;
- sp->caller = sp->callee = NULL;
- sp->level = -1;
- return sp;
-}
-
-Symbol *
get_symbol(char *name)
{
- Symbol *sp;
+ Symbol *sp = lookup(name) ;
- if (sp = lookup(name)) {
+ if (sp) {
for (; sp; sp = sp->next) {
if (sp->type == SymIdentifier && strcmp(sp->name, name) == 0)
break;
@@ -1062,7 +1042,7 @@ get_symbol(char *name)
if (sp)
return sp;
}
- return install_ident(name);
+ return install_ident(name, ExternStorage);
}
Symbol *
@@ -1095,9 +1075,9 @@ call(char *name, int line)
if (sp->arity < 0)
sp->arity = 0;
if (caller) {
- if (!symbol_in_list(caller, sp->caller))
+ if (!data_in_list(caller, sp->caller))
linked_list_append(&sp->caller, caller);
- if (!symbol_in_list(sp, caller->callee))
+ if (!data_in_list(sp, caller->callee))
linked_list_append(&caller->callee, sp);
}
}
@@ -1109,9 +1089,9 @@ reference(char *name, int line)
if (!sp)
return;
if (caller) {
- if (!symbol_in_list(caller, sp->caller))
+ if (!data_in_list(caller, sp->caller))
linked_list_append(&sp->caller, caller);
- if (!symbol_in_list(sp, caller->callee))
+ if (!data_in_list(sp, caller->callee))
linked_list_append(&caller->callee, sp);
}
}
diff --git a/src/symbol.c b/src/symbol.c
index e3ccd7c..80c01a3 100644
--- a/src/symbol.c
+++ b/src/symbol.c
@@ -22,6 +22,22 @@
static Hash_table *symbol_table;
+static struct linked_list *static_symbol_list;
+static struct linked_list *auto_symbol_list;
+
+static void
+append_symbol(struct linked_list **plist, Symbol *sp)
+{
+ if (sp->entry) {
+ linked_list_unlink(sp->entry->list, sp->entry);
+ sp->entry = NULL;
+ }
+ if (!data_in_list(sp, *plist)) {
+ linked_list_append(plist, sp);
+ sp->entry = (*plist)->tail;
+ }
+}
+
struct table_entry {
Symbol *sym;
};
@@ -89,32 +105,88 @@ install(char *name)
if (ret->sym->type != SymUndefined)
sym->next = ret->sym;
ret->sym = sym;
+ free(tp);
}
+ sym->owner = ret;
+ if (sym->flag == symbol_temp)
+ append_symbol(&static_symbol_list, sym);
return sym;
}
-/* Unlink the first symbol from the table entry */
-static Symbol *
-unlink_symbol(struct table_entry *tp)
+void
+ident_change_storage(Symbol *sp, enum storage storage)
+{
+ if (sp->storage == storage)
+ return;
+ if (sp->storage == StaticStorage)
+ /* FIXME */;
+
+ switch (storage) {
+ case StaticStorage:
+ append_symbol(&static_symbol_list, sp);
+ break;
+ case AutoStorage:
+ append_symbol(&auto_symbol_list, sp);
+ break;
+ default:
+ break;
+ }
+ sp->storage = storage;
+}
+
+Symbol *
+install_ident(char *name, enum storage storage)
{
- Symbol *s = tp->sym;
- if (s)
- tp->sym = s->next;
- return s;
+ Symbol *sp;
+
+ sp = install(name);
+ sp->type = SymIdentifier;
+ sp->arity = -1;
+ sp->storage = ExternStorage;
+ sp->decl = NULL;
+ sp->source = NULL;
+ sp->def_line = -1;
+ sp->ref_line = NULL;
+ sp->caller = sp->callee = NULL;
+ sp->level = -1;
+ ident_change_storage(sp, storage);
+ return sp;
+}
+
+/* Unlink the symbol from the table entry */
+static void
+unlink_symbol(Symbol *sym)
+{
+ Symbol *s, *prev = NULL;
+ struct table_entry *tp = sym->owner;
+ for (s = tp->sym; s; ) {
+ Symbol *next = s->next;
+ if (s == sym) {
+ if (prev)
+ prev->next = next;
+ else
+ tp->sym = next;
+ break;
+ } else
+ prev = s;
+ s = next;
+ }
+
+ sym->owner = NULL;
}
/* Unlink and free the first symbol from the table entry */
static void
-delete_symbol(struct table_entry *tp)
+delete_symbol(Symbol *sym)
{
- Symbol *s = unlink_symbol(tp);
+ unlink_symbol(sym);
/* The symbol could have been referenced even if it is static
in -i^s mode. See tests/static.at for details. */
- if (s->ref_line == NULL) {
- linked_list_destroy(&s->ref_line);
- linked_list_destroy(&s->caller);
- linked_list_destroy(&s->callee);
- free(s);
+ if (sym->ref_line == NULL) {
+ linked_list_destroy(&sym->ref_line);
+ linked_list_destroy(&sym->caller);
+ linked_list_destroy(&sym->callee);
+ free(sym);
}
}
@@ -127,71 +199,63 @@ delete_symbol(struct table_entry *tp)
so we don't have to check the name of the source where the symbol was
defined. */
-static bool
-static_processor(void *data, void *proc_data)
-{
- struct table_entry *t = data;
-
- if (t->sym
- && t->sym->type == SymIdentifier
- && t->sym->storage == StaticStorage) {
- if (globals_only())
- delete_symbol(t);
- else
- unlink_symbol(t);
- }
- return true;
-}
-
-static bool
-temp_processor(void *data, void *proc_data)
+static void
+static_free(void *data)
{
- struct table_entry *t = data;
-
- if (t->sym && t->sym->flag == symbol_temp)
- delete_symbol(t);
- return true;
+ Symbol *sym = data;
+ struct table_entry *t = sym->owner;
+
+ if (!t)
+ return;
+ if (sym->flag == symbol_temp
+ || globals_only())
+ delete_symbol(sym);
+ else
+ unlink_symbol(sym);
}
void
delete_statics()
{
- hash_do_for_each (symbol_table, static_processor, NULL);
- hash_do_for_each (symbol_table, temp_processor, NULL);
+ if (static_symbol_list) {
+ static_symbol_list->free_data = static_free;
+ linked_list_destroy(&static_symbol_list);
+ }
}
/* See NOTE above */
-bool
-auto_processor(void *data, void *proc_data)
+
+/* Delete from the symbol table all auto variables with given nesting
+ level. */
+int
+delete_level_autos(void *data, void *call_data)
{
- struct table_entry *t = data;
- Symbol *s = t->sym;
- if (s) {
- int *level = proc_data;
- if (s->type == SymIdentifier && s->level == *level) {
- switch (s->storage) {
- case AutoStorage:
- delete_symbol(t);
- break;
-
- case StaticStorage:
- unlink_symbol(t);
- break;
-
- default:
- break;
- }
- }
+ int level = *(int*)call_data;
+ Symbol *s = data;
+ if (s->level == level) {
+ delete_symbol(s);
+ return 1;
}
- return true;
+ return 0;
+}
+
+int
+delete_level_statics(void *data, void *call_data)
+{
+ int level = *(int*)call_data;
+ Symbol *s = data;
+ if (s->level == level) {
+ unlink_symbol(s);
+ return 1;
+ }
+ return 0;
}
-/* Delete from the symbol table all auto variables with given nesting
- level. */
void
delete_autos(int level)
{
- hash_do_for_each (symbol_table, auto_processor, &level);
+ linked_list_iterate(&auto_symbol_list, delete_level_autos, &level);
+ linked_list_iterate(&static_symbol_list, delete_level_statics, &level);
}
struct collect_data {
@@ -237,41 +301,28 @@ collect_symbols(Symbol ***return_sym, int (*sel)(Symbol *p))
/* Special handling for function parameters */
-static bool
-delete_parm_processor(void *data, void *proc_data)
+int
+delete_parms_itr(void *data, void *call_data)
{
- struct table_entry *t = data;
- Symbol *s = t->sym;
- if (s) {
- int *level = proc_data;
- if (s->type == SymIdentifier && s->storage == AutoStorage
- && s->flag == symbol_parm && s->level > *level)
- delete_symbol(t);
+ int level = *(int*)call_data;
+ Symbol *s = data;
+ struct table_entry *t = s->owner;
+
+ if (!t)
+ return 1;
+ if (s->type == SymIdentifier && s->storage == AutoStorage
+ && s->flag == symbol_parm && s->level > level) {
+ delete_symbol(s);
+ return 1;
}
- return true;
+ return 0;
}
/* Delete all parameters with parameter nesting level greater than LEVEL */
void
delete_parms(int level)
{
- hash_do_for_each (symbol_table, delete_parm_processor, &level);
-}
-
-static bool
-move_parm_processor(void *data, void *proc_data)
-{
- struct table_entry *t = data;
- Symbol *s = t->sym;
- if (s) {
- int level = *(int*)proc_data;
- if (s->type == SymIdentifier && s->storage == AutoStorage
- && s->flag == symbol_parm) {
- s->level = level;
- s->flag = symbol_none;
- }
- }
- return true;
+ linked_list_iterate(&auto_symbol_list, delete_parms_itr, &level);
}
/* Redeclare all saved parameters as automatic variables with the
@@ -279,83 +330,16 @@ move_parm_processor(void *data, void *proc_data)
void
move_parms(int level)
{
- hash_do_for_each (symbol_table, move_parm_processor, &level);
-}
-
-
-
-static struct linked_list *
-deref_linked_list (struct linked_list **plist)
-{
- if (!*plist) {
- struct linked_list *list = xmalloc(sizeof(*list));
- list->free_data = NULL;
- list->head = list->tail = NULL;
- *plist = list;
- }
- return *plist;
-}
-
-
-struct linked_list *
-linked_list_create(linked_list_free_data_fp fun)
-{
- struct linked_list *list = xmalloc(sizeof(*list));
- list->free_data = fun;
- list->head = list->tail = NULL;
- return list;
-}
-
-void
-linked_list_append(struct linked_list **plist, void *data)
-{
- struct linked_list *list = deref_linked_list (plist);
- struct linked_list_entry *entry = xmalloc(sizeof(*entry));
- entry->next = NULL;
- entry->data = data;
- if (list->tail)
- list->tail->next = entry;
- else
- list->head = entry;
- list->tail = entry;
-}
+ struct linked_list_entry *p;
-void
-linked_list_prepend(struct linked_list **plist, void *data)
-{
- struct linked_list *list = deref_linked_list (plist);
- struct linked_list_entry *entry = xmalloc(sizeof(*entry));
- entry->next = list->head;
- entry->data = data;
- list->head = entry;
- if (!list->tail)
- list->tail = entry;
-}
+ for (p = linked_list_head(auto_symbol_list); p; p = p->next) {
+ Symbol *s = p->data;
-void
-linked_list_destroy(struct linked_list **plist)
-{
- if (plist && *plist) {
- struct linked_list *list = *plist;
- struct linked_list_entry *p;
-
- for (p = list->head; p; p = p->next) {
- if (list->free_data)
- list->free_data(p->data);
- free(p);
+ if (s->type == SymIdentifier && s->storage == AutoStorage
+ && s->flag == symbol_parm) {
+ s->level = level;
+ s->flag = symbol_none;
}
- free(list);
- *plist = NULL;
}
}
-int
-symbol_in_list(Symbol *sym, struct linked_list *list)
-{
- struct linked_list_entry *p;
-
- for (p = linked_list_head(list); p; p = p->next)
- if ((Symbol*)p->data == sym)
- return 1;
- return 0;
-}

Return to:

Send suggestions and report system problems to the System administrator.