diff options
Diffstat (limited to 'libjava/classpath/javax/swing/text/GapContent.java')
| -rw-r--r-- | libjava/classpath/javax/swing/text/GapContent.java | 469 |
1 files changed, 255 insertions, 214 deletions
diff --git a/libjava/classpath/javax/swing/text/GapContent.java b/libjava/classpath/javax/swing/text/GapContent.java index 219accb..1780d7d 100644 --- a/libjava/classpath/javax/swing/text/GapContent.java +++ b/libjava/classpath/javax/swing/text/GapContent.java @@ -39,13 +39,10 @@ exception statement from your version. */ package javax.swing.text; import java.io.Serializable; -import java.lang.ref.WeakReference; -import java.util.ArrayList; -import java.util.Collections; -import java.util.Comparator; import java.util.Iterator; -import java.util.ListIterator; +import java.util.Set; import java.util.Vector; +import java.util.WeakHashMap; import javax.swing.undo.AbstractUndoableEdit; import javax.swing.undo.CannotRedoException; @@ -60,8 +57,6 @@ import javax.swing.undo.UndoableEdit; * minimal (simple array access). The array only has to be shifted around when * the insertion point moves (then the gap also moves and one array copy is * necessary) or when the gap is filled up and the buffer has to be enlarged. - * - * TODO: Implement UndoableEdit support stuff */ public class GapContent implements AbstractDocument.Content, Serializable @@ -71,11 +66,14 @@ public class GapContent * A {@link Position} implementation for <code>GapContent</code>. */ private class GapContentPosition - implements Position, Comparable + implements Position { - /** The index within the buffer array. */ - int mark; + /** + * The index to the positionMarks array entry, which in turn holds the + * mark into the buffer array. + */ + int index; /** * Creates a new GapContentPosition object. @@ -84,33 +82,20 @@ public class GapContent */ GapContentPosition(int mark) { - this.mark = mark; - } - - /** - * Comparable interface implementation. This is used to store all - * positions in an ordered fashion. - * - * @param o the object to be compared to this - * - * @return a negative integer if this is less than <code>o</code>, zero - * if both are equal or a positive integer if this is greater than - * <code>o</code> - * - * @throws ClassCastException if <code>o</code> is not a - * GapContentPosition or Integer object - */ - public int compareTo(Object o) - { - if (o instanceof Integer) + // Try to find the mark in the positionMarks array, and store the index + // to it. + synchronized (GapContent.this) { - int otherMark = ((Integer) o).intValue(); - return mark - otherMark; - } - else - { - GapContentPosition other = (GapContentPosition) o; - return mark - other.mark; + int i = binarySearch(positionMarks, mark, numMarks); + if (i >= 0) // mark found + { + index = i; + } + else + { + index = -i - 1; + insertMark(index, mark); + } } } @@ -121,14 +106,19 @@ public class GapContent */ public int getOffset() { - // Check precondition. - assert mark <= gapStart || mark >= gapEnd : "mark: " + mark - + ", gapStart: " + gapStart - + ", gapEnd: " + gapEnd; - if (mark <= gapStart) - return mark; - else - return mark - (gapEnd - gapStart); + synchronized (GapContent.this) + { + // Fetch the actual mark. + int mark = positionMarks[index]; + // Check precondition. + assert mark <= gapStart || mark >= gapEnd : "mark: " + mark + + ", gapStart: " + gapStart + + ", gapEnd: " + gapEnd; + int res = mark; + if (mark > gapStart) + res -= (gapEnd - gapStart); + return res; + } } } @@ -209,40 +199,6 @@ public class GapContent } - /** - * Compares WeakReference objects in a List by comparing the referenced - * objects instead. - * - * @author Roman Kennke (kennke@aicas.com) - */ - private class WeakPositionComparator - implements Comparator - { - - /** - * Compares two objects of type WeakReference. The objects are compared - * using the referenced objects compareTo() method. - */ - public int compare(Object o1, Object o2) - { - // Unwrap references. - if (o1 instanceof WeakReference) - o1 = ((WeakReference) o1).get(); - if (o2 instanceof WeakReference) - o2 = ((WeakReference) o2).get(); - - GapContentPosition p1 = (GapContentPosition) o1; - GapContentPosition p2 = (GapContentPosition) o2; - - int retVal; - if (p1 == null || p2 == null) - retVal = -1; - else - retVal = p1.compareTo(p2); - return retVal; - } - } - /** The serialization UID (compatible with JDK1.5). */ private static final long serialVersionUID = -6226052713477823730L; @@ -267,12 +223,26 @@ public class GapContent */ int gapEnd; + // FIXME: We might want to track GC'ed GapContentPositions and remove their + // corresponding marks, or alternativly, perform some regular cleanup of + // the positionMarks array. + + /** + * Holds the marks for positions. These marks are referenced by the + * GapContentPosition instances by an index into this array. + */ + int[] positionMarks; + /** - * The positions generated by this GapContent. They are kept in an ordered - * fashion, so they can be looked up easily. The value objects will be - * WeakReference objects that in turn hold GapContentPosition objects. + * The number of elements in the positionMarks array. The positionMarks array + * might be bigger than the actual number of elements. */ - private ArrayList positions; + int numMarks; + + /** + * (Weakly) Stores the GapContentPosition instances. + */ + WeakHashMap positions; /** * Creates a new GapContent object. @@ -294,7 +264,9 @@ public class GapContent gapStart = 1; gapEnd = size; buffer[0] = '\n'; - positions = new ArrayList(); + positions = new WeakHashMap(); + positionMarks = new int[10]; + numMarks = 0; } /** @@ -483,26 +455,30 @@ public class GapContent */ public Position createPosition(final int offset) throws BadLocationException { - if (offset < 0 || offset > length()) - throw new BadLocationException("The offset was out of the bounds of this" - + " buffer", offset); - - clearPositionReferences(); - - // We store the actual array index in the GapContentPosition. The real - // offset is then calculated in the GapContentPosition. - int mark = offset; - if (offset >= gapStart) - mark += gapEnd - gapStart; - GapContentPosition pos = new GapContentPosition(mark); - WeakReference r = new WeakReference(pos); - - // Add this into our list in a sorted fashion. - int index = Collections.binarySearch(positions, r, - new WeakPositionComparator()); - if (index < 0) - index = -(index + 1); - positions.add(index, r); + // We try to find a GapContentPosition at the specified offset and return + // that. Otherwise we must create a new one. + GapContentPosition pos = null; + Set positionSet = positions.keySet(); + for (Iterator i = positionSet.iterator(); i.hasNext();) + { + GapContentPosition p = (GapContentPosition) i.next(); + if (p.getOffset() == offset) + { + pos = p; + break; + } + } + + // If none was found, then create and return a new one. + if (pos == null) + { + int mark = offset; + if (mark >= gapStart) + mark += (gapEnd - gapStart); + pos = new GapContentPosition(mark); + positions.put(pos, null); + } + return pos; } @@ -542,7 +518,6 @@ public class GapContent { if (newGapStart == gapStart) return; - int newGapEnd = newGapStart + gapEnd - gapStart; if (newGapStart < gapStart) { @@ -583,7 +558,7 @@ public class GapContent assert newGapStart < gapStart : "The new gap start must be less than the " + "old gap start."; - setPositionsInRange(newGapStart, gapStart - newGapStart, gapStart); + setPositionsInRange(newGapStart, gapStart, false); gapStart = newGapStart; } @@ -602,7 +577,7 @@ public class GapContent assert newGapEnd > gapEnd : "The new gap end must be greater than the " + "old gap end."; - setPositionsInRange(gapEnd, newGapEnd - gapEnd, newGapEnd); + setPositionsInRange(gapEnd, newGapEnd, false); gapEnd = newGapEnd; } @@ -688,85 +663,79 @@ public class GapContent else res.clear(); - int endOffset = offset + length; - - int index1 = Collections.binarySearch(positions, - new GapContentPosition(offset), - new WeakPositionComparator()); - if (index1 < 0) - index1 = -(index1 + 1); - - // Search the first index with the specified offset. The binarySearch does - // not necessarily find the first one. - while (index1 > 0) - { - WeakReference r = (WeakReference) positions.get(index1 - 1); - GapContentPosition p = (GapContentPosition) r.get(); - if (p != null && p.mark == offset || p == null) - index1--; - else - break; - } + int endOffs = offset + length; - for (ListIterator i = positions.listIterator(index1); i.hasNext();) + Set positionSet = positions.keySet(); + for (Iterator i = positionSet.iterator(); i.hasNext();) { - WeakReference r = (WeakReference) i.next(); - GapContentPosition p = (GapContentPosition) r.get(); - if (p == null) - continue; - - if (p.mark > endOffset) - break; - if (p.mark >= offset && p.mark <= endOffset) + GapContentPosition p = (GapContentPosition) i.next(); + int offs = p.getOffset(); + if (offs >= offset && offs < endOffs) res.add(p); } + return res; } /** - * Sets the mark of all <code>Position</code>s that are in the range - * specified by <code>offset</code> and </code>length</code> within - * the buffer array to <code>value</code> + * Crunches all positions in the specified range to either the start or + * end of that interval. The interval boundaries are meant to be inclusive + * [start, end]. * - * @param offset the start offset of the range to search - * @param length the length of the range to search - * @param value the new value for each mark + * @param start the start offset of the range + * @param end the end offset of the range + * @param toStart a boolean indicating if the positions should be crunched + * to the start (true) or to the end (false) */ - private void setPositionsInRange(int offset, int length, int value) + private void setPositionsInRange(int start, int end, boolean toStart) { - int endOffset = offset + length; - - int index1 = Collections.binarySearch(positions, - new GapContentPosition(offset), - new WeakPositionComparator()); - if (index1 < 0) - index1 = -(index1 + 1); - - // Search the first index with the specified offset. The binarySearch does - // not necessarily find the first one. - while (index1 > 0) + // We slump together all the GapContentPositions to point to + // one mark. So this is implemented as follows: + // 1. Remove all the marks in the specified range. + // 2. Insert one new mark at the correct location. + // 3. Adjust all affected GapContentPosition instances to point to + // this new mark. + + synchronized (this) { - WeakReference r = (WeakReference) positions.get(index1 - 1); - GapContentPosition p = (GapContentPosition) r.get(); - if (p != null && p.mark == offset || p == null) - index1--; + int startIndex = binarySearch(positionMarks, start, numMarks); + if (startIndex < 0) // Translate to insertion index, if not found. + startIndex = - startIndex - 1; + int endIndex = binarySearch(positionMarks, end, numMarks); + if (endIndex < 0) // Translate to insertion index - 1, if not found. + endIndex = - endIndex - 2; + + // Update the marks. + // We have inclusive interval bounds, but let one element over for + // filling in the new value. + int removed = endIndex - startIndex; + if (removed <= 0) + return; + System.arraycopy(positionMarks, endIndex + 1, positionMarks, + startIndex + 1, positionMarks.length - endIndex - 1); + numMarks -= removed; + if (toStart) + { + positionMarks[startIndex] = start; + } else - break; - } - - for (ListIterator i = positions.listIterator(index1); i.hasNext();) - { - WeakReference r = (WeakReference) i.next(); - GapContentPosition p = (GapContentPosition) r.get(); - if (p == null) - continue; - - if (p.mark > endOffset) - break; - - if (p.mark >= offset && p.mark <= endOffset) - p.mark = value; - } + { + positionMarks[startIndex] = end; + } + + // Update all affected GapContentPositions to point to the new index + // and all GapContentPositions that come after the interval to + // have their index moved by -removed. + Set positionSet = positions.keySet(); + for (Iterator i = positionSet.iterator(); i.hasNext();) + { + GapContentPosition p = (GapContentPosition) i.next(); + if (p.index > startIndex || p.index <= endIndex) + p.index = startIndex; + else if (p.index > endIndex) + p.index -= removed; + } + } } /** @@ -780,39 +749,44 @@ public class GapContent */ private void adjustPositionsInRange(int offset, int length, int incr) { - int endOffset = offset + length; + int endMark = offset + length; - int index1 = Collections.binarySearch(positions, - new GapContentPosition(offset), - new WeakPositionComparator()); - if (index1 < 0) - index1 = -(index1 + 1); - - // Search the first index with the specified offset. The binarySearch does - // not necessarily find the first one. - while (index1 > 0) + synchronized (this) { - WeakReference r = (WeakReference) positions.get(index1 - 1); - GapContentPosition p = (GapContentPosition) r.get(); - if (p != null && p.mark == offset || p == null) - index1--; - else - break; + // Find the start and end indices in the positionMarks array. + int startIndex = binarySearch(positionMarks, offset, numMarks); + if (startIndex < 0) // Translate to insertion index, if not found. + startIndex = - startIndex - 1; + int endIndex = binarySearch(positionMarks, endMark, numMarks); + if (endIndex < 0) // Translate to insertion index - 1, if not found. + endIndex = - endIndex - 2; + + // We must not change the order of the marks, this would have + // unpredictable results while binary-searching the marks. + assert (startIndex <= 0 + || positionMarks[startIndex - 1] + <= positionMarks [startIndex] + incr) + && (endIndex >= numMarks - 1 + || positionMarks[endIndex + 1] + >= positionMarks[endIndex] + incr) + : "Adjusting the marks must not change their order"; + + // Some debug helper output to determine if the start or end of the + // should ever be coalesced together with adjecent marks. + if (startIndex > 0 && positionMarks[startIndex - 1] + == positionMarks[startIndex] + incr) + System.err.println("DEBUG: We could coalesce the start of the region" + + " in GapContent.adjustPositionsInRange()"); + if (endIndex < numMarks - 1 && positionMarks[endIndex + 1] + == positionMarks[endIndex] + incr) + System.err.println("DEBUG: We could coalesce the end of the region" + + " in GapContent.adjustPositionsInRange()"); + + // Actually adjust the marks. + for (int i = startIndex; i <= endIndex; i++) + positionMarks[i] += incr; } - for (ListIterator i = positions.listIterator(index1); i.hasNext();) - { - WeakReference r = (WeakReference) i.next(); - GapContentPosition p = (GapContentPosition) r.get(); - if (p == null) - continue; - - if (p.mark > endOffset) - break; - - if (p.mark >= offset && p.mark <= endOffset) - p.mark += incr; - } } /** @@ -826,7 +800,7 @@ public class GapContent if (gapStart != 0) return; - setPositionsInRange(gapEnd, 0, 0); + positionMarks[0] = 0; } /** @@ -866,27 +840,94 @@ public class GapContent System.err.println(); } - private void dumpPositions() + /** + * Prints out the position marks. + */ + private void dumpMarks() + { + System.err.print("positionMarks: "); + for (int i = 0; i < numMarks; i++) + System.err.print(positionMarks[i] + ", "); + System.err.println(); + } + + /** + * Inserts a mark into the positionMarks array. This must update all the + * GapContentPosition instances in positions that come after insertionPoint. + * + * This is package private to avoid synthetic accessor methods. + * + * @param insertionPoint the index at which to insert the mark + * @param mark the mark to insert + */ + void insertMark(int insertionPoint, int mark) { - for (Iterator i = positions.iterator(); i.hasNext();) + synchronized (this) { - WeakReference r = (WeakReference) i.next(); - GapContentPosition pos = (GapContentPosition) r.get(); - System.err.println("position at: " + pos.mark); + // Update the positions. + Set positionSet = positions.keySet(); + for (Iterator i = positionSet.iterator(); i.hasNext();) + { + GapContentPosition p = (GapContentPosition) i.next(); + if (p.index >= insertionPoint) + p.index++; + } + + // Update the position marks. + if (positionMarks.length <= numMarks) + { + int[] newMarks = new int[positionMarks.length + 10]; + System.arraycopy(positionMarks, 0, newMarks, 0, insertionPoint); + newMarks[insertionPoint] = mark; + System.arraycopy(positionMarks, insertionPoint, newMarks, + insertionPoint + 1, + numMarks - insertionPoint); + positionMarks = newMarks; + } + else + { + System.arraycopy(positionMarks, insertionPoint, positionMarks, + insertionPoint + 1, + numMarks - insertionPoint); + positionMarks[insertionPoint] = mark; + } + numMarks++; } } /** - * Clears all GC'ed references in the positions array. + * An adaption of {@link java.util.Arrays#binarySearch(int[], int)} to + * specify a maximum index up to which the array is searched. This allows + * us to have some trailing entries that we ignore. + * + * This is package private to avoid synthetic accessor methods. + * + * @param a the array + * @param key the key to search for + * @param maxIndex the maximum index up to which the search is performed + * + * @return the index of the found entry, or (-(index)-1) for the + * insertion point when not found + * + * @see java.util.Arrays#binarySearch(int[], int) */ - private void clearPositionReferences() + int binarySearch(int[] a, int key, int maxIndex) { - Iterator i = positions.iterator(); - while (i.hasNext()) + int low = 0; + int hi = maxIndex - 1; + int mid = 0; + while (low <= hi) { - WeakReference r = (WeakReference) i.next(); - if (r.get() == null) - i.remove(); + mid = (low + hi) >> 1; + final int d = a[mid]; + if (d == key) + return mid; + else if (d > key) + hi = mid - 1; + else + // This gets the insertion point right on the last loop. + low = ++mid; } + return -mid - 1; } } |