Menu
Can somebody point me towards an algorithm for a sorted thread-safe atomic (lock-free) linked list/priority queue? I'm aware of how to do just a linked list itself, but now I need one that is sorted. I'm unsure if this is minor change or significant redesign compared to an unsorted list, thus would like to see an existing algorithm before I make my own.
It needn't actually be a list (or technically sorted), but behaves like a priority queue with these properties:
The contents will likely be pointers to structures. The integer field to sort is one of the members of that structure.
This is for a C++ program, but I don't need code examples, an algorithm description is fine. Algorithms which come close, but not perfect, are also appreciated.
468
This priority queue will be sorted according to the same comparator as the given collection, or according to its elements' natural order if the collection is sorted according to its elements' natural order. Parameters: c - the collection whose elements are to be placed into this priority queue.
A priority queue is a special type of queue in which each element is associated with a priority value. And, elements are served on the basis of their priority. That is, higher priority elements are served first. However, if elements with the same priority occur, they are served according to their order in the queue.
Priority Queues can be implemented using common data structures like arrays, linked-lists, heaps and binary trees. The list is so created so that the highest priority element is always at the head of the list. The list is arranged in descending order of elements based on their priority.
In Priority queue items are ordered by key value so that item with the lowest value of key is at front and item with the highest value of key is at rear or vice versa. So we're assigned priority to item based on its key value. Lower the value, higher the priority.
Look at this: "Fast and Lock-Free Concurrent Priority Queues for Multi-Thread Systems". Googling will give you more links for sure.
91
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
