In this article, we’ll continue our story on the mapping data structure, but this time, we’ll go through the data structure upgrade and reach a new functionality: the iterative mapping data structure.
This way, by upgrading the readily available data structure, we’ll get a broader perspective and better understanding of how it works and how it can be used to make an even richer and more capable data structure.
It’s part of our long-standing tradition to make this (and other) articles a faithful companion, or a supplement to the official Solidity documentation, starting with docs for this article’s topic.
In the next section, we’ll just lay out the source code for easier reference and testing purposes. After that, we’ll analyze what the code does and comment on the points of interest.
Smart Contract – Iterable Mappings
Let’s quickly glance over the code example before we discuss it in greater detail afterward:
// SPDX-License-Identifier: GPL-3.0
pragma solidity ^0.8.8;
struct IndexValue { uint keyIndex; uint value; }
struct KeyFlag { uint key; bool deleted; }
struct itmap {
mapping(uint => IndexValue) data;
KeyFlag[] keys;
uint size;
}
type Iterator is uint;
library IterableMapping {
function insert(itmap storage self, uint key, uint value) internal returns (bool replaced) {
uint keyIndex = self.data[key].keyIndex;
self.data[key].value = value;
if (keyIndex > 0)
return true;
else {
keyIndex = self.keys.length;
self.keys.push();
self.data[key].keyIndex = keyIndex + 1;
self.keys[keyIndex].key = key;
self.size++;
return false;
}
}
function remove(itmap storage self, uint key) internal returns (bool success) {
uint keyIndex = self.data[key].keyIndex;
if (keyIndex == 0)
return false;
delete self.data[key];
self.keys[keyIndex - 1].deleted = true;
self.size --;
}
function contains(itmap storage self, uint key) internal view returns (bool) {
return self.data[key].keyIndex > 0;
}
function iterateStart(itmap storage self) internal view returns (Iterator) {
return iteratorSkipDeleted(self, 0);
}
function iterateValid(itmap storage self, Iterator iterator) internal view returns (bool) {
return Iterator.unwrap(iterator) < self.keys.length;
}
function iterateNext(itmap storage self, Iterator iterator) internal view returns (Iterator) {
return iteratorSkipDeleted(self, Iterator.unwrap(iterator) + 1);
}
function iterateGet(itmap storage self, Iterator iterator) internal view returns (uint key, uint value) {
uint keyIndex = Iterator.unwrap(iterator);
key = self.keys[keyIndex].key;
value = self.data[key].value;
}
function iteratorSkipDeleted(itmap storage self, uint keyIndex) private view returns (Iterator) {
while (keyIndex < self.keys.length && self.keys[keyIndex].deleted)
keyIndex++;
return Iterator.wrap(keyIndex);
}
}
contract User {
itmap data;
using IterableMapping for itmap;
function insert(uint k, uint v) public returns (uint size) {
data.insert(k, v);
return data.size;
}
function sum() public view returns (uint s) {
for (
Iterator i = data.iterateStart();
data.iterateValid(i);
i = data.iterateNext(i)
) {
(, uint value) = data.iterateGet(i);
s += value;
}
}
}
Smart Contract – Iterable Mappings – Code Breakdown and Analysis
Mappings in Solidity are not iterable in their original form because we cannot enumerate mapping keys.
However, we will examine an example showing how we can support iterable mappings by implementing an auxiliary structure.
The following example first implements an IterableMapping library. The User contract uses IterableMapping by adding the data.
The summing function is then used for iterating and summing data contained in IterableMapping.
// SPDX-License-Identifier: GPL-3.0 pragma solidity ^0.8.8;
Declares a data structure that tracks the index of each inserted key with its actual value.
struct IndexValue { uint keyIndex; uint value; }Declares a data structure that enables key iteration by sequentially recording the inserted keys and the deletion status for each inserted key.
Keys are marked as deleted to preserve the array layout.
Otherwise, an actual element removal would cause the shifting of elements and updating of their indexes.
If a key is deleted and inserted at any point, its previous index is not reused. Index reuse is a behavior that could be beneficial for preventing the accumulation of old, unused indexes, but it’s not in the original example.
struct KeyFlag { uint key; bool deleted; }Declares a data structure holding the auxiliary information about the underlying mapping data.
The information is stored in two previously introduced data structures, IndexValue as the value type of mapping, KeyFlag as the iteration-enabling member array, and size as the size-keeping member.
struct itmap {
mapping(uint => IndexValue) data;
KeyFlag[] keys;
uint size;
}
Declares a custom type.
type Iterator is uint;
Declares a library containing the functionality of our iterable mapping.
library IterableMapping {Declares the function for inserting a key/value pair into our custom itmap data structure.
The function returns true if an existing value has been updated, otherwise, it returns false and inserts the key/value pair into itmap.
function insert(itmap storage self, uint key, uint value) internal returns (bool replaced) {Retrieves an existing keyIndex if it exists. A key index that exists will always be greater than 0, and if it doesn’t exist, it will be 0 (the default uint value).
uint keyIndex = self.data[key].keyIndex;
Assigns the value to the given key. We should remember that all possible keys are virtually initialized with default values when a mapping is declared.
self.data[key].value = value;
Checks if there was a keyIndex for the key inserted, and if so, the insert operation is treated as a replace (update) operation.
if (keyIndex > 0)
return true;
Otherwise, the key/value pair is inserted into itmap for the first time.
else {keyIndex of the newly added key is equal to the current length of the array (the keys array uses zero-based indexing).
keyIndex = self.keys.length;
Pushes a currently empty element to the end of the keys array.
self.keys.push();
Translates the keyIndex to one-based indexing by adding 1 to differentiate it from the default keyIndex, which is 0.
self.data[key].keyIndex = keyIndex + 1;
Stores the key into the keys array (zero-based indexing) at the actual keyIndex location.
self.keys[keyIndex].key = key;
Updates the array size to +1.
self.size++;
Returns false because this was not a replace operation, but an insert operation.
return false;
}
}
“Deletes” the key/value pair from the itmap.
function remove(itmap storage self, uint key) internal returns (bool success) {Calculates the keyIndex.
uint keyIndex = self.data[key].keyIndex;
Checks if the key exists in the keys array. If not, there’s nothing to delete, so false is returned.
if (keyIndex == 0)
return false;
“Deletes”, i.e. resets the value part of the key/value pair to default values.
delete self.data[key];
Just marks the key as being deleted. No actual removal is performed, because we want to preserve the array layout.
self.keys[keyIndex - 1].deleted = true;
Update the itmap size.
self.size--;
}
Checks if a key/value pair exists. If not, keyIndex is equal to 0 as it holds the default value when it doesn’t “exist”, except virtually.
function contains(itmap storage self, uint key) internal view returns (bool) {
return self.data[key].keyIndex > 0;
}
Finds the start of an iterable mapping. Iterator is just a custom type that represents an index.
function iterateStart(itmap storage self) internal view returns (Iterator) {
return iteratorSkipDeleted(self, 0);
}
Checks if the iterator is valid, i.e. it didn’t overshoot all the keys.
function iterateValid(itmap storage self, Iterator iterator) internal view returns (bool) {
return Iterator.unwrap(iterator) < self.keys.length;
}
Gets the next available iterator.
function iterateNext(itmap storage self, Iterator iterator) internal view returns (Iterator) {
return iteratorSkipDeleted(self, Iterator.unwrap(iterator) + 1);
}
Gets (returns) a key/value pair.
function iterateGet(itmap storage self, Iterator iterator) internal view returns (uint key, uint value) {
uint keyIndex = Iterator.unwrap(iterator);
key = self.keys[keyIndex].key;
value = self.data[key].value;
}
Finds the first not-deleted, actual keyIndex, i.e. iterator.
function iteratorSkipDeleted(itmap storage self, uint keyIndex) private view returns (Iterator) {
while (keyIndex < self.keys.length && self.keys[keyIndex].deleted)
keyIndex++;
return Iterator.wrap(keyIndex);
}
}
Declares a contract that uses our iterable mapping itmap.
contract User {Declares the itmap.
itmap data;
Applies the library functions to the itmap data type.
using IterableMapping for itmap;
Inserts a key/value pair into data.
function insert(uint k, uint v) public returns (uint size) {
// This calls IterableMapping.insert(data, k, v)
data.insert(k, v);
Returns the size of data (the number of valid key/value pairs).
return data.size;
}
Computes the sum of all valid (non-deleted) value parts.
function sum() public view returns (uint s) {
for (
The initialization part of the for loop; gets the starting iterator of data, i.e. the index of the first valid key/value pair.
Iterator i = data.iterateStart();
The condition part of the for loop; when the iterator overshoots, the loop ends.
data.iterateValid(i);
The iterator part of the for loop; gets the next iterator., i.e. index of the next valid key/value pair.
i = data.iterateNext(i)
) {
Declares the value variable, extracts the second (value) part of the returned key/value pair.
(, uint value) = data.iterateGet(i);
Adds the extracted value to the accumulation variable s.
s += value;
}
}
}
Appendix – Running the Example: Iterable Mappings
This section contains additional information for running the contract. We should expect that our example accounts may change with each refresh/reload of Remix.
To run the example, we will just deploy the User contract and call the insert(...) function.
Test Scenario: Iterable Mappings
- Call the
insert(10, 1)function. - Call the
insert(20, 20)function. - Call the
insert(30, 300)function. - Call the
insert(40, 4000)function. - Get the result of 4321.
Conclusion
In this article, we walked through an example of a custom data structure that implements iterable mapping. As the mapping data structure is not iterable by itself, we also explained all the modifications and showed how the example works.
First, we gave a clean listing of the iterable mapping type example.
Second, we broke down the code of the iterable mapping example and analyzed it thoroughly.
Third, we got familiar with a very simple and short topic of how to run the iterable mapping example.
Fourth, we went through the actual steps of running the iterable mapping example and interpreting the results.
What’s Next?
This tutorial is part of our extended Solidity documentation with videos and more accessible examples and explanations. You can navigate the series here (all links open in a new tab):