From 23abfa7a31bf5dedd09cd0963da7dc4a291631eb Mon Sep 17 00:00:00 2001 From: Sergey Poznyakoff Date: Mon, 29 Jun 2009 02:15:52 +0300 Subject: 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. --- src/Makefile.am | 15 +-- src/cflow.h | 15 ++- src/linked-list.c | 148 ++++++++++++++++++++++++++ src/parser.c | 44 +++----- src/symbol.c | 312 ++++++++++++++++++++++++++---------------------------- 5 files changed, 329 insertions(+), 205 deletions(-) create mode 100644 src/linked-list.c 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 --- /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 + +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; @@ -1031,30 +1029,12 @@ declare_type(Ident *ident) ident->name); } -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; -} -- cgit v1.2.1