-
-
Notifications
You must be signed in to change notification settings - Fork 8.6k
/
TreeString.java
225 lines (195 loc) · 6.98 KB
/
TreeString.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
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
/*
* The MIT License
*
* Copyright (c) 2012, CloudBees, Inc.
*
* Permission is hereby granted, free of charge, to any person obtaining a copy
* of this software and associated documentation files (the "Software"), to deal
* in the Software without restriction, including without limitation the rights
* to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
* copies of the Software, and to permit persons to whom the Software is
* furnished to do so, subject to the following conditions:
*
* The above copyright notice and this permission notice shall be included in
* all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
* AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
* OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
* THE SOFTWARE.
*/
package jenkins.util;
import java.io.Serializable;
import java.util.Map;
import org.apache.commons.lang.StringUtils;
import com.thoughtworks.xstream.XStream;
import com.thoughtworks.xstream.converters.Converter;
import com.thoughtworks.xstream.converters.MarshallingContext;
import com.thoughtworks.xstream.converters.UnmarshallingContext;
import com.thoughtworks.xstream.io.HierarchicalStreamReader;
import com.thoughtworks.xstream.io.HierarchicalStreamWriter;
/**
* {@link TreeString} is an alternative string representation that saves the
* memory when you have a large number of strings that share common prefixes
* (such as various file names.)
* <p>
* {@link TreeString} can be built with {@link TreeStringBuilder}.
*
* @author Kohsuke Kawaguchi
* @since 1.473
*/
// CHECKSTYLE:OFF
@SuppressWarnings("PMD")
public final class TreeString implements Serializable {
private static final long serialVersionUID = 3621959682117480904L;
/**
* Parent node that represents the prefix.
*/
private TreeString parent;
/**
* {@link #parent}+{@link #label} is the string value of this node.
*/
private char[] label;
/**
* Creates a new root {@link TreeString}
*/
/* package */TreeString() {
this(null, "");
}
/* package */TreeString(final TreeString parent, final String label) {
assert parent == null || label.length() > 0; // if there's a parent,
// label can't be empty.
this.parent = parent;
this.label = label.toCharArray(); // string created as a substring of
// another string can have a lot of
// garbage attached to it.
}
/* package */String getLabel() {
return new String(label);
}
/**
* Inserts a new node between this node and its parent, and returns the
* newly inserted node.
* <p>
* This operation doesn't change the string representation of this node.
*/
/* package */TreeString split(final String prefix) {
assert getLabel().startsWith(prefix);
char[] suffix = new char[label.length - prefix.length()];
System.arraycopy(label, prefix.length(), suffix, 0, suffix.length);
TreeString middle = new TreeString(parent, prefix);
label = suffix;
parent = middle;
return middle;
}
/**
* How many nodes do we have from the root to this node (including 'this'
* itself?) Thus depth of the root node is 1.
*/
private int depth() {
int i = 0;
for (TreeString p = this; p != null; p = p.parent) {
i++;
}
return i;
}
@Override
public boolean equals(final Object rhs) {
if (rhs == null) {
return false;
}
return rhs.getClass() == TreeString.class
&& ((TreeString)rhs).getLabel().equals(getLabel());
}
@Override
public int hashCode() {
int h = parent == null ? 0 : parent.hashCode();
for (char c : label) {
h = 31 * h + c;
}
assert toString().hashCode() == h;
return h;
}
/**
* Returns the full string representation.
*/
@Override
public String toString() {
char[][] tokens = new char[depth()][];
int i = tokens.length;
int sz = 0;
for (TreeString p = this; p != null; p = p.parent) {
tokens[--i] = p.label;
sz += p.label.length;
}
StringBuilder buf = new StringBuilder(sz);
for (char[] token : tokens) {
buf.append(token);
}
return buf.toString();
}
/**
* Interns {@link #label}
*/
/* package */void dedup(final Map<String, char[]> table) {
String l = getLabel();
char[] v = table.get(l);
if (v != null) {
label = v;
}
else {
table.put(l, label);
}
}
public boolean isBlank() {
return StringUtils.isBlank(toString());
}
public static String toString(final TreeString t) {
return t == null ? null : t.toString();
}
/**
* Creates a {@link TreeString}. Useful if you need to create one-off
* {@link TreeString} without {@link TreeStringBuilder}. Memory consumption
* is still about the same to {@code new String(s)}.
*
* @return null if the parameter is null
*/
public static TreeString of(final String s) {
if (s == null) {
return null;
}
return new TreeString(null, s);
}
/**
* Default {@link Converter} implementation for XStream that does interning
* scoped to one unmarshalling.
*/
@SuppressWarnings("all")
public static final class ConverterImpl implements Converter {
public ConverterImpl(final XStream xs) {}
public void marshal(final Object source, final HierarchicalStreamWriter writer,
final MarshallingContext context) {
writer.setValue(source == null ? null : source.toString());
}
public Object unmarshal(final HierarchicalStreamReader reader, final UnmarshallingContext context) {
TreeStringBuilder builder = (TreeStringBuilder)context.get(TreeStringBuilder.class);
if (builder == null) {
context.put(TreeStringBuilder.class, builder = new TreeStringBuilder());
// dedup at the end
final TreeStringBuilder _builder = builder;
context.addCompletionCallback(new Runnable() {
public void run() {
_builder.dedup();
}
}, 0);
}
return builder.intern(reader.getValue());
}
public boolean canConvert(final Class type) {
return type == TreeString.class;
}
}
}