GapTextStore


1   /*******************************************************************************
2    * Copyright (c) 2000, 2006 IBM Corporation and others.
3    * All rights reserved. This program and the accompanying materials
4    * are made available under the terms of the Eclipse Public License v1.0
5    * which accompanies this distribution, and is available at
6    * http://www.eclipse.org/legal/epl-v10.html
7    *
8    * Contributors:
9    *     IBM Corporation - initial API and implementation
10   *******************************************************************************/
11  package org.eclipse.jface.text;
12  
13  import org.eclipse.core.runtime.Assert;
14  
15  
16  /**
17   * Implements a gap managing text store. The gap text store relies on the assumption that
18   * consecutive changes to a document are co-located. The start of the gap is always moved to the
19   * location of the last change.
20   * <p>
21   * <strong>Performance:</strong> Typing-style changes perform in constant time unless re-allocation
22   * becomes necessary. Generally, a change that does not cause re-allocation will cause at most one
23   * {@linkplain System#arraycopy(Object, int, Object, int, int) arraycopy} operation of a length of
24   * about <var>d</var>, where <var>d</var> is the distance from the previous change. Let <var>a(x)</var>
25   * be the algorithmic performance of an <code>arraycopy</code> operation of the length <var>x</var>,
26   * then such a change then performs in <i>O(a(x))</i>,
27   * {@linkplain #get(int, int) get(int, <var>length</var>)} performs in <i>O(a(length))</i>,
28   * {@link #get(int)} in <i>O(1)</i>.
29   * <p>
30   * How frequently the array needs re-allocation is controlled by the constructor parameters.
31   * </p>
32   * <p>
33   * This class is not intended to be subclassed.
34   * </p>
35   * 
36   * @see CopyOnWriteTextStore for a copy-on-write text store wrapper
37   */
38  public class GapTextStore implements ITextStore {
39      /**
40       * The minimum gap size allocated when re-allocation occurs.
41       * @since 3.3
42       */
43      private final int fMinGapSize;
44      /**
45       * The maximum gap size allocated when re-allocation occurs.
46       * @since 3.3
47       */
48      private final int fMaxGapSize;
49      /**
50       * The multiplier to compute the array size from the content length
51       * (1&nbsp;&lt;=&nbsp;fSizeMultiplier&nbsp;&lt;=&nbsp;2).
52       * 
53       * @since 3.3
54       */
55      private final float fSizeMultiplier;
56  
57      /** The store's content */
58      private char[] fContent= new char[0];
59      /** Starting index of the gap */
60      private int fGapStart= 0;
61      /** End index of the gap */
62      private int fGapEnd= 0;
63      /**
64       * The current high water mark. If a change would cause the gap to grow larger than this, the
65       * array is re-allocated.
66       * @since 3.3
67       */
68      private int fThreshold= 0;
69  
70      /**
71       * Creates a new empty text store using the specified low and high watermarks.
72       * 
73       * @param lowWatermark unused - at the lower bound, the array is only resized when the content
74       *        does not fit
75       * @param highWatermark if the gap is ever larger than this, it will automatically be shrunken
76       *        (&gt;=&nbsp;0)
77       * @deprecated use {@link GapTextStore#GapTextStore(int, int, float)} instead
78       */
79      public GapTextStore(int lowWatermark, int highWatermark) {
80          /*
81           * Legacy constructor. The API contract states that highWatermark is the upper bound for the
82           * gap size. Albeit this contract was not previously adhered to, it is now: The allocated
83           * gap size is fixed at half the highWatermark. Since the threshold is always twice the
84           * allocated gap size, the gap will never grow larger than highWatermark. Previously, the
85           * gap size was initialized to highWatermark, causing re-allocation if the content length
86           * shrunk right after allocation. The fixed gap size is now only half of the previous value,
87           * circumventing that problem (there was no API contract specifying the initial gap size).
88           *
89           * The previous implementation did not allow the gap size to become smaller than
90           * lowWatermark, which doesn't make any sense: that area of the gap was simply never ever
91           * used.
92           */
93          this(highWatermark / 2, highWatermark / 2, 0f);
94      }
95      
96      /**
97       * Equivalent to
98       * {@linkplain GapTextStore#GapTextStore(int, int, float) new GapTextStore(256, 4096, 0.1f)}.
99       * 
100      * @since 3.3
101      */
102     public GapTextStore() {
103         this(256, 4096, 0.1f);
104     }
105 
106     /**
107      * Creates an empty text store that uses re-allocation thresholds relative to the content
108      * length. Re-allocation is controlled by the <em>gap factor</em>, which is the quotient of
109      * the gap size and the array size. Re-allocation occurs if a change causes the gap factor to go
110      * outside <code>[0,&nbsp;maxGapFactor]</code>. When re-allocation occurs, the array is sized
111      * such that the gap factor is <code>0.5 * maxGapFactor</code>. The gap size computed in this
112      * manner is bounded by the <code>minSize</code> and <code>maxSize</code> parameters.
113      * <p>
114      * A <code>maxGapFactor</code> of <code>0</code> creates a text store that never has a gap
115      * at all (if <code>minSize</code> is 0); a <code>maxGapFactor</code> of <code>1</code>
116      * creates a text store that doubles its size with every re-allocation and that never shrinks.
117      * </p>
118      * <p>
119      * The <code>minSize</code> and <code>maxSize</code> parameters are absolute bounds to the
120      * allocated gap size. Use <code>minSize</code> to avoid frequent re-allocation for small
121      * documents. Use <code>maxSize</code> to avoid a huge gap being allocated for large
122      * documents.
123      * </p>
124      * 
125      * @param minSize the minimum gap size to allocate (&gt;=&nbsp;0; use 0 for no minimum)
126      * @param maxSize the maximum gap size to allocate (&gt;=&nbsp;minSize; use
127      *        {@link Integer#MAX_VALUE} for no maximum)
128      * @param maxGapFactor is the maximum fraction of the array that is occupied by the gap (<code>0&nbsp;&lt;=&nbsp;maxGapFactor&nbsp;&lt;=&nbsp;1</code>)
129      * @since 3.3
130      */
131     public GapTextStore(int minSize, int maxSize, float maxGapFactor) {
132         Assert.isLegal(0f <= maxGapFactor && maxGapFactor <= 1f);
133         Assert.isLegal(0 <= minSize && minSize <= maxSize);
134         fMinGapSize= minSize;
135         fMaxGapSize= maxSize;
136         fSizeMultiplier= 1 / (1 - maxGapFactor / 2);
137     }
138 
139     /*
140      * @see org.eclipse.jface.text.ITextStore#get(int)
141      */
142     public final char get(int offset) {
143         if (offset < fGapStart)
144             return fContent[offset];
145 
146         return fContent[offset + gapSize()];
147     }
148 
149     /*
150      * @see org.eclipse.jface.text.ITextStore#get(int, int)
151      */
152     public final String   get(int offset, int length) {
153         if (fGapStart <= offset)
154             return new String  (fContent, offset + gapSize() , length);
155 
156         final int end= offset + length;
157 
158         if (end <= fGapStart)
159             return new String  (fContent, offset, length);
160 
161         StringBuffer   buf= new StringBuffer  (length);
162         buf.append(fContent, offset, fGapStart - offset);
163         buf.append(fContent, fGapEnd, end - fGapStart);
164         return buf.toString();
165     }
166 
167     /*
168      * @see org.eclipse.jface.text.ITextStore#getLength()
169      */
170     public final int getLength() {
171         return fContent.length - gapSize();
172     }
173 
174     /*
175      * @see org.eclipse.jface.text.ITextStore#set(java.lang.String)
176      */
177     public final void set(String   text) {
178         /*
179          * Moves the gap to the end of the content. There is no sensible prediction of where the
180          * next change will occur, but at least the next change will not trigger re-allocation. This
181          * is especially important when using the GapTextStore within a CopyOnWriteTextStore, where
182          * the GTS is only initialized right before a modification.
183          */
184         replace(0, getLength(), text);
185     }
186 
187     /*
188      * @see org.eclipse.jface.text.ITextStore#replace(int, int, java.lang.String)
189      */
190     public final void replace(int offset, int length, String   text) {
191         if (text == null) {
192             adjustGap(offset, length, 0);
193         } else {
194             int textLength= text.length();
195             adjustGap(offset, length, textLength);
196             if (textLength != 0)
197                 text.getChars(0, textLength, fContent, offset);
198         }
199     }
200 
201     /**
202      * Moves the gap to <code>offset + add</code>, moving any content after
203      * <code>offset + remove</code> behind the gap. The gap size is kept between 0 and
204      * {@link #fThreshold}, leading to re-allocation if needed. The content between
205      * <code>offset</code> and <code>offset + add</code> is undefined after this operation.
206      * 
207      * @param offset the offset at which a change happens
208      * @param remove the number of character which are removed or overwritten at <code>offset</code>
209      * @param add the number of character which are inserted or overwriting at <code>offset</code>
210      */
211     private void adjustGap(int offset, int remove, int add) {
212         final int oldGapSize= gapSize();
213         final int newGapSize= oldGapSize - add + remove;
214         final boolean reuseArray= 0 <= newGapSize && newGapSize <= fThreshold;
215 
216         final int newGapStart= offset + add;
217         final int newGapEnd;
218 
219         if (reuseArray)
220             newGapEnd= moveGap(offset, remove, oldGapSize, newGapSize, newGapStart);
221         else
222             newGapEnd= reallocate(offset, remove, oldGapSize, newGapSize, newGapStart);
223 
224         fGapStart= newGapStart;
225         fGapEnd= newGapEnd;
226     }
227 
228     /**
229      * Moves the gap to <code>newGapStart</code>.
230      * 
231      * @param offset the change offset
232      * @param remove the number of removed / overwritten characters
233      * @param oldGapSize the old gap size
234      * @param newGapSize the gap size after the change
235      * @param newGapStart the offset in the array to move the gap to
236      * @return the new gap end
237      * @since 3.3
238      */
239     private int moveGap(int offset, int remove, int oldGapSize, int newGapSize, int newGapStart) {
240         /*
241          * No re-allocation necessary. The area between the change offset and gap can be copied
242          * in at most one operation. Don't copy parts that will be overwritten anyway.
243          */
244         final int newGapEnd= newGapStart + newGapSize;
245         if (offset < fGapStart) {
246             int afterRemove= offset + remove;
247             if (afterRemove < fGapStart) {
248                 final int betweenSize= fGapStart - afterRemove;
249                 arrayCopy(afterRemove, fContent, newGapEnd, betweenSize);
250             }
251             // otherwise, only the gap gets enlarged
252         } else {
253             final int offsetShifted= offset + oldGapSize;
254             final int betweenSize= offsetShifted - fGapEnd; // in the typing case, betweenSize is 0
255             arrayCopy(fGapEnd, fContent, fGapStart, betweenSize);
256         }
257         return newGapEnd;
258     }
259 
260     /**
261      * Reallocates a new array and copies the data from the previous one.
262      * 
263      * @param offset the change offset
264      * @param remove the number of removed / overwritten characters
265      * @param oldGapSize the old gap size
266      * @param newGapSize the gap size after the change if no re-allocation would occur (can be negative)
267      * @param newGapStart the offset in the array to move the gap to
268      * @return the new gap end
269      * @since 3.3
270      */
271     private int reallocate(int offset, int remove, final int oldGapSize, int newGapSize, final int newGapStart) {
272         // the new content length (without any gap)
273         final int newLength= fContent.length - newGapSize;
274         // the new array size based on the gap factor
275         int newArraySize= (int) (newLength * fSizeMultiplier);
276         newGapSize= newArraySize - newLength;
277 
278         // bound the gap size within min/max
279         if (newGapSize < fMinGapSize) {
280             newGapSize= fMinGapSize;
281             newArraySize= newLength + newGapSize;
282         } else if (newGapSize > fMaxGapSize) {
283             newGapSize= fMaxGapSize;
284             newArraySize= newLength + newGapSize;
285         }
286 
287         // the upper threshold is always twice the gapsize
288         fThreshold= newGapSize * 2;
289         final char[] newContent= allocate(newArraySize);
290         final int newGapEnd= newGapStart + newGapSize;
291 
292         /*
293          * Re-allocation: The old content can be copied in at most 3 operations to the newly allocated
294          * array. Either one of change offset and the gap may come first.
295          * - unchanged area before the change offset / gap
296          * - area between the change offset and the gap (either one may be first)
297          * - rest area after the change offset / after the gap
298          */
299         if (offset < fGapStart) {
300             // change comes before gap
301             arrayCopy(0, newContent, 0, offset);
302             int afterRemove= offset + remove;
303             if (afterRemove < fGapStart) {
304                 // removal is completely before the gap
305                 final int betweenSize= fGapStart - afterRemove;
306                 arrayCopy(afterRemove, newContent, newGapEnd, betweenSize);
307                 final int restSize= fContent.length - fGapEnd;
308                 arrayCopy(fGapEnd, newContent, newGapEnd + betweenSize, restSize);
309             } else {
310                 // removal encompasses the gap
311                 afterRemove += oldGapSize;
312                 final int restSize= fContent.length - afterRemove;
313                 arrayCopy(afterRemove, newContent, newGapEnd, restSize);
314             }
315         } else {
316             // gap comes before change
317             arrayCopy(0, newContent, 0, fGapStart);
318             final int offsetShifted= offset + oldGapSize;
319             final int betweenSize= offsetShifted - fGapEnd;
320             arrayCopy(fGapEnd, newContent, fGapStart, betweenSize);
321             final int afterRemove= offsetShifted + remove;
322             final int restSize= fContent.length - afterRemove;
323             arrayCopy(afterRemove, newContent, newGapEnd, restSize);
324         }
325 
326         fContent= newContent;
327         return newGapEnd;
328     }
329 
330     /**
331      * Allocates a new <code>char[size]</code>.
332      * 
333      * @param size the length of the new array.
334      * @return a newly allocated char array
335      * @since 3.3
336      */
337     private char[] allocate(int size) {
338         return new char[size];
339     }
340 
341     /*
342      * Executes System.arraycopy if length != 0. A length < 0 cannot happen -> don't hide coding
343      * errors by checking for negative lengths.
344      * @since 3.3
345      */
346     private void arrayCopy(int srcPos, char[] dest, int destPos, int length) {
347         if (length != 0)
348             System.arraycopy(fContent, srcPos, dest, destPos, length);
349     }
350 
351     /**
352      * Returns the gap size.
353      * 
354      * @return the gap size
355      * @since 3.3
356      */
357     private int gapSize() {
358         return fGapEnd - fGapStart;
359     }
360 
361     /**
362      * Returns a copy of the content of this text store.
363      * For internal use only.
364      *
365      * @return a copy of the content of this text store
366      */
367     protected String   getContentAsString() {
368         return new String  (fContent);
369     }
370 
371     /**
372      * Returns the start index of the gap managed by this text store.
373      * For internal use only.
374      *
375      * @return the start index of the gap managed by this text store
376      */
377     protected int getGapStartIndex() {
378         return fGapStart;
379     }
380 
381     /**
382      * Returns the end index of the gap managed by this text store.
383      * For internal use only.
384      *
385      * @return the end index of the gap managed by this text store
386      */
387     protected int getGapEndIndex() {
388         return fGapEnd;
389     }
390 }
391
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags