Skip to content

Latest commit

 

History

History
755 lines (609 loc) · 25.7 KB

智能合约库_基础类型_数组解读.md

File metadata and controls

755 lines (609 loc) · 25.7 KB
Raw

智能合约库之基础类型——一维数组类型合约的解读

分析任何工程，小到一把小刀:knife:，大到一座大桥:bridge_at_night:。无一都是先从整体结构进行剖析，逐个击破来认识。今天，我们就从数组合约的解读启航吧！！！

启航前的一些前提条件：

  • 具备高级语言的相关基础知识，C/C++,java,python,go,c#等；
  • 需要了解一些简单的数据结构算法；
  • 需要有一些基本的solidity语法知识。

智能合约开源地址：SmartDev-Contract/contracts/base_type/array at master · WeBankBlockchain/SmartDev-Contract (github.com)

我们就像读一篇优秀的文章一样，先来认识一下它的结构：

智能合约之数组类型的代码结构

总共三个4个文件，演示用例2个，核心实现文件2个。依赖关系如下：

文件依赖关系

从文件名上区分出：一个是一维数组的相关实现，一个是二维数组的相关实现。

 
pragma solidity ^0.4.25;

import "./LibSafeMathForUint256Utils.sol";

library LibArrayForUint256Utils {

	//在array数组里，二分搜索出key（查询）。
	function binarySearch(uint256[] storage array, uint256 key) internal view returns (bool, uint) {
        if(array.length == 0){
        	return (false, 0);
        }

        uint256 low = 0;
        uint256 high = array.length-1;

        while(low <= high){
        	uint256 mid = LibSafeMathForUint256Utils.average(low, high);
        	if(array[mid] == key){
        		return (true, mid);
        	}else if (array[mid] > key) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }

        return (false, 0);
    }
	//在array数组里，寻找出key出现的第一个位置【从前往后】
    function firstIndexOf(uint256[] storage array, uint256 key) internal view returns (bool, uint256) {

    	if(array.length == 0){
    		return (false, 0);
    	}

    	for(uint256 i = 0; i < array.length; i++){
    		if(array[i] == key){
    			return (true, i);
    		}
    	}
    	return (false, 0);
    }
	//将array数组进行反转。
    function reverse(uint256[] storage array) internal {
        uint256 temp;
        for (uint i = 0; i < array.length / 2; i++) {
            temp = array[i];
            array[i] = array[array.length - 1 - i];
            array[array.length - 1 - i] = temp;
        }
    }
	//数组a与数组b是否相等。
    function equals(uint256[] storage a, uint256[] storage b) internal view returns (bool){
    	if(a.length != b.length){
    		return false;
    	}
    	for(uint256 i = 0; i < a.length; i++){
    		if(a[i] != b[i]){
    			return false;
    		}
    	}
    	return true;
    }
	//在数组array中，移除掉index上对应的元素【硬删除】
    function removeByIndex(uint256[] storage array, uint index) internal{
    	require(index < array.length, "ArrayForUint256: index out of bounds");

        while (index < array.length - 1) {
            array[index] = array[index + 1];
            index++;
        }
        array.length--;
    }
    //在数组array中，移除掉元素为value的【硬删除】
    function removeByValue(uint256[] storage array, uint256 value) internal{
        uint index;
        bool isIn;
        (isIn, index) = firstIndexOf(array, value);
        if(isIn){
          removeByIndex(array, index);
        }
    }
	//在数组的末尾追加元素value。
    function addValue(uint256[] storage array, uint256 value) internal{
    	uint index;
        bool isIn;
        (isIn, index) = firstIndexOf(array, value);
        if(!isIn){
        	array.push(value);
        }
    }
	//复制数组b里面的所有元素到a数组里边。
    function extend(uint256[] storage a, uint256[] storage b) internal {
    	if(b.length != 0){
    		for(uint i = 0; i < b.length; i++){
    			a.push(b[i]);
    		}
    	}
    }
	//去除array数组里边的重复元素
    function distinct(uint256[] storage array) internal returns (uint256 length) {
        bool contains;
        uint index;
        for (uint i = 0; i < array.length; i++) {
            contains = false;
            index = 0;
            uint j = i+1;
            for(;j < array.length; j++){
                if(array[j] == array[i]){
                    contains =true;
                    index = i;
                    break;
                }
            }
            if (contains) {
                for (j = index; j < array.length - 1; j++){
                    array[j] = array[j + 1];
                }
                array.length--;
                i--;
            }
        }
        length = array.length;
    }
	//对数组进行快排。
    function qsort(uint256[] storage array) internal {
        qsort(array, 0, array.length-1);
    }

    function qsort(uint256[] storage array, uint256 begin, uint256 end) private {
        if(begin >= end || end == uint256(-1)) return;
        uint256 pivot = array[end];

        uint256 store = begin;
        uint256 i = begin;
        for(;i<end;i++){
            if(array[i] < pivot){
                uint256 tmp = array[i];
                array[i] = array[store];
                array[store] = tmp;
                store++;
            }
        }

        array[end] = array[store];
        array[store] = pivot;

        qsort(array, begin, store-1);
        qsort(array, store+1, end);
    }
	//找出数组中最大的元素
    function max(uint256[] storage array) internal view returns (uint256 maxValue, uint256 maxIndex) {
        maxValue = array[0];
        maxIndex = 0;
        for(uint256 i = 0;i < array.length;i++){
            if(array[i] > maxValue){
                maxValue = array[i];
                maxIndex = i;
            }
        }
    }

	//找出数组中最小的元素
    function min(uint256[] storage array) internal view returns (uint256 minValue, uint256 minIndex) {
        minValue = array[0];
        minIndex = 0;
        for(uint256 i = 0;i < array.length;i++){
            if(array[i] < minValue){
                minValue = array[i];
                minIndex = i;
            }
        }
    }

}

