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 }