OLD | NEW |
1 // Protocol Buffers - Google's data interchange format | 1 // Protocol Buffers - Google's data interchange format |
2 // Copyright 2008 Google Inc. All rights reserved. | 2 // Copyright 2008 Google Inc. All rights reserved. |
3 // https://developers.google.com/protocol-buffers/ | 3 // https://developers.google.com/protocol-buffers/ |
4 // | 4 // |
5 // Redistribution and use in source and binary forms, with or without | 5 // Redistribution and use in source and binary forms, with or without |
6 // modification, are permitted provided that the following conditions are | 6 // modification, are permitted provided that the following conditions are |
7 // met: | 7 // met: |
8 // | 8 // |
9 // * Redistributions of source code must retain the above copyright | 9 // * Redistributions of source code must retain the above copyright |
10 // notice, this list of conditions and the following disclaimer. | 10 // notice, this list of conditions and the following disclaimer. |
(...skipping 33 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
44 import java.nio.charset.UnsupportedCharsetException; | 44 import java.nio.charset.UnsupportedCharsetException; |
45 import java.util.ArrayList; | 45 import java.util.ArrayList; |
46 import java.util.Arrays; | 46 import java.util.Arrays; |
47 import java.util.Collection; | 47 import java.util.Collection; |
48 import java.util.Collections; | 48 import java.util.Collections; |
49 import java.util.Iterator; | 49 import java.util.Iterator; |
50 import java.util.List; | 50 import java.util.List; |
51 import java.util.NoSuchElementException; | 51 import java.util.NoSuchElementException; |
52 | 52 |
53 /** | 53 /** |
54 * Immutable sequence of bytes. Substring is supported by sharing the reference | 54 * Immutable sequence of bytes. Substring is supported by sharing the reference
to the immutable |
55 * to the immutable underlying bytes, as with {@link String}. Concatenation is | 55 * underlying bytes. Concatenation is likewise supported without copying (long s
trings) by building |
56 * likewise supported without copying (long strings) by building a tree of | 56 * a tree of pieces in {@link RopeByteString}. |
57 * pieces in {@link RopeByteString}. | 57 * |
58 * <p> | 58 * <p>Like {@link String}, the contents of a {@link ByteString} can never be obs
erved to change, not |
59 * Like {@link String}, the contents of a {@link ByteString} can never be | 59 * even in the presence of a data race or incorrect API usage in the client code
. |
60 * observed to change, not even in the presence of a data race or incorrect | |
61 * API usage in the client code. | |
62 * | 60 * |
63 * @author crazybob@google.com Bob Lee | 61 * @author crazybob@google.com Bob Lee |
64 * @author kenton@google.com Kenton Varda | 62 * @author kenton@google.com Kenton Varda |
65 * @author carlanton@google.com Carl Haverl | 63 * @author carlanton@google.com Carl Haverl |
66 * @author martinrb@google.com Martin Buchholz | 64 * @author martinrb@google.com Martin Buchholz |
67 */ | 65 */ |
68 public abstract class ByteString implements Iterable<Byte>, Serializable { | 66 public abstract class ByteString implements Iterable<Byte>, Serializable { |
69 | 67 |
70 /** | 68 /** |
71 * When two strings to be concatenated have a combined length shorter than | 69 * When two strings to be concatenated have a combined length shorter than |
72 * this, we just copy their bytes on {@link #concat(ByteString)}. | 70 * this, we just copy their bytes on {@link #concat(ByteString)}. |
73 * The trade-off is copy size versus the overhead of creating tree nodes | 71 * The trade-off is copy size versus the overhead of creating tree nodes |
74 * in {@link RopeByteString}. | 72 * in {@link RopeByteString}. |
75 */ | 73 */ |
76 static final int CONCATENATE_BY_COPY_SIZE = 128; | 74 static final int CONCATENATE_BY_COPY_SIZE = 128; |
77 | 75 |
78 /** | 76 /** |
79 * When copying an InputStream into a ByteString with .readFrom(), | 77 * When copying an InputStream into a ByteString with .readFrom(), |
80 * the chunks in the underlying rope start at 256 bytes, but double | 78 * the chunks in the underlying rope start at 256 bytes, but double |
81 * each iteration up to 8192 bytes. | 79 * each iteration up to 8192 bytes. |
82 */ | 80 */ |
83 static final int MIN_READ_FROM_CHUNK_SIZE = 0x100; // 256b | 81 static final int MIN_READ_FROM_CHUNK_SIZE = 0x100; // 256b |
84 static final int MAX_READ_FROM_CHUNK_SIZE = 0x2000; // 8k | 82 static final int MAX_READ_FROM_CHUNK_SIZE = 0x2000; // 8k |
85 | 83 |
86 /** | 84 /** |
87 * Empty {@code ByteString}. | 85 * Empty {@code ByteString}. |
88 */ | 86 */ |
89 public static final ByteString EMPTY = new LiteralByteString(Internal.EMPTY_BY
TE_ARRAY); | 87 public static final ByteString EMPTY = new LiteralByteString(Internal.EMPTY_BY
TE_ARRAY); |
90 | 88 |
91 /** | 89 /** |
92 * An interface to efficiently copy {@code byte[]}. | 90 * An interface to efficiently copy {@code byte[]}. |
93 * | 91 * |
94 * <p>One of the noticable costs of copying a byte[] into a new array using | 92 * <p>One of the noticeable costs of copying a byte[] into a new array using |
95 * {@code System.arraycopy} is nullification of a new buffer before the copy.
It has been shown | 93 * {@code System.arraycopy} is nullification of a new buffer before the copy.
It has been shown |
96 * the Hotspot VM is capable to intrisicfy {@code Arrays.copyOfRange} operatio
n to avoid this | 94 * the Hotspot VM is capable to intrisicfy {@code Arrays.copyOfRange} operatio
n to avoid this |
97 * expensive nullification and provide substantial performance gain. Unfortuna
tely this does not | 95 * expensive nullification and provide substantial performance gain. Unfortuna
tely this does not |
98 * hold on Android runtimes and could make the copy slightly slower due to add
itional code in | 96 * hold on Android runtimes and could make the copy slightly slower due to add
itional code in |
99 * the {@code Arrays.copyOfRange}. Thus we provide two different implementatio
n for array copier | 97 * the {@code Arrays.copyOfRange}. Thus we provide two different implementatio
n for array copier |
100 * for Hotspot and Android runtimes. | 98 * for Hotspot and Android runtimes. |
101 */ | 99 */ |
102 private interface ByteArrayCopier { | 100 private interface ByteArrayCopier { |
103 /** | 101 /** |
104 * Copies the specified range of the specified array into a new array | 102 * Copies the specified range of the specified array into a new array |
105 */ | 103 */ |
106 byte[] copyFrom(byte[] bytes, int offset, int size); | 104 byte[] copyFrom(byte[] bytes, int offset, int size); |
107 } | 105 } |
108 | 106 |
109 /** Implementation of {@code ByteArrayCopier} which uses {@link System#arrayco
py}. */ | 107 /** Implementation of {@code ByteArrayCopier} which uses {@link System#arrayco
py}. */ |
110 private static final class SystemByteArrayCopier implements ByteArrayCopier { | 108 private static final class SystemByteArrayCopier implements ByteArrayCopier { |
111 @Override | 109 @Override |
112 public byte[] copyFrom(byte[] bytes, int offset, int size) { | 110 public byte[] copyFrom(byte[] bytes, int offset, int size) { |
113 byte[] copy = new byte[size]; | 111 byte[] copy = new byte[size]; |
114 System.arraycopy(bytes, offset, copy, 0, size); | 112 System.arraycopy(bytes, offset, copy, 0, size); |
115 return copy; | 113 return copy; |
116 } | 114 } |
117 } | 115 } |
118 | 116 |
119 /** Implementation of {@code ByteArrayCopier} which uses {@link Arrays#copyOfR
ange}. */ | 117 /** Implementation of {@code ByteArrayCopier} which uses {@link Arrays#copyOfR
ange}. */ |
120 private static final class ArraysByteArrayCopier implements ByteArrayCopier { | 118 private static final class ArraysByteArrayCopier implements ByteArrayCopier { |
121 @Override | 119 @Override |
122 public byte[] copyFrom(byte[] bytes, int offset, int size) { | 120 public byte[] copyFrom(byte[] bytes, int offset, int size) { |
123 return Arrays.copyOfRange(bytes, offset, offset + size); | 121 return Arrays.copyOfRange(bytes, offset, offset + size); |
124 } | 122 } |
125 } | 123 } |
126 | 124 |
127 private static final ByteArrayCopier byteArrayCopier; | 125 private static final ByteArrayCopier byteArrayCopier; |
128 static { | 126 static { |
129 boolean isAndroid = true; | 127 boolean isAndroid = true; |
130 try { | 128 try { |
131 Class.forName("android.content.Context"); | 129 Class.forName("android.content.Context"); |
132 } catch (ClassNotFoundException e) { | 130 } catch (ClassNotFoundException e) { |
133 isAndroid = false; | 131 isAndroid = false; |
134 } | 132 } |
135 | 133 |
136 byteArrayCopier = isAndroid ? new SystemByteArrayCopier() : new ArraysByteAr
rayCopier(); | 134 byteArrayCopier = isAndroid ? new SystemByteArrayCopier() : new ArraysByteAr
rayCopier(); |
137 } | 135 } |
138 | 136 |
139 /** | 137 /** |
140 * Cached hash value. Intentionally accessed via a data race, which | 138 * Cached hash value. Intentionally accessed via a data race, which |
141 * is safe because of the Java Memory Model's "no out-of-thin-air values" | 139 * is safe because of the Java Memory Model's "no out-of-thin-air values" |
142 * guarantees for ints. A value of 0 implies that the hash has not been set. | 140 * guarantees for ints. A value of 0 implies that the hash has not been set. |
143 */ | 141 */ |
144 private int hash = 0; | 142 private int hash = 0; |
145 | 143 |
(...skipping 156 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
302 | 300 |
303 /** | 301 /** |
304 * Copies the given bytes into a {@code ByteString}. | 302 * Copies the given bytes into a {@code ByteString}. |
305 * | 303 * |
306 * @param bytes to copy | 304 * @param bytes to copy |
307 * @return new {@code ByteString} | 305 * @return new {@code ByteString} |
308 */ | 306 */ |
309 public static ByteString copyFrom(byte[] bytes) { | 307 public static ByteString copyFrom(byte[] bytes) { |
310 return copyFrom(bytes, 0, bytes.length); | 308 return copyFrom(bytes, 0, bytes.length); |
311 } | 309 } |
312 | 310 |
| 311 /** |
| 312 * Wraps the given bytes into a {@code ByteString}. Intended for internal only
usage. |
| 313 */ |
| 314 static ByteString wrap(ByteBuffer buffer) { |
| 315 if (buffer.hasArray()) { |
| 316 final int offset = buffer.arrayOffset(); |
| 317 return ByteString.wrap(buffer.array(), offset + buffer.position(), buffer.
remaining()); |
| 318 } else { |
| 319 return new NioByteString(buffer); |
| 320 } |
| 321 } |
| 322 |
313 /** | 323 /** |
314 * Wraps the given bytes into a {@code ByteString}. Intended for internal only | 324 * Wraps the given bytes into a {@code ByteString}. Intended for internal only |
315 * usage to force a classload of ByteString before LiteralByteString. | 325 * usage to force a classload of ByteString before LiteralByteString. |
316 */ | 326 */ |
317 static ByteString wrap(byte[] bytes) { | 327 static ByteString wrap(byte[] bytes) { |
318 // TODO(dweis): Return EMPTY when bytes are empty to reduce allocations? | 328 // TODO(dweis): Return EMPTY when bytes are empty to reduce allocations? |
319 return new LiteralByteString(bytes); | 329 return new LiteralByteString(bytes); |
320 } | 330 } |
321 | 331 |
322 /** | 332 /** |
(...skipping 72 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
395 | 405 |
396 /** | 406 /** |
397 * Completely reads the given stream's bytes into a | 407 * Completely reads the given stream's bytes into a |
398 * {@code ByteString}, blocking if necessary until all bytes are | 408 * {@code ByteString}, blocking if necessary until all bytes are |
399 * read through to the end of the stream. | 409 * read through to the end of the stream. |
400 * | 410 * |
401 * <b>Performance notes:</b> The returned {@code ByteString} is an | 411 * <b>Performance notes:</b> The returned {@code ByteString} is an |
402 * immutable tree of byte arrays ("chunks") of the stream data. The | 412 * immutable tree of byte arrays ("chunks") of the stream data. The |
403 * first chunk is small, with subsequent chunks each being double | 413 * first chunk is small, with subsequent chunks each being double |
404 * the size, up to 8K. | 414 * the size, up to 8K. |
405 * | 415 * |
406 * <p>Each byte read from the input stream will be copied twice to ensure | 416 * <p>Each byte read from the input stream will be copied twice to ensure |
407 * that the resulting ByteString is truly immutable. | 417 * that the resulting ByteString is truly immutable. |
408 * | 418 * |
409 * @param streamToDrain The source stream, which is read completely | 419 * @param streamToDrain The source stream, which is read completely |
410 * but not closed. | 420 * but not closed. |
411 * @return A new {@code ByteString} which is made up of chunks of | 421 * @return A new {@code ByteString} which is made up of chunks of |
412 * various sizes, depending on the behavior of the underlying | 422 * various sizes, depending on the behavior of the underlying |
413 * stream. | 423 * stream. |
414 * @throws IOException IOException is thrown if there is a problem | 424 * @throws IOException IOException is thrown if there is a problem |
415 * reading the underlying stream. | 425 * reading the underlying stream. |
(...skipping 130 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
546 return EMPTY; | 556 return EMPTY; |
547 } | 557 } |
548 | 558 |
549 return balancedConcat(byteStrings.iterator(), size); | 559 return balancedConcat(byteStrings.iterator(), size); |
550 } | 560 } |
551 | 561 |
552 // Internal function used by copyFrom(Iterable<ByteString>). | 562 // Internal function used by copyFrom(Iterable<ByteString>). |
553 // Create a balanced concatenation of the next "length" elements from the | 563 // Create a balanced concatenation of the next "length" elements from the |
554 // iterable. | 564 // iterable. |
555 private static ByteString balancedConcat(Iterator<ByteString> iterator, int le
ngth) { | 565 private static ByteString balancedConcat(Iterator<ByteString> iterator, int le
ngth) { |
556 assert length >= 1; | 566 if (length < 1) { |
| 567 throw new IllegalArgumentException(String.format("length (%s) must be >= 1
", length)); |
| 568 } |
557 ByteString result; | 569 ByteString result; |
558 if (length == 1) { | 570 if (length == 1) { |
559 result = iterator.next(); | 571 result = iterator.next(); |
560 } else { | 572 } else { |
561 int halfLength = length >>> 1; | 573 int halfLength = length >>> 1; |
562 ByteString left = balancedConcat(iterator, halfLength); | 574 ByteString left = balancedConcat(iterator, halfLength); |
563 ByteString right = balancedConcat(iterator, length - halfLength); | 575 ByteString right = balancedConcat(iterator, length - halfLength); |
564 result = left.concat(right); | 576 result = left.concat(right); |
565 } | 577 } |
566 return result; | 578 return result; |
(...skipping 105 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
672 * <p>This method may expose internal backing buffers of the {@link ByteString
} to the {@link | 684 * <p>This method may expose internal backing buffers of the {@link ByteString
} to the {@link |
673 * ByteOutput} in order to avoid additional copying overhead. It would be poss
ible for a malicious | 685 * ByteOutput} in order to avoid additional copying overhead. It would be poss
ible for a malicious |
674 * {@link ByteOutput} to corrupt the {@link ByteString}. Use with caution! | 686 * {@link ByteOutput} to corrupt the {@link ByteString}. Use with caution! |
675 * | 687 * |
676 * @param byteOutput the output target to receive the bytes | 688 * @param byteOutput the output target to receive the bytes |
677 * @throws IOException if an I/O error occurs | 689 * @throws IOException if an I/O error occurs |
678 * @see UnsafeByteOperations#unsafeWriteTo(ByteString, ByteOutput) | 690 * @see UnsafeByteOperations#unsafeWriteTo(ByteString, ByteOutput) |
679 */ | 691 */ |
680 abstract void writeTo(ByteOutput byteOutput) throws IOException; | 692 abstract void writeTo(ByteOutput byteOutput) throws IOException; |
681 | 693 |
| 694 |
682 /** | 695 /** |
683 * Constructs a read-only {@code java.nio.ByteBuffer} whose content | 696 * Constructs a read-only {@code java.nio.ByteBuffer} whose content |
684 * is equal to the contents of this byte string. | 697 * is equal to the contents of this byte string. |
685 * The result uses the same backing array as the byte string, if possible. | 698 * The result uses the same backing array as the byte string, if possible. |
686 * | 699 * |
687 * @return wrapped bytes | 700 * @return wrapped bytes |
688 */ | 701 */ |
689 public abstract ByteBuffer asReadOnlyByteBuffer(); | 702 public abstract ByteBuffer asReadOnlyByteBuffer(); |
690 | 703 |
691 /** | 704 /** |
(...skipping 121 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
813 @Override | 826 @Override |
814 protected final int getTreeDepth() { | 827 protected final int getTreeDepth() { |
815 return 0; | 828 return 0; |
816 } | 829 } |
817 | 830 |
818 @Override | 831 @Override |
819 protected final boolean isBalanced() { | 832 protected final boolean isBalanced() { |
820 return true; | 833 return true; |
821 } | 834 } |
822 | 835 |
| 836 |
823 /** | 837 /** |
824 * Check equality of the substring of given length of this object starting a
t | 838 * Check equality of the substring of given length of this object starting a
t |
825 * zero with another {@code ByteString} substring starting at offset. | 839 * zero with another {@code ByteString} substring starting at offset. |
826 * | 840 * |
827 * @param other what to compare a substring in | 841 * @param other what to compare a substring in |
828 * @param offset offset into other | 842 * @param offset offset into other |
829 * @param length number of bytes to compare | 843 * @param length number of bytes to compare |
830 * @return true for equality of substrings, else false. | 844 * @return true for equality of substrings, else false. |
831 */ | 845 */ |
832 abstract boolean equalsRange(ByteString other, int offset, int length); | 846 abstract boolean equalsRange(ByteString other, int offset, int length); |
(...skipping 386 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1219 throw new IndexOutOfBoundsException("End index: " + endIndex + " >= " + si
ze); | 1233 throw new IndexOutOfBoundsException("End index: " + endIndex + " >= " + si
ze); |
1220 } | 1234 } |
1221 return length; | 1235 return length; |
1222 } | 1236 } |
1223 | 1237 |
1224 @Override | 1238 @Override |
1225 public final String toString() { | 1239 public final String toString() { |
1226 return String.format("<ByteString@%s size=%d>", | 1240 return String.format("<ByteString@%s size=%d>", |
1227 Integer.toHexString(System.identityHashCode(this)), size()); | 1241 Integer.toHexString(System.identityHashCode(this)), size()); |
1228 } | 1242 } |
1229 | 1243 |
1230 /** | 1244 /** |
1231 * This class implements a {@link com.google.protobuf.ByteString} backed by a | 1245 * This class implements a {@link com.google.protobuf.ByteString} backed by a |
1232 * single array of bytes, contiguous in memory. It supports substring by | 1246 * single array of bytes, contiguous in memory. It supports substring by |
1233 * pointing to only a sub-range of the underlying byte array, meaning that a | 1247 * pointing to only a sub-range of the underlying byte array, meaning that a |
1234 * substring will reference the full byte-array of the string it's made from, | 1248 * substring will reference the full byte-array of the string it's made from, |
1235 * exactly as with {@link String}. | 1249 * exactly as with {@link String}. |
1236 * | 1250 * |
1237 * @author carlanton@google.com (Carl Haverl) | 1251 * @author carlanton@google.com (Carl Haverl) |
1238 */ | 1252 */ |
1239 // Keep this class private to avoid deadlocks in classloading across threads a
s ByteString's | 1253 // Keep this class private to avoid deadlocks in classloading across threads a
s ByteString's |
(...skipping 203 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1443 | 1457 |
1444 /** | 1458 /** |
1445 * Offset into {@code bytes[]} to use, non-zero for substrings. | 1459 * Offset into {@code bytes[]} to use, non-zero for substrings. |
1446 * | 1460 * |
1447 * @return always 0 for this class | 1461 * @return always 0 for this class |
1448 */ | 1462 */ |
1449 protected int getOffsetIntoBytes() { | 1463 protected int getOffsetIntoBytes() { |
1450 return 0; | 1464 return 0; |
1451 } | 1465 } |
1452 } | 1466 } |
1453 | 1467 |
1454 /** | 1468 /** |
1455 * This class is used to represent the substring of a {@link ByteString} over
a | 1469 * This class is used to represent the substring of a {@link ByteString} over
a |
1456 * single byte array. In terms of the public API of {@link ByteString}, you en
d | 1470 * single byte array. In terms of the public API of {@link ByteString}, you en
d |
1457 * up here by calling {@link ByteString#copyFrom(byte[])} followed by {@link | 1471 * up here by calling {@link ByteString#copyFrom(byte[])} followed by {@link |
1458 * ByteString#substring(int, int)}. | 1472 * ByteString#substring(int, int)}. |
1459 * | 1473 * |
1460 * <p>This class contains most of the overhead involved in creating a substrin
g | 1474 * <p>This class contains most of the overhead involved in creating a substrin
g |
1461 * from a {@link LiteralByteString}. The overhead involves some range-checkin
g | 1475 * from a {@link LiteralByteString}. The overhead involves some range-checkin
g |
1462 * and two extra fields. | 1476 * and two extra fields. |
1463 * | 1477 * |
(...skipping 71 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1535 Object writeReplace() { | 1549 Object writeReplace() { |
1536 return ByteString.wrap(toByteArray()); | 1550 return ByteString.wrap(toByteArray()); |
1537 } | 1551 } |
1538 | 1552 |
1539 private void readObject(@SuppressWarnings("unused") ObjectInputStream in) th
rows IOException { | 1553 private void readObject(@SuppressWarnings("unused") ObjectInputStream in) th
rows IOException { |
1540 throw new InvalidObjectException( | 1554 throw new InvalidObjectException( |
1541 "BoundedByteStream instances are not to be serialized directly"); | 1555 "BoundedByteStream instances are not to be serialized directly"); |
1542 } | 1556 } |
1543 } | 1557 } |
1544 } | 1558 } |
OLD | NEW |