Skip to content

Latest commit

 

History

History
490 lines (419 loc) · 15.4 KB

EnumerableAddressSet.md

File metadata and controls

490 lines (419 loc) · 15.4 KB
Raw

EnumerableAddressSet.sol

View Source: contracts/mixins/EnumerableAddressSet.sol

EnumerableAddressSet contract

Based on Library for managing https://en.wikipedia.org/wiki/Set_(abstract_data_type)[sets] of primitive types.

  • Sets have the following properties:
    • Elements are added, removed, and checked for existence in constant time (O(1)).
  • Elements are enumerated in O(n). No guarantees are made on the ordering.
  • As of v2.5.0, only address sets are supported.
  • Include with using EnumerableSet for EnumerableSet.AddressSet;.
  • Available since v2.5.0.

Structs

AddressSet

struct AddressSet {
 mapping(address => uint256) index,
 address[] values
}

Functions

add

Add a value to a set. O(1). Returns false if the value was already in the set.

function add(struct EnumerableAddressSet.AddressSet set, address value) internal nonpayable
returns(bool)

Arguments

Name Type Description
set struct EnumerableAddressSet.AddressSet
value address
Source Code 
function add(AddressSet storage set, address value) internal returns (bool) {
        if (!contains(set, value)) {
            set.index[value] = set.values.push(value);
            return true;
        } else {
            return false;
        }
    }

remove

Removes a value from a set. O(1). Returns false if the value was not present in the set.

function remove(struct EnumerableAddressSet.AddressSet set, address value) internal nonpayable
returns(bool)

Arguments

Name Type Description
set struct EnumerableAddressSet.AddressSet
value address
Source Code 
function remove(AddressSet storage set, address value) internal returns (bool) {
        if (contains(set, value)) {
            uint256 toDeleteIndex = set.index[value] - 1;
            uint256 lastIndex = set.values.length - 1;

            // If the element we're deleting is the last one, we can just remove it without doing a swap
            if (lastIndex != toDeleteIndex) {
                address lastValue = set.values[lastIndex];

                // Move the last value to the index where the deleted value is
                set.values[toDeleteIndex] = lastValue;
                // Update the index for the moved value
                set.index[lastValue] = toDeleteIndex + 1; // All indexes are 1-based
            }

            // Delete the index entry for the deleted value
            delete set.index[value];

            // Delete the old entry for the moved value
            set.values.pop();

            return true;
        } else {
            return false;
        }
    }

contains

Returns true if the value is in the set. O(1).

function contains(struct EnumerableAddressSet.AddressSet set, address value) internal view
returns(bool)

Arguments

Name Type Description
set struct EnumerableAddressSet.AddressSet
value address
Source Code 
function contains(AddressSet storage set, address value) internal view returns (bool) {
        return set.index[value] != 0;
    }

enumerate

Returns an array with all values in the set. O(N). Note that there are no guarantees on the ordering of values inside the array, and it may change when more values are added or removed. WARNING: This function may run out of gas on large sets: use {length} and {get} instead in these cases.

function enumerate(struct EnumerableAddressSet.AddressSet set) internal view
returns(address[])

Arguments

Name Type Description
set struct EnumerableAddressSet.AddressSet
Source Code 
function enumerate(AddressSet storage set) internal view returns (address[] memory) {
        address[] memory output = new address[](set.values.length);
        for (uint256 i; i < set.values.length; i++) {
            output[i] = set.values[i];
        }
        return output;
    }

enumerateChunk

Returns a chunk of array as recommended in enumerate() to avoid running of gas. Note that there are no guarantees on the ordering of values inside the array, and it may change when more values are added or removed. WARNING: This function may run out of gas on large sets: use {length} and {get} instead in these cases.

function enumerateChunk(struct EnumerableAddressSet.AddressSet set, uint256 start, uint256 count) internal view
returns(output address[])

Arguments

Name Type Description
set struct EnumerableAddressSet.AddressSet
start uint256 start index of chunk
count uint256 num of element to return; if count == 0 then returns all the elements from the
Source Code 
function enumerateChunk(
        AddressSet storage set,
        uint256 start,
        uint256 count
    ) internal view returns (address[] memory output) {
        uint256 end = start + count;
        require(end >= start, "addition overflow");
        end = (set.values.length < end || count == 0) ? set.values.length : end;
        if (end == 0 || start >= end) {
            return output;
        }

        output = new address[](end - start);
        for (uint256 i; i < end - start; i++) {
            output[i] = set.values[i + start];
        }
        return output;
    }

length

Returns the number of elements on the set. O(1).

function length(struct EnumerableAddressSet.AddressSet set) internal view
returns(uint256)

Arguments

Name Type Description
set struct EnumerableAddressSet.AddressSet
Source Code 
function length(AddressSet storage set) internal view returns (uint256) {
        return set.values.length;
    }

get

Returns the element stored at position index in the set. O(1). Note that there are no guarantees on the ordering of values inside the array, and it may change when more values are added or removed. * Requirements: * - index must be strictly less than {length}.

function get(struct EnumerableAddressSet.AddressSet set, uint256 index) internal view
returns(address)

Arguments

Name Type Description
set struct EnumerableAddressSet.AddressSet
index uint256
Source Code 
function get(AddressSet storage set, uint256 index) internal view returns (address) {
        return set.values[index];
    }

Contracts