Jetpack之FastSafeIterableMap源码

2021-04-26

我们在分析Lifecycle源码之前先看下FastSafeIterableMap的源码，因为Lifecycle组件的关键类LifecycleRegistry使用到，而且是关键的属性。

首先，他继承自SafeIterableMap，而SafeIterableMap继承自Iterable<Map.Entry<K, V>>。我们就先分析SafeIterableMap的源码

`SafeIterableMap`

他是一个不同于HashMap的键值对，他是由Key组成的链表，每个Key里面存储了Value，具有头部和尾部，我们先看他的声明

1
2
3

public class SafeIterableMap<K, V> implements Iterable<Map.Entry<K, V>> {
//继承自Iterable<Map.Entry<K, V>>
}

然后是他的属性

private Entry<K, V> mStart //头部指针
private Entry<K, V> mEnd //尾部指针
private WeakHashMap<SupportRemove<K, V>, Boolean> mIterators = new WeakHashMap<>() //与迭代器有关，后续再说
private int mSize = 0 //链表长度

其中Entry是继承自Map.Entry的，他的声明是

static class Entry<K, V> implements Map.Entry<K, V> {
        final K mKey; //自己的key
        final V mValue; //自己的value
        Entry<K, V> mNext; //指向下一个元素的指针
        Entry<K, V> mPrevious; //指向上一个的指针
        Entry(@NonNull K key, @NonNull V value) {
            mKey = key;
            this.mValue = value;
        }
        @Override
        public K getKey() {
            return mKey;
        }
        @Override
        public V getValue() {
            return mValue;
        }
        @Override
        public V setValue(V value) {
            //只能通过构造函数传入
            throw new UnsupportedOperationException("An entry modification is not supported");
        }
        ....
    }

然后我们分析他的put方法

protected Entry<K, V> put(@NonNull K key, @NonNull V v) {
        //该方法是不判断是否存在相同的key在存入的，判断是否相同的key在存入是putIfAbsent方法
        Entry<K, V> newEntry = new Entry<>(key, v);
        //长度增加
        mSize++;
        if (mEnd == null) {
            //假如是第一次则设置mStart，mEnd
            mStart = newEntry;
            mEnd = mStart;
            return newEntry;
        }
        //不是初始化则把mEnd的next指向newEntry，newEntry的mPrevious指向之前的mEnd，然后把newEntry复制给mEnd
        //从这里我们知道mEnd是没有mPrevious的
        mEnd.mNext = newEntry;
        newEntry.mPrevious = mEnd;
        mEnd = newEntry;
        return newEntry;
    }
    //putIfAbsent方法
    public V putIfAbsent(@NonNull K key, @NonNull V v) {
        //获取之前的
        Entry<K, V> entry = get(key);
        if (entry != null) {
            //存在就不put了，一般是调用这个方法居多
            return entry.mValue;
        }
        put(key, v);
        return null;
    }

然后是他的get方法

protected Entry<K, V> get(K k) {
       Entry<K, V> currentNode = mStart;
       //从mStart开始遍历
       while (currentNode != null) {
           if (currentNode.mKey.equals(k)) {
               //找到则返回
               break;
           }
           //否则继续
           currentNode = currentNode.mNext;
       }
       //没有找到返回mStart头部
       return currentNode;
   }

然后是迭代器，SafeIterableMap具有两个迭代器，分别通过iterator()(forEatch循环使用的)得到的AscendingIterator以及descendingIterator得到的DescendingIterator。分别是正序和反序遍历，他们都继承自内部类ListIterator

Iterator

我们先说下ListIterator，直接看源码

private abstract static class ListIterator<K, V> implements Iterator<Map.Entry<K, V>>,
            SupportRemove<K, V> {
        //他实现了SupportRemove接口
        Entry<K, V> mExpectedEnd;
        Entry<K, V> mNext;
        ListIterator(Entry<K, V> start, Entry<K, V> expectedEnd) {
            this.mExpectedEnd = expectedEnd;
            this.mNext = start;
        }
        @Override
        public boolean hasNext() {
            //不存在mNext则遍历完成
            return mNext != null;
        }
        @SuppressWarnings("ReferenceEquality")
        @Override
        public void supportRemove(@NonNull Entry<K, V> entry) {
            //该方法由SafeIterableMap的remove触发，假如需要移除的entry是最后一个而且也是当前的mNext
            if (mExpectedEnd == entry && entry == mNext) {
                //则把这两个清空
                mNext = null;
                mExpectedEnd = null;
            }
            //假如外部只是移除了最后一个，则把mExpectedEnd指向他的前一个
            if (mExpectedEnd == entry) {
                mExpectedEnd = backward(mExpectedEnd);
            }    
            //假如需要移除的是mNext，则把mNext指向下一个
            if (mNext == entry) {
                mNext = nextNode();
            }
        }
        @SuppressWarnings("ReferenceEquality")
        private Entry<K, V> nextNode() {
            //假如不存在了就不处理，否则返回他的下一个，该方法不校对mNext指针
            if (mNext == mExpectedEnd || mExpectedEnd == null) {
                return null;
            }
            return forward(mNext);
        }
        @Override
        public Map.Entry<K, V> next() {
            //获取下一个
            Map.Entry<K, V> result = mNext;
            //校对mNext指针
            mNext = nextNode();
            return result;
        }
        //下面两个由子类实现
        abstract Entry<K, V> forward(Entry<K, V> entry);
        abstract Entry<K, V> backward(Entry<K, V> entry);
    }

