Can we get all elements stored in a mapping in the contract using web3.js ?

up vote 34 down vote accepted

Mappings do not store their keys, only the value which is stored at the state memory address calculated by a sha3 hash of the the key itself. Any lookup into a mapping has to provide that original key or be able to calculate it.

This means that a contract has no way of discovering mapped data without assistance which can lead to orphaned data bloating the state database, particularly after a contract is selfdestructed.

I strongly believe that contract authors should be responsible in regards to garbage collection and write total discoverable data contracts in which all data can be discovered and deleted if and when required. For mappings, that requires key storage or calculation in some way or another.

Look Up Tables

The simplest pattern to key storage is a simple lookup table:

mapping (address => uint) public balances;
address[] public addressLUT;

// Requires a public getter for array size
function size() public returns (uint) {
    return addressLUT.length;
}

To which the associated JS could iterate across the whole mapping:

for(i = 0; i < k.size(); i++) {
    someFunc( k.balances(k.addressLUT(i)) );
}

One drawback with arrays is they can get gappy over time when elements are deleted. This can lead to unpredictable gas costs if a contract itself has to search through those gaps.

Linked List Indexes

Another approach is linked list indexes.

mapping (address => address) llIndex;
mapping (address => uint) public balances;

function add(address _addr) public 
{
    llIndex[_addr] = llIndex[0x0];
    llIndex[0x0] = _addr;
}

Here we insert address keys at llIndex[0x0] when we create a new balance. We can then iterate the entire balance mapping by stepping through the llIndex mapping starting a key 0x0 and given the first node points to 0x0 by default, we don't need a separate store for size bounding:

var current = k.llIndex(0);
while (current) {
    console.log( k.balances(current) );
    current = k.llIndex(current);
}

Link lists don't suffer the same potential gappiness as arrays and so don't waste machine cycles looking for valid data. However, deleting from a singular linked list does require a search to find the parent node.

function remove(address _addr) {
    address parent;

    // Warning: unbounded gas loop
    while (llIndex[parent] != _addr) parent = llIndex[parent];

    llIndex[parent] = llIndex[ llIndex[parent]];
    delete llIndex[_addr];
    delete balances[_addr];
}

This is fine when you're confident the data set won't grow to a size where a potential search uses unacceptable amounts of gas, or causes OOG altogether. Here 'unacceptable' is a bit subjective, so I'll quantify it with "more gas than the cost of a storage slot" which is 20000 for a new one and 5000 from the second and dealer ;).

Double Linked List indexes

In such cases it's worth removing search loops altogether at the expense of an extra storage slot per indexed element. For this we can use a Double Linked List index using a nested bool mapping for bidirectional links where we interpret PREV == false and NEXT == true):

mapping(address => ( mapping(bool => address) ) dllIndex;
mapping(address => uint) balances;

function add(address _addr)
{
    // Link the new node 
    dllIndex[_addr][PREV] = 0x0;
    dllIndex[_addr][NEXT] = dllIndex[0x0][NEXT];

    // Insert the new node
    dllIndex[dllIndex[0x0][NEXT]][PREV] = _addr;
    dllIndex[0x0][NEXT] = _addr;
}

function remove(address _addr)
{
    // Stitch the neighbours together
    dllIndex[ dllIndex[_addr][PREV] ][NEXT] = dllIndex[_addr][TRUE];
    dllIndex[ dllIndex[_addr][NEXT] ][PREV] = dllIndex[_addr][PREV];

    // Delete state storage
    delete dllIndex[_addr][PREV];
    delete dllIndex[_addr][NEXT];
    delete balances[_addr];
}

We now have a directly addressable and fully iterable storage structure, which is not just a Double Linked List but a Circular Double Linked List by default with the head at 0x0. This gives us two very desirable properties for free...

FIFO and FILO Queues

First In First Out (FIFO) and First In Last Out (FILO) queues are a very common concept in computing. FIFO can be used for task queues while FILO is also used for memory 'stacks'.

FIFO's can be used in any contracts that require atomic sequential order processing. Here a new order is simply inserted previous to the head, while the oldest order is simply taken from next to the head. No search loops required.

If you think these structures might be useful, check out my Circular Double Linked List Index Library which is used by my Intrinsically Tradable Tokens (ITT) contract.

  • Should it be address[] public addressLUT; instead of addresses[] public addressLUT;? – Nyxynyx Nov 18 '17 at 6:01
  • Fixed. Thanks for spotting! – o0ragman0o Nov 19 '17 at 10:51
  • Would it also possible to get the length of a double linked list index? And how would you do that? Thanks – The Code Buccaneer Dec 10 '17 at 8:05
  • My LibCLL has a sizeOf() function which starts at head (always index 0) and counts steps until it sees the head again. – o0ragman0o Dec 11 '17 at 0:41
  • Should llIndex[0x0] first initialized, what does it map to at the beginning or should we can see it as null value ? It this the correct way to visualize it?: gist.github.com/avatar-lavventura/…. As I understand the algorithm always pushes new element into head of the linked list @o0ragman0o – alper Apr 29 at 21:30

You have to track an index of the elements you stored in the mapping.

Some solution patterns here: Are there well-solved and simple storage patterns for Solidity?

Hope it helps.

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.