* Calculate the sub-set of vertices v from the affected region [y..x] * where v reaches x. Return the number of vertices in this subset. */
| 2154 | * where v reaches x. Return the number of vertices in this subset. |
| 2155 | */ |
| 2156 | static int |
| 2157 | graph_delta_backward(struct owner_graph *g, struct owner_vertex *x, |
| 2158 | struct owner_vertex *y, struct owner_vertex_list *delta) |
| 2159 | { |
| 2160 | uint32_t gen; |
| 2161 | struct owner_vertex *v; |
| 2162 | struct owner_edge *e; |
| 2163 | int n; |
| 2164 | |
| 2165 | /* |
| 2166 | * We start with a set containing just x. Then for each vertex |
| 2167 | * v in the set so far unprocessed, we add each vertex that v |
| 2168 | * has an in-edge from and that is within the affected region |
| 2169 | * [y..x]. |
| 2170 | */ |
| 2171 | TAILQ_INIT(delta); |
| 2172 | TAILQ_INSERT_TAIL(delta, x, v_link); |
| 2173 | v = x; |
| 2174 | n = 1; |
| 2175 | gen = g->g_gen; |
| 2176 | while (v) { |
| 2177 | LIST_FOREACH(e, &v->v_inedges, e_inlink) { |
| 2178 | if (e->e_from->v_order > y->v_order |
| 2179 | && e->e_from->v_gen != gen) { |
| 2180 | e->e_from->v_gen = gen; |
| 2181 | TAILQ_INSERT_HEAD(delta, e->e_from, v_link); |
| 2182 | n++; |
| 2183 | } |
| 2184 | } |
| 2185 | v = TAILQ_PREV(v, owner_vertex_list, v_link); |
| 2186 | } |
| 2187 | |
| 2188 | return (n); |
| 2189 | } |
| 2190 | |
| 2191 | static int |
| 2192 | graph_add_indices(int *indices, int n, struct owner_vertex_list *set) |