Coarse Set is a collection of unique elements maintained as a linked list. The list of nodes are arranged in ascending order by their key, which is obtained using hashCode(). This facilitates the search of a item within the list. When the list is empty, it contains two sentinel nodes head and tail with minimum and maximum key values respectively. These sentinel nodes are not part of the set.

It uses a common, coarse-grained lock, for all method calls. This set performs well only when contention is low. If however, contention is high, despite the performance of lock, all methods calls will be essential sequential. The main advantage of this algorithms is that its obviously correct.

Course: Concurrent Data Structures, Monsoon 2020
Taught by: Prof. Govindarajulu Regeti

add():
1.Createnewnodebeforehand.
2.Acquirelockbeforeanyaction.
3.Findnodeafterwhichtoinsert.
4.Addnode, onlyifkeyisunique.
5.Incrementsizeifnodewasadded.
6.Releasethelock.

remove():
1.Acquirelockbeforeanyaction.
2.Findnodeafterwhichtoremove.
3.Removenode, onlyifkeymatches.
4.Decrementsizeifnodewasremoved.
5.Releasethelock.

contains():
1.Acquirelockbeforeanyaction.
2.Findnodeprevioustosearchkey.
3.Checkifnextnodematchessearchkey.
4.Releasethelock.

See CoarseSet.java for code, Main.java for test, and repl.it for output.

references

• The Art of Multiprocessor Programming :: Maurice Herlihy, Nir Shavit