我们先将这些函数列举出来：

  • binarySearch(uint256[] storage array, uint256 key) //在array数组里，二分搜索出key（查询）。
  • firstIndexOf(uint256[] storage array, uint256 key) //在array数组里，寻找出key出现的第一个位置【从前往后】
  • reverse(uint256[] storage array)//将array数组进行反转。
  • equals(uint256[] storage a, uint256[] storage b)//数组a与数组b是否相等。
  • removeByIndex(uint256[] storage array, uint index)
  • addValue(uint256[] storage array, uint256 value)
  • extend(uint256[] storage a, uint256[] storage b)
  • distinct(uint256[] storage array)
  • qsort(uint256[] storage array)
  • qsort(uint256[] storage array, uint256 begin, uint256 end) private
  • max(uint256[] storage array)
  • min(uint256[] storage array)

binarySearch二分查找

首先，讲解一下这个binarySearch(uint256[] storage array, uint256 key)，参数需要一个数组和一个目标值key，数组类型属性被storage修饰，它的意思是接受一个存储状态变量（链上变量）。大白话就是，这个变量是一个指针（引用），可以对他进行修改。

关于二分法，分为两种。一种是上述代码所描述的查找，另一种是二分出来的边界。对于后者，这个属于算法方面的，在这里不去对它进行论述，我们讲解前者即二分查找。

二分查找一个最基本的前提是，要求数组里面的元素是按照升序，降序的规则已经预处理好的。然后不断的求其中间下标的元素与目标key值进行比较，来看之间的大小关系，按照升序/降序的规则，来逐个砍掉另一半（不满足要求的，换言之，在这里永远找不到目标key），直到找到目标key为止。

给一张图片，帮助理解下：

二分查找

红色的方块，就是我们要找的key值，我们趁着茶还没凉，对这一块的代码进行讲解。

