10 | Android 高级进阶(源码剖析篇) Square

2018-03-24 本文已影响72人 asce1885

作者简介：ASCE1885，《Android 高级进阶》作者。
本文由于潜在的商业目的，未经授权不开放全文转载许可，谢谢！
本文分析的源码版本已经 fork 到我的 Github。

1520301887857.jpg

本文我们重点来介绍 okio 中的 segment 和 SegmentPool，segment 是一个底层的数据结构，本质上是一个字节数组，同时由于它被用于链表或者循环链表中，因此，segment 中也定义了链表的相关操作。而 SegmentPool 中保存的是未使用的 segment 的集合，需要使用 segment 时从这个池子中取用，用完后及时释放回这个池子，两者的关系如下图所示：

关系图

segment

接下来我们首先介绍 segment，从上图可以看到，segment 有两个核心概念：

读取指针 pos：segment 数据读取时下一个要读取的字节位置
写入指针 limit：segment 数据写入时将会写入的第一个字节位置

segment 根据其中的字节数据 final byte[] data 是否能够被多个 segment 共用，可以分为共享 segment 和非共享 segment，通过变量 boolean shared 来标识；同时同一份数据多个 segment 在使用时，通过变量 boolean owner 来区分谁是这份数据的拥有者，一份数据只有一个拥有者，其他的都是使用者，一般来说，数据拥有者对共享的 final byte[] data 数组拥有读写权限，数据使用者对其只有只读权限。

从 Segment 类的构造方法也可以看出它是否共享 segment：

/** segment 中字节数组的大小 */
static final int SIZE = 8192;

/** segment 拆分时，当数据量少于这个值时不做数据共享 */
static final int SHARE_MINIMUM = 1024;

/** segment 中实际存放数据的地方 */
final byte[] data;

/** 数据读取指针 */
int pos;

/** 数据写入指针 */
int limit;

/** 为 true 表示有其他 segment 和当前 segment 共享 data 数组 */
boolean shared;

/** 为 true 时表示当前 segment 拥有 data 数组，并能够进行数据的写入 */
boolean owner;
  
/** 非共享 segment */
Segment() {
    this.data = new byte[SIZE];
    this.owner = true;
    this.shared = false;
}

/** 共享 segment */
Segment(Segment shareFrom) {
    this(shareFrom.data, shareFrom.pos, shareFrom.limit);
    shareFrom.shared = true;
}

/** 共享 segment */
Segment(byte[] data, int pos, int limit) {
    this.data = data;
    this.pos = pos;
    this.limit = limit;
    this.owner = false;
    this.shared = true;
}

链表操作

当 segment 被用于链表或者循环链表时，就会存在指向链表前面一个 segment 的指针 prev，或者指向后面一个 segment 的指针 next，同时存在链表元素的添加和删除，熟悉数据结构的同学应该知道，这是典型的链表操作，链表元素的添加和删除基本上就是指针的指向操作。

双向链表在某个元素后面插入一个新元素的步骤如下：

将新元素的前向指针 prev 指向当前元素
将新元素的后向指针 next 指向当前元素的后面一个元素，也就是当前元素的 next 指针
当前元素的前向指针改为指向新元素
当前元素下一个元素的前向指针改为指向新元素

代码如下所示：

/** 链表或者双向循环链表中当前元素的后面一个元素指针 */
Segment next;

/** 双向循环链表中当前元素的前一个元素指针 */
Segment prev;

/** 在当前 segment 后面添加一个新的 segment */
public Segment push(Segment segment) {
    segment.prev = this;
    segment.next = next;
    next.prev = segment;
    next = segment;
    return segment;
}

双向链表删除当前元素并返回当前元素的后面一个元素的步骤如下：

获取当前元素的后面一个元素（缓存起来）
当前元素的前一个元素的后向指针改为指向当前元素的后一个元素
当前元素的后一个元素的前向指针改为指向当前元素的前一个元素
当前元素的前向指针和后向指针都设置为空，从而从链表中删除

代码如下所示：

/** 双向链表删除当前元素并返回当前元素的后面一个元素 */
public @Nullable Segment pop() {
    Segment result = next != this ? next : null;
    prev.next = next;
    next.prev = prev;
    next = null;
    prev = null;
    return result;
}

相信工科相关专业的同学应该都学习过严蔚敏的那本经典的数据结构教程，印象不深的可以回味一下。

segment 的拆分

为了高效的利用内存和方便 Buffer 的操作，segment 支持拆分和合并，拆分指的是将一个 segment 中从读取指针 pos 开始到写入指针 limit 之间的数据拆分到两个 segment 中。使用者需要指定一个字节数 byteCount 用来分割这部分数据，[pos ～ pos+byteCount) 之间的数据拆分到新的 segment 中，[pos+byteCount ~ limit) 之间的数据保留在原来的 segment 中。在链表的视角看，新拆分出来的 segment 位于原来 segment 的前面。

在拆分的过程中，涉及到新 segment 的生成，为了获得高性能，有如下两个理念截然相反的问题需要关注和平衡：

尽可能避免数据拷贝，这个可以通过前面介绍过的共享 segment 来实现
当拷贝数据量很小时，避免使用共享 segment，因为共享部分数据是只读的，而且可能会导致链表中存在很多数据量很小的 segment，影响性能

因此，在拆分时，只有当数据量 byteCount 不小于 segment 大小的八分之一（即 1024 字节）时，才会使用共享 segment，否则使用非共享 segment，并通过 System.arraycopy 进行数据的拷贝。然后修改新产生的 segment 的指针指向并将其插入链表中，代码如下所示：

public Segment split(int byteCount) {
    // 参数范围校验
    if (byteCount <= 0 || byteCount > limit - pos) throw new IllegalArgumentException();
    
    // 拆分出来的新 segment
    Segment prefix; 
    if (byteCount >= SHARE_MINIMUM) {
      // 共享 segment
      prefix = new Segment(this);
    } else {
      // 非共享 segment
      prefix = SegmentPool.take();
      System.arraycopy(data, pos, prefix.data, 0, byteCount);
    }

    prefix.limit = prefix.pos + byteCount;
    pos += byteCount;
    prev.push(prefix);
    return prefix;
}

上面代码中如果拆分出来的新 segment 走的是共享 segment 分支代码，那么拆分后新的 segment 和原来的 segment 在数据结构上是共享的，也就是两者的数据都存放在同一个 final byte[] data 中，两者不同的只是读取指针 pos 和写入指针 limit 的位置，如下图所示：

10 | Android 高级进阶(源码剖析篇) Square

segment

链表操作

segment 的拆分

猜你喜欢

热点阅读