File D:\maven-qcr-plugin-testsunitaires\qcr4java\jenkins-master\target\site\qc\core\src\main\java\jenkins\util\TreeStringBuilder.java.html

1 package jenkins.util;
2
3 import java.util.Collections;
4 import java.util.HashMap;
5 import java.util.Map;
6
7 /**
8 * Builds {@link TreeString}s that share common prefixes. Call
9 * {@link #intern(String)} and you get the {@link TreeString} that represents
10 * the same string, but as you interns more strings that share the same
11 * prefixes, those {@link TreeString}s that you get back start to share data.
12 * <p>
13 * Because the internal state of {@link TreeString}s get mutated as new strings
14 * are interned (to exploit new-found common prefixes), {@link TreeString}s
15 * returned from {@link #intern(String)} aren't thread-safe until
16 * {@link TreeStringBuilder} is disposed. That is, you have to make sure other
17 * threads don't see those {@link TreeString}s until you are done interning
18 * strings.
19 *
20 * @author Kohsuke Kawaguchi
21 * @since 1.473
22 */
23 @SuppressWarnings({"PMD", "all"})
24 //CHECKSTYLE:OFF
25 public class TreeStringBuilder {
26 Child root = new Child(new TreeString());
27
28 private static class Child {
29 private final TreeString node;
30
31 private Map<String, Child> children = NO_CHILDREN;
32
33 private Child(final TreeString node) {
34 this.node = node;
35 }
36
37 /**
38 * Adds one edge and leaf to this tree node, or returns an existing node
39 * if any.
40 */
41 public Child intern(final String s) {
42 if (s.length() == 0) {
43 return this;
44 }
45
46 makeWritable();
47 for (Map.Entry<String, Child> e : children.entrySet()) {
48 int plen = commonPrefix(e.getKey(), s);
49 if (plen > 0) {
50 if (plen < e.getKey().length()) {
51 // insert a node between this and e.value
52 Child c = e.getValue();
53 String prefix = s.substring(0, plen);
54 Child middle = c.split(prefix);
55
56 // add 'middle' instead of 'c'
57 children.remove(e.getKey());
58 children.put(prefix, middle);
59
60 return middle.intern(s.substring(plen));
61 }
62 else {// entire key is suffix
63 return e.getValue().intern(s.substring(plen));
64 }
65 }
66 }
67
68 // no common prefix. an entirely new node.
69 Child t = children.get(s);
70 if (t == null) {
71 children.put(s, t = new Child(new TreeString(node, s)));
72 }
73 return t;
74 }
75
76 /**
77 * Makes sure {@link #children} is writable.
78 */
79 private void makeWritable() {
80 if (children == NO_CHILDREN) {
81 children = new HashMap<String, Child>();
82 }
83 }
84
85 /**
86 * Inserts a new node between this node and its parent, and returns that
87 * node. Newly inserted 'middle' node will have this node as its sole
88 * child.
89 */
90 private Child split(final String prefix) {
91 String suffix = node.getLabel().substring(prefix.length());
92
93 Child middle = new Child(node.split(prefix));
94 middle.makeWritable();
95 middle.children.put(suffix, this);
96
97 return middle;
98 }
99
100 /**
101 * Returns the common prefix between two strings.
102 */
103 private int commonPrefix(final String a, final String b) {
104 int m = Math.min(a.length(), b.length());
105
106 for (int i = 0; i < m; i++) {
107 if (a.charAt(i) != b.charAt(i)) {
108 return i;
109 }
110 }
111 return m;
112 }
113
114 /**
115 * Calls {@link TreeString#dedup(Map)} recursively.
116 */
117 private void dedup(final Map<String, char[]> table) {
118 node.dedup(table);
119 for (Child child : children.values()) {
120 child.dedup(table);
121 }
122 }
123 }
124
125 /**
126 * Interns a string.
127 */
128 public TreeString intern(final String s) {
129 if (s==null) return null;
130 return root.intern(s).node;
131 }
132
133 /**
134 * Interns a {@link TreeString} created elsewhere.
135 */
136 public TreeString intern(final TreeString s) {
137 if (s==null) return null;
138 return root.intern(s.toString()).node;
139 }
140
141 /**
142 * Further reduces the memory footprint by finding the same labels across
143 * multiple {@link TreeString}s.
144 */
145 public void dedup() {
146 root.dedup(new HashMap<String, char[]>());
147 }
148
149 /**
150 * Place holder that represents no child node, until one is added.
151 */
152 private static final Map<String, Child> NO_CHILDREN = Collections.emptyMap();
153
154 }
155