Line data    Source code

       1             : // Copyright (C) 2009 The Android Open Source Project
       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.gerrit.prettify.common;
      16             : 
      17             : import com.google.auto.value.AutoValue;
      18             : import com.google.common.annotations.VisibleForTesting;
      19             : import com.google.common.collect.ImmutableList;
      20             : import com.google.gerrit.common.Nullable;
      21             : 
      22             : /**
      23             :  * A class to store subset of a file's lines in a memory efficient way. Internally, it stores lines
      24             :  * as a list of ranges. Each range represents continuous set of lines and has information about line
      25             :  * numbers in original file (zero-based).
      26             :  *
      27             :  * <p>{@link SparseFileContent.Accessor} must be used to work with the stored content.
      28             :  */
      29             : @AutoValue
      30          15 : public abstract class SparseFileContent {
      31             :   abstract ImmutableList<Range> getRanges();
      32             : 
      33             :   public abstract int getSize();
      34             : 
      35             :   public static SparseFileContent create(ImmutableList<Range> ranges, int size) {
      36          15 :     return new AutoValue_SparseFileContent(ranges, size);
      37             :   }
      38             : 
      39             :   @VisibleForTesting
      40             :   public int getRangesCount() {
      41           1 :     return getRanges().size();
      42             :   }
      43             : 
      44             :   public Accessor createAccessor() {
      45          11 :     return new Accessor(this);
      46             :   }
      47             : 
      48             :   /**
      49             :    * Provide a methods to work with the content of a {@link SparseFileContent}.
      50             :    *
      51             :    * <p>The class hides internal representation of a {@link SparseFileContent} and provides
      52             :    * convenient way for accessing a content.
      53             :    */
      54             :   public static class Accessor {
      55             :     private final SparseFileContent content;
      56             :     private int currentRangeIdx;
      57             : 
      58          11 :     private Accessor(SparseFileContent content) {
      59          11 :       this.content = content;
      60          11 :     }
      61             : 
      62             :     public String get(int idx) {
      63          11 :       final String line = getLine(idx);
      64          11 :       if (line == null) {
      65           0 :         throw new ArrayIndexOutOfBoundsException(idx);
      66             :       }
      67          11 :       return line;
      68             :     }
      69             : 
      70             :     public int getSize() {
      71          11 :       return content.getSize();
      72             :     }
      73             : 
      74             :     public boolean contains(int idx) {
      75           5 :       return getLine(idx) != null;
      76             :     }
      77             : 
      78             :     public int first() {
      79           3 :       return content.getRanges().isEmpty() ? getSize() : content.getRanges().get(0).getBase();
      80             :     }
      81             : 
      82             :     public int next(int idx) {
      83             :       // Most requests are sequential in nature, fetching the next
      84             :       // line from the current range, or the immediate next range.
      85             :       //
      86           6 :       ImmutableList<Range> ranges = content.getRanges();
      87           6 :       int high = ranges.size();
      88           6 :       if (currentRangeIdx < high) {
      89           6 :         Range cur = ranges.get(currentRangeIdx);
      90           6 :         if (cur.contains(idx + 1)) {
      91           6 :           return idx + 1;
      92             :         }
      93             : 
      94           6 :         if (++currentRangeIdx < high) {
      95             :           // Its not plus one, its the base of the next range.
      96             :           //
      97           1 :           return ranges.get(currentRangeIdx).getBase();
      98             :         }
      99             :       }
     100             : 
     101             :       // Binary search for the current value, since we know its a sorted list.
     102             :       //
     103           6 :       int low = 0;
     104             :       do {
     105           6 :         final int mid = (low + high) / 2;
     106           6 :         final Range cur = ranges.get(mid);
     107             : 
     108           6 :         if (cur.contains(idx)) {
     109           6 :           if (cur.contains(idx + 1)) {
     110             :             // Trivial plus one case above failed due to wrong currentRangeIdx.
     111             :             // Reset the cache so we don't miss in the future.
     112             :             //
     113           0 :             currentRangeIdx = mid;
     114           0 :             return idx + 1;
     115             :           }
     116             : 
     117           6 :           if (mid + 1 < ranges.size()) {
     118             :             // Its the base of the next range.
     119           0 :             currentRangeIdx = mid + 1;
     120           0 :             return ranges.get(currentRangeIdx).getBase();
     121             :           }
     122             : 
     123             :           // No more lines in the file.
     124             :           //
     125           6 :           return getSize();
     126             :         }
     127             : 
     128           1 :         if (idx < cur.getBase()) {
     129           0 :           high = mid;
     130             :         } else {
     131           1 :           low = mid + 1;
     132             :         }
     133           1 :       } while (low < high);
     134             : 
     135           0 :       return getSize();
     136             :     }
     137             : 
     138             :     @Nullable
     139             :     private String getLine(int idx) {
     140             :       // Most requests are sequential in nature, fetching the next
     141             :       // line from the current range, or the next range.
     142             :       //
     143          11 :       ImmutableList<Range> ranges = content.getRanges();
     144          11 :       int high = ranges.size();
     145          11 :       if (currentRangeIdx < high) {
     146          11 :         Range cur = ranges.get(currentRangeIdx);
     147          11 :         if (cur.contains(idx)) {
     148          11 :           return cur.get(idx);
     149             :         }
     150             : 
     151           3 :         if (++currentRangeIdx < high) {
     152           2 :           final Range next = ranges.get(currentRangeIdx);
     153           2 :           if (next.contains(idx)) {
     154           2 :             return next.get(idx);
     155             :           }
     156             :         }
     157             :       }
     158             : 
     159             :       // Binary search for the range, since we know its a sorted list.
     160             :       //
     161           3 :       if (ranges.isEmpty()) {
     162           3 :         return null;
     163             :       }
     164             : 
     165           3 :       int low = 0;
     166             :       do {
     167           3 :         final int mid = (low + high) / 2;
     168           3 :         final Range cur = ranges.get(mid);
     169           3 :         if (cur.contains(idx)) {
     170           3 :           currentRangeIdx = mid;
     171           3 :           return cur.get(idx);
     172             :         }
     173           3 :         if (idx < cur.getBase()) {
     174           3 :           high = mid;
     175             :         } else {
     176           3 :           low = mid + 1;
     177             :         }
     178           3 :       } while (low < high);
     179           3 :       return null;
     180             :     }
     181             :   }
     182             : 
     183             :   @Override
     184             :   public final String toString() {
     185           0 :     final StringBuilder b = new StringBuilder();
     186           0 :     b.append("SparseFileContent[\n");
     187           0 :     for (Range r : getRanges()) {
     188           0 :       b.append("  ");
     189           0 :       b.append(r.toString());
     190           0 :       b.append('\n');
     191           0 :     }
     192           0 :     b.append("]");
     193           0 :     return b.toString();
     194             :   }
     195             : 
     196             :   @AutoValue
     197          15 :   abstract static class Range {
     198             :     static Range create(int base, ImmutableList<String> lines) {
     199          15 :       return new AutoValue_SparseFileContent_Range(base, lines);
     200             :     }
     201             : 
     202             :     abstract int getBase();
     203             : 
     204             :     abstract ImmutableList<String> getLines();
     205             : 
     206             :     private String get(int i) {
     207          11 :       return getLines().get(i - getBase());
     208             :     }
     209             : 
     210             :     private int end() {
     211          11 :       return getBase() + getLines().size();
     212             :     }
     213             : 
     214             :     private boolean contains(int i) {
     215          11 :       return getBase() <= i && i < end();
     216             :     }
     217             : 
     218             :     @Override
     219             :     public final String toString() {
     220             :       // Usage of [ and ) is intentional to denote inclusive/exclusive range
     221           0 :       return "Range[" + getBase() + "," + end() + ")";
     222             :     }
     223             :   }
     224             : }