corrade-vassal – Blame information for rev 1

Subversion Repositories:
Rev:
Rev Author Line No. Line
1 vero 1 /*
2 * Copyright (c) 2006-2014, 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 OpenMetaverse
31 {
32 /// <summary>
33 /// A thread-safe lockless queue that supports multiple readers and
34 /// multiple writers
35 /// </summary>
36 public sealed class LocklessQueue<T>
37 {
38 /// <summary>
39 /// Provides a node container for data in a singly linked list
40 /// </summary>
41 private sealed class SingleLinkNode
42 {
43 /// <summary>Pointer to the next node in list</summary>
44 public SingleLinkNode Next;
45 /// <summary>The data contained by the node</summary>
46 public T Item;
47  
48 /// <summary>
49 /// Constructor
50 /// </summary>
51 public SingleLinkNode() { }
52  
53 /// <summary>
54 /// Constructor
55 /// </summary>
56 public SingleLinkNode(T item)
57 {
58 this.Item = item;
59 }
60 }
61  
62 /// <summary>Queue head</summary>
63 SingleLinkNode head;
64 /// <summary>Queue tail</summary>
65 SingleLinkNode tail;
66 /// <summary>Queue item count</summary>
67 int count;
68  
69 /// <summary>Gets the current number of items in the queue. Since this
70 /// is a lockless collection this value should be treated as a close
71 /// estimate</summary>
72 public int Count { get { return count; } }
73  
74 /// <summary>
75 /// Constructor
76 /// </summary>
77 public LocklessQueue()
78 {
79 count = 0;
80 head = tail = new SingleLinkNode();
81 }
82  
83 /// <summary>
84 /// Enqueue an item
85 /// </summary>
86 /// <param name="item">Item to enqeue</param>
87 public void Enqueue(T item)
88 {
89 SingleLinkNode newNode = new SingleLinkNode { Item = item };
90  
91 while (true)
92 {
93 SingleLinkNode oldTail = tail;
94 SingleLinkNode oldTailNext = oldTail.Next;
95  
96 if (tail == oldTail)
97 {
98 if (oldTailNext != null)
99 {
100 CAS(ref tail, oldTail, oldTailNext);
101 }
102 else if (CAS(ref tail.Next, null, newNode))
103 {
104 CAS(ref tail, oldTail, newNode);
105 Interlocked.Increment(ref count);
106 return;
107 }
108 }
109 }
110 }
111  
112 /// <summary>
113 /// Try to dequeue an item
114 /// </summary>
115 /// <param name="item">Dequeued item if the dequeue was successful</param>
116 /// <returns>True if an item was successfully deqeued, otherwise false</returns>
117 public bool TryDequeue(out T item)
118 {
119 while (true)
120 {
121 SingleLinkNode oldHead = head;
122 SingleLinkNode oldHeadNext = oldHead.Next;
123  
124 if (oldHead == head)
125 {
126 if (oldHeadNext == null)
127 {
128 item = default(T);
129 count = 0;
130 return false;
131 }
132 if (CAS(ref head, oldHead, oldHeadNext))
133 {
134 item = oldHeadNext.Item;
135 Interlocked.Decrement(ref count);
136 return true;
137 }
138 }
139 }
140 }
141  
142 private static bool CAS(ref SingleLinkNode location, SingleLinkNode comparand, SingleLinkNode newValue)
143 {
144 return
145 (object)comparand ==
146 (object)Interlocked.CompareExchange<SingleLinkNode>(ref location, newValue, comparand);
147 }
148 }
149 }