1  using System;
  2  using System.Collections.Generic;
  3  using System.Diagnostics;
  4  using System.Runtime.CompilerServices;
  5  
  6  namespace ARMeilleure.IntermediateRepresentation
  7  {
  8      /// <summary>
  9      /// Represents a efficient linked list that stores the pointer on the object directly and does not allocate.
 10      /// </summary>
 11      /// <typeparam name="T">Type of the list items</typeparam>
 12      class IntrusiveList<T> where T : IEquatable<T>, IIntrusiveListNode<T>
 13      {
 14          /// <summary>
 15          /// First item of the list, or null if empty.
 16          /// </summary>
 17          public T First { get; private set; }
 18  
 19          /// <summary>
 20          /// Last item of the list, or null if empty.
 21          /// </summary>
 22          public T Last { get; private set; }
 23  
 24          /// <summary>
 25          /// Total number of items on the list.
 26          /// </summary>
 27          public int Count { get; private set; }
 28  
 29          /// <summary>
 30          /// Initializes a new instance of the <see cref="IntrusiveList{T}"/> class.
 31          /// </summary>
 32          /// <exception cref="ArgumentException"><typeparamref name="T"/> is not pointer sized.</exception>
 33          public IntrusiveList()
 34          {
 35              if (Unsafe.SizeOf<T>() != IntPtr.Size)
 36              {
 37                  throw new ArgumentException("T must be a reference type or a pointer sized struct.");
 38              }
 39          }
 40  
 41          /// <summary>
 42          /// Adds a item as the first item of the list.
 43          /// </summary>
 44          /// <param name="newNode">Item to be added</param>
 45          [MethodImpl(MethodImplOptions.AggressiveInlining)]
 46          public T AddFirst(T newNode)
 47          {
 48              if (!EqualsNull(First))
 49              {
 50                  return AddBefore(First, newNode);
 51              }
 52              else
 53              {
 54                  Debug.Assert(EqualsNull(newNode.ListPrevious));
 55                  Debug.Assert(EqualsNull(newNode.ListNext));
 56                  Debug.Assert(EqualsNull(Last));
 57  
 58                  First = newNode;
 59                  Last = newNode;
 60  
 61                  Debug.Assert(Count == 0);
 62  
 63                  Count = 1;
 64  
 65                  return newNode;
 66              }
 67          }
 68  
 69          /// <summary>
 70          /// Adds a item as the last item of the list.
 71          /// </summary>
 72          /// <param name="newNode">Item to be added</param>
 73          [MethodImpl(MethodImplOptions.AggressiveInlining)]
 74          public T AddLast(T newNode)
 75          {
 76              if (!EqualsNull(Last))
 77              {
 78                  return AddAfter(Last, newNode);
 79              }
 80              else
 81              {
 82                  Debug.Assert(EqualsNull(newNode.ListPrevious));
 83                  Debug.Assert(EqualsNull(newNode.ListNext));
 84                  Debug.Assert(EqualsNull(First));
 85  
 86                  First = newNode;
 87                  Last = newNode;
 88  
 89                  Debug.Assert(Count == 0);
 90  
 91                  Count = 1;
 92  
 93                  return newNode;
 94              }
 95          }
 96  
 97          /// <summary>
 98          /// Adds a item before a existing item on the list.
 99          /// </summary>
100          /// <param name="node">Item on the list that will succeed the new item</param>
101          /// <param name="newNode">Item to be added</param>
102          /// <returns>New item</returns>
103          [MethodImpl(MethodImplOptions.AggressiveInlining)]
104          public T AddBefore(T node, T newNode)
105          {
106              Debug.Assert(EqualsNull(newNode.ListPrevious));
107              Debug.Assert(EqualsNull(newNode.ListNext));
108  
109              newNode.ListPrevious = node.ListPrevious;
110              newNode.ListNext = node;
111  
112              node.ListPrevious = newNode;
113  
114              if (!EqualsNull(newNode.ListPrevious))
115              {
116                  newNode.ListPrevious.ListNext = newNode;
117              }
118  
119              if (Equals(First, node))
120              {
121                  First = newNode;
122              }
123  
124              Count++;
125  
126              return newNode;
127          }
128  
129          /// <summary>
130          /// Adds a item after a existing item on the list.
131          /// </summary>
132          /// <param name="node">Item on the list that will preceed the new item</param>
133          /// <param name="newNode">Item to be added</param>
134          /// <returns>New item</returns>
135          [MethodImpl(MethodImplOptions.AggressiveInlining)]
136          public T AddAfter(T node, T newNode)
137          {
138              Debug.Assert(EqualsNull(newNode.ListPrevious));
139              Debug.Assert(EqualsNull(newNode.ListNext));
140  
141              newNode.ListPrevious = node;
142              newNode.ListNext = node.ListNext;
143  
144              node.ListNext = newNode;
145  
146              if (!EqualsNull(newNode.ListNext))
147              {
148                  newNode.ListNext.ListPrevious = newNode;
149              }
150  
151              if (Equals(Last, node))
152              {
153                  Last = newNode;
154              }
155  
156              Count++;
157  
158              return newNode;
159          }
160  
161          /// <summary>
162          /// Removes a item from the list.
163          /// </summary>
164          /// <param name="node">The item to be removed</param>
165          [MethodImpl(MethodImplOptions.AggressiveInlining)]
166          public void Remove(T node)
167          {
168              if (!EqualsNull(node.ListPrevious))
169              {
170                  node.ListPrevious.ListNext = node.ListNext;
171              }
172              else
173              {
174                  Debug.Assert(Equals(First, node));
175  
176                  First = node.ListNext;
177              }
178  
179              if (!EqualsNull(node.ListNext))
180              {
181                  node.ListNext.ListPrevious = node.ListPrevious;
182              }
183              else
184              {
185                  Debug.Assert(Equals(Last, node));
186  
187                  Last = node.ListPrevious;
188              }
189  
190              node.ListPrevious = default;
191              node.ListNext = default;
192  
193              Count--;
194          }
195  
196          [MethodImpl(MethodImplOptions.AggressiveInlining)]
197          private static bool EqualsNull(T a)
198          {
199              return EqualityComparer<T>.Default.Equals(a, default);
200          }
201  
202          [MethodImpl(MethodImplOptions.AggressiveInlining)]
203          private static bool Equals(T a, T b)
204          {
205              return EqualityComparer<T>.Default.Equals(a, b);
206          }
207      }
208  }