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:
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.
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.
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:
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}?
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?
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
Comments
So for example, if you have sequentially indexed mapping, it's easy: 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: 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...
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: 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 tonodes(<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}
?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?
address[] internal members;
That´s more elegant and you can use
members.length
in place of the memberCount.