function binarySearch(uint256[] storage array, uint256 key) internal view returns (bool, uint) {
        if(array.length == 0){
        	return (false, 0);
        }

        uint256 low = 0;
        uint256 high = array.length-1;

        while(low <= high){
        	uint256 mid = LibSafeMathForUint256Utils.average(low, high);
        	if(array[mid] == key){
        		return (true, mid);
        	}else if (array[mid] > key) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }

        return (false, 0);
    }
  1. 长度是否为0的判断，这个表明了数组array里边是否存在元素；
  2. 定义了2个变量（哨兵）low和high，两者都从数组的两端开始；
  3. 在while循环中，我们要保证两个哨兵不能错位。
    1. 求出两个哨兵的中间值，作为low或high的下一个位置；
    2. 判断它们与key之间的关系，这个决定了low和high的位置，mid+1，mid-1就是说array[mid]这个值不符合要求了，需要将它从里边剔除掉，还有一个因素是，由于数组是从0开始的，mid-1的操作，并不会把array[mid-1]这个位置上符合key的元素值剔除。
  4. 直到找到为止。

时间复杂度和空间复杂度这方面，做个简要的分析吧，因为对智能合约来说也相当重要

时间复杂度：由于每次都是折半操作，均摊下来的话，就是一个二叉搜索树，时间复杂度上是O(log n)【n=array.length】；

空间复杂度：这里没有涉及到额外空间（memory创建的数组等）即O(1)。

firstIndexOf找出第一次出现的位置

function firstIndexOf(uint256[] storage array, uint256 key) internal view returns (bool, uint256) {

    	if(array.length == 0){
    		return (false, 0);
    	}

    	for(uint256 i = 0; i < array.length; i++){
    		if(array[i] == key){
    			return (true, i);
    		}
    	}
    	return (false, 0);
    }

对于这块代码，我想都不陌生。

  1. 检测数组的长度是否!=0；
  2. 循环比较，找到与key相等的，返回目标索引。

reverse反转

	//将array数组进行反转。
    function reverse(uint256[] storage array) internal {
        uint256 temp;
        for (uint i = 0; i < array.length / 2; i++) {
            temp = array[i];
            array[i] = array[array.length - 1 - i];
            array[array.length - 1 - i] = temp;
        }
    }

这段代码就是把数组做了个反转，[1,3,2,6]反转为[6,2,3,1]

  1. 一个临时变量temp，用于做交换的备份变量。

  2. 从arrary.length/2中间的位置开始，这个其实就是数组中间位置反转之后是不会变化的。那么/2操作，在数组长度为偶数的情况下，就会有疑惑，这个疑惑可以不必在意，且听我说。

    1. 奇数情况：/2的情况下，由于长度为uint，那么它就会下取整，比如长度为5的数组[1,3,2,6,0]，下取整的下标就是2，刚好是中间位置。在这里，array.length/2刚好到[5]也就停止了，并且完成了交换的操作。

    2. 偶数情况：/2后，刚好会落到数组中间位置右边的元素，比如[1,3,2,6]，那就是[2]，在数组的中间线后边。对于这种情况，还没完成呢，就把[x,3,2,x]中的[3,2]交换为[2,3]，然后i到达array.length/2停止了，这是刚刚好的。

      我们设mid=array.length/2，存在一个i和j(array.length - 1 - i)在mid的两边，交换需要保证i≤mid≤j

      在进行交换时，有i=array.length-1-i，mid-i = (array.length-1-i)-mid = 0,且(mid-i>=0,j-mid>=0)这个前提，对于数组长度为偶数的情况，有mid-i<0，j-mid<0这个情况。做个不等式的转换有:mid<i ，j>mid，与i≤mid≤j矛盾，因此，不存在它俩错位交换的情况。

时间复杂度：O(n/2)

空间复杂度：O(1)

equals数组是否相等

  function equals(uint256[] storage a, uint256[] storage b) internal view returns (bool){
    	if(a.length != b.length){
    		return false;
    	}
    	for(uint256 i = 0; i < a.length; i++){
    		if(a[i] != b[i]){
    			return false;
    		}
    	}
    	return true;
    }
  1. 两个数组长度不同，必然不相等；
  2. 两个数组在长度相同的条件下，存在一个元素不同，不然不同。

