Skip to content

Latest commit

 

History

History
911 lines (692 loc) · 24.8 KB

SortedTroves.md

File metadata and controls

911 lines (692 loc) · 24.8 KB

SortedTroves.sol

View Source: contracts/SortedTroves.sol

↗ Extends: SortedTrovesStorage, CheckContract, ISortedTroves

SortedTroves

Events

event TroveManagerAddressChanged(address  _troveManagerAddress);
event BorrowerOperationsAddressChanged(address  _borrowerOperationsAddress);
event NodeAdded(address  _id, uint256  _NICR);
event NodeRemoved(address  _id);

Functions

setParams

function setParams(uint256 _size, address _troveManagerAddress, address _borrowerOperationsAddress) external nonpayable onlyOwner

Arguments

Name Type Description
_size uint256
_troveManagerAddress address
_borrowerOperationsAddress address
Source Code 
function setParams(uint256 _size, address _troveManagerAddress, address _borrowerOperationsAddress) external override onlyOwner {
        require(_size > 0, "SortedTroves: Size can’t be zero");
        checkContract(_troveManagerAddress);
        checkContract(_borrowerOperationsAddress);

        data.maxSize = _size;

        troveManager = ITroveManager(_troveManagerAddress);
        borrowerOperationsAddress = _borrowerOperationsAddress;

        emit TroveManagerAddressChanged(_troveManagerAddress);
        emit BorrowerOperationsAddressChanged(_borrowerOperationsAddress);

    }

insert

Add a node to the list

function insert(address _id, uint256 _NICR, address _prevId, address _nextId) external nonpayable

Arguments

Name Type Description
_id address Node's id
_NICR uint256 Node's NICR
_prevId address Id of previous node for the insert position
_nextId address Id of next node for the insert position
Source Code 
nction insert (address _id, uint256 _NICR, address _prevId, address _nextId) external override {
        ITroveManager troveManagerCached = troveManager;

        _requireCallerIsBOorTroveM(troveManagerCached);
        _insert(troveManagerCached, _id, _NICR, _prevId, _nextId);
    }

_insert

function _insert(ITroveManager _troveManager, address _id, uint256 _NICR, address _prevId, address _nextId) internal nonpayable

Arguments

Name Type Description
_troveManager ITroveManager
_id address
_NICR uint256
_prevId address
_nextId address
Source Code 
nction _insert(ITroveManager _troveManager, address _id, uint256 _NICR, address _prevId, address _nextId) internal {
        // List must not be full
        require(!isFull(), "SortedTroves: List is full");
        // List must not already contain node
        require(!contains(_id), "SortedTroves: List already contains the node");
        // Node id must not be null
        require(_id != address(0), "SortedTroves: Id cannot be zero");
        // NICR must be non-zero
        require(_NICR > 0, "SortedTroves: NICR must be positive");

        address prevId = _prevId;
        address nextId = _nextId;

        if (!_validInsertPosition(_troveManager, _NICR, prevId, nextId)) {
            // Sender's hint was not a valid insert position
            // Use sender's hint to find a valid insert position
            (prevId, nextId) = _findInsertPosition(_troveManager, _NICR, prevId, nextId);
        }

         data.nodes[_id].exists = true;

        if (prevId == address(0) && nextId == address(0)) {
            // Insert as head and tail
            data.head = _id;
            data.tail = _id;
        } else if (prevId == address(0)) {
            // Insert before `prevId` as the head
            data.nodes[_id].nextId = data.head;
            data.nodes[data.head].prevId = _id;
            data.head = _id;
        } else if (nextId == address(0)) {
            // Insert after `nextId` as the tail
            data.nodes[_id].prevId = data.tail;
            data.nodes[data.tail].nextId = _id;
            data.tail = _id;
        } else {
            // Insert at insert position between `prevId` and `nextId`
            data.nodes[_id].nextId = nextId;
            data.nodes[_id].prevId = prevId;
            data.nodes[prevId].nextId = _id;
            data.nodes[nextId].prevId = _id;
        }

        data.size = data.size.add(1);
        emit NodeAdded(_id, _NICR);
    }

remove

function remove(address _id) external nonpayable

Arguments

Name Type Description
_id address
Source Code 
nction remove(address _id) external override {
        _requireCallerIsTroveManager();
        _remove(_id);
    }

_remove

Remove a node from the list

function _remove(address _id) internal nonpayable

Arguments

Name Type Description
_id address Node's id
Source Code 
nction _remove(address _id) internal {
        // List must contain the node
        require(contains(_id), "SortedTroves: List does not contain the id");

        if (data.size > 1) {
            // List contains more than a single node
            if (_id == data.head) {
                // The removed node is the head
                // Set head to next node
                data.head = data.nodes[_id].nextId;
                // Set prev pointer of new head to null
                data.nodes[data.head].prevId = address(0);
            } else if (_id == data.tail) {
                // The removed node is the tail
                // Set tail to previous node
                data.tail = data.nodes[_id].prevId;
                // Set next pointer of new tail to null
                data.nodes[data.tail].nextId = address(0);
            } else {
                // The removed node is neither the head nor the tail
                // Set next pointer of previous node to the next node
                data.nodes[data.nodes[_id].prevId].nextId = data.nodes[_id].nextId;
                // Set prev pointer of next node to the previous node
                data.nodes[data.nodes[_id].nextId].prevId = data.nodes[_id].prevId;
            }
        } else {
            // List contains a single node
            // Set the head and tail to null
            data.head = address(0);
            data.tail = address(0);
        }

        delete data.nodes[_id];
        data.size = data.size.sub(1);
        NodeRemoved(_id);
    }

