1 // ConcurrentSkipList.cs
3 // Copyright (c) 2008 Jérémie "Garuma" Laval
5 // Permission is hereby granted, free of charge, to any person obtaining a copy
6 // of this software and associated documentation files (the "Software"), to deal
7 // in the Software without restriction, including without limitation the rights
8 // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
9 // copies of the Software, and to permit persons to whom the Software is
10 // furnished to do so, subject to the following conditions:
12 // The above copyright notice and this permission notice shall be included in
13 // all copies or substantial portions of the Software.
15 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
18 // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
20 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
27 using System.Threading;
28 using System.Collections;
29 using System.Collections.Generic;
31 namespace System.Collections.Concurrent
34 internal class ConcurrentSkipList<T> : IProducerConsumerCollection<T>
36 // Used for randomSeed
39 // Used in FindNodes and thus most others methods
40 // avoid heavy local array creation at each method call and use
41 // for thread locallity ThreadStatic attribute
43 static Node[] precedents;
45 static Node[] succedings;
47 static bool[] takenLocks;
53 public readonly int Key;
55 public readonly int TopLayer;
56 public readonly Node[] Nexts;
57 public volatile bool Marked;
58 public volatile bool FullyLinked;
61 public Node (int key, T value, int heightValue)
65 TopLayer = heightValue;
66 Nexts = new Node [heightValue + 1];
67 Lock = new SpinLock (true);
68 Marked = FullyLinked = false;
75 const int MaxHeight = 200;
80 public ConcurrentSkipList () : this ((value) => value.GetHashCode ())
84 public ConcurrentSkipList (IEqualityComparer<T> comparer)
85 : this ((value) => comparer.GetHashCode (value))
89 public ConcurrentSkipList(Func<T, int> hasher)
97 leftSentinel = new Node (int.MinValue, default (T), MaxHeight);
98 rightSentinel = new Node (int.MaxValue, default (T), MaxHeight);
100 for (int i = 0; i < MaxHeight; i++) {
101 leftSentinel.Nexts [i] = rightSentinel;
103 // The or ensures that randomSeed != 0
104 randomSeed = ((uint)Math.Abs (Next())) | 0x0100;
107 public bool TryAdd (T value)
110 throw new ArgumentNullException ("value");
113 int topLayer = GetRandomLevel ();
115 int v = GetKey (value);
118 int found = FindNode (v, precedents, succedings);
120 // A node with the same key already exists
121 Node nodeFound = succedings [found];
122 if (!nodeFound.Marked) {
123 SpinWait sw = new SpinWait ();
124 while (!nodeFound.FullyLinked)
131 int highestLocked = -1;
133 bool valid = LockNodes (topLayer, ref highestLocked, precedents, succedings,
134 (layer, pred, succ) => !pred.Marked && !succ.Marked && pred.Nexts [layer] == succ);
138 Node newNode = new Node (v, value, topLayer);
139 for (int layer = 0; layer <= topLayer; layer++) {
140 newNode.Nexts [layer] = succedings [layer];
141 precedents [layer].Nexts [layer] = newNode;
143 newNode.FullyLinked = true;
145 Unlock (precedents, takenLocks, highestLocked);
147 Interlocked.Increment (ref count);
152 bool IProducerConsumerCollection<T>.TryTake (out T value)
154 throw new NotSupportedException ();
157 public T[] ToArray ()
159 int countSnapshot = count;
160 T[] temp = new T [countSnapshot];
167 public void CopyTo (T[] array, int startIndex)
169 IEnumerator<T> e = GetInternalEnumerator ();
170 for (int i = startIndex; i < array.Length; i++) {
173 array [i] = e.Current;
178 void ICollection.CopyTo (Array array, int startIndex)
180 T[] temp = array as T[];
184 CopyTo (temp, startIndex);
187 object ICollection.SyncRoot {
193 bool ICollection.IsSynchronized {
199 public bool Remove (T value)
202 throw new ArgumentNullException ("value");
205 Node toDelete = null;
206 bool isMarked = false;
208 int v = GetKey (value);
211 int found = FindNode (v, precedents, succedings);
213 int highestLocked = -1;
215 if (isMarked || (found != -1 && OkToDelete (succedings [found], found))) {
216 // If not marked then logically delete the node
219 toDelete = succedings [found];
220 topLayer = toDelete.TopLayer;
222 toDelete.Lock.Enter (ref taken);
223 // Now that we have the lock, check if the node hasn't already been marked
227 toDelete.Marked = true;
231 bool valid = LockNodes (topLayer, ref highestLocked, precedents, succedings,
232 (layer, pred, succ) => !pred.Marked && pred.Nexts [layer] == succ);
236 for (int layer = topLayer; layer >= 0; layer--)
237 precedents [layer].Nexts [layer] = toDelete.Nexts [layer];
240 toDelete.Lock.Exit ();
241 Unlock (precedents, takenLocks, highestLocked);
244 Interlocked.Decrement (ref count);
252 public bool Contains (T value)
255 throw new ArgumentNullException ("value");
257 return ContainsFromHash (GetKey (value));
260 internal bool ContainsFromHash (int hash)
263 int found = FindNode (hash, precedents, succedings);
264 return found != -1 && succedings [found].FullyLinked && !succedings [found].Marked;
267 internal bool GetFromHash (int hash, out T value)
271 // We are blindly supposing that the hash is correct
272 // i.e. I trust myself :-)
273 int found = FindNode (hash, precedents, succedings);
278 Node node = succedings [found];
281 node.Lock.Enter (ref taken);
283 if (node.FullyLinked && !node.Marked) {
301 IEnumerator<T> IEnumerable<T>.GetEnumerator ()
303 return GetInternalEnumerator ();
306 IEnumerator IEnumerable.GetEnumerator ()
308 return GetInternalEnumerator ();
311 IEnumerator<T> GetInternalEnumerator ()
313 Node curr = leftSentinel;
314 while ((curr = curr.Nexts [0]) != rightSentinel) {
315 // If there is an Add operation ongoing we wait a little
316 // Possible optimization : use a helping scheme
317 SpinWait sw = new SpinWait ();
318 while (!curr.FullyLinked)
321 yield return curr.Value;
325 void Unlock (Node[] preds, bool[] takenLocks, int highestLocked)
327 for (int layer = 0; layer <= highestLocked; layer++)
328 if (takenLocks [layer])
329 preds [layer].Lock.Exit ();
332 bool LockNodes (int topLayer, ref int highestLocked, Node[] preds, Node[] succs, Func<int, Node, Node, bool> validityTest)
334 Node pred, succ, prevPred = null;
337 for (int layer = 0; valid && (layer <= topLayer); layer++) {
338 pred = preds [layer];
339 succ = succs [layer];
340 takenLocks[layer] = false;
342 if (pred != prevPred) {
343 // Possible optimization : limit topLayer to the first refused lock
344 pred.Lock.Enter (ref takenLocks[layer]);
345 highestLocked = layer;
349 valid = validityTest (layer, pred, succ);
355 int FindNode (int v, Node[] preds, Node[] succs)
357 // With preds and succs we record the path we use for searching v
358 if (preds.Length != MaxHeight || succs.Length != MaxHeight)
359 throw new Exception ("preds or succs don't have the good length");
362 Node pred = leftSentinel;
364 // We start at the higher layer
365 for (int layer = MaxHeight - 1; layer >= 0; layer--) {
366 Node curr = pred.Nexts [layer];
367 // In the current layer we find the best position, then the operation will continue on the
368 // layer just beneath
369 while (v > curr.Key) {
371 curr = curr.Nexts [layer];
373 if (found == -1 && v == curr.Key)
375 preds [layer] = pred;
376 succs [layer] = curr;
382 bool OkToDelete (Node candidate, int found)
384 return candidate.FullyLinked && candidate.TopLayer == found && !candidate.Marked;
387 // Taken from Doug Lea's code released in the public domain
388 int GetRandomLevel ()
395 if ((x & 0x80000001) != 0) // test highest and lowest bits
398 while (((x >>= 1) & 1) != 0) ++level;
404 // If one is null, the others too
405 if (succedings == null) {
406 succedings = new Node [MaxHeight];
407 precedents = new Node [MaxHeight];
408 takenLocks = new bool [MaxHeight];
413 // Hopefully these are more optimized than a bare for loop
414 // (I suppose it uses memset internally)
415 Array.Clear (precedents, 0, precedents.Length);
416 Array.Clear (succedings, 0, succedings.Length);
417 Array.Clear (takenLocks, 0, takenLocks.Length);