Home | History | Annotate | Download | only in generator 
      1 // Copyright 2016 Google Inc. All rights reserved.
      2 //
      3 // Licensed under the Apache License, Version 2.0 (the "License");
      4 // you may not use this file except in compliance with the License.
      5 // You may obtain a copy of the License at
      6 //
      7 //     http://www.apache.org/licenses/LICENSE-2.0
      8 //
      9 // Unless required by applicable law or agreed to in writing, software
     10 // distributed under the License is distributed on an "AS IS" BASIS,
     11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
     12 // See the License for the specific language governing permissions and
     13 // limitations under the License.
     14 
     15 package com.google.archivepatcher.generator;
     16 
     17 import java.io.File;
     18 import java.util.ArrayList;
     19 import java.util.Collections;
     20 import java.util.Comparator;
     21 import java.util.List;
     22 
     23 /**
     24  * Limits the size of the delta-friendly old blob, which is an implicit limitation on the amount of
     25  * temp space required to apply a patch.
     26  *
     27  * <p>This class implements the following algorithm:
     28  *
     29  * <ol>
     30  *   <li>Check the size of the old archive and subtract it from the maximum size, this is the number
     31  *       of bytes that can be used to uncompress entries in the delta-friendly old file.
     32  *   <li>Identify all of the {@link QualifiedRecommendation}s that have {@link
     33  *       Recommendation#uncompressOldEntry} set to <code>true</code>. These identify all the entries
     34  *       that would be uncompressed in the delta-friendly old file.
     35  *   <li>Sort those {@link QualifiedRecommendation}s in order of decreasing uncompressed size.
     36  *   <li>Iterate over the list in order. For each entry, calculate the difference between the
     37  *       uncompressed size and the compressed size; this is the number of bytes that would be
     38  *       consumed to transform the data from compressed to uncompressed in the delta-friendly old
     39  *       file. If the number of bytes that would be consumed is less than the number of bytes
     40  *       remaining before hitting the cap, retain it; else, discard it.
     41  *   <li>Return the resulting list of the retained entries. Note that the order of this list may not
     42  *       be the same as the input order (i.e., it has been sorted in order of decreasing compressed
     43  *       size).
     44  * </ol>
     45  */
     46 public class DeltaFriendlyOldBlobSizeLimiter implements RecommendationModifier {
     47 
     48   /** The maximum size of the delta-friendly old blob. */
     49   private final long maxSizeBytes;
     50 
     51   private static final Comparator<QualifiedRecommendation> COMPARATOR =
     52       new UncompressedOldEntrySizeComparator();
     53 
     54   /**
     55    * Create a new limiter that will restrict the total size of the delta-friendly old blob.
     56    *
     57    * @param maxSizeBytes the maximum size of the delta-friendly old blob
     58    */
     59   public DeltaFriendlyOldBlobSizeLimiter(long maxSizeBytes) {
     60     if (maxSizeBytes < 0) {
     61       throw new IllegalArgumentException("maxSizeBytes must be non-negative: " + maxSizeBytes);
     62     }
     63     this.maxSizeBytes = maxSizeBytes;
     64   }
     65 
     66   @Override
     67   public List<QualifiedRecommendation> getModifiedRecommendations(
     68       File oldFile, File newFile, List<QualifiedRecommendation> originalRecommendations) {
     69 
     70     List<QualifiedRecommendation> sorted = sortRecommendations(originalRecommendations);
     71 
     72     List<QualifiedRecommendation> result = new ArrayList<>(sorted.size());
     73     long bytesRemaining = maxSizeBytes - oldFile.length();
     74     for (QualifiedRecommendation originalRecommendation : sorted) {
     75       if (!originalRecommendation.getRecommendation().uncompressOldEntry) {
     76         // Keep the original recommendation, no need to track size since it won't be uncompressed.
     77         result.add(originalRecommendation);
     78       } else {
     79         long extraBytesConsumed =
     80             originalRecommendation.getOldEntry().getUncompressedSize()
     81                 - originalRecommendation.getOldEntry().getCompressedSize();
     82         if (bytesRemaining - extraBytesConsumed >= 0) {
     83           // Keep the original recommendation, but also subtract from the remaining space.
     84           result.add(originalRecommendation);
     85           bytesRemaining -= extraBytesConsumed;
     86         } else {
     87           // Update the recommendation to prevent uncompressing this tuple.
     88           result.add(
     89               new QualifiedRecommendation(
     90                   originalRecommendation.getOldEntry(),
     91                   originalRecommendation.getNewEntry(),
     92                   Recommendation.UNCOMPRESS_NEITHER,
     93                   RecommendationReason.RESOURCE_CONSTRAINED));
     94         }
     95       }
     96     }
     97     return result;
     98   }
     99 
    100   private static List<QualifiedRecommendation> sortRecommendations(
    101       List<QualifiedRecommendation> originalRecommendations) {
    102     List<QualifiedRecommendation> sorted =
    103         new ArrayList<QualifiedRecommendation>(originalRecommendations);
    104     Collections.sort(sorted, COMPARATOR);
    105     Collections.reverse(sorted);
    106     return sorted;
    107   }
    108 
    109   /** Helper class implementing the sort order described in the class documentation. */
    110   private static class UncompressedOldEntrySizeComparator
    111       implements Comparator<QualifiedRecommendation> {
    112     @Override
    113     public int compare(QualifiedRecommendation qr1, QualifiedRecommendation qr2) {
    114       return Long.compare(
    115           qr1.getOldEntry().getUncompressedSize(), qr2.getOldEntry().getUncompressedSize());
    116     }
    117   }
    118 }
    119