diff options
author | Sergey Poznyakoff <gray@gnu.org.ua> | 2009-11-09 01:50:43 +0200 |
---|---|---|
committer | Sergey Poznyakoff <gray@gnu.org.ua> | 2009-11-09 01:50:43 +0200 |
commit | dc1a81526099095b12ef6edb655cf1a773dfa983 (patch) | |
tree | 17defadb706683a3a59ee41428200ee66d91d34b /src/depmap.c | |
parent | 4d75955e833201c4f1d0219d48676521aeee1afa (diff) | |
download | cflow-dc1a81526099095b12ef6edb655cf1a773dfa983.tar.gz cflow-dc1a81526099095b12ef6edb655cf1a773dfa983.tar.bz2 |
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.
Diffstat (limited to 'src/depmap.c')
-rw-r--r-- | src/depmap.c | 118 |
1 files changed, 118 insertions, 0 deletions
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); +} + |