Creating a Smart Contract having Iterable Mapping
Smart contracts created with Solidity provide a mapping type for storing key-value pairs. This mapping type is useful for storing or reading value values for a specific key. However, it does not provide an iteration function to retrieve all the lists stored in the mapping, or to sequentially read the value by repeating the list.
In this article, let’s look at a pattern that iterates lists stored in a mapping. You’ll also notice some things to keep in mind when adding a new list to a mapping or deleting an existing list.
Non-iterable smart contract with only mapping
Let’s look at a smart contract example that includes a mapping that has an address type as key and a byte32 type as value
It contains maps, add, remove, contains, and getByKey functions of type mapping (address => bytes32)
The mapping type provides the ability to store and retrieve values for a particular key. However, it does not provide the ability to return an iterable list of keys. If you want to create an iterable mapping, you must include additional functionality.
Things to consider when creating an iterable mapping
1. Save the mapping keys as an array
Add a keyList to the array to record the keys stored in the map. The keyList is composed of an array of addresses which are the type corresponding to the key of the map.
The add function adds a key to the keyList in addition to writing the value to map.
A size function that returns the length of the entire map with keyList, and a getKeys function that returns a complete list of keys have been added.
In the above example, there are some not included features.
- The existing key in
addfunction has not been processed. removefunction is not implemented.- Determines whether it is not a scored value with the value 0 in the
containsfunction. There is a constraint that the value in the map can not be zero.
The common points of the above items are the problems that arise because the index value of the keyList can not be known to the key input when add and remove function are executed. You can loop through all the items in keyList to find the index value, but it is necessary to record the index position of the keyList because it is inefficient.
2. Record the index value of the array together
Let’s store the index value of the keyList in the value stored in the map.
Create a new struct to create an Entry that contains a value and an index, and replace it with the value type of the mapping.
The Entry struct contains the value of the value and the index of the keyList. Note that the index value is the real index value of keyList plus one. The index of the keyList has a value ranging from 0 to (length-1). Since 0 is used as a value for indicating an item having no value, a value of 1 to length is recorded in the Entry.
If we look at the contents of the add function, we find the entry in the map from the input key value and compare the stored index value. If index = 0, add a new item to the keyList with push function. Then, the value of Entry.index is stored as the index in keyList plus one.
The contains function determines whether the index value of the Entry is 0, as described above. In this case, you can store a value of 0 as a value.
The remove function is not included, but is described in the next section.
3. Remove an array item when implementing remove
The remove function is more complicated than add. You can find the entry in the map and delete it with the input key value, and get the index value to delete the keyList. There are considerations when deleting an item from an Array. When you add a new item to keyList, you can easily add an item with the push function of Array type. However, when deleting an item, it is necessary to implement the operation of directly changing the index of the array.
If you look at lines 2 through 4, find the entry in the map with the key value entered in the remove function. Checking the entry.index value causes an error if it is an entry without an entry or an invalid index value.
If you look at lines 7 through 11, it is the process of removing the index item from the keyList. Array does not provide a function for deletion. When delete keyList [index] is executed, the corresponding item value is changed to 0, and the item of keyList is not deleted. So here we move the value of the last item of the keyList to the index, and delete the last item. The deletion of the last item in the keyList only needs to reduce the value of keyList.length by one. delete keyList [keyList.length-1] does not need to consume gas while executing it because it changes the value to 0 only.
Line 12 is the process of deleting the items in the map.
Final code
The following is a summary of the smart contract example with the iterable mapping.
You can check the example code and test code through github ( https://github.com/rayonprotocol-research/solidity-iterable-mapping ).
