src/third_party/cacheinvalidation/src/java/com/google/ipc/invalidation/util/Bytes.java

   1 /*
   2  * Copyright 2011 Google Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  * http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16 package com.google.ipc.invalidation.util;
  17
  18 import com.google.ipc.invalidation.util.LazyString.LazyStringReceiver;
  19
  20 import java.nio.ByteBuffer;
  21 import java.nio.charset.Charset;
  22 import java.util.Arrays;
  23 import java.util.Locale;
  24
  25
  26 /**
  27  * A class that encapsulates a (fixed size) sequence of bytes and provides a
  28  * equality (along with hashcode) method that considers two sequences to be
  29  * equal if they have the same contents. Borrowed from protobuf's ByteString
  30  *
  31  */
  32 public class Bytes extends InternalBase implements Comparable<Bytes> {
  33
  34   public static final Bytes EMPTY_BYTES = new Bytes(new byte[0]);
  35   private static final Charset UTF_8 = Charset.forName("UTF-8");
  36
  37   /**
  38    * Interface accessing byte elements from {@code T}, which may be (for instance)
  39    * {@link com.google.protobuf.ByteString ByteString} or {@code byte[]}.
  40    */
  41   interface BytesAccessor<T> {
  42     int size(T bytes);
  43     byte get(T bytes, int index);
  44   }
  45
  46   private static final BytesAccessor<byte[]> BYTE_ARRAY_ACCESSOR = new BytesAccessor<byte[]>() {
  47     @Override public int size(byte[] bytes) {
  48       return bytes == null ? 0 : bytes.length;
  49     }
  50
  51     @Override public byte get(byte[] bytes, int index) {
  52       return bytes[index];
  53     }
  54   };
  55
  56   private static final LazyStringReceiver<byte[]> BYTE_ARRAY_RECEIVER =
  57       new LazyStringReceiver<byte[]>() {
  58     @Override public void appendToBuilder(TextBuilder builder, byte[] element) {
  59       toCompactString(builder, element);
  60     }
  61   };
  62
  63   /**
  64    * Three arrays that store the representation of each character from 0 to 255.
  65    * The ith number's octal representation is: CHAR_OCTAL_STRINGS1[i],
  66    * CHAR_OCTAL_STRINGS2[i], CHAR_OCTAL_STRINGS3[i]
  67    * <p>
  68    * E.g., if the number 128, these arrays contain 2, 0, 0 at index 128. We use
  69    * 3 char arrays instead of an array of strings since the code path for a
  70    * character append operation is quite a bit shorter than the append operation
  71    * for strings.
  72    */
  73   private static final char[] CHAR_OCTAL_STRINGS1 = new char[256];
  74   private static final char[] CHAR_OCTAL_STRINGS2 = new char[256];
  75   private static final char[] CHAR_OCTAL_STRINGS3 = new char[256];
  76
  77   /** The actual sequence. */
  78   private final byte[] bytes;
  79
  80   /** Cached hash */
  81   private volatile int hash = 0;
  82
  83   static {
  84     // Initialize the array with the Octal string values so that we do not have
  85     // to do String.format for every byte during runtime.
  86     for (int i = 0; i < CHAR_OCTAL_STRINGS1.length; i++) {
  87       String value = String.format(Locale.ROOT, "\\%03o", i);
  88       CHAR_OCTAL_STRINGS1[i] = value.charAt(1);
  89       CHAR_OCTAL_STRINGS2[i] = value.charAt(2);
  90       CHAR_OCTAL_STRINGS3[i] = value.charAt(3);
  91     }
  92   }
  93
  94   public Bytes(byte[] bytes) {
  95     this.bytes = bytes;
  96   }
  97
  98   /**
  99    * Creates a Bytes object with the contents of {@code array1} followed by the
 100    * contents of {@code array2}.
 101    */
 102   public Bytes(byte[] array1, byte[] array2) {
 103     Preconditions.checkNotNull(array1);
 104     Preconditions.checkNotNull(array2);
 105     ByteBuffer buffer = ByteBuffer.allocate(array1.length + array2.length);
 106     buffer.put(array1);
 107     buffer.put(array2);
 108     this.bytes = buffer.array();
 109   }
 110
 111   /**
 112    * Creates a Bytes object with the contents of {@code b1} followed by the
 113    * contents of {@code b2}.
 114    */
 115   public Bytes(Bytes b1, Bytes b2) {
 116     this(b1.bytes, b2.bytes);
 117   }
 118
 119   public Bytes(byte b) {
 120     this.bytes = new byte[1];
 121     bytes[0] = b;
 122   }
 123
 124   /** Creates a Bytes object from the given string encoded as a UTF-8 byte array. */
 125   public static Bytes fromUtf8Encoding(String s) {
 126     return new Bytes(s.getBytes(UTF_8));
 127   }
 128
 129   /**
 130    * Gets the byte at the given index.
 131    *
 132    * @throws ArrayIndexOutOfBoundsException {@code index} is < 0 or >= size
 133    */
 134   public byte byteAt(final int index) {
 135     return bytes[index];
 136   }
 137
 138   /**
 139    * Gets the number of bytes.
 140    */
 141   public int size() {
 142     return bytes.length;
 143   }
 144
 145   /**
 146    * Returns the internal byte array.
 147    */
 148   public byte[] getByteArray() {
 149     return bytes;
 150   }
 151
 152   /**
 153    * Returns a new {@code Bytes} containing the given subrange of bytes [{@code from}, {@code to}).
 154    */
 155   public Bytes subsequence(int from, int to) {
 156     // Identical semantics to Arrays.copyOfRange() but implemented manually so runs on
 157     // Froyo (JDK 1.5).
 158     int newLength = to - from;
 159     if (newLength < 0) {
 160       throw new IllegalArgumentException(from + " > " + to);
 161     }
 162     byte[] copy = new byte[newLength];
 163     System.arraycopy(bytes, from, copy, 0, Math.min(bytes.length - from, newLength));
 164     return new Bytes(copy);
 165   }
 166
 167   @Override public boolean equals(final Object o) {
 168     if (o == this) {
 169       return true;
 170     }
 171
 172     if (!(o instanceof Bytes)) {
 173       return false;
 174     }
 175
 176     final Bytes other = (Bytes) o;
 177     return Arrays.equals(bytes, other.bytes);
 178   }
 179
 180   @Override public int hashCode() {
 181     int h = hash;
 182
 183     // If the hash has been not computed, go through each byte and compute it.
 184     if (h == 0) {
 185       final byte[] thisBytes = bytes;
 186       final int size = bytes.length;
 187
 188       h = size;
 189       for (int i = 0; i < size; i++) {
 190         h = h * 31 + thisBytes[i];
 191       }
 192       if (h == 0) {
 193         h = 1;
 194       }
 195
 196       hash = h;
 197     }
 198
 199     return h;
 200   }
 201
 202   /**
 203    * Returns whether these bytes are a prefix (either proper or improper) of
 204    * {@code other}.
 205    */
 206   public boolean isPrefixOf(Bytes other) {
 207     Preconditions.checkNotNull(other);
 208     if (size() > other.size()) {
 209       return false;
 210     }
 211     for (int i = 0; i < size(); ++i) {
 212       if (bytes[i] != other.bytes[i]) {
 213         return false;
 214       }
 215     }
 216     return true;
 217   }
 218
 219   /**
 220    * Returns whether these bytes are a suffix (either proper or improper) of
 221    * {@code other}.
 222    */
 223   public boolean isSuffixOf(Bytes other) {
 224     Preconditions.checkNotNull(other);
 225     int diff = other.size() - size();
 226     if (diff < 0) {
 227       return false;
 228     }
 229     for (int i = 0; i < size(); ++i) {
 230       if (bytes[i] != other.bytes[i + diff]) {
 231         return false;
 232       }
 233     }
 234     return true;
 235   }
 236
 237   @Override public int compareTo(Bytes other) {
 238     return compare(bytes, other.bytes);
 239   }
 240
 241   public static Bytes fromByteArray(byte[] bytes) {
 242     return (bytes == null) ? null : new Bytes(bytes);
 243   }
 244
 245   /**
 246    * Same specs as {@link #compareTo} except for the byte[] type. Null arrays are ordered before
 247    * non-null arrays.
 248    */
 249   public static int compare(byte[] first, byte[] second) {
 250     return compare(BYTE_ARRAY_ACCESSOR, first, second);
 251   }
 252
 253   /**
 254    * Performs lexicographic comparison of two byte sequences. Null sequences are ordered before
 255    * non-null sequences.
 256    */
 257   static <T> int compare(BytesAccessor<T> accessor, T first, T second) {
 258     // Order null arrays before non-null arrays.
 259     if (first == null) {
 260       return (second == null) ? 0 : -1;
 261     }
 262     if (second == null) {
 263       return 1;
 264     }
 265
 266     int minLength = Math.min(accessor.size(first), accessor.size(second));
 267     for (int i = 0; i < minLength; i++) {
 268
 269       if (accessor.get(first, i) != accessor.get(second, i)) {
 270         int firstByte = accessor.get(first, i) & 0xff;
 271         int secondByte = accessor.get(second, i) & 0xff;
 272         return firstByte - secondByte;
 273       }
 274     }
 275     // At this point, either both arrays are equal length or one of the arrays has ended.
 276     // * If the arrays are of equal length, they must be identical (else we would have
 277     //   returned the correct value above
 278     // * If they are not of equal length, the one with the longer length is greater.
 279     return accessor.size(first) - accessor.size(second);
 280   }
 281
 282   /**
 283    * Renders the bytes as a string in standard bigtable ascii / octal mix compatible with bt and
 284    * returns it.
 285    */
 286   public static String toString(byte[] bytes) {
 287     return toCompactString(new TextBuilder(), bytes).toString();
 288   }
 289
 290   /**
 291    * Renders the bytes as a string in standard bigtable ascii / octal mix compatible with bt and
 292    * adds it to builder.
 293    */
 294   @Override public void toCompactString(TextBuilder builder) {
 295     toCompactString(builder, bytes);
 296   }
 297
 298   /**
 299    * Renders the bytes as a string in standard bigtable ascii / octal mix compatible with bt and
 300    * adds it to builder. Returns {@code builder}.
 301    */
 302   public static TextBuilder toCompactString(TextBuilder builder, byte[] bytes) {
 303     return toCompactString(BYTE_ARRAY_ACCESSOR, builder, bytes);
 304   }
 305
 306   /**
 307    * Returns an object that lazily formats {@code bytes} when {@link Object#toString()} is called.
 308    */
 309   public static Object toLazyCompactString(byte[] bytes) {
 310     if (bytes == null || bytes.length == 0) {
 311       return "";
 312     }
 313     return LazyString.toLazyCompactString(bytes, BYTE_ARRAY_RECEIVER);
 314   }
 315
 316   /**
 317    * Renders the bytes as a string in standard bigtable ascii / octal mix compatible with bt and
 318    * adds it to builder. Borrowed from Bigtable's {@code Util$keyToString()}.
 319    * Returns {@code builder}.
 320    */
 321   static <T> TextBuilder toCompactString(BytesAccessor<T> accessor, TextBuilder builder,
 322       T bytes) {
 323     for (int i = 0; i < accessor.size(bytes); i++) {
 324       byte c = accessor.get(bytes, i);
 325       switch(c) {
 326         case '\n': builder.append('\\'); builder.append('n'); break;
 327         case '\r': builder.append('\\'); builder.append('r'); break;
 328         case '\t': builder.append('\\'); builder.append('t'); break;
 329         case '\"': builder.append('\\'); builder.append('"'); break;
 330         case '\\': builder.append('\\'); builder.append('\\'); break;
 331         default:
 332           if ((c >= 32) && (c < 127) && c != '\'') {
 333             builder.append((char) c);
 334           } else {
 335             int byteValue = c;
 336             if (c < 0) {
 337               byteValue = c + 256;
 338             }
 339             builder.append('\\');
 340             builder.append(CHAR_OCTAL_STRINGS1[byteValue]);
 341             builder.append(CHAR_OCTAL_STRINGS2[byteValue]);
 342             builder.append(CHAR_OCTAL_STRINGS3[byteValue]);
 343           }
 344       }
 345     }
 346     return builder;
 347   }
 348 }