OpenZeppelin庫DoubleEndedQueue數(shù)據(jù)結(jié)構(gòu)的分析

顧名思義DoubleEndedQueue是一個隊列，是一個雙端隊列。
雙端隊列是一種抽象數(shù)據(jù)類型，它概括了一個隊列，其中的元素可以從前(頭) 或后(尾) 添加或刪除。 因此也經(jīng)常被稱為首尾鏈表。
用Solidity語言如何來實現(xiàn)一個雙端隊列呢？

分析源碼可知，定義了一個結(jié)構(gòu)體Bytes32Deque。其中聲明了一個mapping(int128 => byte32)類型的變量_data；還聲明了兩個int128類型的變量_begin和_end。_begin和_end作為mapping的key使用。

mapping類型中的byte32可以理解，因為值類型的數(shù)據(jù)都可以經(jīng)過類型轉(zhuǎn)換得到byte32類型的數(shù)據(jù)。

為什么_begin和_end要定義成int128類型呢？
// 查詢首尾元素時，隊列為空拋出該錯誤
error Empty();
// 通過元素在隊列中的位置查詢元素時，檢查越界問題
error OutOfBounds();

// _begin隊列頭，_end隊列位，作為mapping的key使用。
// mapping 存儲數(shù)據(jù)
struct Bytes32Deque {
        int128 _begin;
        int128 _end;
        mapping(int128 => bytes32) _data;
    }

通過_begin和_end的類型可以分析出，對列的最大長度是uint256。
因為_begin到_end的長度就是兩個int128，所以最大長度則是uint256。
這里要注意int128包含正數(shù)和負數(shù)，也就意味著mapping的key可以為負數(shù)和正數(shù)。

雙端隊列的特性是支持頭尾插入、刪除。下面我們分析下如何實現(xiàn)頭尾插入和刪除。

頭尾插入元素

/**  隊列尾插入元素
     * @dev Inserts an item at the end of the queue.
     */
    function pushBack(Bytes32Deque storage deque, bytes32 value) internal {
        // 獲取當前隊列尾的位置，再直接存儲值
        int128 backIndex = deque._end;
        deque._data[backIndex] = value;
        unchecked {
            // 加1，更新隊列尾的位置
            deque._end = backIndex + 1;
        }
    }

    /** 隊列頭插入元素
     * @dev Inserts an item at the beginning of the queue.
     */
    function pushFront(Bytes32Deque storage deque, bytes32 value) internal {
        int128 frontIndex;
        unchecked {
            // 頭插入，找到當前頭的位置，在減去 1
            frontIndex = deque._begin - 1; 
        }
        // 存儲值
        deque._data[frontIndex] = value;
        // 更新隊列頭的位置
        deque._begin = frontIndex;
    }

pushBack函數(shù)是從隊列末尾插入元素。先獲取當前隊列尾的位置，再直接存儲值，最后加1更新_end。
pushFront函數(shù)是從隊列頭部插入元素。先找到當前頭的位置，減去 1，再存儲值，最后更新_begin。

由于_begin和_end都是int128類型，所以默認值都是0。pushBack函數(shù)在進行尾插入是從0開始，依次遞增，占用正數(shù)段；而pushFront頭插入是從-1開始，依次遞減，占用負數(shù)段。

頭尾刪除元素

 /**   檢查隊列是否為空，只對首尾位置進行判斷，并未操作mapping
     * @dev Returns true if the queue is empty.
     */
    function empty(Bytes32Deque storage deque) internal view returns (bool) {
        return deque._end <= deque._begin;
    }