removeByIndex移除index对应的元素

 function removeByIndex(uint256[] storage array, uint index) internal{
    	require(index < array.length, "ArrayForUint256: index out of bounds");

        while (index < array.length - 1) {
            array[index] = array[index + 1];
            index++;
        }
        array.length--;
    }
  1. index确保在数组长度的范围之内；
  2. 将index后边的元素逐个覆盖前边的，最后长度-1，达到移除；

removeByValue移除掉value第一个出现的位置

function removeByValue(uint256[] storage array, uint256 value) internal{
        uint index;
        bool isIn;
        (isIn, index) = firstIndexOf(array, value);
        if(isIn){
          removeByIndex(array, index);
        }
    }
  1. 调用了firstIndexOf()函数查找value的位置，最后调用removeByIndex()传入下标移除。

addValue不重复添加元素

function addValue(uint256[] storage array, uint256 value) internal{
    	uint index;
        bool isIn;
        (isIn, index) = firstIndexOf(array, value);
        if(!isIn){
        	array.push(value);
        }
    }
  1. 调用了firstIndexOf()查找出元素出现的位置，以及是否出现isIn；
  2. 根据isIn是否为假（value不存在）来决定往array中push新的元素。

extend复制数组b的所有元素到数组a

function extend(uint256[] storage a, uint256[] storage b) internal {
	if(b.length != 0){
		for(uint i = 0; i < b.length; i++){
			a.push(b[i]);
		}
	}
}
  1. 确保数组b在存在元素的情况下，将b数组中的每一个都放入到a中。

distinct去重

 function distinct(uint256[] storage array) internal returns (uint256 length) {
        bool contains;
        uint index;
        for (uint i = 0; i < array.length; i++) {
            contains = false;
            index = 0;
            uint j = i+1;
            for(;j < array.length; j++){
                if(array[j] == array[i]){
                    contains =true;
                    index = i;
                    break;
                }
            }
            if (contains) {
                for (j = index; j < array.length - 1; j++){
                    array[j] = array[j + 1];
                }
                array.length--;
                i--;
            }
        }
        length = array.length;
    }

  1. i与j错开，即j在i的后边，然后判断array[i]与array[j]的元素是否相同；

  2. 将contains标记设为true，并将这个array[j]与array[i]相同的元素，从j+1开始往前覆盖，之后长度-1，i-1因为当前array[i]可能是一个新的元素；

  3. 最后返回去重后的数组长度。

qsort快排

 function qsort(uint256[] storage array, uint256 begin, uint256 end) private {
        if(begin >= end || end == uint256(-1)) return;
        uint256 pivot = array[end];

        uint256 store = begin;
        uint256 i = begin;
        for(;i<end;i++){
            if(array[i] < pivot){
                uint256 tmp = array[i];
                array[i] = array[store];
                array[store] = tmp;
                store++;
            }
        }

        array[end] = array[store];
        array[store] = pivot;

        qsort(array, begin, store-1);
        qsort(array, store+1, end);
    }

快排是排序算法的一种，思想就是利用了递归的思想。

快速排序

从图片上看到key=2作为轴值，不断的与low(begin)和high(end)进行对比，然后按照规则把它放到对应的位置，并移动该位置上的下标，重合时，就是key=2的合适位置。

  1. 首先确保给定的begin和end是否满足条件，如果不满足，这个数组默认是不合法的，因为我们后续都要在这两个变量上做手脚；
  2. pivot备份了最后一个元素的值，i和store两个从begin开始的变量；
  3. 在for循环中确保没有达到end边界处的条件下，判断array[i]值是否小于当前阶段的目标值pivot。如果小于就对其进行交换，大于的话则不交换，在经过一轮循环之后，store会找到一个轴值pivot在当前阶段所在的合适位置，并把array[store]之前的值放在pivot所在的位置；
  4. 之后对它们的两边进行递归操作，直到把所有的array[store]找到合适的位置即完成排序。

