lock-free skiplist contains method error

[maneesh t s v]

In the contains method of lockfree skiplist class, there might be an error as the contains method does not jump over marked nodes, instead goes into an infinite loop.

139 boolean contains(T x) {

140 int bottomLevel = 0;

141 int v = x.hashCode();

142 boolean[] marked = {false};

143 Node<T> pred = head, curr = null, succ = null;

144 for (int level = MAX_LEVEL; level >= bottomLevel; level--) {

145 curr = pred.next[level].getReference();

146 while (true) {

147 succ = curr.next[level].get(marked);

148 while (marked[0]) {

149 curr = pred.next[level].getReference();

150 succ = curr.next[level].get(marked);

151 }

152 if (curr.key < v){

153 pred = curr;

154 curr = succ;

155 } else {

156 break;

157 }

158 }

159 }

160 return

In line 149, the curr node points to the next nide of pred at that level even before the assignment took place and hence the assignment is not changing its value, so the succ node will also be the same as before and the marked value will be true until some find process deletes it.

So, the contains method does not jump over marked nodes.

Please correct me if I am wrong.

Thank you

[Maurice Herlihy]

Dear Maneesh:

Thank you! We will look at this carefully.

  best,

  Maurice

--
You received this message because you are subscribed to the Google Groups "Art of Multiprocessor Programming" group.
To unsubscribe from this group and stop receiving emails from it, send an email to art-of-multiprocessor-...@googlegroups.com.
To post to this group, send email to art-of-multiproc...@googlegroups.com.
Visit this group at http://groups.google.com/group/art-of-multiprocessor-programming.
For more options, visit https://groups.google.com/d/optout.

--

Maurice Herlihy
Professor
Computer Science
Brown University