Iterating mapping types

o0ragman0o

Is there any way to iterate over a Solidity mapping type variable as one might in a python dictionary?
e.g.,

 for a in b: print(b[a])

Glasswalker

I haven't seen an actual iterator concept in Solidity yet (in any of the docs/blogs/posts I've reviewed). So the way I've been doing it in my code is overlaying an index alongside.

So for example, if you have sequentially indexed mapping, it's easy:

mapping (uint => address) members;
uint memberCount;
function iterateMembers()
{
    for(uint i=0;i<memberCount;i++)
    {
        doSomeStuff(members[i]);
    }
}

And if you have a non sequentially indexed mapping (For example in a wallet list with a list of addresses and balances) then you have no easy way to iterate, because any value in the index field results in a read of a default state. Basically all possible records exist as defaults.

So you overlay an index on top:

mapping (address => uint) accountBalances;
mapping (uint => address) accountIndex;
uint accountCount;
function iterateAccountsBalances()
{
    for(uint i=0;i<accountCount;i++)
    {
        doSomeStuff(accountBalances[accountIndex[i]]);
    }
}

You just need to be careful to maintain your "count" and "index" appropriately using your accessor functions (getters/setters). So anytime you add to the balances mapping, you need to add an index record, and increment the count, and vice versa, decrement it when you remove.

Hopefully that helps...

o0ragman0o

Thanks @Glasswalker. That helps a lot.
A sequential mapping is intrinsically trivial so it is the non-sequential mappings I'm interested in such as iterating a name register.

The double storage hit in the dual mapping solution is a bit uncomfortable as is the inability to easily drop elements of a mapping.

So I've look into a Linked List approach using Accessor functions and come up with something like this:

contract LLMapping {
	//Accessor functions: 
	//	LLMapping.nodes()
	//	LLMapping.nodes().addr
	//	LLMapping.nodes().next

	struct node {address addr; string32 next;}

	function LLMapping() {
		// Set up head node.
		head = 'root';
		nodes['root'].next = 'root';
		nodes['root'].addr = 0;
	}

	function add (string32 _name, address _addr) {
		// Add node to link list. 
		// ! does not test for prior existance of node.
		nodes[_name].next = head;
		nodes[_name].addr = _addr;
		head = _name;
	}

	function iterate() {
		// Iterates through nodes performing some operation.
		for (name = head; name != 'root'; name = nodes[name].next) {
			// do something
		}

	mapping (string32 => node) public nodes; // string32 is name index. node contains address and next index.
	string32 head;
}

The nodes mapping stores only 3 elements as opposed to 4 of the parallel indexed mappings. nodes can also be stepped, iterated through or dropped easily by reference and adjustments to nodes(<index>).next value.

Code's not tested or complete (still getting my head around JS wrappers).

Add() needs an existence test otherwise it can update the head to an existing node and break the list.

So next question is, given there is no Null or typecasting to bool, how do I test for existence such as if address {//do something}?

Glasswalker

Hey, glad it spawned a good idea

You make some excellent points... one things I hadn't considered is random Insertion/Deletion capability in the list. In my implementation I never remove an entry, and always append on the end.

In addition with the data storage costs in Frontier so far, it's looking VERY expensive to store, relative to execution.

To your problem about identifying existence of a record in a mapping. Not possible without some artificial means (ie: in solidity all records "virtually" exist in the case of a mapping). But you can add a bool to your struct. Bool will default to false, so it acts as an "exists" check, set to true upon creating a new record.

You should be fine for storage because addresses are 160bit and bool is tiny, so the one advantage is the new optimizer/packer in solidity will pack the values tightly together. So your address and bool should share a single cell.

Hell, if you can get your string index shortened enough, you might be able to optimize down your record size to 2 slots. Address is 160bit, your bool, then an 80 bit string, (10 bytes) as an index would all cram into a single slot (in theory). I believe you can use bytes10... I don't think they need to be on even 2^x boundries...

Either way I like your linked list implementation. It's pretty elegant. Supports easy iteration, and direct indexing and eats up less storage. Mind if I use this in place of my indexed mappings in some of my solutions?

chriseth

At some point we will hopefully have template datatypes so that you do not have to worry about implementing all this stuff on your own, but rather use something like

contract C {
  struct MyData { uint timeout; address addr; }
  LinkedList[bytes8, MyData] nodes;
  function add(bytes8 name, uint timeout, address addr) {
    nodes.append(name, MyData(timeout, addr));
  }
}

Where the struct is defined similar to

struct MyData[KeyType, ValueType] {
  mapping(KeyType => ValueType) data;
   ...
}

chevdor

Instead of using a mapping and maintaining a count, you can use an Array.

address[] internal members;

That´s more elegant and you can use members.length in place of the memberCount.