001: /*******************************************************************************
002: * Copyright (c) 2000, 2006 IBM Corporation and others.
003: * All rights reserved. This program and the accompanying materials
004: * are made available under the terms of the Eclipse Public License v1.0
005: * which accompanies this distribution, and is available at
006: * http://www.eclipse.org/legal/epl-v10.html
007: *
008: * Contributors:
009: * IBM Corporation - initial API and implementation
010: *******************************************************************************/package org.eclipse.jface.text;
011:
012: import org.eclipse.core.runtime.Assert;
013:
014: /**
015: * Implements a gap managing text store. The gap text store relies on the assumption that
016: * consecutive changes to a document are co-located. The start of the gap is always moved to the
017: * location of the last change.
018: * <p>
019: * <strong>Performance:</strong> Typing-style changes perform in constant time unless re-allocation
020: * becomes necessary. Generally, a change that does not cause re-allocation will cause at most one
021: * {@linkplain System#arraycopy(Object, int, Object, int, int) arraycopy} operation of a length of
022: * about <var>d</var>, where <var>d</var> is the distance from the previous change. Let <var>a(x)</var>
023: * be the algorithmic performance of an <code>arraycopy</code> operation of the length <var>x</var>,
024: * then such a change then performs in <i>O(a(x))</i>,
025: * {@linkplain #get(int, int) get(int, <var>length</var>)} performs in <i>O(a(length))</i>,
026: * {@link #get(int)} in <i>O(1)</i>.
027: * <p>
028: * How frequently the array needs re-allocation is controlled by the constructor parameters.
029: * </p>
030: * <p>
031: * This class is not intended to be subclassed.
032: * </p>
033: *
034: * @see CopyOnWriteTextStore for a copy-on-write text store wrapper
035: */
036: public class GapTextStore implements ITextStore {
037: /**
038: * The minimum gap size allocated when re-allocation occurs.
039: * @since 3.3
040: */
041: private final int fMinGapSize;
042: /**
043: * The maximum gap size allocated when re-allocation occurs.
044: * @since 3.3
045: */
046: private final int fMaxGapSize;
047: /**
048: * The multiplier to compute the array size from the content length
049: * (1 <= fSizeMultiplier <= 2).
050: *
051: * @since 3.3
052: */
053: private final float fSizeMultiplier;
054:
055: /** The store's content */
056: private char[] fContent = new char[0];
057: /** Starting index of the gap */
058: private int fGapStart = 0;
059: /** End index of the gap */
060: private int fGapEnd = 0;
061: /**
062: * The current high water mark. If a change would cause the gap to grow larger than this, the
063: * array is re-allocated.
064: * @since 3.3
065: */
066: private int fThreshold = 0;
067:
068: /**
069: * Creates a new empty text store using the specified low and high watermarks.
070: *
071: * @param lowWatermark unused - at the lower bound, the array is only resized when the content
072: * does not fit
073: * @param highWatermark if the gap is ever larger than this, it will automatically be shrunken
074: * (>= 0)
075: * @deprecated use {@link GapTextStore#GapTextStore(int, int, float)} instead
076: */
077: public GapTextStore(int lowWatermark, int highWatermark) {
078: /*
079: * Legacy constructor. The API contract states that highWatermark is the upper bound for the
080: * gap size. Albeit this contract was not previously adhered to, it is now: The allocated
081: * gap size is fixed at half the highWatermark. Since the threshold is always twice the
082: * allocated gap size, the gap will never grow larger than highWatermark. Previously, the
083: * gap size was initialized to highWatermark, causing re-allocation if the content length
084: * shrunk right after allocation. The fixed gap size is now only half of the previous value,
085: * circumventing that problem (there was no API contract specifying the initial gap size).
086: *
087: * The previous implementation did not allow the gap size to become smaller than
088: * lowWatermark, which doesn't make any sense: that area of the gap was simply never ever
089: * used.
090: */
091: this (highWatermark / 2, highWatermark / 2, 0f);
092: }
093:
094: /**
095: * Equivalent to
096: * {@linkplain GapTextStore#GapTextStore(int, int, float) new GapTextStore(256, 4096, 0.1f)}.
097: *
098: * @since 3.3
099: */
100: public GapTextStore() {
101: this (256, 4096, 0.1f);
102: }
103:
104: /**
105: * Creates an empty text store that uses re-allocation thresholds relative to the content
106: * length. Re-allocation is controlled by the <em>gap factor</em>, which is the quotient of
107: * the gap size and the array size. Re-allocation occurs if a change causes the gap factor to go
108: * outside <code>[0, maxGapFactor]</code>. When re-allocation occurs, the array is sized
109: * such that the gap factor is <code>0.5 * maxGapFactor</code>. The gap size computed in this
110: * manner is bounded by the <code>minSize</code> and <code>maxSize</code> parameters.
111: * <p>
112: * A <code>maxGapFactor</code> of <code>0</code> creates a text store that never has a gap
113: * at all (if <code>minSize</code> is 0); a <code>maxGapFactor</code> of <code>1</code>
114: * creates a text store that doubles its size with every re-allocation and that never shrinks.
115: * </p>
116: * <p>
117: * The <code>minSize</code> and <code>maxSize</code> parameters are absolute bounds to the
118: * allocated gap size. Use <code>minSize</code> to avoid frequent re-allocation for small
119: * documents. Use <code>maxSize</code> to avoid a huge gap being allocated for large
120: * documents.
121: * </p>
122: *
123: * @param minSize the minimum gap size to allocate (>= 0; use 0 for no minimum)
124: * @param maxSize the maximum gap size to allocate (>= minSize; use
125: * {@link Integer#MAX_VALUE} for no maximum)
126: * @param maxGapFactor is the maximum fraction of the array that is occupied by the gap (<code>0 <= maxGapFactor <= 1</code>)
127: * @since 3.3
128: */
129: public GapTextStore(int minSize, int maxSize, float maxGapFactor) {
130: Assert.isLegal(0f <= maxGapFactor && maxGapFactor <= 1f);
131: Assert.isLegal(0 <= minSize && minSize <= maxSize);
132: fMinGapSize = minSize;
133: fMaxGapSize = maxSize;
134: fSizeMultiplier = 1 / (1 - maxGapFactor / 2);
135: }
136:
137: /*
138: * @see org.eclipse.jface.text.ITextStore#get(int)
139: */
140: public final char get(int offset) {
141: if (offset < fGapStart)
142: return fContent[offset];
143:
144: return fContent[offset + gapSize()];
145: }
146:
147: /*
148: * @see org.eclipse.jface.text.ITextStore#get(int, int)
149: */
150: public final String get(int offset, int length) {
151: if (fGapStart <= offset)
152: return new String(fContent, offset + gapSize(), length);
153:
154: final int end = offset + length;
155:
156: if (end <= fGapStart)
157: return new String(fContent, offset, length);
158:
159: StringBuffer buf = new StringBuffer(length);
160: buf.append(fContent, offset, fGapStart - offset);
161: buf.append(fContent, fGapEnd, end - fGapStart);
162: return buf.toString();
163: }
164:
165: /*
166: * @see org.eclipse.jface.text.ITextStore#getLength()
167: */
168: public final int getLength() {
169: return fContent.length - gapSize();
170: }
171:
172: /*
173: * @see org.eclipse.jface.text.ITextStore#set(java.lang.String)
174: */
175: public final void set(String text) {
176: /*
177: * Moves the gap to the end of the content. There is no sensible prediction of where the
178: * next change will occur, but at least the next change will not trigger re-allocation. This
179: * is especially important when using the GapTextStore within a CopyOnWriteTextStore, where
180: * the GTS is only initialized right before a modification.
181: */
182: replace(0, getLength(), text);
183: }
184:
185: /*
186: * @see org.eclipse.jface.text.ITextStore#replace(int, int, java.lang.String)
187: */
188: public final void replace(int offset, int length, String text) {
189: if (text == null) {
190: adjustGap(offset, length, 0);
191: } else {
192: int textLength = text.length();
193: adjustGap(offset, length, textLength);
194: if (textLength != 0)
195: text.getChars(0, textLength, fContent, offset);
196: }
197: }
198:
199: /**
200: * Moves the gap to <code>offset + add</code>, moving any content after
201: * <code>offset + remove</code> behind the gap. The gap size is kept between 0 and
202: * {@link #fThreshold}, leading to re-allocation if needed. The content between
203: * <code>offset</code> and <code>offset + add</code> is undefined after this operation.
204: *
205: * @param offset the offset at which a change happens
206: * @param remove the number of character which are removed or overwritten at <code>offset</code>
207: * @param add the number of character which are inserted or overwriting at <code>offset</code>
208: */
209: private void adjustGap(int offset, int remove, int add) {
210: final int oldGapSize = gapSize();
211: final int newGapSize = oldGapSize - add + remove;
212: final boolean reuseArray = 0 <= newGapSize
213: && newGapSize <= fThreshold;
214:
215: final int newGapStart = offset + add;
216: final int newGapEnd;
217:
218: if (reuseArray)
219: newGapEnd = moveGap(offset, remove, oldGapSize, newGapSize,
220: newGapStart);
221: else
222: newGapEnd = reallocate(offset, remove, oldGapSize,
223: newGapSize, newGapStart);
224:
225: fGapStart = newGapStart;
226: fGapEnd = newGapEnd;
227: }
228:
229: /**
230: * Moves the gap to <code>newGapStart</code>.
231: *
232: * @param offset the change offset
233: * @param remove the number of removed / overwritten characters
234: * @param oldGapSize the old gap size
235: * @param newGapSize the gap size after the change
236: * @param newGapStart the offset in the array to move the gap to
237: * @return the new gap end
238: * @since 3.3
239: */
240: private int moveGap(int offset, int remove, int oldGapSize,
241: int newGapSize, int newGapStart) {
242: /*
243: * No re-allocation necessary. The area between the change offset and gap can be copied
244: * in at most one operation. Don't copy parts that will be overwritten anyway.
245: */
246: final int newGapEnd = newGapStart + newGapSize;
247: if (offset < fGapStart) {
248: int afterRemove = offset + remove;
249: if (afterRemove < fGapStart) {
250: final int betweenSize = fGapStart - afterRemove;
251: arrayCopy(afterRemove, fContent, newGapEnd, betweenSize);
252: }
253: // otherwise, only the gap gets enlarged
254: } else {
255: final int offsetShifted = offset + oldGapSize;
256: final int betweenSize = offsetShifted - fGapEnd; // in the typing case, betweenSize is 0
257: arrayCopy(fGapEnd, fContent, fGapStart, betweenSize);
258: }
259: return newGapEnd;
260: }
261:
262: /**
263: * Reallocates a new array and copies the data from the previous one.
264: *
265: * @param offset the change offset
266: * @param remove the number of removed / overwritten characters
267: * @param oldGapSize the old gap size
268: * @param newGapSize the gap size after the change if no re-allocation would occur (can be negative)
269: * @param newGapStart the offset in the array to move the gap to
270: * @return the new gap end
271: * @since 3.3
272: */
273: private int reallocate(int offset, int remove,
274: final int oldGapSize, int newGapSize, final int newGapStart) {
275: // the new content length (without any gap)
276: final int newLength = fContent.length - newGapSize;
277: // the new array size based on the gap factor
278: int newArraySize = (int) (newLength * fSizeMultiplier);
279: newGapSize = newArraySize - newLength;
280:
281: // bound the gap size within min/max
282: if (newGapSize < fMinGapSize) {
283: newGapSize = fMinGapSize;
284: newArraySize = newLength + newGapSize;
285: } else if (newGapSize > fMaxGapSize) {
286: newGapSize = fMaxGapSize;
287: newArraySize = newLength + newGapSize;
288: }
289:
290: // the upper threshold is always twice the gapsize
291: fThreshold = newGapSize * 2;
292: final char[] newContent = allocate(newArraySize);
293: final int newGapEnd = newGapStart + newGapSize;
294:
295: /*
296: * Re-allocation: The old content can be copied in at most 3 operations to the newly allocated
297: * array. Either one of change offset and the gap may come first.
298: * - unchanged area before the change offset / gap
299: * - area between the change offset and the gap (either one may be first)
300: * - rest area after the change offset / after the gap
301: */
302: if (offset < fGapStart) {
303: // change comes before gap
304: arrayCopy(0, newContent, 0, offset);
305: int afterRemove = offset + remove;
306: if (afterRemove < fGapStart) {
307: // removal is completely before the gap
308: final int betweenSize = fGapStart - afterRemove;
309: arrayCopy(afterRemove, newContent, newGapEnd,
310: betweenSize);
311: final int restSize = fContent.length - fGapEnd;
312: arrayCopy(fGapEnd, newContent, newGapEnd + betweenSize,
313: restSize);
314: } else {
315: // removal encompasses the gap
316: afterRemove += oldGapSize;
317: final int restSize = fContent.length - afterRemove;
318: arrayCopy(afterRemove, newContent, newGapEnd, restSize);
319: }
320: } else {
321: // gap comes before change
322: arrayCopy(0, newContent, 0, fGapStart);
323: final int offsetShifted = offset + oldGapSize;
324: final int betweenSize = offsetShifted - fGapEnd;
325: arrayCopy(fGapEnd, newContent, fGapStart, betweenSize);
326: final int afterRemove = offsetShifted + remove;
327: final int restSize = fContent.length - afterRemove;
328: arrayCopy(afterRemove, newContent, newGapEnd, restSize);
329: }
330:
331: fContent = newContent;
332: return newGapEnd;
333: }
334:
335: /**
336: * Allocates a new <code>char[size]</code>.
337: *
338: * @param size the length of the new array.
339: * @return a newly allocated char array
340: * @since 3.3
341: */
342: private char[] allocate(int size) {
343: return new char[size];
344: }
345:
346: /*
347: * Executes System.arraycopy if length != 0. A length < 0 cannot happen -> don't hide coding
348: * errors by checking for negative lengths.
349: * @since 3.3
350: */
351: private void arrayCopy(int srcPos, char[] dest, int destPos,
352: int length) {
353: if (length != 0)
354: System.arraycopy(fContent, srcPos, dest, destPos, length);
355: }
356:
357: /**
358: * Returns the gap size.
359: *
360: * @return the gap size
361: * @since 3.3
362: */
363: private int gapSize() {
364: return fGapEnd - fGapStart;
365: }
366:
367: /**
368: * Returns a copy of the content of this text store.
369: * For internal use only.
370: *
371: * @return a copy of the content of this text store
372: */
373: protected String getContentAsString() {
374: return new String(fContent);
375: }
376:
377: /**
378: * Returns the start index of the gap managed by this text store.
379: * For internal use only.
380: *
381: * @return the start index of the gap managed by this text store
382: */
383: protected int getGapStartIndex() {
384: return fGapStart;
385: }
386:
387: /**
388: * Returns the end index of the gap managed by this text store.
389: * For internal use only.
390: *
391: * @return the end index of the gap managed by this text store
392: */
393: protected int getGapEndIndex() {
394: return fGapEnd;
395: }
396: }
|