Dear all,
attached is an updated version of Patch 2. The change is that I removed
the global variable for fill_st_vector and updated the comment for
do_traverse_symtree to make assumptions clearer.
This version of the patch was build and regtested (gfortran + libgomp).
OK?
Dear Tobias S.,
Tobias Schlüter wrote:
I don't remember all this very clearly, but I think that the
gfc_symbol::tlink field is intended for something like this
I think that's a rather different issue: It relates to undoing a symbol,
which I do not want to do. Additionally, a tlink symbol is already added
to a symtree (which is hence rebalanced). One possibility is to delay
the inclusion of symbols into the symtree - and do only so after the
traversal - but that might cause issues if one later searches in called
function for that symtree. Thus, I think my current patch should be
sufficiently simple, fast and solid.
Tobias
2011-11-02 Tobias Burnus <bur...@net-b.de>
* symbol.c (clear_sym_mark, traverse_ns): Remove functions.
(count_st_nodes, do_traverse_symtree, fill_st_vector): New functions.
(gfc_traverse_symtree, gfc_traverse_ns): Call do_traverse_symtree.
diff --git a/gcc/fortran/symbol.c b/gcc/fortran/symbol.c
index 67d65cb..c3a0867 100644
--- a/gcc/fortran/symbol.c
+++ b/gcc/fortran/symbol.c
@@ -3310,46 +3310,81 @@ gfc_symbol_done_2 (void)
}
-/* Clear mark bits from symbol nodes associated with a symtree node. */
+/* Count how many nodes a symtree has. */
-static void
-clear_sym_mark (gfc_symtree *st)
+static unsigned
+count_st_nodes (const gfc_symtree *st)
{
+ unsigned nodes;
+ if (!st)
+ return 0;
- st->n.sym->mark = 0;
+ nodes = count_st_nodes (st->left);
+ nodes++;
+ nodes += count_st_nodes (st->right);
+
+ return nodes;
}
-/* Recursively traverse the symtree nodes. */
+/* Convert symtree tree into symtree vector. */
-void
-gfc_traverse_symtree (gfc_symtree *st, void (*func) (gfc_symtree *))
+static unsigned
+fill_st_vector (gfc_symtree *st, gfc_symtree **st_vec, unsigned node_cntr)
{
if (!st)
- return;
+ return node_cntr;
+
+ node_cntr = fill_st_vector (st->left, st_vec, node_cntr);
+ st_vec[node_cntr++] = st;
+ node_cntr = fill_st_vector (st->right, st_vec, node_cntr);
- gfc_traverse_symtree (st->left, func);
- (*func) (st);
- gfc_traverse_symtree (st->right, func);
+ return node_cntr;
}
-/* Recursive namespace traversal function. */
+/* Traverse namespace. As the functions might modify the symtree, we store the
+ symtree as a vector and operate on this vector. Note: We assume that
+ sym_func or st_func never deletes nodes from the symtree - only adding is
+ allowed. */
static void
-traverse_ns (gfc_symtree *st, void (*func) (gfc_symbol *))
+do_traverse_symtree (gfc_symtree *st, void (*st_func) (gfc_symtree *),
+ void (*sym_func) (gfc_symbol *))
{
+ gfc_symtree **st_vec;
+ unsigned nodes, i, node_cntr;
- if (st == NULL)
- return;
+ gcc_assert ((st_func && !sym_func) || (!st_func && sym_func));
+ nodes = count_st_nodes (st);
+ st_vec = XALLOCAVEC (gfc_symtree *, nodes);
+ node_cntr = 0;
+ fill_st_vector (st, st_vec, node_cntr);
+
+ if (sym_func)
+ {
+ /* Clear marks. */
+ for (i = 0; i < nodes; i++)
+ st_vec[i]->n.sym->mark = 0;
+ for (i = 0; i < nodes; i++)
+ if (!st_vec[i]->n.sym->mark)
+ {
+ (*sym_func) (st_vec[i]->n.sym);
+ st_vec[i]->n.sym->mark = 1;
+ }
+ }
+ else
+ for (i = 0; i < nodes; i++)
+ (*st_func) (st_vec[i]);
+}
- traverse_ns (st->left, func);
- if (st->n.sym->mark == 0)
- (*func) (st->n.sym);
- st->n.sym->mark = 1;
+/* Recursively traverse the symtree nodes. */
- traverse_ns (st->right, func);
+void
+gfc_traverse_symtree (gfc_symtree *st, void (*st_func) (gfc_symtree *))
+{
+ do_traverse_symtree (st, st_func, NULL);
}
@@ -3357,12 +3392,9 @@ traverse_ns (gfc_symtree *st, void (*func) (gfc_symbol *))
care that each gfc_symbol node is called exactly once. */
void
-gfc_traverse_ns (gfc_namespace *ns, void (*func) (gfc_symbol *))
+gfc_traverse_ns (gfc_namespace *ns, void (*sym_func) (gfc_symbol *))
{
-
- gfc_traverse_symtree (ns->sym_root, clear_sym_mark);
-
- traverse_ns (ns->sym_root, func);
+ do_traverse_symtree (ns->sym_root, NULL, sym_func);
}
