Skip to content

Coarse Set is a collection of unique elements maintained as a linked list. It uses a coarse grained lock, and useful when contention is low.

License

Notifications You must be signed in to change notification settings

javaf/coarse-set

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

6 Commits
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

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. Create new node beforehand.
2. Acquire lock before any action.
3. Find node after which to insert.
4. Add node, only if key is unique.
5. Increment size if node was added.
6. Release the lock.
remove():
1. Acquire lock before any action.
2. Find node after which to remove.
3. Remove node, only if key matches.
4. Decrement size if node was removed.
5. Release the lock.
contains():
1. Acquire lock before any action.
2. Find node previous to search key.
3. Check if next node matches search key.
4. Release the lock.

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

references

About

Coarse Set is a collection of unique elements maintained as a linked list. It uses a coarse grained lock, and useful when contention is low.

Topics

Resources

License

Stars

Watchers

Forks

Languages