Lines Matching refs:vertex
119 return unix_sk(edge->successor->listener)->vertex; in unix_edge_successor()
121 return edge->successor->vertex; in unix_edge_successor()
127 static void unix_update_graph(struct unix_vertex *vertex) in unix_update_graph() argument
132 if (!vertex) in unix_update_graph()
151 struct unix_vertex *vertex = edge->predecessor->vertex; in unix_add_edge() local
153 if (!vertex) { in unix_add_edge()
154 vertex = list_first_entry(&fpl->vertices, typeof(*vertex), entry); in unix_add_edge()
155 vertex->index = unix_vertex_unvisited_index; in unix_add_edge()
156 vertex->out_degree = 0; in unix_add_edge()
157 INIT_LIST_HEAD(&vertex->edges); in unix_add_edge()
158 INIT_LIST_HEAD(&vertex->scc_entry); in unix_add_edge()
160 list_move_tail(&vertex->entry, &unix_unvisited_vertices); in unix_add_edge()
161 edge->predecessor->vertex = vertex; in unix_add_edge()
164 vertex->out_degree++; in unix_add_edge()
165 list_add_tail(&edge->vertex_entry, &vertex->edges); in unix_add_edge()
172 struct unix_vertex *vertex = edge->predecessor->vertex; in unix_del_edge() local
178 vertex->out_degree--; in unix_del_edge()
180 if (!vertex->out_degree) { in unix_del_edge()
181 edge->predecessor->vertex = NULL; in unix_del_edge()
182 list_move_tail(&vertex->entry, &fpl->vertices); in unix_del_edge()
188 struct unix_vertex *vertex, *next_vertex; in unix_free_vertices() local
190 list_for_each_entry_safe(vertex, next_vertex, &fpl->vertices, entry) { in unix_free_vertices()
191 list_del(&vertex->entry); in unix_free_vertices()
192 kfree(vertex); in unix_free_vertices()
273 unix_update_graph(unix_sk(receiver->listener)->vertex); in unix_update_edges()
281 struct unix_vertex *vertex; in unix_prepare_fpl() local
288 vertex = kmalloc(sizeof(*vertex), GFP_KERNEL); in unix_prepare_fpl()
289 if (!vertex) in unix_prepare_fpl()
292 list_add(&vertex->entry, &fpl->vertices); in unix_prepare_fpl()
316 static bool unix_vertex_dead(struct unix_vertex *vertex) in unix_vertex_dead() argument
322 list_for_each_entry(edge, &vertex->edges, vertex_entry) { in unix_vertex_dead()
332 if (next_vertex->scc_index != vertex->scc_index) in unix_vertex_dead()
338 edge = list_first_entry(&vertex->edges, typeof(*edge), vertex_entry); in unix_vertex_dead()
343 if (total_ref != vertex->out_degree) in unix_vertex_dead()
351 struct unix_vertex *vertex; in unix_collect_skb() local
353 list_for_each_entry_reverse(vertex, scc, scc_entry) { in unix_collect_skb()
358 edge = list_first_entry(&vertex->edges, typeof(*edge), vertex_entry); in unix_collect_skb()
384 struct unix_vertex *vertex; in unix_scc_cyclic() local
391 vertex = list_first_entry(scc, typeof(*vertex), scc_entry); in unix_scc_cyclic()
394 list_for_each_entry(edge, &vertex->edges, vertex_entry) { in unix_scc_cyclic()
395 if (unix_edge_successor(edge) == vertex) in unix_scc_cyclic()
405 static void __unix_walk_scc(struct unix_vertex *vertex, unsigned long *last_index, in __unix_walk_scc() argument
417 list_add(&vertex->scc_entry, &vertex_stack); in __unix_walk_scc()
419 vertex->index = *last_index; in __unix_walk_scc()
420 vertex->scc_index = *last_index; in __unix_walk_scc()
424 list_for_each_entry(edge, &vertex->edges, vertex_entry) { in __unix_walk_scc()
438 vertex = next_vertex; in __unix_walk_scc()
448 next_vertex = vertex; in __unix_walk_scc()
449 vertex = edge->predecessor->vertex; in __unix_walk_scc()
455 vertex->scc_index = min(vertex->scc_index, next_vertex->scc_index); in __unix_walk_scc()
463 vertex->scc_index = min(vertex->scc_index, next_vertex->scc_index); in __unix_walk_scc()
469 if (vertex->index == vertex->scc_index) { in __unix_walk_scc()
479 __list_cut_position(&scc, &vertex_stack, &vertex->scc_entry); in __unix_walk_scc()
515 struct unix_vertex *vertex; in unix_walk_scc() local
517 vertex = list_first_entry(&unix_unvisited_vertices, typeof(*vertex), entry); in unix_walk_scc()
518 __unix_walk_scc(vertex, &last_index, hitlist); in unix_walk_scc()
532 struct unix_vertex *vertex; in unix_walk_scc_fast() local
536 vertex = list_first_entry(&unix_unvisited_vertices, typeof(*vertex), entry); in unix_walk_scc_fast()
537 list_add(&scc, &vertex->scc_entry); in unix_walk_scc_fast()
539 list_for_each_entry_reverse(vertex, &scc, scc_entry) { in unix_walk_scc_fast()
540 list_move_tail(&vertex->entry, &unix_visited_vertices); in unix_walk_scc_fast()
543 scc_dead = unix_vertex_dead(vertex); in unix_walk_scc_fast()