OpenZeppelin庫是基于Solidity 0.8.0版本進(jìn)行分析。(https://docs.openzeppelin.com/contracts/4.x/)
首先EnumerableSet是一種數(shù)據(jù)結(jié)構(gòu)菱父，用來存儲(chǔ)數(shù)據(jù)摊溶，方便增刪改查的操作沪猴。
在Solidity語言中璃吧，key-value形式的mapping數(shù)據(jù)類型也支持增刪改查嫡纠，但是它的刪除只會(huì)將value設(shè)置成類型對(duì)應(yīng)的默認(rèn)值递沪。所以，要實(shí)現(xiàn)存儲(chǔ)的值真正意義上的刪除沫勿，需要借助數(shù)組來實(shí)現(xiàn)挨约。使用數(shù)組還可以獲取數(shù)組長(zhǎng)度（_length函數(shù)），檢查元素是否存在(_contains函數(shù))产雹，便于查找(_at函數(shù))诫惭，這些mapping都無法單獨(dú)實(shí)現(xiàn)。
于是蔓挖，其中就定義了一個(gè)結(jié)構(gòu)體Set夕土。
struct Set {
// Storage of set values
bytes32[] _values;
// Position of the value in the `values` array, plus 1 because index 0
// means a value is not in the set.
mapping(bytes32 => uint256) _indexes;
}
_values變量是一個(gè)字節(jié)數(shù)組用來存儲(chǔ)值，_indexes是一個(gè)mapping類型瘟判，用來記錄值在數(shù)組中的位置怨绣。
_indexes變量的key，bytes32是我們需要存儲(chǔ)的值拷获；_indexes變量的value篮撑，uint256就是value在數(shù)組中的索引位置。
add函數(shù)
// 存儲(chǔ)值value在數(shù)組中的位置是否為0刀诬，為0表示數(shù)組中不存在咽扇，否則數(shù)組中存在該value
function _contains(Set storage set, bytes32 value) private view returns (bool) {
return set._indexes[value] != 0;
}
// 新增
function _add(Set storage set, bytes32 value) private returns (bool) {
if (!_contains(set, value)) {
set._values.push(value);
// The value is stored at length-1, but we add 1 to all indexes
// and use 0 as a sentinel value
set._indexes[value] = set._values.length;
return true;
} else {
return false;
}
}
在_add函數(shù)中邪财，傳遞byte32類型的value參數(shù)陕壹。先檢查數(shù)組是否存儲(chǔ)過該值，已經(jīng)存儲(chǔ)返回false树埠，否則進(jìn)行存儲(chǔ)糠馆，返回true。
這里存儲(chǔ)使用了數(shù)組的push函數(shù)怎憋，同時(shí)在mapping類型的_indexes中記錄當(dāng)前數(shù)組的索引位置又碌，這里給的是數(shù)組的長(zhǎng)度。存儲(chǔ)一個(gè)值绊袋，索引位置就是1毕匀，每新增一個(gè)值，索引位置會(huì)依次累加癌别。這樣就實(shí)現(xiàn)了新增功能皂岔。
remove
function _remove(Set storage set, bytes32 value) private returns (bool) {
// We read and store the value's index to prevent multiple reads from the same storage slot
uint256 valueIndex = set._indexes[value];
if (valueIndex != 0) {
// Equivalent to contains(set, value)
// To delete an element from the _values array in O(1), we swap the element to delete with the last one in
// the array, and then remove the last element (sometimes called as 'swap and pop').
// This modifies the order of the array, as noted in {at}.
uint256 toDeleteIndex = valueIndex - 1;
uint256 lastIndex = set._values.length - 1;
if (lastIndex != toDeleteIndex) {
bytes32 lastValue = set._values[lastIndex];
// Move the last value to the index where the value to delete is
set._values[toDeleteIndex] = lastValue;
// Update the index for the moved value
set._indexes[lastValue] = valueIndex; // Replace lastValue's index to valueIndex
}
// Delete the slot where the moved value was stored
set._values.pop();
// Delete the index for the deleted slot
delete set._indexes[value];
return true;
} else {
return false;
}
}
_remove刪除函數(shù)的邏輯是，先找出要?jiǎng)h除value的索引位置展姐，這里的if判斷同樣是檢查數(shù)組中是否存在該值躁垛。
uint256 toDeleteIndex = valueIndex - 1;
uint256 lastIndex = set._values.length - 1;
toDeleteIndex和lastIndex的值為什么要減去1剖毯？
前面新增函數(shù)提到過，指定索引位置時(shí)數(shù)組的長(zhǎng)度教馆，由于數(shù)組的索引下標(biāo)是從0開始逊谋，所以這里需要減去1。
bytes32 lastValue = set._values[lastIndex];
// Move the last value to the index where the value to delete is
set._values[toDeleteIndex] = lastValue;
// Update the index for the moved value
set._indexes[lastValue] = valueIndex; // Replace lastValue's index to valueIndex
// 開始刪除
// Delete the slot where the moved value was stored
set._values.pop();
// Delete the index for the deleted slot
delete set._indexes[value];
這里是將要?jiǎng)h除的value和數(shù)組最后一個(gè)元素交換位置土铺，使用數(shù)組的pop函數(shù)胶滋，移除最后一個(gè)元素，這樣就實(shí)現(xiàn)了需要?jiǎng)h除指定的value悲敷。最后镀钓，再使用delete指令把mapping中記錄的索引位置刪除，會(huì)自動(dòng)設(shè)置為0镀迂，所以前面的_contains函數(shù)要判斷不等于0丁溅。
通過 _add 函數(shù)可以看出，EnumerableSet的value具有唯一性探遵，不可重復(fù)窟赏。
通過 _remove 函數(shù)可以看出，EnumerableSet無法保證數(shù)據(jù)存儲(chǔ)的順序性箱季。
at函數(shù) 查找
function _at(Set storage set, uint256 index) private view returns (bytes32) {
return set._values[index];
}
查找就很簡(jiǎn)單了涯穷，直接通過數(shù)組的 [ ] 方式來訪問。
length長(zhǎng)度
function _length(Set storage set) private view returns (uint256) {
return set._values.length;
}
獲取EnumerableSet的長(zhǎng)度藏雏，其實(shí)就是數(shù)組的長(zhǎng)度拷况。
以上函數(shù)都是private修飾，只允許在EnumerableSet內(nèi)訪問掘殴。所以赚瘦，我們?cè)谑褂玫臅r(shí)候并不能訪問這些函數(shù)，所以定義了三種類型的結(jié)構(gòu)體奏寨，Bytes32Set起意、AddressSet和UintSet共開發(fā)者使用；可以看出分別支持bytes32病瞳、address和uint三種基本類型揽咕。
// bytes32
struct Bytes32Set {
Set _inner;
}
// address
struct AddressSet {
Set _inner;
}
// uint
struct UintSet {
Set _inner;
}
同時(shí)分別對(duì)這三種結(jié)構(gòu)體做了add、remove套菜、at亲善、contains、length逗柴、values函數(shù)的重載蛹头。這些函數(shù)都是用了internal修飾，而不是private。
Bytes32Set
function add(Bytes32Set storage set, bytes32 value) internal returns (bool) {
return _add(set._inner, value);
}
function remove(Bytes32Set storage set, bytes32 value) internal returns (bool) {
return _remove(set._inner, value);
}
function contains(Bytes32Set storage set, bytes32 value) internal view returns (bool) {
return _contains(set._inner, value);
}
function length(Bytes32Set storage set) internal view returns (uint256) {
return _length(set._inner);
}
function at(Bytes32Set storage set, uint256 index) internal view returns (bytes32) {
return _at(set._inner, index);
}
function values(Bytes32Set storage set) internal view returns (bytes32[] memory) {
bytes32[] memory store = _values(set._inner);
bytes32[] memory result;
/// @solidity memory-safe-assembly
assembly {
result := store
}
return result;
}
add掘而、remove函數(shù)傳遞的參數(shù)是bytes32類型挟冠，Bytes32Set類型的變量set調(diào)用了_inner屬性；即set._inner袍睡。
set._inner其實(shí)就是一個(gè)Set結(jié)構(gòu)知染，傳遞到_add和_remove函數(shù)中，并且_add和_remove函數(shù)接收的value參數(shù)正好是byte32類型斑胜。所以控淡，Bytes32Set類型在函數(shù)調(diào)用處理value時(shí)不需要進(jìn)行類型轉(zhuǎn)換。
然而止潘，AddressSet和UintSet則不一樣掺炭，他們需要進(jìn)行類型轉(zhuǎn)換，將address和uint基本類型轉(zhuǎn)換成bytes32類型才能調(diào)用_add和_remove函數(shù)凭戴。
AddressSet
function add(AddressSet storage set, address value) internal returns (bool) {
return _add(set._inner, bytes32(uint256(uint160(value))));
}
function remove(AddressSet storage set, address value) internal returns (bool) {
return _remove(set._inner, bytes32(uint256(uint160(value))));
}
function at(AddressSet storage set, uint256 index) internal view returns (address) {
return address(uint160(uint256(_at(set._inner, index))));
}
這里重點(diǎn)關(guān)注下類型轉(zhuǎn)換涧狮，將address類型轉(zhuǎn)換成byte32類型、將byte32類型轉(zhuǎn)換成address類型么夫。
address -> bytes32
add和remove函數(shù)在調(diào)用_add和_remove函數(shù)時(shí)者冤，需要傳遞bytes32類型，所以這里需要對(duì)address類型進(jìn)行轉(zhuǎn)換档痪。
- uint160(value)：由于address類型的長(zhǎng)度是20個(gè)字節(jié)涉枫，也就是160位，所以先轉(zhuǎn)成了uint160腐螟。
- uint256(uint160(value))：由于bytes32是32字節(jié)愿汰，256位，所以用uint256做了一次轉(zhuǎn)換乐纸。
- bytes32(uint256(uint160(value)))：最后將uint256類型轉(zhuǎn)換成bytes32類型衬廷。
byte32 ->address
觀察at函數(shù)的返回值 return address(uint160(uint256(_at(set._inner, index)))); 把bytes32轉(zhuǎn)換成address。
- _at(set._inner, index) 返回值是bytes32類型锯仪，256位泵督，所以需要uint256進(jìn)行轉(zhuǎn)換。
- uint256(_at(set._inner, index)) address類型20字節(jié)庶喜，160位，需要uint160進(jìn)行轉(zhuǎn)換救鲤。
- uint160(uint256(_at(set._inner, index))) uint160直接轉(zhuǎn)換成address類型即可久窟。
- address(uint160(uint256(_at(set._inner, index))))。
UintSet
function add(UintSet storage set, uint256 value) internal returns (bool) {
return _add(set._inner, bytes32(value));
}
function remove(UintSet storage set, uint256 value) internal returns (bool) {
return _remove(set._inner, bytes32(value));
}
function at(UintSet storage set, uint256 index) internal view returns (uint256) {
return uint256(_at(set._inner, index));
}
UintSet同AddressSet一樣本缠，需要進(jìn)行類型轉(zhuǎn)換斥扛，不過轉(zhuǎn)換步驟要簡(jiǎn)單很多。
uint256 -> bytes32
add和remove函數(shù)接收參數(shù)是uint256類型，uint256和bytes32類型都是256位稀颁，所以直接轉(zhuǎn)換就行芬失，bytes32(value)
bytes32-> uint256
這里同理，直接轉(zhuǎn)換即可匾灶。
總結(jié)
- EnumerableSet具有元素?zé)o序性棱烂、唯一性。
- 類型不同時(shí)阶女，需要進(jìn)行類型轉(zhuǎn)換颊糜。
- 查找元素時(shí)，沒有使用for循環(huán)秃踩，效率高衬鱼。
思考
- 為什么不實(shí)現(xiàn)一個(gè)修改的函數(shù)？
// Move the last value to the index where the value to delete is
set._values[toDeleteIndex] = lastValue;
從_remove函數(shù)的實(shí)現(xiàn)來看憔杨，要實(shí)現(xiàn)修改其實(shí)也是可以的鸟赫，通過傳參value查找mapping中記錄的索引位置，再通過數(shù)組訪問索引位置消别，重新賦值即可惯疙。
為什么源碼庫沒有實(shí)現(xiàn)這個(gè)修改操作呢？
- Solidity中有很多基礎(chǔ)數(shù)據(jù)類型妖啥，uint8霉颠、uint120、int16荆虱、bytes20等等蒿偎，而EnumerableSet僅僅支持bytes32、address和uint256三種基礎(chǔ)數(shù)據(jù)類型怀读。這些數(shù)據(jù)類型應(yīng)該如何使用EnumerableSet的一些函數(shù)呢诉位？
也許通過類型轉(zhuǎn)換，轉(zhuǎn)換成EnumerableSet需要的類型就能滿足要求了菜枷。 - 從EnumerableSet名字可以看出苍糠，為什么是Set？是否與Java中Set相似啤誊？
也許是因?yàn)閿?shù)據(jù)存儲(chǔ)的無序性岳瞭，不能保證數(shù)據(jù)存儲(chǔ)順序的一致性，所以命名為EnumerableSet蚊锹。
