1 /*
2 * Copyright (c) 2014, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
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();
98 this.redirectStream = new ImageStream();
99 this.locationOffsetStream = new ImageStream();
100 this.locationStream = new ImageStream();
101 this.allIndexStream = new ImageStream();
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 }