Note that Stree and DTM used a single FastStringBuffer as a string pool, by recording start and length indices within this single buffer. This minimizes heap overhead, but of course requires more work when retrieving the data.
FastStringBuffer operates as a "chunked buffer". Doing so reduces the need to recopy existing information when an append exceeds the space available; we just allocate another chunk and flow across to it. (The array of chunks may need to grow, admittedly, but that's a much smaller object.) Some excess recopying may arise when we extract Strings which cross chunk boundaries; larger chunks make that less frequent.
The size values are parameterized, to allow tuning this code. In theory, Result Tree Fragments might want to be tuned differently from the main document's text.
%REVIEW% An experiment in self-tuning is included in the code (using nested FastStringBuffers to achieve variation in chunk sizes), but this implementation has proven to be problematic when data may be being copied from the FSB into itself. We should either re-architect that to make this safe (if possible) or remove that code and clean up for performance/maintainability reasons.
| Modifier and Type | Field and Description |
|---|---|
| private static final int | CARRY_WS
Manifest constant: Carry trailing whitespace of one chunk as leading whitespace of the next chunk. |
| pack-priv static final boolean | |
| pack-priv static final int | |
| pack-priv char[][] | m_array
Field m_array holds the string buffer's text contents, using an array-of-arrays. |
| pack-priv int | m_chunkBits
Field m_chunkBits sets our chunking strategy, by saying how many bits of index can be used within a single chunk before flowing over to the next chunk. |
| pack-priv int | m_chunkMask
Field m_chunkMask is m_chunkSize-1 -- in other words, m_chunkBits worth of low-order '1' bits, useful for shift-and-mask addressing within the chunks. |
| pack-priv int | m_chunkSize
Field m_chunkSize establishes the maximum size of one chunk of the array as 2**chunkbits characters. |
| pack-priv int | m_firstFree
Field m_firstFree is an index into m_array[m_lastChunk][], pointing to the first character in the Chunked Array which is not part of the FastStringBuffer's current content. |
| pack-priv FastStringBuffer | m_innerFSB
Field m_innerFSB, when non-null, is a FastStringBuffer whose total length equals m_chunkSize, and which replaces m_array[0]. |
| pack-priv int | m_lastChunk
Field m_lastChunk is an index into m_array[], pointing to the last chunk of the Chunked Array currently in use. |
| pack-priv int | m_maxChunkBits
Field m_maxChunkBits affects our chunk-growth strategy, by saying what the largest permissible chunk size is in this particular FastStringBuffer hierarchy. |
| pack-priv int | m_rebundleBits
Field m_rechunkBits affects our chunk-growth strategy, by saying how many chunks should be allocated at one size before we encapsulate them into the first chunk of the next size up. |
| pack-priv static final char[] | |
| public static final int | SUPPRESS_BOTH
Manifest constant: Suppress both leading and trailing whitespace. |
| public static final int | SUPPRESS_LEADING_WS
Manifest constant: Suppress leading whitespace. |
| public static final int | SUPPRESS_TRAILING_WS
Manifest constant: Suppress trailing whitespace. |
| Access | Constructor and Description |
|---|---|
| public | FastStringBuffer(int
Length in characters of the initial allocation
of a chunk, expressed in log-base-2. (That is, 10 means allocate 1024
characters.) Later chunks will use larger allocation units, to trade off
allocation speed of large document against storage efficiency of small
ones. initChunkBits, int Number of character-offset bits that should be used for
addressing within a chunk. Maximum length of a chunk is 2^chunkBits
characters. maxChunkBits, int Number of character-offset bits that addressing should
advance before we attempt to take a step from initChunkBits to maxChunkBits rebundleBits)Construct a FastStringBuffer, with allocation policy as per parameters. |
| public | FastStringBuffer(int initChunkBits, int maxChunkBits)
Construct a FastStringBuffer, using a default rebundleBits value. |
| public | FastStringBuffer(int initChunkBits)
Construct a FastStringBuffer, using default maxChunkBits and rebundleBits values. |
| public | |
| private |
| Modifier and Type | Method and Description |
|---|---|
| public final void | append(char
character to be appended. value)Append a single character onto the FastStringBuffer, growing the storage if necessary. |
| public final void | |
| public final void | append(StringBuffer
StringBuffer whose contents are to be appended. value)Append the contents of a StringBuffer onto the FastStringBuffer, growing the storage if necessary. |
| public final void | append(char[]
character array from which data is to be copied chars, int offset in chars of first character to be copied,
zero-based. start, int number of characters to be copied length)Append part of the contents of a Character Array onto the FastStringBuffer, growing the storage if necessary. |
| public final void | append(FastStringBuffer
FastStringBuffer whose contents are
to be appended. value)Append the contents of another FastStringBuffer onto this FastStringBuffer, growing the storage if necessary. |
| public char | Returns: A character from the requested position.character position requested. pos)Get a single character from the string buffer. |
| private void | getChars(int
index of the first character in the string
to copy. srcBegin, int index after the last character in the string
to copy. srcEnd, char[] the destination array. dst, int the start offset in the destination array. dstBegin)Copies characters from this string into the destination character array. |
| protected String | |
| public String | getString(int
Offset of first character in the range. start, int Number of characters to send. length)Returns: a new String object initialized from the specified range of characters. |
| pack-priv StringBuffer | getString(StringBuffer
StringBuffer to be appended to sb, int Offset of first character in the range. start, int Number of characters to send. length)Returns: sb with the requested text appended to it |
| pack-priv StringBuffer | Returns: the contents of the FastStringBuffer as a standard Java string.Internal support for toString() and getString(). |
| public boolean | isWhitespace(int
Offset of first character in the range. start, int Number of characters to send. length)Returns: true if the specified range of characters are all whitespace, as defined by XMLCharacterRecognizer. |
| public final int | Returns: the number of characters in the FastStringBuffer's content.Get the length of the list. |
| public final void | reset()
Discard the content of the FastStringBuffer, and most of the memory that was allocated by it, restoring the initial state. |
| public int | Returns: normalization status to apply to next chunk (because we may have been called recursively to process an inner FSB):
SAX ContentHandler object to receive the event. ch, int Offset of first character in the range. start, int Number of characters to send. length)Sends the specified range of characters as one or more SAX characters() events, normalizing the characters according to XSLT rules. |
| pack-priv static int | Returns: normalization status, as in the edgeTreatmentFlags parameter:
The characters from the XML document. ch, int The start position in the array. start, int The number of characters to read from the array. length, ContentHandler SAX ContentHandler object to receive the event. handler, int How leading/trailing spaces should be handled.
This is a bitfield contining two flags, bitwise-ORed together:
edgeTreatmentFlags)
Internal method to directly normalize and dispatch the character array. |
| public static void | sendNormalizedSAXcharacters(char[]
The characters from the XML document. ch, int The start position in the array. start, int The number of characters to read from the array. length, ContentHandler SAX ContentHandler object to receive the event. handler)Directly normalize and dispatch the character array. |
| public void | sendSAXcharacters(ContentHandler
SAX ContentHandler object to receive the event. ch, int Offset of first character in the range. start, int Number of characters to send. length)Sends the specified range of characters as one or more SAX characters() events. |
| public void | sendSAXComment(LexicalHandler
SAX LexicalHandler object to receive the event. ch, int Offset of first character in the range. start, int Number of characters to send. length)Sends the specified range of characters as sax Comment. |
| public final void | setLength(int
New length. If l<0 or l>=getLength(), this operation will
not report an error but future operations will almost certainly fail. l)Directly set how much of the FastStringBuffer's storage is to be considered part of its content. |
| private final void | |
| public final int | Returns: the number of characters in the FastStringBuffer's content.Get the length of the list. |
| public final String | Returns: the contents of the FastStringBuffer as a standard Java string.Overrides java. Note that this operation has been somewhat deoptimized by the shift to a chunked array, as there is no factory method to produce a String object directly from an array of arrays and hence a double copy is needed. |
| CARRY_WS | back to summary |
|---|---|
| private static final int CARRY_WS Manifest constant: Carry trailing whitespace of one chunk as leading whitespace of the next chunk. Used internally; I don't see any reason to make it public right now. | |
| DEBUG_FORCE_FIXED_CHUNKSIZE | back to summary |
|---|---|
| pack-priv static final boolean DEBUG_FORCE_FIXED_CHUNKSIZE | |
| DEBUG_FORCE_INIT_BITS | back to summary |
|---|---|
| pack-priv static final int DEBUG_FORCE_INIT_BITS / | |
| m_array | back to summary |
|---|---|
| pack-priv char[][] m_array Field m_array holds the string buffer's text contents, using an array-of-arrays. Note that this array, and the arrays it contains, may be reallocated when necessary in order to allow the buffer to grow; references to them should be considered to be invalidated after any append. However, the only time these arrays are directly exposed is in the sendSAXcharacters call. | |
| m_chunkBits | back to summary |
|---|---|
| pack-priv int m_chunkBits Field m_chunkBits sets our chunking strategy, by saying how many bits of index can be used within a single chunk before flowing over to the next chunk. For example, if m_chunkbits is set to 15, each chunk can contain up to 2^15 (32K) characters | |
| m_chunkMask | back to summary |
|---|---|
| pack-priv int m_chunkMask Field m_chunkMask is m_chunkSize-1 -- in other words, m_chunkBits worth of low-order '1' bits, useful for shift-and-mask addressing within the chunks. | |
| m_chunkSize | back to summary |
|---|---|
| pack-priv int m_chunkSize Field m_chunkSize establishes the maximum size of one chunk of the array as 2**chunkbits characters. (Which may also be the minimum size if we aren't tuning for storage) | |
| m_firstFree | back to summary | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| pack-priv int m_firstFree Field m_firstFree is an index into m_array[m_lastChunk][], pointing to
the first character in the Chunked Array which is not part of the
FastStringBuffer's current content. Since m_array[][] is zero-based,
the length of that content can be calculated as
(m_lastChunk< Field m_innerFSB, when non-null, is a FastStringBuffer whose total
length equals m_chunkSize, and which replaces m_array[0]. This allows
building a hierarchy of FastStringBuffers, where early appends use
a smaller chunkSize (for less wasted memory overhead) but later
ones use a larger chunkSize (for less heap activity overhead).
Field m_lastChunk is an index into m_array[], pointing to the last
chunk of the Chunked Array currently in use. Note that additional
chunks may actually be allocated, eg if the FastStringBuffer had
previously been truncated or if someone issued an ensureSpace request.
The insertion point for append operations is addressed by the combination
of m_lastChunk and m_firstFree.
Field m_maxChunkBits affects our chunk-growth strategy, by saying what
the largest permissible chunk size is in this particular FastStringBuffer
hierarchy.
Field m_rechunkBits affects our chunk-growth strategy, by saying how
many chunks should be allocated at one size before we encapsulate them
into the first chunk of the next size up. For example, if m_rechunkBits
is set to 3, then after 8 chunks at a given size we will rebundle
them as the first element of a FastStringBuffer using a chunk size
8 times larger (chunkBits shifted left three bits).
Manifest constant: Suppress both leading and trailing whitespace.
This should be used when normalize-to-SAX is called for a complete string.
(I'm not wild about the name of this one. Ideas welcome.)
Manifest constant: Suppress leading whitespace.
This should be used when normalize-to-SAX is called for the first chunk of a
multi-chunk output, or one following unsuppressed whitespace in a previous
chunk.
Manifest constant: Suppress trailing whitespace.
This should be used when normalize-to-SAX is called for the last chunk of a
multi-chunk output; it may have to be or'ed with SUPPRESS_LEADING_WS.
Construct a FastStringBuffer, with allocation policy as per parameters.
For coding convenience, I've expressed both allocation sizes in terms of
a number of bits. That's needed for the final size of a chunk,
to permit fast and efficient shift-and-mask addressing. It's less critical
for the inital size, and may be reconsidered.
An alternative would be to accept integer sizes and round to powers of two;
that really doesn't seem to buy us much, if anything.
Length in characters of the initial allocation
of a chunk, expressed in log-base-2. (That is, 10 means allocate 1024
characters.) Later chunks will use larger allocation units, to trade off
allocation speed of large document against storage efficiency of small
ones.
Number of character-offset bits that should be used for
addressing within a chunk. Maximum length of a chunk is 2^chunkBits
characters.
Number of character-offset bits that addressing should
advance before we attempt to take a step from initChunkBits to maxChunkBits
Construct a FastStringBuffer, using a default rebundleBits value.
NEEDSDOC @param initChunkBits
NEEDSDOC @param maxChunkBits
Construct a FastStringBuffer, using default maxChunkBits and
rebundleBits values. Issue
Should this call assert initial size, or fixed size?
Now configured as initial, with a default for fixed.
NEEDSDOC @param initChunkBits
Construct a FastStringBuffer, using a default allocation policy.
Encapsulation c'tor. After this is called, the source FastStringBuffer
will be reset to use the new object as its m_innerFSB, and will have
had its chunk size reset appropriately. IT SHOULD NEVER BE CALLED
EXCEPT WHEN source.length()==1<<(source.m_chunkBits+source.m_rebundleBits)
NEEDSDOC @param source
Append a single character onto the FastStringBuffer, growing the
storage if necessary.
NOTE THAT after calling append(), previously obtained
references to m_array[][] may no longer be valid....
though in fact they should be in this instance.
character to be appended.
Append the contents of a String onto the FastStringBuffer,
growing the storage if necessary.
NOTE THAT after calling append(), previously obtained
references to m_array[] may no longer be valid.
String whose contents are to be appended.
Append the contents of a StringBuffer onto the FastStringBuffer,
growing the storage if necessary.
NOTE THAT after calling append(), previously obtained
references to m_array[] may no longer be valid.
StringBuffer whose contents are to be appended.
Append part of the contents of a Character Array onto the
FastStringBuffer, growing the storage if necessary.
NOTE THAT after calling append(), previously obtained
references to m_array[] may no longer be valid.
character array from which data is to be copied
offset in chars of first character to be copied,
zero-based.
number of characters to be copied
Append the contents of another FastStringBuffer onto
this FastStringBuffer, growing the storage if necessary.
NOTE THAT after calling append(), previously obtained
references to m_array[] may no longer be valid.
FastStringBuffer whose contents are
to be appended.
Get a single character from the string buffer.
character position requested.
A character from the requested position.
Copies characters from this string into the destination character
array.
index of the first character in the string
to copy.
index after the last character in the string
to copy.
the destination array.
the start offset in the destination array.
Offset of first character in the range.
Number of characters to send.
a new String object initialized from the specified range of
characters.
StringBuffer to be appended to
Offset of first character in the range.
Number of characters to send.
sb with the requested text appended to it
Internal support for toString() and getString().
PLEASE NOTE SIGNATURE CHANGE from earlier versions; it now appends into
and returns a StringBuffer supplied by the caller. This simplifies
m_innerFSB support.
Note that this operation has been somewhat deoptimized by the shift to a
chunked array, as there is no factory method to produce a String object
directly from an array of arrays and hence a double copy is needed.
By presetting length we hope to minimize the heap overhead of building
the intermediate StringBuffer.
(It really is a pity that Java didn't design String as a final subclass
of MutableString, rather than having StringBuffer be a separate hierarchy.
We'd avoid a lot of double-buffering.)
the contents of the FastStringBuffer as a standard Java string.
Offset of first character in the range.
Number of characters to send.
true if the specified range of characters are all whitespace,
as defined by XMLCharacterRecognizer.
CURRENTLY DOES NOT CHECK FOR OUT-OF-RANGE.
Get the length of the list. Synonym for size().
the number of characters in the FastStringBuffer's content.
Discard the content of the FastStringBuffer, and most of the memory
that was allocated by it, restoring the initial state. Note that this
may eventually be different from setLength(0), which see.
Sends the specified range of characters as one or more SAX characters()
events, normalizing the characters according to XSLT rules.
SAX ContentHandler object to receive the event.
Offset of first character in the range.
Number of characters to send.
normalization status to apply to next chunk (because we may
have been called recursively to process an inner FSB):
Internal method to directly normalize and dispatch the character array.
This version is aware of the fact that it may be called several times
in succession if the data is made up of multiple "chunks", and thus
must actively manage the handling of leading and trailing whitespace.
Note
The recursion is due to the possible recursion of inner FSBs.
The characters from the XML document.
The start position in the array.
The number of characters to read from the array.
SAX ContentHandler object to receive the event.
How leading/trailing spaces should be handled.
This is a bitfield contining two flags, bitwise-ORed together:
normalization status, as in the edgeTreatmentFlags parameter:
Directly normalize and dispatch the character array.
The characters from the XML document.
The start position in the array.
The number of characters to read from the array.
SAX ContentHandler object to receive the event.
Sends the specified range of characters as one or more SAX characters()
events.
Note that the buffer reference passed to the ContentHandler may be
invalidated if the FastStringBuffer is edited; it's the user's
responsibility to manage access to the FastStringBuffer to prevent this
problem from arising.
Note too that there is no promise that the output will be sent as a
single call. As is always true in SAX, one logical string may be split
across multiple blocks of memory and hence delivered as several
successive events.
SAX ContentHandler object to receive the event.
Offset of first character in the range.
Number of characters to send.
Sends the specified range of characters as sax Comment.
Note that, unlike sendSAXcharacters, this has to be done as a single
call to LexicalHandler#comment.
SAX LexicalHandler object to receive the event.
Offset of first character in the range.
Number of characters to send.
Directly set how much of the FastStringBuffer's storage is to be
considered part of its content. This is a fast but hazardous
operation. It is not protected against negative values, or values
greater than the amount of storage currently available... and even
if additional storage does exist, its contents are unpredictable.
The only safe use for our setLength() is to truncate the FastStringBuffer
to a shorter string.
New length. If l<0 or l>=getLength(), this operation will
not report an error but future operations will almost certainly fail.
Subroutine for the public setLength() method. Deals with the fact
that truncation may require restoring one of the innerFSBs
NEEDSDOC @param l
NEEDSDOC @param rootFSB
Get the length of the list. Synonym for length().
the number of characters in the FastStringBuffer's content.
Overrides java. Note that this operation has been somewhat deoptimized by the shift to a
chunked array, as there is no factory method to produce a String object
directly from an array of arrays and hence a double copy is needed.
By using ensureCapacity we hope to minimize the heap overhead of building
the intermediate StringBuffer.
(It really is a pity that Java didn't design String as a final subclass
of MutableString, rather than having StringBuffer be a separate hierarchy.
We'd avoid a lot of double-buffering.)
the contents of the FastStringBuffer as a standard Java string.
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||