| package aQute.lib.properties; |
| |
| /** |
| * Implements a gap managing text store. The gap text store relies on the |
| * assumption that consecutive changes to a document are co-located. The start |
| * of the gap is always moved to the location of the last change. |
| * <p> |
| * <strong>Performance:</strong> Typing-style changes perform in constant time |
| * unless re-allocation becomes necessary. Generally, a change that does not |
| * cause re-allocation will cause at most one |
| * {@linkplain System#arraycopy(Object, int, Object, int, int) arraycopy} |
| * operation of a length of about <var>d</var>, where <var>d</var> is the |
| * distance from the previous change. Let <var>a(x)</var> be the algorithmic |
| * performance of an <code>arraycopy</code> operation of the length |
| * <var>x</var>, then such a change then performs in <i>O(a(x))</i>, |
| * {@linkplain #get(int, int) get(int, <var>length</var>)} performs in |
| * <i>O(a(length))</i>, {@link #get(int)} in <i>O(1)</i>. |
| * <p> |
| * How frequently the array needs re-allocation is controlled by the constructor |
| * parameters. |
| * </p> |
| * <p> |
| * This class is not intended to be subclassed. |
| * </p> |
| * |
| * @see CopyOnWriteTextStore for a copy-on-write text store wrapper |
| * @noextend This class is not intended to be subclassed by clients. |
| */ |
| public class GapTextStore implements ITextStore { |
| /** |
| * The minimum gap size allocated when re-allocation occurs. |
| * |
| * @since 3.3 |
| */ |
| private final int fMinGapSize; |
| /** |
| * The maximum gap size allocated when re-allocation occurs. |
| * |
| * @since 3.3 |
| */ |
| private final int fMaxGapSize; |
| /** |
| * The multiplier to compute the array size from the content length |
| * (1 <= fSizeMultiplier <= 2). |
| * |
| * @since 3.3 |
| */ |
| private final float fSizeMultiplier; |
| |
| /** The store's content */ |
| private char[] fContent = new char[0]; |
| /** Starting index of the gap */ |
| private int fGapStart = 0; |
| /** End index of the gap */ |
| private int fGapEnd = 0; |
| /** |
| * The current high water mark. If a change would cause the gap to grow |
| * larger than this, the array is re-allocated. |
| * |
| * @since 3.3 |
| */ |
| private int fThreshold = 0; |
| |
| /** |
| * Creates a new empty text store using the specified low and high |
| * watermarks. |
| * |
| * @param lowWatermark |
| * unused - at the lower bound, the array is only resized when |
| * the content does not fit |
| * @param highWatermark |
| * if the gap is ever larger than this, it will automatically be |
| * shrunken (>= 0) |
| * @deprecated use {@link GapTextStore#GapTextStore(int, int, float)} |
| * instead |
| */ |
| public GapTextStore(int lowWatermark, int highWatermark) { |
| /* |
| * Legacy constructor. The API contract states that highWatermark is the |
| * upper bound for the gap size. Albeit this contract was not previously |
| * adhered to, it is now: The allocated gap size is fixed at half the |
| * highWatermark. Since the threshold is always twice the allocated gap |
| * size, the gap will never grow larger than highWatermark. Previously, |
| * the gap size was initialized to highWatermark, causing re-allocation |
| * if the content length shrunk right after allocation. The fixed gap |
| * size is now only half of the previous value, circumventing that |
| * problem (there was no API contract specifying the initial gap size). |
| * The previous implementation did not allow the gap size to become |
| * smaller than lowWatermark, which doesn't make any sense: that area of |
| * the gap was simply never ever used. |
| */ |
| this(highWatermark / 2, highWatermark / 2, 0f); |
| } |
| |
| /** |
| * Equivalent to {@linkplain GapTextStore#GapTextStore(int, int, float) new |
| * GapTextStore(256, 4096, 0.1f)}. |
| * |
| * @since 3.3 |
| */ |
| public GapTextStore() { |
| this(256, 4096, 0.1f); |
| } |
| |
| /** |
| * Creates an empty text store that uses re-allocation thresholds relative |
| * to the content length. Re-allocation is controlled by the |
| * <em>gap factor</em>, which is the quotient of the gap size and the array |
| * size. Re-allocation occurs if a change causes the gap factor to go |
| * outside <code>[0, maxGapFactor]</code>. When re-allocation occurs, |
| * the array is sized such that the gap factor is |
| * <code>0.5 * maxGapFactor</code>. The gap size computed in this manner is |
| * bounded by the <code>minSize</code> and <code>maxSize</code> parameters. |
| * <p> |
| * A <code>maxGapFactor</code> of <code>0</code> creates a text store that |
| * never has a gap at all (if <code>minSize</code> is 0); a |
| * <code>maxGapFactor</code> of <code>1</code> creates a text store that |
| * doubles its size with every re-allocation and that never shrinks. |
| * </p> |
| * <p> |
| * The <code>minSize</code> and <code>maxSize</code> parameters are absolute |
| * bounds to the allocated gap size. Use <code>minSize</code> to avoid |
| * frequent re-allocation for small documents. Use <code>maxSize</code> to |
| * avoid a huge gap being allocated for large documents. |
| * </p> |
| * |
| * @param minSize |
| * the minimum gap size to allocate (>= 0; use 0 for no |
| * minimum) |
| * @param maxSize |
| * the maximum gap size to allocate (>= minSize; use |
| * {@link Integer#MAX_VALUE} for no maximum) |
| * @param maxGapFactor |
| * is the maximum fraction of the array that is occupied by the |
| * gap ( |
| * <code>0 <= maxGapFactor <= 1</code>) |
| * @since 3.3 |
| */ |
| public GapTextStore(int minSize, int maxSize, float maxGapFactor) { |
| fMinGapSize = minSize; |
| fMaxGapSize = maxSize; |
| fSizeMultiplier = 1 / (1 - maxGapFactor / 2); |
| } |
| |
| /* |
| * @see org.eclipse.jface.text.ITextStore#get(int) |
| */ |
| public final char get(int offset) { |
| if (offset < fGapStart) |
| return fContent[offset]; |
| |
| return fContent[offset + gapSize()]; |
| } |
| |
| /* |
| * @see org.eclipse.jface.text.ITextStore#get(int, int) |
| */ |
| public final String get(int offset, int length) { |
| if (fGapStart <= offset) |
| return new String(fContent, offset + gapSize(), length); |
| |
| final int end = offset + length; |
| |
| if (end <= fGapStart) |
| return new String(fContent, offset, length); |
| |
| StringBuffer buf = new StringBuffer(length); |
| buf.append(fContent, offset, fGapStart - offset); |
| buf.append(fContent, fGapEnd, end - fGapStart); |
| return buf.toString(); |
| } |
| |
| /* |
| * @see org.eclipse.jface.text.ITextStore#getLength() |
| */ |
| public final int getLength() { |
| return fContent.length - gapSize(); |
| } |
| |
| /* |
| * @see org.eclipse.jface.text.ITextStore#set(java.lang.String) |
| */ |
| public final void set(String text) { |
| /* |
| * Moves the gap to the end of the content. There is no sensible |
| * prediction of where the next change will occur, but at least the next |
| * change will not trigger re-allocation. This is especially important |
| * when using the GapTextStore within a CopyOnWriteTextStore, where the |
| * GTS is only initialized right before a modification. |
| */ |
| replace(0, getLength(), text); |
| } |
| |
| /* |
| * @see org.eclipse.jface.text.ITextStore#replace(int, int, |
| * java.lang.String) |
| */ |
| public final void replace(int offset, int length, String text) { |
| if (text == null) { |
| adjustGap(offset, length, 0); |
| } else { |
| int textLength = text.length(); |
| adjustGap(offset, length, textLength); |
| if (textLength != 0) |
| text.getChars(0, textLength, fContent, offset); |
| } |
| } |
| |
| /** |
| * Moves the gap to <code>offset + add</code>, moving any content after |
| * <code>offset + remove</code> behind the gap. The gap size is kept between |
| * 0 and {@link #fThreshold}, leading to re-allocation if needed. The |
| * content between <code>offset</code> and <code>offset + add</code> is |
| * undefined after this operation. |
| * |
| * @param offset |
| * the offset at which a change happens |
| * @param remove |
| * the number of character which are removed or overwritten at |
| * <code>offset</code> |
| * @param add |
| * the number of character which are inserted or overwriting at |
| * <code>offset</code> |
| */ |
| private void adjustGap(int offset, int remove, int add) { |
| final int oldGapSize = gapSize(); |
| final int newGapSize = oldGapSize - add + remove; |
| final boolean reuseArray = 0 <= newGapSize && newGapSize <= fThreshold; |
| |
| final int newGapStart = offset + add; |
| final int newGapEnd; |
| |
| if (reuseArray) |
| newGapEnd = moveGap(offset, remove, oldGapSize, newGapSize, newGapStart); |
| else |
| newGapEnd = reallocate(offset, remove, oldGapSize, newGapSize, newGapStart); |
| |
| fGapStart = newGapStart; |
| fGapEnd = newGapEnd; |
| } |
| |
| /** |
| * Moves the gap to <code>newGapStart</code>. |
| * |
| * @param offset |
| * the change offset |
| * @param remove |
| * the number of removed / overwritten characters |
| * @param oldGapSize |
| * the old gap size |
| * @param newGapSize |
| * the gap size after the change |
| * @param newGapStart |
| * the offset in the array to move the gap to |
| * @return the new gap end |
| * @since 3.3 |
| */ |
| private int moveGap(int offset, int remove, int oldGapSize, int newGapSize, int newGapStart) { |
| /* |
| * No re-allocation necessary. The area between the change offset and |
| * gap can be copied in at most one operation. Don't copy parts that |
| * will be overwritten anyway. |
| */ |
| final int newGapEnd = newGapStart + newGapSize; |
| if (offset < fGapStart) { |
| int afterRemove = offset + remove; |
| if (afterRemove < fGapStart) { |
| final int betweenSize = fGapStart - afterRemove; |
| arrayCopy(afterRemove, fContent, newGapEnd, betweenSize); |
| } |
| // otherwise, only the gap gets enlarged |
| } else { |
| final int offsetShifted = offset + oldGapSize; |
| final int betweenSize = offsetShifted - fGapEnd; // in the typing |
| // case, |
| // betweenSize |
| // is 0 |
| arrayCopy(fGapEnd, fContent, fGapStart, betweenSize); |
| } |
| return newGapEnd; |
| } |
| |
| /** |
| * Reallocates a new array and copies the data from the previous one. |
| * |
| * @param offset |
| * the change offset |
| * @param remove |
| * the number of removed / overwritten characters |
| * @param oldGapSize |
| * the old gap size |
| * @param newGapSize |
| * the gap size after the change if no re-allocation would occur |
| * (can be negative) |
| * @param newGapStart |
| * the offset in the array to move the gap to |
| * @return the new gap end |
| * @since 3.3 |
| */ |
| private int reallocate(int offset, int remove, final int oldGapSize, int newGapSize, final int newGapStart) { |
| // the new content length (without any gap) |
| final int newLength = fContent.length - newGapSize; |
| // the new array size based on the gap factor |
| int newArraySize = (int) (newLength * fSizeMultiplier); |
| newGapSize = newArraySize - newLength; |
| |
| // bound the gap size within min/max |
| if (newGapSize < fMinGapSize) { |
| newGapSize = fMinGapSize; |
| newArraySize = newLength + newGapSize; |
| } else if (newGapSize > fMaxGapSize) { |
| newGapSize = fMaxGapSize; |
| newArraySize = newLength + newGapSize; |
| } |
| |
| // the upper threshold is always twice the gapsize |
| fThreshold = newGapSize * 2; |
| final char[] newContent = allocate(newArraySize); |
| final int newGapEnd = newGapStart + newGapSize; |
| |
| /* |
| * Re-allocation: The old content can be copied in at most 3 operations |
| * to the newly allocated array. Either one of change offset and the gap |
| * may come first. - unchanged area before the change offset / gap - |
| * area between the change offset and the gap (either one may be first) |
| * - rest area after the change offset / after the gap |
| */ |
| if (offset < fGapStart) { |
| // change comes before gap |
| arrayCopy(0, newContent, 0, offset); |
| int afterRemove = offset + remove; |
| if (afterRemove < fGapStart) { |
| // removal is completely before the gap |
| final int betweenSize = fGapStart - afterRemove; |
| arrayCopy(afterRemove, newContent, newGapEnd, betweenSize); |
| final int restSize = fContent.length - fGapEnd; |
| arrayCopy(fGapEnd, newContent, newGapEnd + betweenSize, restSize); |
| } else { |
| // removal encompasses the gap |
| afterRemove += oldGapSize; |
| final int restSize = fContent.length - afterRemove; |
| arrayCopy(afterRemove, newContent, newGapEnd, restSize); |
| } |
| } else { |
| // gap comes before change |
| arrayCopy(0, newContent, 0, fGapStart); |
| final int offsetShifted = offset + oldGapSize; |
| final int betweenSize = offsetShifted - fGapEnd; |
| arrayCopy(fGapEnd, newContent, fGapStart, betweenSize); |
| final int afterRemove = offsetShifted + remove; |
| final int restSize = fContent.length - afterRemove; |
| arrayCopy(afterRemove, newContent, newGapEnd, restSize); |
| } |
| |
| fContent = newContent; |
| return newGapEnd; |
| } |
| |
| /** |
| * Allocates a new <code>char[size]</code>. |
| * |
| * @param size |
| * the length of the new array. |
| * @return a newly allocated char array |
| * @since 3.3 |
| */ |
| private char[] allocate(int size) { |
| return new char[size]; |
| } |
| |
| /* |
| * Executes System.arraycopy if length != 0. A length < 0 cannot happen -> |
| * don't hide coding errors by checking for negative lengths. |
| * @since 3.3 |
| */ |
| private void arrayCopy(int srcPos, char[] dest, int destPos, int length) { |
| if (length != 0) |
| System.arraycopy(fContent, srcPos, dest, destPos, length); |
| } |
| |
| /** |
| * Returns the gap size. |
| * |
| * @return the gap size |
| * @since 3.3 |
| */ |
| private int gapSize() { |
| return fGapEnd - fGapStart; |
| } |
| |
| /** |
| * Returns a copy of the content of this text store. For internal use only. |
| * |
| * @return a copy of the content of this text store |
| */ |
| protected String getContentAsString() { |
| return new String(fContent); |
| } |
| |
| /** |
| * Returns the start index of the gap managed by this text store. For |
| * internal use only. |
| * |
| * @return the start index of the gap managed by this text store |
| */ |
| protected int getGapStartIndex() { |
| return fGapStart; |
| } |
| |
| /** |
| * Returns the end index of the gap managed by this text store. For internal |
| * use only. |
| * |
| * @return the end index of the gap managed by this text store |
| */ |
| protected int getGapEndIndex() { |
| return fGapEnd; |
| } |
| } |