/**   隊列尾刪除元素
     * @dev Removes the item at the end of the queue and returns it.
     *
     * Reverts with `Empty` if the queue is empty.
     */
    function popBack(Bytes32Deque storage deque) internal returns (bytes32 value) {
        if (empty(deque)) revert Empty();
        int128 backIndex;
        unchecked {
            // 這里減1，因為 每次隊列尾插入后，會先加1再更新_end的值，意味著在有效范圍內(nèi)，隊列最后一個位置沒有元素。
            // 這里需要先減去1，獲取到最后一個元素的位置
            backIndex = deque._end - 1;
        }
        // 從mapping中取值，并返回
        value = deque._data[backIndex];
        // 刪除mapping中的該值
        delete deque._data[backIndex];
        // 更新末尾位置
        deque._end = backIndex;
    }

 /**   隊列頭刪除元素
     * @dev Removes the item at the beginning of the queue and returns it.
     *
     * Reverts with `Empty` if the queue is empty.
     */
    function popFront(Bytes32Deque storage deque) internal returns (bytes32 value) {
        if (empty(deque)) revert Empty();
        // 隊列頭插入時，更新begin時，存在元素，這里不需要加減 1
        int128 frontIndex = deque._begin;
        // 從mapping獲取元素，并返回
        value = deque._data[frontIndex];
        // 刪除mapping中該元素
        delete deque._data[frontIndex];
        unchecked {
            // 更新頭部的位置，因為刪除了隊列的第一個元素，又因頭插入占用的是負數(shù)段，所以頭部位置需要加 1。
            deque._begin = frontIndex + 1;
        }
    }

popBack函數(shù)是從隊列末尾刪除元素。先校驗空隊列，再進行刪除，最后更新末尾位置?？梢钥吹絙ackIndex的 值是由_end減去1得來，這里減1，因為每次隊列尾插入后，會先加1再更新_end的值，意味著在有效范圍內(nèi)，隊列最后一個位置沒有元素。

popFront函數(shù)是從隊列頭部刪除元素。同樣是先校驗空隊列，在獲取frontIndex的值時，沒有進行減1操作。最后在更新_begin時，做了加1操作，因為刪除了隊列的第一個元素，又因頭插入占用的是負數(shù)段，所以頭部位置需要加 1。例如，隊列頭部_begin的值是 -10，刪除一個元素后，_begin的值應(yīng)更新為 -9。

查詢首尾元素

/**
     * @dev Returns the item at the beginning of the queue.
     *
     * Reverts with `Empty` if the queue is empty.
     */
    function front(Bytes32Deque storage deque) internal view returns (bytes32 value) {
        if (empty(deque)) revert Empty();
        int128 frontIndex = deque._begin;
        return deque._data[frontIndex];
    }

    /**
     * @dev Returns the item at the end of the queue.
     *
     * Reverts with `Empty` if the queue is empty.
     */
    function back(Bytes32Deque storage deque) internal view returns (bytes32 value) {
        if (empty(deque)) revert Empty();
        int128 backIndex;
        unchecked {
            backIndex = deque._end - 1;
        }
        return deque._data[backIndex];
    }

front函數(shù)是獲取隊列頭第一個元素。
back函數(shù)是獲取隊列最后一個元素。backIndex = deque._end - 1; 這里還是那個原理，隊列尾插入后，更新_end時做了加1操作。

根據(jù)隊列位置查詢元素

/**
     * @dev Return the item at a position in the queue given by `index`, with the first item at 0 and last item at
     * `length(deque) - 1`.
     *
     * Reverts with `OutOfBounds` if the index is out of bounds.
     */
    function at(Bytes32Deque storage deque, uint256 index) internal view returns (bytes32 value) {
        // int256(deque._begin) is a safe upcast
        // 入?yún)㈩愋褪?uint256，必須先轉(zhuǎn)換成 int256
       // _begin要與index求和，所以_begin的類型是int128，也必須向上轉(zhuǎn)換成 int256
      // idx是 _begin到_end之間的值
        int128 idx = SafeCast.toInt128(int256(deque._begin) + SafeCast.toInt256(index));
        if (idx >= deque._end) revert OutOfBounds();
        return deque._data[idx];
    }

    // SafeCast.sol
    function toInt128(int256 value) internal pure returns (int128 downcasted) {
        downcasted = int128(value);
        require(downcasted == value, "SafeCast: value doesn't fit in 128 bits");
    }

    function toInt256(uint256 value) internal pure returns (int256) {
        // Note: Unsafe cast below is okay because `type(int256).max` is guaranteed to be positive
        require(value <= uint256(type(int256).max), "SafeCast: value doesn't fit in an int256");
        return int256(value);
    }

