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)
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 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!
![[Web front-end] Node.js quick start](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