max最大值

 function max(uint256[] storage array) internal view returns (uint256 maxValue, uint256 maxIndex) {
        maxValue = array[0];
        maxIndex = 0;
        for(uint256 i = 0;i < array.length;i++){
            if(array[i] > maxValue){
                maxValue = array[i];
                maxIndex = i;
            }
        }
    }
  1. 经过一轮循环，将找到一个最大值，并返回对应的下标。

min最小值

function min(uint256[] storage array) internal view returns (uint256 minValue, uint256 minIndex) {
        minValue = array[0];
        minIndex = 0;
        for(uint256 i = 0;i < array.length;i++){
            if(array[i] < minValue){
                minValue = array[i];
                minIndex = i;
            }
        }
    }
  1. 经过一轮循环，将找到一个最小值，并返回对应的下标。

到这里就结束了，关于参数为storage，就是避免了在传参过程中solidity的虚拟机EVM对数组进行复制，产生不必要的时间消耗和空间占用。

智能合约库之基础类型——二维数组类型合约的解读

趁热打铁，我们将难度提上一提，讲解下二维数组库合约的实现。

// SPDX-License-Identifier: Apache-2.0
pragma solidity >=0.4.25;
/**
* @author wpzczbyqy <[email protected]>
* @title  uint256类型 二维数组操作
* 提供二维数组的操作，增加新元素，删除元素，修改值，查找值，合并扩展数组等
**/

library Lib2DArrayForUint256 {
    /**
    *@dev 二维数组中增加一个数组元素
    *@param  array uint256类型二维数组
    *@param  value uint256类型一维数组
    **/
    function addValue(uint256[][] storage array,uint256[] memory value) internal{
        require(value.length > 0, "Empty Array: can not add empty array");
        array.push(value);
    }

    /**
    *@dev    查找二维数组中指定位置的值
    *@param  array uint256类型二维数组
    *@param  row   值所在的行
    *@param  col   值所在的列
    *@return uint256 返回查找的值
    **/
    function getValue(uint256[][] storage array, uint256 row, uint256 col) internal view returns (uint256) {
        if(array.length == 0){
            return 0;
        }
        require(row < array.length,"Row: index out of bounds");
        require(col < array[row].length, "Col: index out of bounds");
        return array[row][col];
    }

    /**
    *@dev    修改二维数组中指定位置的值
    *@param  array uint256类型二维数组
    *@param  row   值所在的行
    *@param  col   值所在的列
    *@param  val   修改指定位置的值为val
    *@return uint256[][] 返回修改后的数组
    **/
    function setValue(uint256[][] storage array, uint256 row, uint256 col, uint256 val) internal returns (uint256[][] memory) {
        require(array.length > 0, "Array is empty");
        require(row < array.length, "Row: index out of bounds");
        require(col < array[row].length, "Col: index out of bounds");
        
        array[row][col] = val;
        return array;
    }

    /**
    *@dev    查找二维数组array第一个值为val的元素索引
    *@param  array uint256类型二维数组
    *@param  val   要查找的值
    *@return  bool   是否查找得到
    *@return uint256 找到的元素一维下标
    *@return uint256 找到的元素二维下标
    **/
    function firstIndexOf(uint256[][] storage array, uint256 val) internal view returns (bool, uint256, uint256) {
        uint256 row;
        uint256 col;
        if (array.length == 0) {
            return (false, 0, 0);
        }
        for(uint256 i = 0; i < array.length; i++) {
            for(uint256 j = 0; j < array[i].length; j++) {
                if(array[i][j] == val){
                    row = i;
                    col = j;
                    return (true, row, col);
                }
            }
        }
        return (false, 0, 0);
    }

    /**
    *@dev    删除二维数组中的某个数组元素
    *@param  array uint256类型二维数组
    *@param  index 删除第index个数组元素
    *@return uint256[][] 返回修改后的数组
    **/
    function removeByIndex(uint256[][] storage array, uint256 index) internal returns(uint256[][] memory) {
        require(index < array.length, "Index: index out of bounds");
    
        uint256 lastIndex = array.length - 1;
        for (uint256 i = index; i < lastIndex; i++) {
            array[i] = array[i + 1];
        }

        // 删除数组的最后一个元素
        // solidity 0.6.0以下
        // delete array[lastIndex];
        // array.length --;

        // solidity 0.6.0及以上(0.6.0时动态数组的长度是只读的，并且数组引入了pop()方法)
        array.pop();

        return array;
    }

    /**
    *@dev    合并两个二维数组
    *@param  array1 uint256类型二维数组
    *@param  array2 uint256类型二维数组
    *@return uint256[][] 返回合并后的数组
    **/
    function extend(uint256[][] storage array1, uint256[][] storage array2) internal returns(uint256[][] memory){
        require(array2.length > 0, "Extend: can not extend empty array");

        for(uint256 i = 0; i < array2.length; i++){
            array1.push(array2[i]);
        }
        return array1;
    }
}

