Remove element from lock free skip list based priority queue

[Rafał Szefler-Tyrowicz]

Hi guys,

I've managed to successfuly implement lock free skip list based priority queue. What I would like to have now is the additional functionality of item removal. I'm looking for a function void Remove(T element);

So as far as I understand this is hard because the data structure keeps a priority and a reference only. So in order to search for the element I would have to scan entire structure. An alternative would be to keep an (element, priority) map and retrieve priority as a first step of Remove function. But then I add the hash map overhead.

Are there any other alternative? I'd appreciate any help.

Cheers,

R.