at函數(shù)不太好理解，里面用到了一個類型轉(zhuǎn)換工具SafeCast。我們先看at函數(shù)的傳參，傳遞的是uint256，這里為什么需要傳uint256類型呢？
前面我們已經(jīng)提到過，隊列的最大長度是uint256，這里的index取值范圍就是 0 到 type(uint256).max。
index表示，要查詢隊列中哪一個位置的元素。
index = 0，要查詢隊列第一個元素
index = 1，要查詢隊列第二個元素
index = 2，要查詢隊列第三個元素
.....
.....
所以，index只能是uint類型，不可能是int類型。隊列最大長度是兩個int128，所以參數(shù)只能是uint256。
在計算idx時，指定的類型是int128，idx也就是_begin到_end的取值范圍。最后做了一個越界的驗證。

SafeCast.toInt128(int256(deque._begin) + SafeCast.toInt256(index)); 將 _begin 由 int128 轉(zhuǎn)換成 int256，將 index 由 uint256 轉(zhuǎn)換成 int256；二者求和，最后再將和由 int256 轉(zhuǎn)換成 int128 類型。

這里為什么要進行這么多的類型轉(zhuǎn)換？
原因還得從函數(shù)的入?yún)㈩愋秃妥罱K需要的類型是什么說起，入?yún)⑹?uint256，最終需要的是 int128。所以，入?yún)ndex必須要進行類型轉(zhuǎn)換將uint類型轉(zhuǎn)換成int類型，所以就有了SafeCast.toInt256(index)。

_begin本身就是int128類型,為什么也需要進行轉(zhuǎn)換呢？
因為要講_begin 與 index求和，類型必須要統(tǒng)一。index的類型現(xiàn)在是 int256 ，所以 _begin也必須由 int128 類型向上轉(zhuǎn)換成 int256 類型。

最后SafeCast.toInt128就是再將和的類型轉(zhuǎn)換成需要的int128類型。

為什么要對_begin和index求和？
因為_begin是隊列的開始位置。例如要_begin = -2，index傳入的值是1，查詢隊列第一個位置的元素，mapping的key也就是 -1，_begin 與 index 之和就是 -1。

清空隊列

function clear(Bytes32Deque storage deque) internal {
        deque._begin = 0;
        deque._end = 0;
    }

清空隊列很簡單，將開始位置和結(jié)束位置設(shè)置為默認值0，并沒有對mapping內(nèi)部的元素進行刪除操作。

隊列長度

function length(Bytes32Deque storage deque) internal view returns (uint256) {
        // The interface preserves the invariant that begin <= end so we assume this will not overflow.
        // We also assume there are at most int256.max items in the queue.
        unchecked {
            return uint256(int256(deque._end) - int256(deque._begin));
        }
    }

隊列長度就是_end減去_begin。這里類型轉(zhuǎn)換是因為長度是uint256類型，_end和_begin都是int128類型，所以需要進行類型轉(zhuǎn)換。

總結(jié)

  1. 只能從頭或者尾依次添加或刪除元素，無法從中間某個位置刪除或添加。
  2. 可以方便快速地獲取頭尾位置的元素。
  3. 遵循FIFO原則。
  4. 使用時應(yīng)使用storage，不能使用memery。

思考：

  1. 前面我們分析_begin的值是負數(shù)段，那隊列的頭部位置_begin的值可以是大于0的數(shù)嗎？
    創(chuàng)建Bytes32Deque對象時，設(shè)置_begin的默認值大于0。
  2. 清空隊列為什么不刪除元素？
    gas費用問題。
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容