Solidity 102 #3: Maintaining Sorted list

This is part 3/N of Band Protocol’s “Solidity 102” series. We explore and discuss data structures and implementation techniques for writing efficient Solidity code under Ethereum’s unique EVM cost model. Readers should be familiar with coding in Solidity and how EVM works in general.

In the previous article, we talked about (data structure that can iterate on each element) how to add/remove element to/from list. Today we will extend our data structure to maintain sorted link-list on-chain. Like the previous article, we will explain by showing implementation of each functions. Therefore we hope everyone can follow us, if you’re ready, let’s get into it!

Example use case

We want to create a “School” smart contract (again?) but today we just don’t maintain only student address list. We need to maintain their order by their scores, that teacher can add or minus score from student and we can guarantee that our list still maintained order by score at anytime. The last requirement is we can list top-k of students for rewarding students who have a good score.

Let’s think about functions that we need to fulfill all requirements

There are 5 function that we need to implement.

1. Add new student to list with base score
2. Increase score to a student
3. Reduce score of student
4. Remove student from list
5. Get top-k student list

However before we start implement each function, we need to set up base data structure (array, mapping, etc.) and we choose Iterable Map from last article. Create mapping to store score and write interface for each functions, base code will look like this

Note: GUARD is a header of list.

Add a new student with his/her score: addStudent

Let’s start on the first function addStudent. There is one different thing from normal Iterable Map that is we need to insert new item at the correct index instead of add at the front of the list to maintained our order.

Show how to insert dave to maintained sorted list

For make code easy to read, we created 2 helper function to find and verify index of new value.

_verifyIndex function for verify that value is between left and right address. It will return true if left_value ≥ new_value > right_value (In case we maintain descending order and in the case value is equal the new one should be at back of the old ones)

verify index function

_findIndex helper function to find address that new value should insert after it. Loop from GUARD through list to find valid index by checking with verifyIndex. This code guarantee that we will find a valid index for sure

find index function

addStudent insert new item after valid address, update score and increase listSize.

add student function

Remove a student from list: removeStudent

removeStudent is implemented same as previous article because we remove item from list from transitive property if a ≥ b ≥ c, then a ≥ c (our list still sorted after remove b)

Show how to remove bob from list

helper functions _isPrevStudent and _findPrevStudent

check previous student and find previous student

And removeStudent same as previous article add clear scores mapping.

remove student function

Update score of student: increaseScore and reduceScore

increaseScore and reduceScore can use the same logic to implement that is we update value from old to a new one. The main idea is we just remove old item temporary first and add it to new(or same) index where it should be with new value, so we can reuse add/remove function.

Show how to update Bob’s score

update score function

Note: We have checking condition if new value fit in the same index, we don’t need to remove and add item to the same value(It’ s just an optimization save estimate 1000 gas)

If we have this updateScore function, increaseScore and reduceScore functions can be implemented with one line.

increase score and reduce score function

Get top-k list of students order by their scores: getTop

There is nothing fancy in this function, just loop start from GUARD and store address to array and return that array. Easy right?

get top k function

Code is published here

Bonus find index optimization!

Like the previous article, finding index by loop on-chain consumes gas proportionally to the length of list. We can optimize these functions by sending previous address to function (for update we need to send 2 addresses for remove and where to add later) and verify those addressed is valid by our 2 internal functions. That is why we separate verify condition and find address functions. Let’s take a look on each functions!

addStudent

Optimized add student

A lot of requires!! We add 2 requires the first one is check existence of candidateStudent and the second one is verify that new value must be after that candidate.

removeStudent

Just verify by _isPrevStudent for removing element.

Optimized remove student

updateScore

Optimized update score

We add verify condition in case update at the same index. First condition is like remove element and second condition check for new value is valid to be old index.

Full optimized code is published here

Conclusion

In this article, we explore an implementation of Sorted List, a data structure that extends from Iterable Map to maintain sorted list on-chain that can add, remove, and update value in list. We also implemented an optimized version of this data structure to save gas of finding valid index. In the next article, we will extend this data structure not only get list of top-k but we will can check that address is in top-k or not in O(1)! Stay tuned for next article!

Band Protocol is a platform for decentralized data governance. We are a team of engineers who look forward to the future where smart contracts can connect to real-world data efficiently without trusted parties. If you are a passionate developer and want to contribute to Band Protocol, please reach out to us at talent@bandprotocol.com.