Detailed analysis of the List type of Immutable.js source code (with examples)

This article brings you a detailed analysis of the List type of Immutable.js source code (with examples). It has certain reference value. Friends in need can refer to it. I hope it will be helpful to you.

1. Storage Diagram

I use the following code as an example to draw the storage structure of this List:

let myList = [];
for(let i=0;i<p><span class="img-wrap"><img src="https://img.php.cn//upload/image/772/741/819/1543214651133724.png" title="1543214651133724.png" alt="Detailed analysis of the List type of Immutable.js source code (with examples)"></span></p><p><strong>2. The construction process of vector trie</strong></p><p>We use the above code as an example to analyze step by step. The first is to convert the native list into an inmutable list type: </p><pre class="brush:php;toolbar:false">export class List extends IndexedCollection {
  // @pragma Construction

  constructor(value) { // 此时的value就是上面的myList数组
    const empty = emptyList();
    if (value === null || value === undefined) {//判断是否为空
      return empty;
    }
    if (isList(value)) {//判断是否已经是imutable的list类型
      return value;
    }
    const iter = IndexedCollection(value);//序列化数组
    const size = iter.size;
    if (size === 0) {
      return empty;
    }
    assertNotInfinite(size);
    if (size > 0 && size  {
      list.setSize(size);
      iter.forEach((v, i) => list.set(i, v));
    });
  }

  。。。。。。

}

First, an empty list will be created

let EMPTY_LIST;
export function emptyList() {
  return EMPTY_LIST || (EMPTY_LIST = makeList(0, 0, SHIFT));
}

The value of SHIFT is 5, export const SHIFT = 5; // Resulted in best performance after ______?

Continue to look at makeList, you can clearly see the main part of the List:

function makeList(origin, capacity, level, root, tail, ownerID, hash) {
  const list = Object.create(ListPrototype);
  list.size = capacity - origin;// 数组的长度
  list._origin = origin;// 数组的起始位置 一般是0
  list._capacity = capacity;// 数组容量 等于 size
  list._level = level;//树的深度，为0时是叶子结点。默认值是5，存储指数部分，用于方便位运算,增加一个深度，level值+5
  list._root = root;// trie树实现
  list._tail = tail;// 32个为一组，存放最后剩余的数据 其实就是 %32
  list.__ownerID = ownerID;
  list.__hash = hash;
  list.__altered = false;
  return list;
}

Serialize the incoming data

// ArraySeq
iter = {
size: 数组的length,
_array: 传入数组的引用
}

Determine whether the size exceeds 32, size > 0 && size

_root and _tail have the following structure:

// @VNode class
constructor(array, ownerID) {
  this.array = array;
  this.ownerID = ownerID;
}

You can debug and view it like this:

let myList = [];
for(let i=0;i<p>size if it exceeds 32</p><pre class="brush:php;toolbar:false">return empty.withMutations(list => {
    list.setSize(size);//构建树的结构 主要是计算出树的深度
    iter.forEach((v, i) => list.set(i, v));//填充好数据
});

export function withMutations(fn) {
  const mutable = this.asMutable();
  fn(mutable);
  return mutable.wasAltered() ? mutable.__ensureOwner(this.__ownerID) : this;
}

list. There is an important method setListBounds in setSize(size). Below we will mainly look at how this method builds this tree

The main function of this method is to determine the level of the list

function setListBounds(list, begin, end) {

  ......
  
  const newTailOffset = getTailOffset(newCapacity);

  // New size might need creating a higher root.
  // 是否需要增加数的深度 把 1 左移 newLevel + SHIFT 位 相当于 1 * 2 ^ (newLevel + SHIFT)
  // 以 size为 1100 为例子 newTailOffset的值为1088 第一次 1088 > 2 ^ 10 树增加一层深度
  // 第二次 1088 = 1 <pre class="brush:php;toolbar:false">function getTailOffset(size) {
    // (1100 - 1) / 2^5 % 2^5 = 1088
    return size >> SHIFT) <p>through the list. setSize(size);The constructed structure</p><p><span class="img-wrap"><img src="https://img.php.cn//upload/image/732/311/566/1543214714320046.png" title="1543214714320046.png" alt="Detailed analysis of the List type of Immutable.js source code (with examples)"></span></p><p><strong>3. set method</strong></p><p>listiter.forEach( (v, i) => list.set(i, v));Here is to fill the _array in iter to </p><p>The main thing here is to see how the set method sets the data</p><pre class="brush:php;toolbar:false">set(index, value) {
    return updateList(this, index, value);
}

function updateList(list, index, value) {
  ......
  if (index >= getTailOffset(list._capacity)) {
    newTail = updateVNode(newTail, list.__ownerID, 0, index, value, didAlter);
  } else {
    newRoot = updateVNode(
      newRoot,
      list.__ownerID,
      list._level,
      index,
      value,
      didAlter
    );
  }

  ......

}

function updateVNode(node, ownerID, level, index, value, didAlter) {
  // 根据 index 和 level 计算 数据set的位置在哪
  const idx = (index >>> level) & MASK;

  // 利用递归 一步一步的寻找位置 直到找到最终的位置
  if (level > 0) {
    const lowerNode = node && node.array[idx];
    const newLowerNode = updateVNode(
      lowerNode,
      ownerID,
      level - SHIFT,
      index,
      value,
      didAlter
    );
    ......
    // 把node节点的array复制一份生成一个新的节点newNode editableVNode函数见下面源码
    newNode = editableVNode(node, ownerID);
    // 回溯阶段将 子节点的引用赋值给自己
    newNode.array[idx] = newLowerNode;
    return newNode;
  }
  ......
  newNode = editableVNode(node, ownerID);
  // 当递归到叶子节点 也就是level <pre class="brush:php;toolbar:false">function editableVNode(node, ownerID) {
  if (ownerID && node && ownerID === node.ownerID) {
    return node;
  }
  return new VNode(node ? node.array.slice() : [], ownerID);
}

Let’s take a look at the results of running set(0,0)

##After the entire structure is constructed

Let's take a look at the list set (1000, 'Remm') we just built. In fact, the source code of all sets has been parsed above. We Let’s review again.

Call the set method above, index=1000, value='Remm'. Call updateList, then call updateVNode. Calculate the position of the node you are looking for by const idx = (index >>> level) & MASK; (in this example, the values ​​of idx are 0->31->8). Continuous recursive search, when level Updated list:

4. Get method

Complete understanding The above list construction and set, let's look at the source code of immutableList.get(1000) is a piece of cake.

  get(index, notSetValue) {
    index = wrapIndex(this, index);
    if (index >= 0 && index <pre class="brush:php;toolbar:false">function listNodeFor(list, rawIndex) {
  if (rawIndex >= getTailOffset(list._capacity)) {
    return list._tail;
  }
  if (rawIndex  0) {
      // 循环查找节点所在位置
      node = node.array[(rawIndex >>> level) & MASK];
      level -= SHIFT;
    }
    return node;
  }
}

5. Advantages of Tire Tree

Here is a picture stolen from the Internet:

The data structure of this tree (tire tree) ensures that the number of copy references is reduced to a minimum, that is, through extreme methods, the number of copies is greatly reduced. For an object with 1 million attributes, shallow copying is required The assignment is 999,999 times. In the tire tree, according to the depth of its access, only one level only needs to be copied 31 times. This number does not increase as the object attributes increase. As the level goes deeper, the number of copies will increase linearly. However, since the object access depth will not be particularly high, 10 levels are almost invisible. Therefore, the maximum number of copies can be 300 times, which is still very fast.

The situations I analyzed above include construction, modification, and query. In fact, there are also add and delete.

The above is the detailed content of Detailed analysis of the List type of Immutable.js source code (with examples). For more information, please follow other related articles on the PHP Chinese website!