Speed-up recursive call detection.

* src/depmap.c: New file.
* src/Makefile.am: Add depmap.c.
* src/cflow.h (struct symbol.ord): New member.
(collect_symbols): Change signature. All callers
updated.
(collect_functions): New proto.
(symbol_is_function): New proto.
(cflow_depmap_t): New data type.
(depmap_alloc, depmap_set)
(depmap_isset, depmap_tc): New prototypes.
* src/output.c (symbol_is_function): New function.
(scan_tree): Remove.
(tree_output): Use depmap to find out recursive calls.
* src/symbol.c (static_func_list): New list.
(static_free): Add static functions to static_func_list.
(collect_symbols): Return size_t. Take additional number
of slots in the 3rd argument.
(collect_functions): New function.

5 files changed, 228 insertions, 60 deletions

diff --git a/src/Makefile.am b/src/Makefile.am
index 7252ff8..ce4663d 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -26,2 +26,3 @@ cflow_SOURCES = \
  cflow.h\
+ depmap.c\
  gnu.c\
diff --git a/src/cflow.h b/src/cflow.h
index d933750..2593398 100644
--- a/src/cflow.h
+++ b/src/cflow.h
@@ -119,2 +119,3 @@ struct symbol {
      int recursive;                /* Is the function recursive */
+     size_t ord;                   /* ordinal number */
      struct linked_list *caller;   /* List of callers */
@@ -174,3 +175,4 @@ void delete_parms(int level);
 void move_parms(int level);
-int collect_symbols(Symbol ***, int (*sel)());
+size_t collect_symbols(Symbol ***, int (*sel)(), size_t rescnt);
+size_t collect_functions(Symbol ***return_sym);
 struct linked_list *linked_list_create(linked_list_free_data_fp fun);
@@ -200,2 +202,3 @@ int globals_only(void);
 int include_symbol(Symbol *sym);
+int symbol_is_function(Symbol *sym);
 
@@ -235 +238,7 @@ int posix_output_handler(cflow_output_command cmd,
 
+
+typedef struct cflow_depmap *cflow_depmap_t;
+cflow_depmap_t depmap_alloc(size_t count);
+void depmap_set(cflow_depmap_t dmap, size_t row, size_t col);
+int depmap_isset(cflow_depmap_t dmap, size_t row, size_t col);
+void depmap_tc(cflow_depmap_t dmap);
diff --git a/src/depmap.c b/src/depmap.c
new file mode 100644
index 0000000..340d41f
--- /dev/null
+++ b/src/depmap.c
@@ -0,0 +1,118 @@
+/* This file is part of GNU cflow.
+   Copyright (C) 2008, 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, 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, see <http://www.gnu.org/licenses/>. */
+
+#include <cflow.h>
+
+#ifndef CHAR_BIT
+# define CHAR_BIT 8
+#endif
+#define BITS_PER_WORD   (sizeof(unsigned)*CHAR_BIT)
+
+#define WORDSIZE(n)     (((n) + BITS_PER_WORD - 1) / BITS_PER_WORD)
+#define SETBIT(x, i)    ((x)[(i)/BITS_PER_WORD] |= (1<<((i) % BITS_PER_WORD)))
+#define RESETBIT(x, i)  ((x)[(i)/BITS_PER_WORD] &= ~(1<<((i) % BITS_PER_WORD)))
+#define BITISSET(x, i)  (((x)[(i)/BITS_PER_WORD] & (1<<((i) % BITS_PER_WORD))) != 0)
+
+static void
+transitive_closure(unsigned *R, int n)
+{
+     register size_t rowsize;
+     register unsigned mask;
+     register unsigned *rowj;
+     register unsigned *rp;
+     register unsigned *rend;
+     register unsigned *ccol;
+     
+     unsigned *relend;
+     unsigned *cword;
+     unsigned *rowi;
+     
+     rowsize = WORDSIZE (n) * sizeof (unsigned);
+     relend = (unsigned *) ((char *) R + (n * rowsize));
+     
+     cword = R;
+     mask = 1;
+     rowi = R;
+     while (rowi < relend) {
+	  ccol = cword;
+	  rowj = R;
+                
+	  while (rowj < relend) {
+	       if (*ccol & mask) {
+		    rp = rowi;
+		    rend = (unsigned *) ((char *) rowj + rowsize);
+                                
+		    while (rowj < rend)
+			 *rowj++ |= *rp++;
+	       } else {
+		    rowj = (unsigned *) ((char *) rowj + rowsize);
+	       }
+	  
+	       ccol = (unsigned *) ((char *) ccol + rowsize);
+	  }
+                
+	  mask <<= 1;
+	  if (mask == 0) {
+	       mask = 1;
+	       cword++;
+	  }
+	  rowi = (unsigned *) ((char *) rowi + rowsize);
+     }
+}
+
+struct cflow_depmap {
+     size_t nrows;
+     size_t rowlen;
+     unsigned r[1];
+};
+  
+cflow_depmap_t
+depmap_alloc(size_t count)
+{
+     size_t size = (count + BITS_PER_WORD - 1) / BITS_PER_WORD;
+     cflow_depmap_t dmap = xzalloc(sizeof(*dmap) - 1 
+				   + count * size * sizeof(unsigned));
+     dmap->nrows  = count;
+     dmap->rowlen = size;
+     return dmap;
+}
+
+static unsigned *
+depmap_rowptr(cflow_depmap_t dmap, size_t row)
+{
+     return dmap->r + dmap->rowlen * row;
+}
+
+void
+depmap_set(cflow_depmap_t dmap, size_t row, size_t col)
+{
+     unsigned *rptr = depmap_rowptr(dmap, row);
+     SETBIT(rptr, col);
+}
+
+int
+depmap_isset(cflow_depmap_t dmap, size_t row, size_t col)
+{
+     unsigned *rptr = depmap_rowptr(dmap, row);
+     return BITISSET(rptr, col);
+}
+
+void
+depmap_tc(cflow_depmap_t dmap)
+{
+     transitive_closure(dmap->r, dmap->nrows);
+}
+
diff --git a/src/output.c b/src/output.c
index f33d0ae..a617816 100644
--- a/src/output.c
+++ b/src/output.c
@@ -193,2 +193,8 @@ is_var(Symbol *symp)
 
+int
+symbol_is_function(Symbol *symp)
+{
+     return symp->type == SymIdentifier && symp->arity >= 0;
+}
+
 static void
@@ -243,5 +249,5 @@ xref_output()
      Symbol **symbols, *symp;
-     int i, num;
+     size_t i, num;
      
-     num = collect_symbols(&symbols, is_var);
+     num = collect_symbols(&symbols, is_var, 0);
      qsort(symbols, num, sizeof(*symbols), compare);
@@ -269,22 +275,2 @@ xref_output()
 
-/* Scan call tree. Mark the recursive calls
- */
-static void
-scan_tree(int lev, Symbol *sym)
-{
-     struct linked_list_entry *p;
-
-     if (sym->type == SymUndefined)
-	  return;
-     if (sym->active) {
-	  sym->recursive = 1;
-	  return;
-     }
-     sym->active = 1;
-     for (p = linked_list_head(sym->callee); p; p = p->next) {
-	  scan_tree(lev+1, (Symbol*)p->data);
-     }
-     sym->active = 0;
-}
-
 static void
@@ -363,39 +349,64 @@ tree_output()
      Symbol **symbols, *main_sym;
-     int i, num;
+     size_t i, num;
+     cflow_depmap_t depmap;
      
-     /* Collect and sort symbols */
-     num = collect_symbols(&symbols, is_var);
-     qsort(symbols, num, sizeof(*symbols), compare);
-     /* Scan and mark the recursive ones */
+     /* Collect functions and assign them ordinal numbers */
+     num = collect_functions(&symbols);
+     for (i = 0; i < num; i++)
+	  symbols[i]->ord = i;
+     
+     /* Create a dependency matrix */
+     depmap = depmap_alloc(num);
      for (i = 0; i < num; i++) {
-	  if (symbols[i]->callee)
-	       scan_tree(0, symbols[i]);
+	  if (symbols[i]->callee) {
+	       struct linked_list_entry *p;
+	       
+	       for (p = linked_list_head(symbols[i]->callee); p;
+		    p = p->next) {
+		    Symbol *s = (Symbol*) p->data;
+		    if (symbol_is_function(s))
+			 depmap_set(depmap, i, ((Symbol*)p->data)->ord);
+	       }		    
+	  }
      }
      
+     depmap_tc(depmap);
+
+     /* Mark recursive calls */
+     for (i = 0; i < num; i++)
+	  if (depmap_isset(depmap, i, i))
+	       symbols[i]->recursive = 1;
+     free(depmap);
+     free(symbols);
+     
+     /* Collect and sort all symbols */
+     num = collect_symbols(&symbols, is_var, 0);
+     qsort(symbols, num, sizeof(*symbols), compare);
+	       
      /* Produce output */
-    begin();
-    
-    if (reverse_tree) {
-	 for (i = 0; i < num; i++) {
-	      inverted_tree(0, 0, symbols[i]);
-	      separator();
-	 }
-    } else {
-	 main_sym = lookup(start_name);
-	 if (main_sym) {
-	      direct_tree(0, 0, main_sym);
-	      separator();
-	 } else {
-	      for (i = 0; i < num; i++) {
-		   if (symbols[i]->callee == NULL)
-			continue;
-		   direct_tree(0, 0, symbols[i]);
-		   separator();
-	      }
-	 }
-    }
+     begin();
     
-    end();
-    
-    free(symbols);
+     if (reverse_tree) {
+	  for (i = 0; i < num; i++) {
+	       inverted_tree(0, 0, symbols[i]);
+	       separator();
+	  }
+     } else {
+	  main_sym = lookup(start_name);
+	  if (main_sym) {
+	       direct_tree(0, 0, main_sym);
+	       separator();
+	  } else {
+	       for (i = 0; i < num; i++) {
+		    if (symbols[i]->callee == NULL)
+			 continue;
+		    direct_tree(0, 0, symbols[i]);
+		    separator();
+	       }
+	  }
+     }
+     
+     end();
+     
+     free(symbols);
 }
diff --git a/src/symbol.c b/src/symbol.c
index 80c01a3..677f510 100644
--- a/src/symbol.c
+++ b/src/symbol.c
@@ -26,2 +26,3 @@ static struct linked_list *static_symbol_list;
 static struct linked_list *auto_symbol_list;
+static struct linked_list *static_func_list;
 
@@ -209,7 +210,9 @@ static_free(void *data)
 	  return;
-     if (sym->flag == symbol_temp
-	 || globals_only()) 
+     if (sym->flag == symbol_temp) 
 	  delete_symbol(sym);
-     else
+     else {
 	  unlink_symbol(sym);
+	  if (symbol_is_function(sym))
+	       linked_list_append(&static_func_list, sym);
+     }
 }
