LocklessQueue.cs 4.3 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139
  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. using System;
  27. using System.Threading;
  28. namespace OpenSim.Framework
  29. {
  30. public class LocklessQueue<T>
  31. {
  32. private sealed class SingleLinkNode
  33. {
  34. public SingleLinkNode Next;
  35. public T Item;
  36. }
  37. SingleLinkNode head;
  38. SingleLinkNode tail;
  39. int count;
  40. public virtual int Count { get { return count; } }
  41. public LocklessQueue()
  42. {
  43. Init();
  44. }
  45. public void Enqueue(T item)
  46. {
  47. SingleLinkNode oldTail = null;
  48. SingleLinkNode oldTailNext;
  49. SingleLinkNode newNode = new SingleLinkNode();
  50. newNode.Item = item;
  51. bool newNodeWasAdded = false;
  52. while (!newNodeWasAdded)
  53. {
  54. oldTail = tail;
  55. oldTailNext = oldTail.Next;
  56. if (tail == oldTail)
  57. {
  58. if (oldTailNext == null)
  59. newNodeWasAdded = CAS(ref tail.Next, null, newNode);
  60. else
  61. CAS(ref tail, oldTail, oldTailNext);
  62. }
  63. }
  64. CAS(ref tail, oldTail, newNode);
  65. Interlocked.Increment(ref count);
  66. }
  67. public virtual bool Dequeue(out T item)
  68. {
  69. item = default(T);
  70. SingleLinkNode oldHead = null;
  71. bool haveAdvancedHead = false;
  72. while (!haveAdvancedHead)
  73. {
  74. oldHead = head;
  75. SingleLinkNode oldTail = tail;
  76. SingleLinkNode oldHeadNext = oldHead.Next;
  77. if (oldHead == head)
  78. {
  79. if (oldHead == oldTail)
  80. {
  81. if (oldHeadNext == null)
  82. return false;
  83. CAS(ref tail, oldTail, oldHeadNext);
  84. }
  85. else
  86. {
  87. item = oldHeadNext.Item;
  88. haveAdvancedHead = CAS(ref head, oldHead, oldHeadNext);
  89. if (haveAdvancedHead)
  90. {
  91. oldHeadNext.Item = default(T);
  92. oldHead.Next = null;
  93. }
  94. }
  95. }
  96. }
  97. Interlocked.Decrement(ref count);
  98. return true;
  99. }
  100. public void Clear()
  101. {
  102. // ugly
  103. T item;
  104. while(count > 0)
  105. Dequeue(out item);
  106. Init();
  107. }
  108. private void Init()
  109. {
  110. count = 0;
  111. head = tail = new SingleLinkNode();
  112. }
  113. private static bool CAS(ref SingleLinkNode location, SingleLinkNode comparand, SingleLinkNode newValue)
  114. {
  115. return
  116. (object)comparand ==
  117. (object)Interlocked.CompareExchange<SingleLinkNode>(ref location, newValue, comparand);
  118. }
  119. }
  120. }