Use the Linked List to achieve a FIFO access.

[Skyge]

🧐 Motivation
A FIFO access with Linked List in the Solidity.

📝 Details
In my problem, there exists such a situation: I want to store an array structure, such as

    struct PlayerInfo{
        address _account;
        uint256 _ownAmount;
    }

Because I want to push the newest, and pop the oldest,
so there may be an array to store their sequence, such as

   PlayerInfo[] public players;

In my project, recording order is essential.
but when we push in some elements and pop out some elements, we will find that
the first half of the array is empty. so just like in an Array List, in order to use space efficiently,
we would move the second half of the array to the empty position,
such like this:

    for (uint256 i = 1; i <= _length-1; i++) {
        players[i-1] = players[i];
     }
    delete players[_length-1];
    players.length--;

ok, now you will understand what I want to achieve, a FIFO access,
and according to @nventuro 's advice,
it could be a circular buffer.
(thanks for @nventuro at here!),
but we all know that, every operation in the EVM will cost some gas,
so it should be better to achieve by Linked List,
because it can remove element efficiently,
and this is what I want to find out, because I really would run the function of delete() frequently.
So now the problem comes out, how to achieve a Linked List in the Solidity?

And what I need likes this:

    uint256 private _total;
		
    struct PlayerInfo{
    address _account;
    uint256 _ownAmount;
    }

    PlayerInfo[] public players;
	
    /// @dev This should be equal to push an element in the array list.
    function addPlayer(address _sender, uint256 _count) public onlyOwner returns (bool) {}

    /// @dev This should be equal to pop an element in the array list.
    function removePlayer() public onlyOwner returns (bool) {}

    /// @dev This should be equal to delete an element in the linked list.
    function removePlayerByAddress(address _toRemove) public onlyOwner returns (bool) {}

[Skyge]

I thought for a while, and I realize a key point, I want to remove elements by their order,
but why do I must use an array to record, I can make some changes in the struct, such as:

    struct PlayerInfo{
        uint256 _ownAmount;
        address _account;
        address _lastAddress;
        address _nextAddress;
    }

then I can record their sequence without an array, so I should write like:

    mapping(address => PlayerInfo) players;

So all modified code should be:

    address public _currentAddress;
    address public _toRemoveAddress;
    uint256 public _total;
    
    struct PlayerInfo{
        uint256 _ownAmount;
        address _account;
        address _lastAddress;
        address _nextAddress;
    }
    
    mapping(address => PlayerInfo) public players;

    /// @dev This is equal to push an element in the array list.
    function addPlayer(address _account, uint256 _amount) public  returns (bool) {
        if (_total == 0) {
            _toRemoveAddress = _account;
        }else {
            players[_currentAddress]._nextAddress = _account;
        }
        
        players[_account] = PlayerInfo(_amount, _account, _currentAddress, address(0));
        _currentAddress = _account;
        _total = _total + 1;
    }

    /// @dev This is equal to pop an element in the array list.
    function removePlayer() public  returns (bool) {
        address _temp = players[_toRemoveAddress]._nextAddress;
        delete players[_toRemoveAddress];
        players[_temp]._lastAddress = address(0);
        _toRemoveAddress = _temp;
    }

    /// @dev This is equal to delete an element in the linked list.
    function removePlayerByAddress(address _toDelete) public  returns (bool) {
        address _tempLast = players[_toDelete]._lastAddress;
        address _tempNext = players[_toDelete]._nextAddress;
        
        delete players[_toDelete];
        players[_tempLast]._nextAddress = _tempNext;
        players[_tempNext]._lastAddress = _tempLast;
    }

[Skyge]

OK, please just give me some advice, and I will make a standard code
with the version 0.5.x later.

[nventuro]

Hey there @Skyge, thanks for opening this! I know @ElOpio has read lots of awful array-management code while conducting security audits, perhaps you could share some of your learnings and common requirements here?

[Skyge]

Ok, I will think my requirements seriously, and then share it.

[come-maiz]

The biggest problem here is the lack of generics in solidity. This means that if we implement a list for uint256, we will have to implement another one for addresses, and another one for your custom struct.
I think most of our efforts should go towards that first: ethereum/solidity#869

[nventuro]

I don't think Solidity will be adding support for generics soon, and would like to at least get an initial implementation for common types, like uint256 and address. A FIFO queue implemented using a circular buffer with read and write indexes sounds like an appropriate MVP for this.

[frangio]

We should implement for address only IMO.

I thought this issue was about linked lists? I don't understand how a circular buffer would work in the EVM where it's not possible (and not reasonable?) to "lock" until a slot in the buffer is available.

[frangio]

I think linked lists would be a useful structure to have in the EVM but the motivation in this issue is not the right one.

It's not necessary to use space efficiently in the EVM because there is effectively an infinit amount of it. A FIFO queue can be implemented by a dynamic array in storage. Rearranging elements is not necessary because you can assume that there is infinit room to grow the array.

[nventuro]

Heh, I got carried away with the circular buffer idea.

An array-based FIFO is definitely possible and cheaper in the EVM: we'd just need a read index to read elements (which are deleted, but are still in the array), writing is simply arr.push(). Note that this means that the length of the queue is not arr.lenght but arr.lenght - read_idx.

[Skyge]

It's not necessary to use space efficiently in the EVM because there is effectively an infinit amount of it. A FIFO queue can be implemented by a dynamic array in storage. Rearranging elements is not necessary because you can assume that there is infinit room to grow the array.

I am not sure, in my opinion, if I do not recycle space, I think it will be a little weird, because when we delete the first element in an array, array[0] still exists, but its value becomes undefined, so maybe when I try to update an element in the array, I should add a extra requirement require(array[index]!=address(0)), so I think it is a little weird and I want to recycle space.

[Skyge]

An array-based FIFO is definitely possible and cheaper in the EVM: we'd just need a read index to read elements (which are deleted, but are still in the array), writing is simply arr.push(). Note that this means that the length of the queue is not arr.lenght but arr.lenght - read_idx.

Yeah, maybe we can try it in this way.

[nventuro]

so I think it is a little weird and I want to recycle space.

You do get the recycling of space, since you zero-out the slot. This is roughly what I (and I think @frangio) mean (untested!):

contract FIFO {
  address[] private _array;
  uint256 private _read;

  function push(address value) public {
    _array.push(value);
  }

  function pop() public returns (uint256) {
    require(_read < _array.length);

    uin256 value = _array[_read];
    delete(_array[_read]);
    _read += 1;

    return value;
  }

  function length() public view returns (uint256) { 
   return _array.length - _read;
  }
}

[Skyge]

I become a little confused, you said

since you zero-out the slot.

Just like your code, I call pop() to delete the first element, the value of _array[0] change from a specific value to address(0), so although I can still call _array[0], but it does not use any space, does it?

[nventuro]

On the EVM, all storage slots exist (they can be read from and written to), and are initialized with 0. Nodes simply keep track of which ones have been written with a non-zero value, and delete slots from that list when you write zero to them. It is because of this that changing a value from zero to non-zero is more expensive than from non-zero to non-zero, and why changing it back to zero refunds gas.

[Skyge]

Oh, I see, thanks for your explanation.

[nventuro]

@Skyge I think this issue is larger than simply coding a FIFO queue, since e.g. even if we did it for address, it wouldn't be useful for you and your custom data structure. I opened a post in the forum to discuss this and other ideas, come take a look! Closing the issue to continue discussion there.

[Skyge]

OK

[Skyge]

Hi, @nventuro I can not find the post in the forum, so do we delete it?

[frangio]

@Skyge It had been deleted but I think it was an accident. I have restored it now. Apologies.