This fixes some potential race condition in the previous implementation of the GapContentPosition. I used some WeakReference magic there which was potentially racy (binary searching an ArrayList that has WeakReferences in it).
I solved this by inserting an indirection layer. Now the
GapContentPosition do not store their marks directly, they only store an
index to a positionMarks array, which stores the real marks. This way we
can still binary serch the marks, without the need to care if the
GapContentPositions are GC'ed or not.
This has the additional advantage that we can reuse GapContentPositions
as well as existent marks in createPosition().
However, there is one (minor IMO) problem left. As it is now, the
positionMarks array is never cleaned up, that means that marks are kept
there, even if their corresponding GapContentPosition is GC'ed. This
might get slightly inefficient in large documents with lots of edits.
However, the fact that marks and GapContentPositions are reused when
possible alleviates for that inefficiency a little. So the array can
never grow larger than the maximum document length. We might want to
consider to either track GapContentPositions beeing GC'ed (using a
ReferenceQueue) or perform some manual cleanup regularily. I added a
FIXME for that.
2006-05-17 Roman Kennke <[EMAIL PROTECTED]>
PR 26368
* javax/swing/text/GapContent.java
(GapContentPosition): Do no more implement Comparable.
(GapContentPosition.mark): Removed field.
(GapContentPosition.index): New field to hold the index into
the positions array.
(GapContentPosition(int)): Rewritten to use the new indirection
to the positions array.
(GapContentPosition.compareTo): Removed.
(GapContentPosition.getOffset): Synchronized. Fetch mark from
positionMarks array.
(WeakPositionComparator): Removed obsolete class.
(positions): Changed type to WeakHashMap.
(positionMarks): New field, holds the marks of the positions.
(GapContent): Initialize new fields.
(createPosition): Rewritten to use the new indirection
to the positions array.
(getPositionsInRange): Rewritten to use the new indirection
to the positions array.
(setPositionsInRange): Rewritten to use the new indirection
to the positions array.
(adjustPositionsInRange): Rewritten to use the new indirection
to the positions array.
(insertMark): New helper method.
(clearPositionReferences): Removed obsolete methods.
/Roman
--
“Improvement makes straight roads, but the crooked roads, without
Improvement, are roads of Genius.” - William Blake
Index: javax/swing/text/GapContent.java
===================================================================
RCS file: /cvsroot/classpath/classpath/javax/swing/text/GapContent.java,v
retrieving revision 1.46
diff -u -1 -0 -r1.46 GapContent.java
--- javax/swing/text/GapContent.java 2 May 2006 14:11:31 -0000 1.46
+++ javax/swing/text/GapContent.java 17 May 2006 16:27:07 -0000
@@ -32,110 +32,101 @@
module. An independent module is a module which is not derived from
or based on this library. If you modify this library, you may extend
this exception to your version of the library, but you are not
obligated to do so. If you do not wish to do so, delete this
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.Arrays;
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;
import javax.swing.undo.CannotUndoException;
import javax.swing.undo.UndoableEdit;
/**
* This implementation of [EMAIL PROTECTED] AbstractDocument.Content} uses a gapped buffer.
* This takes advantage of the fact that text area content is mostly inserted
* sequentially. The buffer is a char array that maintains a gap at the current
* insertion point. If characters a inserted at gap boundaries, the cost is
* 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
{
/**
* A [EMAIL PROTECTED] 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.
*
* @param mark the mark of this Position
*/
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 = Arrays.binarySearch(positionMarks, mark);
+ if (i >= 0) // mark found
+ {
+ index = i;
+ }
+ else
+ {
+ index = -i - 1;
+ insertMark(index, mark);
+ }
}
}
/**
* Returns the current offset of this Position within the content.
*
* @return the current offset of this Position within the content.
*/
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;
+ }
}
}
private class InsertUndo extends AbstractUndoableEdit
{
public int where, length;
String text;
public InsertUndo(int start, int len)
{
where = start;
@@ -202,54 +193,20 @@
remove(where, text.length());
}
catch (BadLocationException ble)
{
throw new CannotRedoException();
}
}
}
- /**
- * Compares WeakReference objects in a List by comparing the referenced
- * objects instead.
- *
- * @author Roman Kennke ([EMAIL PROTECTED])
- */
- 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;
/**
* This is the default buffer size and the amount of bytes that a buffer is
* extended if it is full.
*/
static final int DEFAULT_BUFSIZE = 10;
/**
@@ -260,26 +217,34 @@
/**
* The index of the first character of the gap.
*/
int gapStart;
/**
* The index of the character after the last character of the gap.
*/
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.
+ * (Weakly) Stores the GapContentPosition instances.
*/
- private ArrayList positions;
+ WeakHashMap positions;
/**
* Creates a new GapContent object.
*/
public GapContent()
{
this(DEFAULT_BUFSIZE);
}
/**
@@ -287,21 +252,22 @@
*
* @param size the initial size of the buffer
*/
public GapContent(int size)
{
size = Math.max(size, 2);
buffer = (char[]) allocateArray(size);
gapStart = 1;
gapEnd = size;
buffer[0] = '\n';
- positions = new ArrayList();
+ positions = new WeakHashMap();
+ positionMarks = new int[0];
}
/**
* Allocates an array of the specified length that can then be used as
* buffer.
*
* @param size the size of the array to be allocated
*
* @return the allocated array
*/
@@ -476,40 +442,44 @@
*
* @param offset the position at which to create the mark
*
* @return the create Position object for the mark
*
* @throws BadLocationException if the offset is not a valid position in the
* buffer
*/
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;
}
/**
* Enlarges the gap. This allocates a new bigger buffer array, copy the
* segment before the gap as it is and the segment after the gap at the end
* of the new buffer array. This does change the gapEnd mark but not the
* gapStart mark.
*
* @param newSize the new size of the gap
@@ -535,21 +505,20 @@
/**
* Shifts the gap to the specified position.
*
* @param newGapStart the new start position of the gap
*/
protected void shiftGap(int newGapStart)
{
if (newGapStart == gapStart)
return;
-
int newGapEnd = newGapStart + gapEnd - gapStart;
if (newGapStart < gapStart)
{
// Update the positions between newGapStart and (old) gapStart. The marks
// must be shifted by (gapEnd - gapStart).
adjustPositionsInRange(newGapStart, gapStart - newGapStart, gapEnd - gapStart);
System.arraycopy(buffer, newGapStart, buffer, newGapEnd, gapStart
- newGapStart);
gapStart = newGapStart;
gapEnd = newGapEnd;
@@ -681,144 +650,85 @@
* @return the positions within the specified range
*/
protected Vector getPositionsInRange(Vector v, int offset, int length)
{
Vector res = v;
if (res == null)
res = new Vector();
else
res.clear();
- int endOffset = offset + length;
+ int endOffs = 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;
- }
-
- 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>
*
* @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
*/
private void setPositionsInRange(int offset, int length, int value)
{
- 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)
- {
- WeakReference r = (WeakReference) positions.get(index1 - 1);
- GapContentPosition p = (GapContentPosition) r.get();
- if (p != null && p.mark == offset || p == null)
- index1--;
- else
- break;
- }
-
- for (ListIterator i = positions.listIterator(index1); i.hasNext();)
+ synchronized (this)
{
- WeakReference r = (WeakReference) i.next();
- GapContentPosition p = (GapContentPosition) r.get();
- if (p == null)
- continue;
+ int startIndex = Arrays.binarySearch(positionMarks, offset);
+ if (startIndex < 0) // Translate to insertion index, if not found.
+ startIndex = - startIndex - 1;
+ int endIndex = Arrays.binarySearch(positionMarks, endMark);
+ if (endIndex < 0) // Translate to insertion index - 1, if not found.
+ endIndex = - endIndex - 2;
- if (p.mark > endOffset)
- break;
-
- if (p.mark >= offset && p.mark <= endOffset)
- p.mark = value;
+ for (int i = startIndex; i <= endIndex; i++)
+ positionMarks[i] = value;
}
}
/**
* Adjusts 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 by <code>increment</code>
*
* @param offset the start offset of the range to search
* @param length the length of the range to search
* @param incr the increment
*/
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)
- {
- WeakReference r = (WeakReference) positions.get(index1 - 1);
- GapContentPosition p = (GapContentPosition) r.get();
- if (p != null && p.mark == offset || p == null)
- index1--;
- else
- break;
- }
-
- for (ListIterator i = positions.listIterator(index1); i.hasNext();)
+ synchronized (this)
{
- WeakReference r = (WeakReference) i.next();
- GapContentPosition p = (GapContentPosition) r.get();
- if (p == null)
- continue;
-
- if (p.mark > endOffset)
- break;
+ int startIndex = Arrays.binarySearch(positionMarks, offset);
+ if (startIndex < 0) // Translate to insertion index, if not found.
+ startIndex = - startIndex - 1;
+ int endIndex = Arrays.binarySearch(positionMarks, endMark);
+ if (endIndex < 0) // Translate to insertion index - 1, if not found.
+ endIndex = - endIndex - 2;
- if (p.mark >= offset && p.mark <= endOffset)
- p.mark += incr;
+ for (int i = startIndex; i <= endIndex; i++)
+ positionMarks[i] += incr;
}
}
/**
* Resets all <code>Position</code> that have an offset of <code>0</code>,
* to also have an array index of <code>0</code>. This might be necessary
* after a call to <code>shiftGap(0)</code>, since then the marks at offset
* <code>0</code> get shifted to <code>gapEnd</code>.
*/
protected void resetMarksAtZero()
@@ -859,34 +769,45 @@
System.err.print('>');
if (!Character.isISOControl(buffer[i]))
System.err.print(buffer[i]);
else
System.err.print('.');
}
System.err.println();
}
- private void dumpPositions()
- {
- for (Iterator i = positions.iterator(); i.hasNext();)
- {
- WeakReference r = (WeakReference) i.next();
- GapContentPosition pos = (GapContentPosition) r.get();
- System.err.println("position at: " + pos.mark);
- }
- }
-
/**
- * Clears all GC'ed references in the positions array.
+ * 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
*/
- private void clearPositionReferences()
+ void insertMark(int insertionPoint, int mark)
{
- Iterator i = positions.iterator();
- while (i.hasNext())
+ synchronized (this)
{
- WeakReference r = (WeakReference) i.next();
- if (r.get() == null)
- i.remove();
+ // 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.
+ // TODO: We might want to do this more efficiently by enlarging the
+ // array in bigger chunks than 1.
+ int[] newMarks = new int[positionMarks.length + 1];
+ System.arraycopy(positionMarks, 0, newMarks, 0, insertionPoint);
+ newMarks[insertionPoint] = mark;
+ System.arraycopy(positionMarks, insertionPoint, newMarks,
+ insertionPoint + 1,
+ positionMarks.length - insertionPoint);
+ positionMarks = newMarks;
}
}
}
signature.asc
Description: Dies ist ein digital signierter Nachrichtenteil
