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.

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
@@ -19,22 +19,23 @@
 # 02110-1301 USA.
 
 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
 
 cflow_LDADD=../lib/libcflow.a @LIBINTL@
 AM_CPPFLAGS=-DLOCALEDIR=\"$(localedir)\"
 AM_LFLAGS=-dvp
diff --git a/src/cflow.h b/src/cflow.h
index c6712c9..d933750 100644
--- a/src/cflow.h
+++ b/src/cflow.h
@@ -43,13 +43,14 @@
 # define setlocale(category, locale) /* empty */
 #endif
 
 #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;
 };
 
 typedef void (*linked_list_free_data_fp) (void*);
 
 struct linked_list {
@@ -85,13 +86,16 @@ enum symbol_flag {
      symbol_parm                   /* Parameter */
 };
 
 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 */
      
      int active;                   /* Set to 1 when the symbol's subtree is
 				      being processed, prevent recursion */
@@ -159,22 +163,29 @@ extern int token_stack_increase;
 
 extern int symbol_count;
 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);
 void move_parms(int level);
 int collect_symbols(Symbol ***, int (*sel)());
 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);
 void init_lex(int debug_level);
 void set_preprocessor(const char *arg);
 void pp_option(const char *arg); 
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 <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
@@ -40,13 +40,12 @@ void declare(Ident*, int maybe_knr);
 void declare_type(Ident*);
 int dcl(Ident*);
 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);
 void reference(char*, int);
 
 int level;                  /* Current nesting level */
@@ -953,15 +952,13 @@ void
 declare(Ident *ident, int maybe_knr)
 {
      Symbol *sp;
      
      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;
 	  } else
 	       sp->level = level;
 	  sp->arity = -1;
@@ -978,26 +975,27 @@ declare(Ident *ident, int maybe_knr)
      }
      
      sp = get_symbol(ident->name);
      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"),
 			     ident->name, sp->arity);
 	       error_at_line(0, 0, sp->source, sp->def_line,
 			     _("this is the place of previous definition"));
 	  }
      }
 
      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;
      sp->level = level;
      if (debug)
 	  printf(_("%s:%d: %s/%d defined to %s\n"),
@@ -1029,43 +1027,25 @@ declare_type(Ident *ident)
 		 filename,
 		 line_num,
 		 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;
 	  }
 	  if (sp)
 	       return sp;
      }
-     return install_ident(name);
+     return install_ident(name, ExternStorage);
 }
 
 Symbol *
 add_reference(char *name, int line)
 {
      Symbol *sp = get_symbol(name);
@@ -1092,27 +1072,27 @@ call(char *name, int line)
      sp = add_reference(name, line);
      if (!sp)
 	  return;
      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);
      }
 }
 
 void
 reference(char *name, int line)
 {
      Symbol *sp = add_reference(name, 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
@@ -19,12 +19,28 @@
 #include <cflow.h>
 #include <parser.h>
 #include <hash.h>
 
 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;
 };
 
 /* Calculate the hash of a string.  */
 static size_t
@@ -86,115 +102,163 @@ install(char *name)
 	  xalloc_die ();
 
      if (ret != tp) {
 	  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);
      }
 }     
 
 /* Delete from the symbol table all static symbols defined in the current
    source.
    If the user requested static symbols in the listing, the symbol is
    not deleted, as it may have been referenced by other symbols. Instead,
    it is unlinked from its table entry.
    NOTE: This takes advantage of the fact that install() uses LIFO strategy,
    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 {
      Symbol **sym;
      int (*sel)(Symbol *p);
      size_t index;
@@ -234,128 +298,48 @@ collect_symbols(Symbol ***return_sym, int (*sel)(Symbol *p))
      return cdata.index;
 }
 
 
 /* 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
    given nesting level */
 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;
-}