Top Description Inners Fields Constructors Methods
com.google.protobuf

pack-priv final Class RopeByteString

extends ByteString
Class Inheritance
Imports
java.io.ByteArrayInputStream, .IOException, .InputStream, .InvalidObjectException, .ObjectInputStream, .OutputStream, java.nio.ByteBuffer, java.nio.charset.Charset, java.util.ArrayDeque, .ArrayList, .Arrays, .Iterator, .List, .NoSuchElementException
Class to represent ByteStrings formed by concatenation of other ByteStrings, without copying the data in the pieces. The concatenation is represented as a tree whose leaf nodes are each a com.google.protobuf.ByteString.LeafByteString.

Most of the operation here is inspired by the now-famous paper BAP95 Ropes: an Alternative to Strings hans-j. boehm, russ atkinson and michael plass

The algorithms described in the paper have been implemented for character strings in com.google.common.string.Rope and in the c++ class cord.cc.

Fundamentally the Rope algorithm represents the collection of pieces as a binary tree. BAP95 uses a Fibonacci bound relating depth to a minimum sequence length, sequences that are too short relative to their depth cause a tree rebalance. More precisely, a tree of depth d is "balanced" in the terminology of BAP95 if its length is at least F(d+2), where F(n) is the n-the Fibonacci number. Thus for depths 0, 1, 2, 3, 4, 5,... we have minimum lengths 1, 2, 3, 5, 8, 13,...

Author
[email protected] (Carl Haverl)

Nested and Inner Type Summary

Modifier and TypeClass and Description
private static class
RopeByteString.Balancer

This class implements the balancing algorithm of BAP95.

private static class
RopeByteString.PieceIterator

This class is a continuable tree traversal, which keeps the state information which would exist on the stack in a recursive traversal instead on a stack of "Bread Crumbs".

private class
RopeByteString.RopeInputStream

This class is the RopeByteString equivalent for ByteArrayInputStream.

Field Summary

Modifier and TypeField and Description
private final ByteString
left

private final int
leftLength

private static final int[]
minLengthByDepth

BAP95.

private final ByteString
right

private static final long
serialVersionUID

private final int
totalLength

private final int
treeDepth

Inherited from com.google.protobuf.ByteString:
CONCATENATE_BY_COPY_SIZEEMPTYMAX_READ_FROM_CHUNK_SIZEMIN_READ_FROM_CHUNK_SIZE

Constructor Summary

AccessConstructor and Description
private
RopeByteString(ByteString
string on the left of this node, should have size() > 0
left, ByteString
string on the right of this node, should have size() > 0
right)

Create a new RopeByteString, which can be thought of as a new tree node, by recording references to the two given strings.

Method Summary

Modifier and TypeMethod and Description
public ByteBuffer
asReadOnlyByteBuffer()

Implements abstract com.google.protobuf.ByteString.asReadOnlyByteBuffer.

Constructs a read-only java.nio.ByteBuffer whose content is equal to the contents of this byte string.
public List<ByteBuffer>
asReadOnlyByteBufferList()

Implements abstract com.google.protobuf.ByteString.asReadOnlyByteBufferList.

Constructs a list of read-only java.nio.ByteBuffer objects such that the concatenation of their contents is equal to the contents of this byte string.
public byte

Returns:

the value
byteAt(int
index of byte
index)

Implements abstract com.google.protobuf.ByteString.byteAt.

Gets the byte at the given index.
pack-priv static ByteString

Returns:

concatenation representing the same sequence as the given strings
concatenate(ByteString
string on the left
left, ByteString
string on the right
right)

Concatenate the given strings while performing various optimizations to slow the growth rate of tree depth and tree node count.

private static ByteString

Returns:

string formed by copying data bytes
concatenateBytes(ByteString
string on the left
left, ByteString
string on the right
right)

Concatenates two strings by copying data values.

public void
copyTo(ByteBuffer
ByteBuffer to copy into.
target)

Implements abstract com.google.protobuf.ByteString.copyTo.

Copies bytes into a ByteBuffer.
protected void
copyToInternal(byte[] target, int sourceOffset, int targetOffset, int numberToCopy)

Implements abstract com.google.protobuf.ByteString.copyToInternal.

Internal (package private) implementation of copyTo(byte[], int, int, int).
public boolean
equals(Object
the reference object with which to compare.
other)

Implements abstract com.google.protobuf.ByteString.equals.

