forked from android-not-respond/Measurement
-
Notifications
You must be signed in to change notification settings - Fork 0
/
Pipeline.java
91 lines (80 loc) · 2.17 KB
/
Pipeline.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
/**
* The data structure of wait-for graph.
*/
class ListNode {
int tid;
ListNode next;
ListNode(int id) {
tid = id;
next = null;
}
}
/**
* The implementation of root cause analysis pipeline.
*/
public class Pipeline {
// Wait-for graph
ListNode waitForGraph = null;
// A set of regexs used to remove irrelevant information from the call stacks
String[] regexs = null;
/**
* Find the end node of a wait-for graph.
*
* @param head Wait-for graph.
* @return The end node.
*/
ListNode findLastThread(ListNode head) {
if (head == null)
return null;
// If there is no cycle in the graph
else if (detectCycle(head) == null){
ListNode p = head;
while (p.next != null) {
p = p.next;
}
return p;
}
}
/**
* The implementation of cycle detection algorithm.
*
* @param head Wait-for graph.
* @return The entrance of the cycle. NULL if there is no cycle.
*/
ListNode detectCycle(ListNode head) {
if (head == null) {
return null;
}
ListNode nodeOfCycle = getCycle(head);
if (nodeOfCycle == null) {
return null;
}
// Try to find the entrance of a detected cycle
ListNode node1 = head;
ListNode node2 = nodeOfCycle;
while (node1 != node2) {
node1 = node1.next;
node2 = node2.next;
}
return node1;
}
/**
* Detect and acquire the cycle of a graph.
*
* @param head Wait-for graph.
* @return A node of the cycle. NULL if there is no cycle.
*/
ListNode getCycle(ListNode head) {
ListNode slowNode = head;
ListNode fastNode = head;
// The faster node will eventually collide with the slower node (if a cycle exists) or reach NULL.
while (fastNode != null && fastNode.next != null) {
slowNode = slowNode.next;
fastNode = fastNode.next.next;
if (slowNode == fastNode) {
return slowNode;
}
}
return null;
}
}