@@ -282,4 +285,5 @@ collect_processor(void *data, void *proc_data)
 
-int
-collect_symbols(Symbol ***return_sym, int (*sel)(Symbol *p))
+size_t
+collect_symbols(Symbol ***return_sym, int (*sel)(Symbol *p),
+		size_t reserved_slots)
 {
@@ -291,3 +295,3 @@ collect_symbols(Symbol ***return_sym, int (*sel)(Symbol *p))
      hash_do_for_each (symbol_table, collect_processor, &cdata);
-     cdata.sym = calloc(cdata.index, sizeof(*cdata.sym));
+     cdata.sym = calloc(cdata.index + reserved_slots, sizeof(*cdata.sym));
      if (!cdata.sym)
@@ -300,2 +304,27 @@ collect_symbols(Symbol ***return_sym, int (*sel)(Symbol *p))
 
+size_t
+collect_functions(Symbol ***return_sym)
+{
+     Symbol **symbols;
+     size_t num, snum;
+     struct linked_list_entry *p;
+
+     /* Count static functions */
+     snum = 0;
+     if (static_func_list)
+	  for (p = linked_list_head(static_func_list); p; p = p->next)
+	       snum++;
+     
+     /* Collect global functions */
+     num = collect_symbols(&symbols, symbol_is_function, snum);
+
+     /* Collect static functions */
+     if (snum) 
+	  for (p = linked_list_head(static_func_list); p; p = p->next)
+	       symbols[num++] = p->data;
+     *return_sym = symbols;
+     return num;
+}
+
+