reInsert

Re-insert the node at a new position, based on its new NICR

function reInsert(address _id, uint256 _newNICR, address _prevId, address _nextId) external nonpayable

Arguments

Name Type Description
_id address Node's id
_newNICR uint256 Node's new NICR
_prevId address Id of previous node for the new insert position
_nextId address Id of next node for the new insert position
Source Code 
nction reInsert(address _id, uint256 _newNICR, address _prevId, address _nextId) external override {
        ITroveManager troveManagerCached = troveManager;

        _requireCallerIsBOorTroveM(troveManagerCached);
        // List must contain the node
        require(contains(_id), "SortedTroves: List does not contain the id");
        // NICR must be non-zero
        require(_newNICR > 0, "SortedTroves: NICR must be positive");

        // Remove node from the list
        _remove(_id);

        _insert(troveManagerCached, _id, _newNICR, _prevId, _nextId);
    }

contains

Checks if the list contains a node

function contains(address _id) public view
returns(bool)

Arguments

Name Type Description
_id address
Source Code 
nction contains(address _id) public view override returns (bool) {
        return data.nodes[_id].exists;
    }

isFull

Checks if the list is full

function isFull() public view
returns(bool)
Source Code 
nction isFull() public view override returns (bool) {
        return data.size == data.maxSize;
    }

isEmpty

Checks if the list is empty

function isEmpty() public view
returns(bool)
Source Code 
nction isEmpty() public view override returns (bool) {
        return data.size == 0;
    }

getSize

Returns the current size of the list

function getSize() external view
returns(uint256)
Source Code 
nction getSize() external view override returns (uint256) {
        return data.size;
    }

getMaxSize

Returns the maximum size of the list

function getMaxSize() external view
returns(uint256)
Source Code 
nction getMaxSize() external view override returns (uint256) {
        return data.maxSize;
    }

getFirst

Returns the first node in the list (node with the largest NICR)

function getFirst() external view
returns(address)
Source Code 
nction getFirst() external view override returns (address) {
        return data.head;
    }

getLast

Returns the last node in the list (node with the smallest NICR)

function getLast() external view
returns(address)
Source Code 
nction getLast() external view override returns (address) {
        return data.tail;
    }

getNext

Returns the next node (with a smaller NICR) in the list for a given node

function getNext(address _id) external view
returns(address)

Arguments

Name Type Description
_id address Node's id
Source Code 
nction getNext(address _id) external view override returns (address) {
        return data.nodes[_id].nextId;
    }

getPrev

Returns the previous node (with a larger NICR) in the list for a given node

function getPrev(address _id) external view
returns(address)

Arguments

Name Type Description
_id address Node's id
Source Code 
nction getPrev(address _id) external view override returns (address) {
        return data.nodes[_id].prevId;
    }

validInsertPosition

Check if a pair of nodes is a valid insertion point for a new node with the given NICR

function validInsertPosition(uint256 _NICR, address _prevId, address _nextId) external view
returns(bool)

Arguments

Name Type Description
_NICR uint256 Node's NICR
_prevId address Id of previous node for the insert position
_nextId address Id of next node for the insert position
Source Code 
nction validInsertPosition(uint256 _NICR, address _prevId, address _nextId) external view override returns (bool) {
        return _validInsertPosition(troveManager, _NICR, _prevId, _nextId);
    }

_validInsertPosition

function _validInsertPosition(ITroveManager _troveManager, uint256 _NICR, address _prevId, address _nextId) internal view
returns(bool)

Arguments

Name Type Description
_troveManager ITroveManager
_NICR uint256
_prevId address
_nextId address
Source Code 
nction _validInsertPosition(ITroveManager _troveManager, uint256 _NICR, address _prevId, address _nextId) internal view returns (bool) {
        if (_prevId == address(0) && _nextId == address(0)) {
            // `(null, null)` is a valid insert position if the list is empty
            return isEmpty();
        } else if (_prevId == address(0)) {
            // `(null, _nextId)` is a valid insert position if `_nextId` is the head of the list
            return data.head == _nextId && _NICR >= _troveManager.getNominalICR(_nextId);
        } else if (_nextId == address(0)) {
            // `(_prevId, null)` is a valid insert position if `_prevId` is the tail of the list
            return data.tail == _prevId && _NICR <= _troveManager.getNominalICR(_prevId);
        } else {
            // `(_prevId, _nextId)` is a valid insert position if they are adjacent nodes and `_NICR` falls between the two nodes' NICRs
            return data.nodes[_prevId].nextId == _nextId &&
                   _troveManager.getNominalICR(_prevId) >= _NICR &&
                   _NICR >= _troveManager.getNominalICR(_nextId);
        }
    }

