title: Producer-Consumer With a Twist
body: <p>So, I'm trying to solve what essentially is a producer-consumer problem, but slightly different.</p>
  
  <ul>
  <li>"Producer" thread creates tokens and adds them to a list </li>
  <li>"Consumer" thread scans the list of tokens and processes them. </li>
  <li>As a result of the processing some tokens may be removed, and others may stay a bit longer.</li>
  </ul>
  
  <p>So the main difference is that producer's outputs can be removed from the list in an arbitrary order, not necessarily FIFO.</p>
  
  <p>Now, I am thinking about the synchronization for the structure shared between two threads. I want to have a lockless structure. I know about lockless queues, however a queue doesn't fit the use case very well because of reasons described above. One can still use a queue for this as follows:</p>
  
  <ul>
  <li>Dequeue a token and process it</li>
  <li>If it should not be removed yet, enqueue it back</li>
  </ul>
  
  <p>However, I'd like to avoid it if possible. Ideally what I want is a lockless singly linked list that one thread can append to, while another thread can remove arbitrary elements from. Can you point me to some implementations or papers on that?</p>