还是同样的，我们先把库函数的合约函数列举一下：

  • addValue(uint256[][] storage array,uint256[] memory value)
  • getValue(uint256[][] storage array, uint256 row, uint256 col)
  • setValue(uint256[][] storage array, uint256 row, uint256 col, uint256 val)
  • firstIndexOf(uint256[][] storage array, uint256 val)
  • removeByIndex(uint256[][] storage array, uint256 index)
  • extend(uint256[][] storage array1, uint256[][] storage array2)

addValue（盖一层楼）向二维数组中添加一个数组元素

    function addValue(uint256[][] storage array,uint256[] memory value) internal{
        require(value.length > 0, "Empty Array: can not add empty array");
        array.push(value);
    }
  1. 确保“新盖的一层楼是实实在在的”；
  2. 将其动态押入到array里边去。

getValue 通过给定的行和列，查找对应的值

  function getValue(uint256[][] storage array, uint256 row, uint256 col) internal view returns (uint256) {
        if(array.length == 0){
            return 0;
        }
        require(row < array.length,"Row: index out of bounds");
        require(col < array[row].length, "Col: index out of bounds");
        return array[row][col];
    }
  1. 做好相关的安全性检查，返回对应的行列值。

setValue在对应的行列处设置值

    function setValue(uint256[][] storage array, uint256 row, uint256 col, uint256 val) internal returns (uint256[][] memory) {
        require(array.length > 0, "Array is empty");
        require(row < array.length, "Row: index out of bounds");
        require(col < array[row].length, "Col: index out of bounds");
        
        array[row][col] = val;
        return array;
    }
  1. 做好相关的安全性检查，设置对应的行列值。

firstIndexOf查找元素出现的第一个位置

  function firstIndexOf(uint256[][] storage array, uint256 val) internal view returns (bool, uint256, uint256) {
        uint256 row;
        uint256 col;
        if (array.length == 0) {
            return (false, 0, 0);
        }
        for(uint256 i = 0; i < array.length; i++) {
            for(uint256 j = 0; j < array[i].length; j++) {
                if(array[i][j] == val){
                    row = i;
                    col = j;
                    return (true, row, col);
                }
            }
        }
        return (false, 0, 0);
    }
  1. array.length==0的判断是确保数组array里边非空；
  2. 逐行逐列的对二维数组进行值搜索；
  3. 返回目标。

removeByIndex基于下标删除子数组

 function removeByIndex(uint256[][] storage array, uint256 index) internal returns(uint256[][] memory) {
        require(index < array.length, "Index: index out of bounds");
        uint256 lastIndex = array.length - 1;
        for (uint256 i = index; i < lastIndex; i++) {
            array[i] = array[i + 1];
        }
        array.pop();
        return array;
    }
  1. 确保删除的子数组下标在array.length范围内，之后后者覆盖前者，达到删除目的。

extend合并两个二维数组

function extend(uint256[][] storage array1, uint256[][] storage array2) internal returns(uint256[][] memory){
        require(array2.length > 0, "Extend: can not extend empty array");

        for(uint256 i = 0; i < array2.length; i++){
            array1.push(array2[i]);
        }
        return array1;
    }
  1. 在检查待合并的数组不是空数组合法后，将array2合并到array1中。