[ jEdit-commits ] SF.net SVN: jedit:[21885] jEdit/trunk

[<k_s...@us...>]

Revision: 21885
          http://jedit.svn.sourceforge.net/jedit/?rev=21885&view=rev
Author:   k_satoda
Date:     2012-06-27 14:06:58 +0000 (Wed, 27 Jun 2012)
Log Message:
-----------
Dropped the artificial limitation to 1024 chars on expanding the gap
in ContentManager. Now it always use the complete remaining buffer which
is expanded in a geometric progression. This change greatly speeds up
big search&replace-all operations in which case copying in moveGapEnd()
exhibited quadratic operation. Now it is amortized linear.
(Patch #3533838 by Thomas Meyer, tweaked by me)

Modified Paths:
--------------
    jEdit/trunk/doc/CHANGES.txt
    jEdit/trunk/org/gjt/sp/jedit/buffer/ContentManager.java

Modified: jEdit/trunk/doc/CHANGES.txt
===================================================================
--- jEdit/trunk/doc/CHANGES.txt	2012-06-27 13:53:47 UTC (rev 21884)
+++ jEdit/trunk/doc/CHANGES.txt	2012-06-27 14:06:58 UTC (rev 21885)
@@ -9,6 +9,9 @@
 
 {{{ Bug fixes
 
+- Fixed unreasonable quadratic operations which could be observable on
+  big search&replace-all. (Patch #3533838 by Thomas Meyer)
+
 - Avoided unreasonable memory consumption by duplicate String instances
   that could be allocated for each occurrence in a big
   search&replace-all. (Patch #3528619 by Thomas Meyer)

Modified: jEdit/trunk/org/gjt/sp/jedit/buffer/ContentManager.java
===================================================================
--- jEdit/trunk/org/gjt/sp/jedit/buffer/ContentManager.java	2012-06-27 13:53:47 UTC (rev 21884)
+++ jEdit/trunk/org/gjt/sp/jedit/buffer/ContentManager.java	2012-06-27 14:06:58 UTC (rev 21885)
@@ -47,13 +47,13 @@
 	public String getText(int start, int len)
 	{
 		if(start >= gapStart)
-			return new String(text,start + gapEnd - gapStart,len);
+			return new String(text,start + gapLength(),len);
 		else if(start + len <= gapStart)
 			return new String(text,start,len);
 		else
 		{
 			return new String(text,start,gapStart - start)
-				.concat(new String(text,gapEnd,start + len - gapStart));
+				.concat(new String(text,gapEnd(),start + len - gapStart));
 		}
 	}
 
@@ -75,7 +75,7 @@
 		if(start >= gapStart)
 		{
 			seg.array = text;
-			seg.offset = start + gapEnd - gapStart;
+			seg.offset = start + gapLength();
 			seg.count = len;
 		}
 		else if(start + len <= gapStart)
@@ -92,7 +92,7 @@
 			System.arraycopy(text,start,seg.array,0,gapStart - start);
 
 			// copy text after gap
-			System.arraycopy(text,gapEnd,seg.array,gapStart - start,
+			System.arraycopy(text,gapEnd(),seg.array,gapStart - start,
 				len + start - gapStart);
 
 			seg.offset = 0;
@@ -114,13 +114,13 @@
 	public CharSequence getSegment(int start, int len)
 	{
 		if(start >= gapStart)
-			return new BufferSegment(text,start + gapEnd - gapStart,len);
+			return new BufferSegment(text,start + gapLength(),len);
 		else if(start + len <= gapStart)
 			return new BufferSegment(text,start,len);
 		else
 		{
 			return new BufferSegment(text,start,gapStart - start,
-				new BufferSegment(text,gapEnd,start + len - gapStart));
+				new BufferSegment(text,gapEnd(),start + len - gapStart));
 		}
 	} //}}}
 
@@ -162,8 +162,10 @@
 	//{{{ _setContent() method
 	public void _setContent(char[] text, int length)
 	{
+		assert text != null;
+		assert text.length >= length;
 		this.text = text;
-		this.gapStart = this.gapEnd = 0;
+		this.gapStart = length;
 		this.length = length;
 	} //}}}
 
@@ -171,19 +173,31 @@
 	public void remove(int start, int len)
 	{
 		moveGapStart(start);
-		gapEnd += len;
 		length -= len;
 	} //}}}
 
 	//{{{ Private members
-	private char[] text;
+	private static final char[] EMPTY_TEXT = new char[0];
+	private char[] text = EMPTY_TEXT;
 	private int gapStart;
-	private int gapEnd;
 	private int length;
 
+	//{{{ gapEnd() method
+	private int gapEnd()
+	{
+		return gapStart + gapLength();
+	} //}}}
+
+	//{{{ gapLength() method
+	private int gapLength()
+	{
+		return text.length - length;
+	} //}}}
+
 	//{{{ moveGapStart() method
 	private void moveGapStart(int newStart)
 	{
+		int gapEnd = gapEnd();
 		int newEnd = gapEnd + (newStart - gapStart);
 
 		if(newStart == gapStart)
@@ -202,24 +216,21 @@
 		}
 
 		gapStart = newStart;
-		gapEnd = newEnd;
 	} //}}}
 
-	//{{{ moveGapEnd() method
-	private void moveGapEnd(int newEnd)
-	{
-		System.arraycopy(text,gapEnd,text,newEnd,length - gapStart);
-		gapEnd = newEnd;
-	} //}}}
-
 	//{{{ ensureCapacity() method
 	private void ensureCapacity(int capacity)
 	{
 		if(capacity >= text.length)
 		{
+			int gapEndOld = gapEnd();
+
 			char[] textN = new char[capacity * 2];
-			System.arraycopy(text,0,textN,0,length + (gapEnd - gapStart));
+			System.arraycopy(text,0,textN,0,text.length);
 			text = textN;
+
+			int gapEndNew = gapEnd();
+			System.arraycopy(text,gapEndOld,text,gapEndNew,text.length - gapEndNew);
 		}
 	} //}}}
 
@@ -227,12 +238,8 @@
 	private void prepareGapForInsertion(int start, int len)
 	{
 		moveGapStart(start);
-		if(gapEnd - gapStart < len)
-		{
-			int gapSize = len + 1024;
-			ensureCapacity(length + gapSize);
-			moveGapEnd(start + gapSize);
-		}
+		if(gapLength() < len)
+			ensureCapacity(length + len);
 	} //}}}
 
 	//}}}

This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.