其中AscendingIterator和DescendingIterator的实现是类似的，源码如下

static class AscendingIterator<K, V> extends ListIterator<K, V> {
        //传入头部和尾部
        AscendingIterator(Entry<K, V> start, Entry<K, V> expectedEnd) {
            super(start, expectedEnd);
        }

        @Override
        Entry<K, V> forward(Entry<K, V> entry) {
        //向后遍历
            return entry.mNext;
           //假如是DescendingIterator则向后遍历则返回他的前者
            //return entry.mPrevious;
        }

        @Override
        Entry<K, V> backward(Entry<K, V> entry) {
            //向前遍历
            return entry.mPrevious;
            //假如是DescendingIterator则向前遍历返回后者
            return entry.mNext;

        }
    }

然后是移除remove方法

public V remove(@NonNull K key) {
        //寻找是否存在，不存在则不处理
        Entry<K, V> toRemove = get(key);
        if (toRemove == null) {
            return null;
        }
        //存在size-1
        mSize--;
        if (!mIterators.isEmpty()) {
            for (SupportRemove<K, V> iter : mIterators.keySet()) {
                iter.supportRemove(toRemove);
            }
        }
        //他的前者不为null则把前者的next指向toRemove的next
        if (toRemove.mPrevious != null) {
            toRemove.mPrevious.mNext = toRemove.mNext;
        } else {
            mStart = toRemove.mNext;
        }
        //如果他的后者不为null，则把他的后者的mPrevious指向他的mPrevious
        if (toRemove.mNext != null) {
            toRemove.mNext.mPrevious = toRemove.mPrevious;
        } else {
            mEnd = toRemove.mPrevious;
        }
        //然后置空
        toRemove.mNext = null;
        toRemove.mPrevious = null;
        //返回值
        return toRemove.mValue;
    }

它还提供了一个iteratorWithAdditions()获取自定义非基础自ListIterator的额外迭代器，具体实现和解析如下

private class IteratorWithAdditions implements Iterator<Map.Entry<K, V>>, SupportRemove<K, V> {
        //继承自Iterator非内部类ListIterator
        //当前节点
        private Entry<K, V> mCurrent;
        //
        private boolean mBeforeStart = true;

        IteratorWithAdditions() {
        }

        @SuppressWarnings("ReferenceEquality")
        @Override
        public void supportRemove(@NonNull Entry<K, V> entry) {
            if (entry == mCurrent) {
            //假如外部需要移除的是当前的，则把当前的mCurrent 指向他的前一个
            //然后判断是否需要重头开始，假如mCurrent 为空则需要
                mCurrent = mCurrent.mPrevious;
                mBeforeStart = mCurrent == null;
            }
        }

        @Override
        public boolean hasNext() {
            //从头开始则判断start是否为null
            if (mBeforeStart) {
                //只有没有执行过next()才会走这里
                return mStart != null;
            }
            //否则是判断mCurrent以及mCurrent.mNext是否为null
            return mCurrent != null && mCurrent.mNext != null;
        }

        @Override
        public Map.Entry<K, V> next() {
            //从头开始则先取头部，默认mBeforeStart为true
            if (mBeforeStart) {
                mBeforeStart = false;
                //指向头部
                mCurrent = mStart;
            } else {
                //后续则从mCurrent的next开始取
                mCurrent = mCurrent != null ? mCurrent.mNext : null;
            }
            return mCurrent;
        }
    }

我们在一开始的时候有提到SafeIterableMap有一个mIterators，他是用于存储生成的所有的Iterator，每次获取任意一种迭代器新生成一个迭代器对象的时候就往mIterators里面放。他会在SafeIterableMap元素被移除的时候调用，去矫正存储的迭代器的当前位置。这就是SafeIterableMap的源码了

FastSafeIterableMap

他是继承了SafeIterableMap，但是他重写了他的get，putIfAbsent,remove方法。而且它使用的是HashMap去存储元素，类型是HashMap<K, Entry<K, V>>。他存储的与SafeIterableMap不一样，他是通过父类存储<K,V>，而自己存储的是<K,<K,V>>，是包裹了一层的。而且LifecycleRegistry也没有直接调用FastSafeIterableMap的put方法，而是调用的putIfAbsent，我们具体他的源码。
首先是putIfAbsent方法

@Override
    public V putIfAbsent(@NonNull K key, @NonNull V v) {
        //查找是否存在，不存在的时候才插入
        Entry<K, V> current = get(key);
        if (current != null) {
            return current.mValue;
        }
        //不存在，调用父类的put得到一个Entry<K, V>，然后在存储自己的变量mHashMap中
        mHashMap.put(key, put(key, v));
        return null;
    }

然后是get方法以及自己增加的ceil方法

@Override
    protected Entry<K, V> get(K k) {
        //获取的是Entry<K, V>
        return mHashMap.get(k);
    }
    
    public Map.Entry<K, V> ceil(K k) {
        if (contains(k)) {
            //获取的是传入key的上一个 Entry<K, V> 
            return mHashMap.get(k).mPrevious;
        }
        return null;
    }
    public boolean contains(K key) {
        //简单的判断
        return mHashMap.containsKey(key);
    }

最后是他的remove方法

@Override
    public V remove(@NonNull K key) {
        V removed = super.remove(key);
        mHashMap.remove(key);
        return removed;
    }

这就是FastSafeIterableMap的源码，比较的简单，他其实是相当于把SafeIterableMap再封装了一层，SafeIterableMap存储的是<K,V>，那么他则是存储的<K,<K,V>。