3
$\begingroup$

I am looking for a thread safe data structure where

  1. an element can be searched in $O(\log n)$,
  2. for any value, $x$, the number of elements greater than (or less than) can be estimated in $O(\log n)$,
  3. an element can be inserted in $O(\log n)$, and
  4. an element can be removed in $O(\log n)$.

Can a skip list or some modification of it be used? Is there an alternative data structures (Parallel Red-Black Tree for example) that can be used?

$\endgroup$
  • $\begingroup$ Can you use a more "typical" structure like a normal balanced tree (red-black / AVL / 2-3 / etc) with each subtree annotated with a size? $\endgroup$ – Curtis F Jul 31 '18 at 17:27
  • $\begingroup$ I could use a red-black tree, but it needs to be thread safe. I believe there are concurrent implementations, but they are not that easy to implement. Do you know of a good reference to a thread safe red black tree implementation? $\endgroup$ – dan b Jul 31 '18 at 19:36
1
$\begingroup$

Based on your comment, it sounds like you would also prefer a solution that is not too difficult to understand or implement.

I would suggest a persistent binary tree as one possible approach. Take any standard balanced tree data structure (e.g., red-black tree, AVL tree, 2-3 tree, etc.). Annotate each node with the size of the subtree under that node. Then, make this data structure persistent. This can be done in a straightforward way using path copying.

Because the data structure is persistent, it handles concurrency nicely. In particular, immutable data structures are inherently good for concurrency; you don't have to worry about two threads writing to it concurrently, since it is immutable. Instead, updates essentially work by creating a new copy of the data structure. Thus, each thread has its own copy of the tree. The only shared variable you need is a single global variable that holds a pointer to the current copy of the tree. To update the tree, a thread reads the pointer in that global variable; makes a new copy of the tree with the update; then does a compare-and-swap to update the value of the global variable (unless it has changed since last reading it, in which case you cancel the operation and retry). Because each thread works on its own local copy of the tree during updates, you don't have to worry about some other thread concurrently accessing that copy.

Hopefully, the principles behind this kind of data structure should be easy to understand, so if you need to implement it yourself, it shouldn't be too bad to work out how to do it.

$\endgroup$
  • $\begingroup$ Your approach would not handle insert and removes in O(Log n) as it would need to copy the entire tree for each insert $\endgroup$ – dan b Aug 8 '18 at 10:47
  • $\begingroup$ @danb only single path from the root to the node is copied. All subtrees that haven’t changed are simply referenced. $\endgroup$ – Dmitri Urbanowicz Aug 8 '18 at 12:14
  • $\begingroup$ @DmitriUrbanowicz I think I get the idea, although the impact of having to retry in the case of clashes is not clear. What about the other part of the question: can one estimate the size using a skip list? $\endgroup$ – dan b Aug 8 '18 at 14:29
  • $\begingroup$ @danb, I don't know about skiplists. Sorry. $\endgroup$ – D.W. Aug 8 '18 at 16:08
1
$\begingroup$

It is possible to extend skip lists with so called "width of the link". For each link it says how many elements are skipped by follow this link. From Wikipedia (section Indexable skiplist):

   1                               10
 o---> o---------------------------------------------------------> o    Top level
   1           3              2                    5
 o---> o---------------> o---------> o---------------------------> o    Level 3
   1        2        1        2              3              2
 o---> o---------> o---> o---------> o---------------> o---------> o    Level 2
   1     1     1     1     1     1     1     1     1     1     1
 o---> o---> o---> o---> o---> o---> o---> o---> o---> o---> o---> o    Bottom level

Head  1st   2nd   3rd   4th   5th   6th   7th   8th   9th   10th  NIL
      Node  Node  Node  Node  Node  Node  Node  Node  Node  Node

These links are easy to update during (non-concurrent) traversals of insert and delete operations. It is as well easy to keep track of total number of skipped elements.

So yes, one can extend skip lists to find the position of the element in the list. But concurrent updates of the counters still might be a problem.

$\endgroup$
  • $\begingroup$ Seems like this would solve the problem if the concurrent updates is possible $\endgroup$ – dan b Aug 13 '18 at 14:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.