diff options
| author | Kuniyuki Iwashima <kuniyu@amazon.com> | 2025-05-21 17:45:23 +0300 |
|---|---|---|
| committer | Greg Kroah-Hartman <gregkh@linuxfoundation.org> | 2025-06-04 15:42:23 +0300 |
| commit | e0e23fc4999202fc68e36264288489a6e3f8e347 (patch) | |
| tree | d7875decd8894707ed97874c9074df4b16400030 /include | |
| parent | 27a07364cefdf97c5ed54654b9b5582f79fd5ecb (diff) | |
| download | linux-e0e23fc4999202fc68e36264288489a6e3f8e347.tar.xz | |
af_unix: Save O(n) setup of Tarjan's algo.
commit ba31b4a4e1018f5844c6eb31734976e2184f2f9a upstream.
Before starting Tarjan's algorithm, we need to mark all vertices
as unvisited. We can save this O(n) setup by reserving two special
indices (0, 1) and using two variables.
The first time we link a vertex to unix_unvisited_vertices, we set
unix_vertex_unvisited_index to index.
During DFS, we can see that the index of unvisited vertices is the
same as unix_vertex_unvisited_index.
When we finalise SCC later, we set unix_vertex_grouped_index to each
vertex's index.
Then, we can know (i) that the vertex is on the stack if the index
of a visited vertex is >= 2 and (ii) that it is not on the stack and
belongs to a different SCC if the index is unix_vertex_grouped_index.
After the whole algorithm, all indices of vertices are set as
unix_vertex_grouped_index.
Next time we start DFS, we know that all unvisited vertices have
unix_vertex_grouped_index, and we can use unix_vertex_unvisited_index
as the not-on-stack marker.
To use the same variable in __unix_walk_scc(), we can swap
unix_vertex_(grouped|unvisited)_index at the end of Tarjan's
algorithm.
Signed-off-by: Kuniyuki Iwashima <kuniyu@amazon.com>
Acked-by: Paolo Abeni <pabeni@redhat.com>
Link: https://lore.kernel.org/r/20240325202425.60930-10-kuniyu@amazon.com
Signed-off-by: Jakub Kicinski <kuba@kernel.org>
Signed-off-by: Lee Jones <lee@kernel.org>
Signed-off-by: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
Diffstat (limited to 'include')
| -rw-r--r-- | include/net/af_unix.h | 1 |
1 files changed, 0 insertions, 1 deletions
diff --git a/include/net/af_unix.h b/include/net/af_unix.h index 9d92dd608fc4..053f67adb9f1 100644 --- a/include/net/af_unix.h +++ b/include/net/af_unix.h @@ -37,7 +37,6 @@ struct unix_vertex { unsigned long out_degree; unsigned long index; unsigned long lowlink; - bool on_stack; }; struct unix_edge { |