XMRInstQueue.cs 6.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192
  1. /*
  2. * Copyright (c) Contributors, http://opensimulator.org/
  3. * See CONTRIBUTORS.TXT for a full list of copyright holders.
  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. * * Redistributions of source code must retain the above copyright
  8. * notice, this list of conditions and the following disclaimer.
  9. * * Redistributions in binary form must reproduce the above copyright
  10. * notice, this list of conditions and the following disclaimer in the
  11. * documentation and/or other materials provided with the distribution.
  12. * * Neither the name of the OpenSimulator Project nor the
  13. * names of its contributors may be used to endorse or promote products
  14. * derived from this software without specific prior written permission.
  15. *
  16. * THIS SOFTWARE IS PROVIDED BY THE DEVELOPERS ``AS IS'' AND ANY
  17. * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  18. * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  19. * DISCLAIMED. IN NO EVENT SHALL THE CONTRIBUTORS BE LIABLE FOR ANY
  20. * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  21. * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  22. * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  23. * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  24. * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  25. * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  26. */
  27. using System;
  28. namespace OpenSim.Region.ScriptEngine.Yengine
  29. {
  30. /**
  31. * @brief Implements a queue of XMRInstance's.
  32. * Do our own queue to avoid shitty little mallocs.
  33. *
  34. * Note: looping inst.m_NextInst and m_PrevInst back to itself
  35. * when inst is removed from a queue is purely for debug.
  36. */
  37. public class XMRInstQueue
  38. {
  39. private XMRInstance m_Head = null;
  40. private XMRInstance m_Tail = null;
  41. /**
  42. * @brief Insert instance at head of queue (in front of all others)
  43. * @param inst = instance to insert
  44. */
  45. public void InsertHead(XMRInstance inst)
  46. {
  47. if((inst.m_PrevInst != inst) || (inst.m_NextInst != inst))
  48. throw new Exception("already in list");
  49. inst.m_PrevInst = null;
  50. if((inst.m_NextInst = m_Head) == null)
  51. m_Tail = inst;
  52. else
  53. m_Head.m_PrevInst = inst;
  54. m_Head = inst;
  55. }
  56. /**
  57. * @brief Insert instance at tail of queue (behind all others)
  58. * @param inst = instance to insert
  59. */
  60. public void InsertTail(XMRInstance inst)
  61. {
  62. if((inst.m_PrevInst != inst) || (inst.m_NextInst != inst))
  63. throw new Exception("already in list");
  64. inst.m_NextInst = null;
  65. if((inst.m_PrevInst = m_Tail) == null)
  66. m_Head = inst;
  67. else
  68. m_Tail.m_NextInst = inst;
  69. m_Tail = inst;
  70. }
  71. /**
  72. * @brief Insert instance before another element in queue
  73. * @param inst = instance to insert
  74. * @param after = element that is to come after one being inserted
  75. */
  76. public void InsertBefore(XMRInstance inst, XMRInstance after)
  77. {
  78. if((inst.m_PrevInst != inst) || (inst.m_NextInst != inst))
  79. throw new Exception("already in list");
  80. if(after == null)
  81. InsertTail(inst);
  82. else
  83. {
  84. inst.m_NextInst = after;
  85. inst.m_PrevInst = after.m_PrevInst;
  86. if(inst.m_PrevInst == null)
  87. m_Head = inst;
  88. else
  89. inst.m_PrevInst.m_NextInst = inst;
  90. after.m_PrevInst = inst;
  91. }
  92. }
  93. /**
  94. * @brief Peek to see if anything in queue
  95. * @returns first XMRInstance in queue but doesn't remove it
  96. * null if queue is empty
  97. */
  98. public XMRInstance PeekHead()
  99. {
  100. return m_Head;
  101. }
  102. /**
  103. * @brief Remove first element from queue, if any
  104. * @returns null if queue is empty
  105. * else returns first element in queue and removes it
  106. */
  107. public XMRInstance RemoveHead()
  108. {
  109. XMRInstance inst = m_Head;
  110. if(inst != null)
  111. {
  112. if((m_Head = inst.m_NextInst) == null)
  113. m_Tail = null;
  114. else
  115. m_Head.m_PrevInst = null;
  116. inst.m_NextInst = inst;
  117. inst.m_PrevInst = inst;
  118. }
  119. return inst;
  120. }
  121. /**
  122. * @brief Remove last element from queue, if any
  123. * @returns null if queue is empty
  124. * else returns last element in queue and removes it
  125. */
  126. public XMRInstance RemoveTail()
  127. {
  128. XMRInstance inst = m_Tail;
  129. if(inst != null)
  130. {
  131. if((m_Tail = inst.m_PrevInst) == null)
  132. m_Head = null;
  133. else
  134. m_Tail.m_NextInst = null;
  135. inst.m_NextInst = inst;
  136. inst.m_PrevInst = inst;
  137. }
  138. return inst;
  139. }
  140. /**
  141. * @brief Remove arbitrary element from queue, if any
  142. * @param inst = element to remove (assumed to be in the queue)
  143. * @returns with element removed
  144. */
  145. public void Remove(XMRInstance inst)
  146. {
  147. XMRInstance next = inst.m_NextInst;
  148. XMRInstance prev = inst.m_PrevInst;
  149. if((prev == inst) || (next == inst))
  150. throw new Exception("not in a list");
  151. if(next == null)
  152. {
  153. if(m_Tail != inst)
  154. throw new Exception("not in this list");
  155. m_Tail = prev;
  156. }
  157. else
  158. next.m_PrevInst = prev;
  159. if(prev == null)
  160. {
  161. if(m_Head != inst)
  162. throw new Exception("not in this list");
  163. m_Head = next;
  164. }
  165. else
  166. prev.m_NextInst = next;
  167. inst.m_NextInst = inst;
  168. inst.m_PrevInst = inst;
  169. }
  170. }
  171. }