eclipse 代码分析（1）CopyOnWriteTextStore

浏览数：41 / 时间：2015年06月20日

今天分析一下eclipse jface 下document 下copyOnwriteTextStore 类的实现。

eclipse 是一个非常受欢迎的ide 工具，既然是ide，强大的文本编辑功能必然是必备功能之一。那么要很好的操纵文本，良好的定位文本和替换特定文本便是文本编辑的基础。

今天来分析一下document 类下的一个实现快速替换文本的类。copyOnwriteTextStore，对java 并发类熟悉的人，听名字可能觉得是不是和CopyOnWriteArrayList 什么的有关系，其实和并发没有什么关系，只是内部有两个工作类，只读的时候，通过StringTextStore来操作文本。当有replace 发生，则换到modifiableTextStore类来实现。document 默认用的是GapTextStore来工作。

GapTextStore 为了提高性能，不在每次replace是都开辟内存，在实现时加了一个冗余gap。好那既然是通过冗余gap来避免不必要的重复开辟内存。实现gap及时算法的关键。那我们先提出几个关于gap问题，之后再给出代码是如何解决这些问题的。1 gap 什么时候产生？2，gap 有范围吗？3 gap 在什么位置产生。知道这三个问题的答案，这个实现也就知道了。

第一，当replace 发生gap 产生，分两种情况一个是gap 加文本长度够且小于阈值的情况。一种是不够或大于gap大于阈值的情况。这两种情况是不同的。

第二，replace 计算新的长度差，新的大于旧的或新的小于旧的，但差值大于阈值，进入第二种情况，否则进入第一种。第二种情况下，先计算新长度，之后乘以一个大于1的长度变化因子获得长度，gap 值为新长度减掉文本长度，如果大于或小于gap上下线，gap自动设为对应值，新长度响应改变。

第三，gap的位置不是在头也不是在尾部，而是在replace 目标替换掉就文本后的后面，这样好处是在第一种情况下文本移动要简单。

一下为调整代码

private 
void adjustGap(int 
offset, int 
remove, int 
add) {
    final 
int oldGapSize= gapSize();
    final 
int newGapSize= oldGapSize - add + remove;
    final 
boolean reuseArray= 0 
<= newGapSize && newGapSize <= fThreshold;
 
    final 
int newGapStart= offset + add;
    final 
int newGapEnd;
 
    if 
(reuseArray)
        newGapEnd= moveGap(offset, remove, oldGapSize, newGapSize, newGapStart);
    else
        newGapEnd= reallocate(offset, remove, oldGapSize, newGapSize, newGapStart);
 
    fGapStart= newGapStart;
    fGapEnd= newGapEnd;
}

　　第二种情况代码：

    private int reallocate(int offset, int remove, final int oldGapSize, int newGapSize, final int newGapStart) {
        // the new content length (without any gap)
        final int newLength= fContent.length - newGapSize;
        // the new array size based on the gap factor
        int newArraySize= (int) (newLength * fSizeMultiplier);
        newGapSize= newArraySize - newLength;

        // bound the gap size within min/max
        if (newGapSize < fMinGapSize) {
            newGapSize= fMinGapSize;
            newArraySize= newLength + newGapSize;
        } else if (newGapSize > fMaxGapSize) {
            newGapSize= fMaxGapSize;
            newArraySize= newLength + newGapSize;
        }

        // the upper threshold is always twice the gapsize
        fThreshold= newGapSize * 2;
        final char[] newContent= allocate(newArraySize);
        final int newGapEnd= newGapStart + newGapSize;

        /*
         * Re-allocation: The old content can be copied in at most 3 operations to the newly allocated
         * array. Either one of change offset and the gap may come first.
         * - unchanged area before the change offset / gap
         * - area between the change offset and the gap (either one may be first)
         * - rest area after the change offset / after the gap
         */
        if (offset < fGapStart) {
            // change comes before gap
            arrayCopy(0, newContent, 0, offset);
            int afterRemove= offset + remove;
            if (afterRemove < fGapStart) {
                // removal is completely before the gap
                final int betweenSize= fGapStart - afterRemove;
                arrayCopy(afterRemove, newContent, newGapEnd, betweenSize);
                final int restSize= fContent.length - fGapEnd;
                arrayCopy(fGapEnd, newContent, newGapEnd + betweenSize, restSize);
            } else {
                // removal encompasses the gap
                afterRemove += oldGapSize;
                final int restSize= fContent.length - afterRemove;
                arrayCopy(afterRemove, newContent, newGapEnd, restSize);
            }
        } else {
            // gap comes before change
            arrayCopy(0, newContent, 0, fGapStart);
            final int offsetShifted= offset + oldGapSize;
            final int betweenSize= offsetShifted - fGapEnd;
            arrayCopy(fGapEnd, newContent, fGapStart, betweenSize);
            final int afterRemove= offsetShifted + remove;
            final int restSize= fContent.length - afterRemove;
            arrayCopy(afterRemove, newContent, newGapEnd, restSize);
        }

        fContent= newContent;
        return newGapEnd;
    }

第一种情况代码：

private int moveGap(int offset, int remove, int oldGapSize, int newGapSize, int newGapStart) {
        /*
         * No re-allocation necessary. The area between the change offset and gap can be copied
         * in at most one operation. Don‘t copy parts that will be overwritten anyway.
         */
        final int newGapEnd= newGapStart + newGapSize;
        if (offset < fGapStart) {
            int afterRemove= offset + remove;
            if (afterRemove < fGapStart) {
                final int betweenSize= fGapStart - afterRemove;
                arrayCopy(afterRemove, fContent, newGapEnd, betweenSize);
            }
            // otherwise, only the gap gets enlarged
        } else {
            final int offsetShifted= offset + oldGapSize;
            final int betweenSize= offsetShifted - fGapEnd; // in the typing case, betweenSize is 0
            arrayCopy(fGapEnd, fContent, fGapStart, betweenSize);
        }
        return newGapEnd;
    }