clockwerk-opensim – Blame information for rev 1

Subversion Repositories:
Rev:
Rev Author Line No. Line
1 vero 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  
27 using System;
28 using System.Threading;
29  
30 namespace 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 if (haveAdvancedHead)
105 {
106 oldHeadNext.Item = default(T);
107 oldHead.Next = null;
108 }
109 }
110 }
111 }
112  
113 Interlocked.Decrement(ref count);
114 return true;
115 }
116  
117 public void Clear()
118 {
119 // ugly
120 T item;
121 while(count > 0)
122 Dequeue(out item);
123 Init();
124 }
125  
126 private void Init()
127 {
128 count = 0;
129 head = tail = new SingleLinkNode();
130 }
131  
132 private static bool CAS(ref SingleLinkNode location, SingleLinkNode comparand, SingleLinkNode newValue)
133 {
134 return
135 (object)comparand ==
136 (object)Interlocked.CompareExchange<SingleLinkNode>(ref location, newValue, comparand);
137 }
138 }
139 }