Indicates whether some other object is "equal to" this one.
private boolean

Returns:

true if the values of this string equals the value of the given one
equalsFragments(ByteString
string of the same length as this one
other)

Determines if this string is equal to another of the same length by iterating over the leaf nodes.

protected int
getTreeDepth()

Implements abstract com.google.protobuf.ByteString.getTreeDepth.

Return the depth of the tree representing this ByteString, if any, whose root is this node.
pack-priv byte
internalByteAt(int
index of byte
index)

Implements abstract com.google.protobuf.ByteString.internalByteAt.

Gets the byte at the given index, assumes bounds checking has already been performed.
protected boolean

Returns:

true if the tree is balanced
isBalanced()

Implements abstract com.google.protobuf.ByteString.isBalanced.

Determines if the tree is balanced according to BAP95, which means the tree is flat-enough with respect to the bounds.
public boolean
isValidUtf8()

Implements abstract com.google.protobuf.ByteString.isValidUtf8.

Tells whether this ByteString represents a well-formed UTF-8 byte sequence, such that the original bytes can be converted to a String object and then round tripped back to bytes without loss.
public ByteString.ByteIterator
iterator()

Overrides com.google.protobuf.ByteString.iterator.

Implements java.lang.Iterable.iterator.

Return a ByteString.ByteIterator over the bytes in the ByteString.
public CodedInputStream
newCodedInput()

Implements abstract com.google.protobuf.ByteString.newCodedInput.

Creates a CodedInputStream which can be used to read the bytes.
public InputStream
newInput()

Implements abstract com.google.protobuf.ByteString.newInput.

Creates an InputStream which can be used to read the bytes.
pack-priv static RopeByteString

Returns:

an unsafe instance for testing only
newInstanceForTest(ByteString
string on the left of this node
left, ByteString
string on the right of this node
right)

Create a new RopeByteString for testing only while bypassing all the defenses of concatenate(ByteString, ByteString).

protected int
partialHash(int
starting hash value
h, int
offset into this value to start looking at data values
offset, int
number of data values to include in the hash computation
length)

Implements abstract com.google.protobuf.ByteString.partialHash.

Compute the hash across the value bytes starting with the given hash, and return the result.
protected int
partialIsValidUtf8(int
either 0 (if this is the initial decoding operation) or the value returned from a call to a partial decoding method for the previous bytes
state, int
offset of the first byte to check
offset, int
number of bytes to check
length)

Implements abstract com.google.protobuf.ByteString.partialIsValidUtf8.

Tells whether the given byte sequence is a well-formed, malformed, or incomplete UTF-8 byte sequence.
private void
readObject(ObjectInputStream in)

public int
size()

Implements abstract com.google.protobuf.ByteString.size.

Gets the number of bytes.
public ByteString

Returns:

substring leaf node or tree
substring(int
start at this index
beginIndex, int
the last character is the one before this index
endIndex)

Implements abstract com.google.protobuf.ByteString.substring.

Takes a substring of this one.
protected String
toStringInternal(Charset
encode using this charset
charset)

Implements abstract com.google.protobuf.ByteString.toStringInternal.

Constructs a new String by decoding the bytes using the specified charset.
pack-priv Object
writeReplace()

public void
writeTo(OutputStream
the output stream to which to write the data.
outputStream)

Implements abstract com.google.protobuf.ByteString.writeTo.

Writes a copy of the contents of this byte string to the specified output stream argument.
pack-priv void
writeTo(ByteOutput
the output target to receive the bytes
output)

Implements abstract com.google.protobuf.ByteString.writeTo.

Writes this ByteString to the provided ByteOutput.
pack-priv void
writeToInternal(OutputStream out, int sourceOffset, int numberToWrite)

Implements abstract com.google.protobuf.ByteString.writeToInternal.

Internal version of writeTo(OutputStream, int, int) that assumes all error checking has already been done.
Inherited from com.google.protobuf.ByteString:
checkIndexcheckRangeconcatcopyFromcopyFromcopyFromcopyFromcopyFromcopyFromcopyFromcopyFromUtf8copyTocopyToendsWithhashCodeisEmptynewCodedBuildernewOutputnewOutputpeekCachedHashCodereadFromreadFromreadFromstartsWithsubstringtoByteArraytoStringtoStringtoStringtoStringUtf8unsignedLexicographicalComparatorwrapwrapwrapwriteTo