* Calculate the sub-set of vertices v from the affected region [y..x] * where v is reachable from y. Return -1 if a loop was detected * (i.e. x is reachable from y, otherwise the number of vertices in * this subset. */
| 2112 | * this subset. |
| 2113 | */ |
| 2114 | static int |
| 2115 | graph_delta_forward(struct owner_graph *g, struct owner_vertex *x, |
| 2116 | struct owner_vertex *y, struct owner_vertex_list *delta) |
| 2117 | { |
| 2118 | uint32_t gen; |
| 2119 | struct owner_vertex *v; |
| 2120 | struct owner_edge *e; |
| 2121 | int n; |
| 2122 | |
| 2123 | /* |
| 2124 | * We start with a set containing just y. Then for each vertex |
| 2125 | * v in the set so far unprocessed, we add each vertex that v |
| 2126 | * has an out-edge to and that is within the affected region |
| 2127 | * [y..x]. If we see the vertex x on our travels, stop |
| 2128 | * immediately. |
| 2129 | */ |
| 2130 | TAILQ_INIT(delta); |
| 2131 | TAILQ_INSERT_TAIL(delta, y, v_link); |
| 2132 | v = y; |
| 2133 | n = 1; |
| 2134 | gen = g->g_gen; |
| 2135 | while (v) { |
| 2136 | LIST_FOREACH(e, &v->v_outedges, e_outlink) { |
| 2137 | if (e->e_to == x) |
| 2138 | return -1; |
| 2139 | if (e->e_to->v_order < x->v_order |
| 2140 | && e->e_to->v_gen != gen) { |
| 2141 | e->e_to->v_gen = gen; |
| 2142 | TAILQ_INSERT_TAIL(delta, e->e_to, v_link); |
| 2143 | n++; |
| 2144 | } |
| 2145 | } |
| 2146 | v = TAILQ_NEXT(v, v_link); |
| 2147 | } |
| 2148 | |
| 2149 | return (n); |
| 2150 | } |
| 2151 | |
| 2152 | /* |
| 2153 | * Calculate the sub-set of vertices v from the affected region [y..x] |