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(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 }