_descendList

Descend the list (larger NICRs to smaller NICRs) to find a valid insert position

function _descendList(ITroveManager _troveManager, uint256 _NICR, address _startId) internal view
returns(address, address)

Arguments

Name Type Description
_troveManager ITroveManager TroveManager contract, passed in as param to save SLOAD’s
_NICR uint256 Node's NICR
_startId address Id of node to start descending the list from
Source Code 
tion _descendList(ITroveManager _troveManager, uint256 _NICR, address _startId) internal view returns (address, address) {
        // If `_startId` is the head, check if the insert position is before the head
        if (data.head == _startId && _NICR >= _troveManager.getNominalICR(_startId)) {
            return (address(0), _startId);
        }

        address prevId = _startId;
        address nextId = data.nodes[prevId].nextId;

        // Descend the list until we reach the end or until we find a valid insert position
        while (prevId != address(0) && !_validInsertPosition(_troveManager, _NICR, prevId, nextId)) {
            prevId = data.nodes[prevId].nextId;
            nextId = data.nodes[prevId].nextId;
        }

        return (prevId, nextId);
    }

_ascendList

Ascend the list (smaller NICRs to larger NICRs) to find a valid insert position

function _ascendList(ITroveManager _troveManager, uint256 _NICR, address _startId) internal view
returns(address, address)

Arguments

Name Type Description
_troveManager ITroveManager TroveManager contract, passed in as param to save SLOAD’s
_NICR uint256 Node's NICR
_startId address Id of node to start ascending the list from
Source Code 
on _ascendList(ITroveManager _troveManager, uint256 _NICR, address _startId) internal view returns (address, address) {
        // If `_startId` is the tail, check if the insert position is after the tail
        if (data.tail == _startId && _NICR <= _troveManager.getNominalICR(_startId)) {
            return (_startId, address(0));
        }

        address nextId = _startId;
        address prevId = data.nodes[nextId].prevId;

        // Ascend the list until we reach the end or until we find a valid insertion point
        while (nextId != address(0) && !_validInsertPosition(_troveManager, _NICR, prevId, nextId)) {
            nextId = data.nodes[nextId].prevId;
            prevId = data.nodes[nextId].prevId;
        }

        return (prevId, nextId);
    }

findInsertPosition

Find the insert position for a new node with the given NICR

function findInsertPosition(uint256 _NICR, address _prevId, address _nextId) external view
returns(address, address)

Arguments

Name Type Description
_NICR uint256 Node's NICR
_prevId address Id of previous node for the insert position
_nextId address Id of next node for the insert position
Source Code 
on findInsertPosition(uint256 _NICR, address _prevId, address _nextId) external view override returns (address, address) {
        return _findInsertPosition(troveManager, _NICR, _prevId, _nextId);
    }

_findInsertPosition

function _findInsertPosition(ITroveManager _troveManager, uint256 _NICR, address _prevId, address _nextId) internal view
returns(address, address)

Arguments

Name Type Description
_troveManager ITroveManager
_NICR uint256
_prevId address
_nextId address
Source Code 
on _findInsertPosition(ITroveManager _troveManager, uint256 _NICR, address _prevId, address _nextId) internal view returns (address, address) {
        address prevId = _prevId;
        address nextId = _nextId;

        if (prevId != address(0)) {
            if (!contains(prevId) || _NICR > _troveManager.getNominalICR(prevId)) {
                // `prevId` does not exist anymore or now has a smaller NICR than the given NICR
                prevId = address(0);
            }
        }

        if (nextId != address(0)) {
            if (!contains(nextId) || _NICR < _troveManager.getNominalICR(nextId)) {
                // `nextId` does not exist anymore or now has a larger NICR than the given NICR
                nextId = address(0);
            }
        }

        if (prevId == address(0) && nextId == address(0)) {
            // No hint - descend list starting from head
            return _descendList(_troveManager, _NICR, data.head);
        } else if (prevId == address(0)) {
            // No `prevId` for hint - ascend list starting from `nextId`
            return _ascendList(_troveManager, _NICR, nextId);
        } else if (nextId == address(0)) {
            // No `nextId` for hint - descend list starting from `prevId`
            return _descendList(_troveManager, _NICR, prevId);
        } else {
            // Descend list starting from `prevId`
            return _descendList(_troveManager, _NICR, prevId);
        }
    }

_requireCallerIsTroveManager

function _requireCallerIsTroveManager() internal view
Source Code 
on _requireCallerIsTroveManager() internal view {
        require(msg.sender == address(troveManager), "SortedTroves: Caller is not the TroveManager");
    }

_requireCallerIsBOorTroveM

function _requireCallerIsBOorTroveM(ITroveManager _troveManager) internal view

Arguments

Name Type Description
_troveManager ITroveManager
Source Code 
on _requireCallerIsBOorTroveM(ITroveManager _troveManager) internal view {
        require(msg.sender == borrowerOperationsAddress || msg.sender == address(_troveManager),
                "SortedTroves: Caller is neither BO nor TroveM");
    }
}

Contracts