aboutsummaryrefslogtreecommitdiffstatshomepage
path: root/OpenSim/Framework/LocklessQueue.cs
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--OpenSim/Framework/LocklessQueue.cs130
1 files changed, 130 insertions, 0 deletions
diff --git a/OpenSim/Framework/LocklessQueue.cs b/OpenSim/Framework/LocklessQueue.cs
new file mode 100644
index 0000000..dd3d201
--- /dev/null
+++ b/OpenSim/Framework/LocklessQueue.cs
@@ -0,0 +1,130 @@
1/*
2 * Copyright (c) 2009, openmetaverse.org
3 * All rights reserved.
4 *
5 * - Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions are met:
7 *
8 * - Redistributions of source code must retain the above copyright notice, this
9 * list of conditions and the following disclaimer.
10 * - Neither the name of the openmetaverse.org nor the names
11 * of its contributors may be used to endorse or promote products derived from
12 * this software without specific prior written permission.
13 *
14 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
15 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
17 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
18 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
19 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
20 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
21 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
22 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
23 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
24 * POSSIBILITY OF SUCH DAMAGE.
25 */
26
27using System;
28using System.Threading;
29
30namespace OpenSim.Framework
31{
32 public sealed class LocklessQueue<T>
33 {
34 private sealed class SingleLinkNode
35 {
36 public SingleLinkNode Next;
37 public T Item;
38 }
39
40 SingleLinkNode head;
41 SingleLinkNode tail;
42 int count;
43
44 public int Count { get { return count; } }
45
46 public LocklessQueue()
47 {
48 Init();
49 }
50
51 public void Enqueue(T item)
52 {
53 SingleLinkNode oldTail = null;
54 SingleLinkNode oldTailNext;
55
56 SingleLinkNode newNode = new SingleLinkNode();
57 newNode.Item = item;
58
59 bool newNodeWasAdded = false;
60
61 while (!newNodeWasAdded)
62 {
63 oldTail = tail;
64 oldTailNext = oldTail.Next;
65
66 if (tail == oldTail)
67 {
68 if (oldTailNext == null)
69 newNodeWasAdded = CAS(ref tail.Next, null, newNode);
70 else
71 CAS(ref tail, oldTail, oldTailNext);
72 }
73 }
74
75 CAS(ref tail, oldTail, newNode);
76 Interlocked.Increment(ref count);
77 }
78
79 public bool Dequeue(out T item)
80 {
81 item = default(T);
82 SingleLinkNode oldHead = null;
83 bool haveAdvancedHead = false;
84
85 while (!haveAdvancedHead)
86 {
87 oldHead = head;
88 SingleLinkNode oldTail = tail;
89 SingleLinkNode oldHeadNext = oldHead.Next;
90
91 if (oldHead == head)
92 {
93 if (oldHead == oldTail)
94 {
95 if (oldHeadNext == null)
96 return false;
97
98 CAS(ref tail, oldTail, oldHeadNext);
99 }
100 else
101 {
102 item = oldHeadNext.Item;
103 haveAdvancedHead = CAS(ref head, oldHead, oldHeadNext);
104 }
105 }
106 }
107
108 Interlocked.Decrement(ref count);
109 return true;
110 }
111
112 public void Clear()
113 {
114 Init();
115 }
116
117 private void Init()
118 {
119 count = 0;
120 head = tail = new SingleLinkNode();
121 }
122
123 private static bool CAS(ref SingleLinkNode location, SingleLinkNode comparand, SingleLinkNode newValue)
124 {
125 return
126 (object)comparand ==
127 (object)Interlocked.CompareExchange<SingleLinkNode>(ref location, newValue, comparand);
128 }
129 }
130} \ No newline at end of file