| 149 | } |
| 150 | |
| 151 | forceinline bool |
| 152 | Graph::mark(void) { |
| 153 | using namespace ViewValGraph; |
| 154 | Region r; |
| 155 | |
| 156 | int n_view_visited = 0; |
| 157 | { |
| 158 | // Marks all edges as used that are on simple paths in the graph |
| 159 | // that start from a free value node by depth-first-search |
| 160 | Support::StaticStack<ValNode<IntView>*,Region> visit(r,n_val); |
| 161 | |
| 162 | // Insert all free value nodes |
| 163 | count++; |
| 164 | { |
| 165 | ValNode<IntView>** v = &val; |
| 166 | while (*v != nullptr) |
| 167 | // Is the node free? |
| 168 | if (!(*v)->matching()) { |
| 169 | // Eliminate empty value nodes |
| 170 | if ((*v)->empty()) { |
| 171 | *v = (*v)->next_val(); |
| 172 | n_val--; |
| 173 | } else { |
| 174 | (*v)->min = count; |
| 175 | visit.push(*v); |
| 176 | v = (*v)->next_val_ref(); |
| 177 | } |
| 178 | } else { |
| 179 | v = (*v)->next_val_ref(); |
| 180 | } |
| 181 | } |
| 182 | |
| 183 | // Invariant: only value nodes are on the stack! |
| 184 | while (!visit.empty()) { |
| 185 | ValNode<IntView>* n = visit.pop(); |
| 186 | for (Edge<IntView>* e = n->edge_fst(); e != n->edge_lst(); |
| 187 | e = e->next()) { |
| 188 | // Is the view node is matched: the path must be alternating! |
| 189 | ViewNode<IntView>* x = e->view(n); |
| 190 | if (x->matched()) { |
| 191 | // Mark the edge as used |
| 192 | e->use(); |
| 193 | if (x->min < count) { |
| 194 | n_view_visited++; |
| 195 | x->min = count; |
| 196 | assert(x->edge_fst()->next() == x->edge_lst()); |
| 197 | ValNode<IntView>* m = x->edge_fst()->val(x); |
| 198 | x->edge_fst()->use(); |
| 199 | if (m->min < count) { |
| 200 | m->min = count; |
| 201 | visit.push(m); |
| 202 | } |
| 203 | } |
| 204 | } |
| 205 | } |
| 206 | } |
| 207 | |
| 208 | } |