8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26 package jdk.internal.jimage;
27
28 import java.io.PrintStream;
29 import java.nio.ByteOrder;
30 import java.util.ArrayList;
31 import java.util.Arrays;
32 import java.util.List;
33
34 public final class BasicImageWriter {
35 private final static int RETRY_LIMIT = 1000;
36
37 private ByteOrder byteOrder;
38 private ImageStrings strings;
39 private int count;
40 private int[] redirect;
41 private ImageLocation[] locations;
42 private List<ImageLocation> input;
43 private ImageStream headerStream;
44 private ImageStream redirectStream;
45 private ImageStream locationOffsetStream;
46 private ImageStream locationStream;
47 private ImageStream allIndexStream;
48
49 static class ImageBucket implements Comparable<ImageBucket> {
50 final List<ImageLocation> list;
51
52 ImageBucket() {
53 this.list = new ArrayList<>();
54 }
55
56 void add(ImageLocation location) {
57 list.add(location);
58 }
59
60 int getSize() {
61 return list.size();
62 }
63
64 List<ImageLocation> getList() {
65 return list;
66 }
67
68 ImageLocation getFirst() {
69 assert !list.isEmpty() : "bucket should never be empty";
70 return list.get(0);
71 }
72
73 @Override
74 public int hashCode() {
75 return getFirst().hashCode();
76 }
77
78 @Override
79 public boolean equals(Object obj) {
80 return this == obj;
81 }
82
83 @Override
84 public int compareTo(ImageBucket o) {
85 return o.getSize() - getSize();
86 }
87 }
88
89 public BasicImageWriter() {
90 this(ByteOrder.nativeOrder());
91 }
92
93 public BasicImageWriter(ByteOrder byteOrder) {
94 this.byteOrder = byteOrder;
95 this.input = new ArrayList<>();
96 this.strings = new ImageStrings();
97 this.headerStream = new ImageStream(byteOrder);
98 this.redirectStream = new ImageStream(byteOrder);
99 this.locationOffsetStream = new ImageStream(byteOrder);
100 this.locationStream = new ImageStream(byteOrder);
101 this.allIndexStream = new ImageStream(byteOrder);
102 }
103
104 public int addString(String string) {
105 return addString(new UTF8String(string));
106 }
107
108 public int addString(UTF8String string) {
109 return strings.add(string);
110 }
111
112 public void addLocation(String fullname, long contentOffset, long compressedSize, long uncompressedSize) {
113 ImageLocation location = ImageLocation.newLocation(new UTF8String(fullname), strings, contentOffset, compressedSize, uncompressedSize);
114 input.add(location);
115 count++;
116 }
117
118 private void generatePerfectHash() {
119 redo:
120 while(true) {
121 redirect = new int[count];
122 locations = new ImageLocation[count];
123
124 ImageBucket[] sorted = createBuckets();
125
126 int free = 0;
127
128 for (ImageBucket bucket : sorted) {
129 if (bucket.getSize() != 1) {
130 if (!packCollidedEntries(bucket, count)) {
131 count = (count + 1) | 1;
132
133 continue redo;
134 }
135 } else {
136 for ( ; free < count && locations[free] != null; free++) {}
137 assert free < count : "no free slots";
138 locations[free] = bucket.getFirst();
139 redirect[bucket.hashCode() % count] = -1 - free;
140 free++;
141 }
142 }
143
144 break;
145 }
146 }
147
148 private ImageBucket[] createBuckets() {
149 ImageBucket[] buckets = new ImageBucket[count];
150
151 input.stream().forEach((location) -> {
152 int index = location.hashCode() % count;
153 ImageBucket bucket = buckets[index];
154
155 if (bucket == null) {
156 buckets[index] = bucket = new ImageBucket();
157 }
158
159 bucket.add(location);
160 });
161
162 ImageBucket[] sorted = Arrays.asList(buckets).stream()
163 .filter((bucket) -> (bucket != null))
164 .sorted()
165 .toArray(ImageBucket[]::new);
166
167 return sorted;
168 }
169
170 private boolean packCollidedEntries(ImageBucket bucket, int count) {
171 List<Integer> undo = new ArrayList<>();
172 int base = UTF8String.HASH_MULTIPLIER + 1;
173
174 int retry = 0;
175
176 redo:
177 while (true) {
178 for (ImageLocation location : bucket.getList()) {
179 int index = location.hashCode(base) % count;
180
181 if (locations[index] != null) {
182 undo.stream().forEach((i) -> {
183 locations[i] = null;
184 });
185
186 undo.clear();
187 base++;
188
189 if (base == 0) {
190 base = 1;
191 }
192
193 if (++retry > RETRY_LIMIT) {
194 return false;
195 }
196
197 continue redo;
198 }
199
200 locations[index] = location;
201 undo.add(index);
202 }
203
204 redirect[bucket.hashCode() % count] = base;
205
206 break;
207 }
208
209 return true;
210 }
211
212 private void prepareStringBytes() {
213 strings.getStream().align(2);
214 }
215
216 private void prepareRedirectBytes() {
217 for (int i = 0; i < count; i++) {
218 redirectStream.putInt(redirect[i]);
219 }
220 }
221
222 private void prepareLocationBytes() {
223 // Reserve location offset zero for empty locations
224 locationStream.put(ImageLocation.ATTRIBUTE_END << 3);
225
226 for (int i = 0; i < count; i++) {
227 ImageLocation location = locations[i];
228
229 if (location != null) {
230 location.writeTo(locationStream);
231 }
232 }
233
234 locationStream.align(2);
235 }
236
237 private void prepareOffsetBytes() {
238 for (int i = 0; i < count; i++) {
239 ImageLocation location = locations[i];
240 locationOffsetStream.putInt(location != null ? location.getLocationOffset() : 0);
241 }
242 }
243
244 private void prepareHeaderBytes() {
245 ImageHeader header = new ImageHeader(count, locationStream.getSize(), strings.getSize());
246 header.writeTo(headerStream);
247 }
248
249 private void prepareTableBytes() {
250 allIndexStream.put(headerStream);
251 allIndexStream.put(redirectStream);
252 allIndexStream.put(locationOffsetStream);
253 allIndexStream.put(locationStream);
254 allIndexStream.put(strings.getStream());
255 }
256
257 public byte[] getBytes() {
258 if (allIndexStream.getSize() == 0) {
259 generatePerfectHash();
260 prepareStringBytes();
261 prepareRedirectBytes();
262 prepareLocationBytes();
263 prepareOffsetBytes();
264 prepareHeaderBytes();
265 prepareTableBytes();
266 }
267
268 return allIndexStream.toArray();
269 }
270
271 ImageLocation find(UTF8String key) {
272 int index = key.hashCode() % count;
273 index = redirect[index];
274
275 if (index < 0) {
276 index = -index - 1;
277 ImageLocation location = locations[index];
278
279 return location;
280 } else {
281 index = key.hashCode(index) % count;
282 ImageLocation location = locations[index];
283
284 return location;
285 }
286 }
287
288 public void statistics() {
289 getBytes();
290 PrintStream out = System.out;
291 out.println("Count: " + count);
292 out.println("Header bytes size: " + headerStream.getSize());
293 out.println("Redirect bytes size: " + redirectStream.getSize());
294 out.println("Offset bytes size: " + locationOffsetStream.getSize());
295 out.println("Location bytes size: " + locationStream.getSize());
296 out.println("String count: " + strings.getCount());
297 out.println("String bytes size: " + strings.getSize());
298 out.println("Total bytes size: " + allIndexStream.getSize());
299 }
300 }
|
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26 package jdk.internal.jimage;
27
28 import java.nio.ByteOrder;
29 import java.util.ArrayList;
30 import java.util.List;
31
32 public final class BasicImageWriter {
33
34 public static final String IMAGE_EXT = ".jimage";
35 public static final String BOOT_NAME = "bootmodules";
36 public static final String BOOT_IMAGE_NAME = BOOT_NAME + IMAGE_EXT;
37
38 private final static int RETRY_LIMIT = 1000;
39
40 private ByteOrder byteOrder;
41 private ImageStringsWriter strings;
42 private int length;
43 private int[] redirect;
44 private ImageLocationWriter[] locations;
45 private List<ImageLocationWriter> input;
46 private ImageStream headerStream;
47 private ImageStream redirectStream;
48 private ImageStream locationOffsetStream;
49 private ImageStream locationStream;
50 private ImageStream allIndexStream;
51
52 public BasicImageWriter() {
53 this(ByteOrder.nativeOrder());
54 }
55
56 public BasicImageWriter(ByteOrder byteOrder) {
57 this.byteOrder = byteOrder;
58 this.input = new ArrayList<>();
59 this.strings = new ImageStringsWriter();
60 this.headerStream = new ImageStream(byteOrder);
61 this.redirectStream = new ImageStream(byteOrder);
62 this.locationOffsetStream = new ImageStream(byteOrder);
63 this.locationStream = new ImageStream(byteOrder);
64 this.allIndexStream = new ImageStream(byteOrder);
65 }
66
67 public ByteOrder getByteOrder() {
68 return byteOrder;
69 }
70
71 public int addString(String string) {
72 return addString(new UTF8String(string));
73 }
74
75 public int addString(UTF8String string) {
76 return strings.add(string);
77 }
78
79 public String getString(int offset) {
80 UTF8String utf8 = strings.get(offset);
81 return utf8 != null? utf8.toString() : null;
82 }
83
84 public void addLocation(String fullname, long contentOffset,
85 long compressedSize, long uncompressedSize) {
86 ImageLocationWriter location =
87 ImageLocationWriter.newLocation(new UTF8String(fullname), strings,
88 contentOffset, compressedSize, uncompressedSize);
89 input.add(location);
90 length++;
91 }
92
93 ImageLocationWriter[] getLocations() {
94 return locations;
95 }
96
97 int getLocationsCount() {
98 return input.size();
99 }
100
101 private void generatePerfectHash() {
102 PerfectHashBuilder<ImageLocationWriter> builder =
103 new PerfectHashBuilder<>(
104 new PerfectHashBuilder.Entry<ImageLocationWriter>().getClass(),
105 new PerfectHashBuilder.Bucket<ImageLocationWriter>().getClass());
106
107 input.forEach((location) -> {
108 builder.put(location.getFullName(), location);
109 });
110
111 builder.generate();
112
113 length = builder.getCount();
114 redirect = builder.getRedirect();
115 PerfectHashBuilder.Entry<ImageLocationWriter>[] order = builder.getOrder();
116 locations = new ImageLocationWriter[length];
117
118 for (int i = 0; i < length; i++) {
119 locations[i] = order[i].getValue();
120 }
121 }
122
123 private void prepareStringBytes() {
124 strings.getStream().align(2);
125 }
126
127 private void prepareRedirectBytes() {
128 for (int i = 0; i < length; i++) {
129 redirectStream.putInt(redirect[i]);
130 }
131 }
132
133 private void prepareLocationBytes() {
134 // Reserve location offset zero for empty locations
135 locationStream.put(ImageLocationWriter.ATTRIBUTE_END << 3);
136
137 for (int i = 0; i < length; i++) {
138 ImageLocationWriter location = locations[i];
139
140 if (location != null) {
141 location.writeTo(locationStream);
142 }
143 }
144
145 locationStream.align(2);
146 }
147
148 private void prepareOffsetBytes() {
149 for (int i = 0; i < length; i++) {
150 ImageLocationWriter location = locations[i];
151 int offset = location != null ? location.getLocationOffset() : 0;
152 locationOffsetStream.putInt(offset);
153 }
154 }
155
156 private void prepareHeaderBytes() {
157 ImageHeader header = new ImageHeader(input.size(), length,
158 locationStream.getSize(), strings.getSize());
159 header.writeTo(headerStream);
160 }
161
162 private void prepareTableBytes() {
163 allIndexStream.put(headerStream);
164 allIndexStream.put(redirectStream);
165 allIndexStream.put(locationOffsetStream);
166 allIndexStream.put(locationStream);
167 allIndexStream.put(strings.getStream());
168 }
169
170 public byte[] getBytes() {
171 if (allIndexStream.getSize() == 0) {
172 generatePerfectHash();
173 prepareStringBytes();
174 prepareRedirectBytes();
175 prepareLocationBytes();
176 prepareOffsetBytes();
177 prepareHeaderBytes();
178 prepareTableBytes();
179 }
180
181 return allIndexStream.toArray();
182 }
183
184 ImageLocationWriter find(UTF8String key) {
185 int index = redirect[key.hashCode() % length];
186
187 if (index < 0) {
188 index = -index - 1;
189 } else {
190 index = key.hashCode(index) % length;
191 }
192
193 return locations[index];
194 }
195 }
|