The Labs \ Source Viewer \ SSCLI \ System.Collections.Generic \ LinkedList

  1. //------------------------------------------------------------------------------
  2. // <copyright file="LinkedList.cs" company="Microsoft">
  3. //
  4. // Copyright (c) 2006 Microsoft Corporation. All rights reserved.
  5. //
  6. // The use and distribution terms for this software are contained in the file
  7. // named license.txt, which can be found in the root of this distribution.
  8. // By using this software in any fashion, you are agreeing to be bound by the
  9. // terms of this license.
  10. //
  11. // You must not remove this notice, or any other, from this software.
  12. //
  13. // </copyright>
  14. //------------------------------------------------------------------------------
  15. namespace System.Collections.Generic
  16. {
  17.     using System;
  18.     using System.Diagnostics;
  19.     using System.Runtime.Serialization;
  20.     using System.Security.Permissions;
  21.    
  22.     [Serializable()]
  23.     [System.Runtime.InteropServices.ComVisible(false)]
  24.     [DebuggerTypeProxy(typeof(System_CollectionDebugView<>))]
  25.     [DebuggerDisplay("Count = {Count}")]
  26.     public class LinkedList<T> : ICollection<T>, System.Collections.ICollection, ISerializable, IDeserializationCallback
  27.     {
  28.         // This LinkedList is a doubly-Linked circular list.
  29.         internal LinkedListNode<T> head;
  30.         internal int count;
  31.         internal int version;
  32.         private object _syncRoot;
  33.        
  34.         private SerializationInfo siInfo;
  35.         //A temporary variable which we need during deserialization.
  36.         // names for serialization
  37.         const string VersionName = "Version";
  38.         const string CountName = "Count";
  39.         const string ValuesName = "Data";
  40.        
  41.         public LinkedList()
  42.         {
  43.         }
  44.        
  45.         public LinkedList(IEnumerable<T> collection)
  46.         {
  47.             if (collection == null) {
  48.                 throw new ArgumentNullException("collection");
  49.             }
  50.            
  51.             foreach (T item in collection) {
  52.                 AddLast(item);
  53.             }
  54.         }
  55.        
  56.         protected LinkedList(SerializationInfo info, StreamingContext context)
  57.         {
  58.             siInfo = info;
  59.         }
  60.        
  61.         public int Count {
  62.             get { return count; }
  63.         }
  64.        
  65.         public LinkedListNode<T> First {
  66.             get { return head; }
  67.         }
  68.        
  69.         public LinkedListNode<T> Last {
  70.             get { return head == null ? null : head.prev; }
  71.         }
  72.        
  73.         bool ICollection<T>.IsReadOnly {
  74.             get { return false; }
  75.         }
  76.        
  77.         void ICollection<T>.Add(T value)
  78.         {
  79.             AddLast(value);
  80.         }
  81.        
  82.         public LinkedListNode<T> AddAfter(LinkedListNode<T> node, T value)
  83.         {
  84.             ValidateNode(node);
  85.             LinkedListNode<T> result = new LinkedListNode<T>(node.list, value);
  86.             InternalInsertNodeBefore(node.next, result);
  87.             return result;
  88.         }
  89.        
  90.         public void AddAfter(LinkedListNode<T> node, LinkedListNode<T> newNode)
  91.         {
  92.             ValidateNode(node);
  93.             ValidateNewNode(newNode);
  94.             InternalInsertNodeBefore(node.next, newNode);
  95.             newNode.list = this;
  96.         }
  97.        
  98.         public LinkedListNode<T> AddBefore(LinkedListNode<T> node, T value)
  99.         {
  100.             ValidateNode(node);
  101.             LinkedListNode<T> result = new LinkedListNode<T>(node.list, value);
  102.             InternalInsertNodeBefore(node, result);
  103.             if (node == head) {
  104.                 head = result;
  105.             }
  106.             return result;
  107.         }
  108.        
  109.         public void AddBefore(LinkedListNode<T> node, LinkedListNode<T> newNode)
  110.         {
  111.             ValidateNode(node);
  112.             ValidateNewNode(newNode);
  113.             InternalInsertNodeBefore(node, newNode);
  114.             newNode.list = this;
  115.             if (node == head) {
  116.                 head = newNode;
  117.             }
  118.         }
  119.        
  120.         public LinkedListNode<T> AddFirst(T value)
  121.         {
  122.             LinkedListNode<T> result = new LinkedListNode<T>(this, value);
  123.             if (head == null) {
  124.                 InternalInsertNodeToEmptyList(result);
  125.             }
  126.             else {
  127.                 InternalInsertNodeBefore(head, result);
  128.                 head = result;
  129.             }
  130.             return result;
  131.         }
  132.        
  133.         public void AddFirst(LinkedListNode<T> node)
  134.         {
  135.             ValidateNewNode(node);
  136.            
  137.             if (head == null) {
  138.                 InternalInsertNodeToEmptyList(node);
  139.             }
  140.             else {
  141.                 InternalInsertNodeBefore(head, node);
  142.                 head = node;
  143.             }
  144.             node.list = this;
  145.         }
  146.        
  147.         public LinkedListNode<T> AddLast(T value)
  148.         {
  149.             LinkedListNode<T> result = new LinkedListNode<T>(this, value);
  150.             if (head == null) {
  151.                 InternalInsertNodeToEmptyList(result);
  152.             }
  153.             else {
  154.                 InternalInsertNodeBefore(head, result);
  155.             }
  156.             return result;
  157.         }
  158.        
  159.         public void AddLast(LinkedListNode<T> node)
  160.         {
  161.             ValidateNewNode(node);
  162.            
  163.             if (head == null) {
  164.                 InternalInsertNodeToEmptyList(node);
  165.             }
  166.             else {
  167.                 InternalInsertNodeBefore(head, node);
  168.             }
  169.             node.list = this;
  170.         }
  171.        
  172.         public void Clear()
  173.         {
  174.             LinkedListNode<T> current = head;
  175.             while (current != null) {
  176.                 LinkedListNode<T> temp = current;
  177.                 current = current.Next;
  178.                 // use Next the instead of "next", otherwise it will loop forever
  179.                 temp.Invalidate();
  180.             }
  181.            
  182.             head = null;
  183.             count = 0;
  184.             version++;
  185.         }
  186.        
  187.         public bool Contains(T value)
  188.         {
  189.             return Find(value) != null;
  190.         }
  191.        
  192.         public void CopyTo(T[] array, int index)
  193.         {
  194.             if (array == null) {
  195.                 throw new ArgumentNullException("array");
  196.             }
  197.            
  198.             if (index < 0 || index > array.Length) {
  199.                 throw new ArgumentOutOfRangeException("index", SR.GetString(SR.IndexOutOfRange, index));
  200.             }
  201.            
  202.             if (array.Length - index < Count) {
  203.                 throw new ArgumentException(SR.GetString(SR.Arg_InsufficientSpace));
  204.             }
  205.            
  206.             LinkedListNode<T> node = head;
  207.             if (node != null) {
  208.                 do {
  209.                     array[index++] = node.item;
  210.                     node = node.next;
  211.                 }
  212.                 while (node != head);
  213.             }
  214.         }
  215.        
  216.         public LinkedListNode<T> Find(T value)
  217.         {
  218.             LinkedListNode<T> node = head;
  219.             EqualityComparer<T> c = EqualityComparer<T>.Default;
  220.             if (node != null) {
  221.                 if (value != null) {
  222.                     do {
  223.                         if (c.Equals(node.item, value)) {
  224.                             return node;
  225.                         }
  226.                         node = node.next;
  227.                     }
  228.                     while (node != head);
  229.                 }
  230.                 else {
  231.                     do {
  232.                         if (node.item == null) {
  233.                             return node;
  234.                         }
  235.                         node = node.next;
  236.                     }
  237.                     while (node != head);
  238.                 }
  239.             }
  240.             return null;
  241.         }
  242.        
  243.         public LinkedListNode<T> FindLast(T value)
  244.         {
  245.             if (head == null)
  246.                 return null;
  247.            
  248.             LinkedListNode<T> last = head.prev;
  249.             LinkedListNode<T> node = last;
  250.             EqualityComparer<T> c = EqualityComparer<T>.Default;
  251.             if (node != null) {
  252.                 if (value != null) {
  253.                     do {
  254.                         if (c.Equals(node.item, value)) {
  255.                             return node;
  256.                         }
  257.                        
  258.                         node = node.prev;
  259.                     }
  260.                     while (node != last);
  261.                 }
  262.                 else {
  263.                     do {
  264.                         if (node.item == null) {
  265.                             return node;
  266.                         }
  267.                         node = node.prev;
  268.                     }
  269.                     while (node != last);
  270.                 }
  271.             }
  272.             return null;
  273.         }
  274.        
  275.         public Enumerator GetEnumerator()
  276.         {
  277.             return new Enumerator(this);
  278.         }
  279.        
  280.         IEnumerator<T> IEnumerable<T>.GetEnumerator()
  281.         {
  282.             return GetEnumerator();
  283.         }
  284.        
  285.         public bool Remove(T value)
  286.         {
  287.             LinkedListNode<T> node = Find(value);
  288.             if (node != null) {
  289.                 InternalRemoveNode(node);
  290.                 return true;
  291.             }
  292.             return false;
  293.         }
  294.        
  295.         public void Remove(LinkedListNode<T> node)
  296.         {
  297.             ValidateNode(node);
  298.             InternalRemoveNode(node);
  299.         }
  300.        
  301.         public void RemoveFirst()
  302.         {
  303.             if (head == null) {
  304.                 throw new InvalidOperationException(SR.GetString(SR.LinkedListEmpty));
  305.             }
  306.             InternalRemoveNode(head);
  307.         }
  308.        
  309.         public void RemoveLast()
  310.         {
  311.             if (head == null) {
  312.                 throw new InvalidOperationException(SR.GetString(SR.LinkedListEmpty));
  313.             }
  314.             InternalRemoveNode(head.prev);
  315.         }
  316.        
  317.         [SecurityPermissionAttribute(SecurityAction.LinkDemand, Flags = SecurityPermissionFlag.SerializationFormatter)]
  318.         public virtual void GetObjectData(SerializationInfo info, StreamingContext context)
  319.         {
  320.             // Customized serialization for LinkedList.
  321.             // We need to do this because it will be too expensive to Serialize each node.
  322.             // This will give us the flexiblility to change internal implementation freely in future.
  323.             if (info == null) {
  324.                 throw new ArgumentNullException("info");
  325.             }
  326.             info.AddValue(VersionName, version);
  327.             info.AddValue(CountName, count);
  328.             //This is the length of the bucket array.
  329.             if (count != 0) {
  330.                 T[] array = new T[Count];
  331.                 CopyTo(array, 0);
  332.                 info.AddValue(ValuesName, array, typeof(T[]));
  333.             }
  334.         }
  335.        
  336.         public virtual void OnDeserialization(object sender)
  337.         {
  338.             if (siInfo == null) {
  339.                 return;
  340.                 //Somebody had a dependency on this Dictionary and fixed us up before the ObjectManager got to it.
  341.             }
  342.            
  343.             int realVersion = siInfo.GetInt32(VersionName);
  344.             int count = siInfo.GetInt32(CountName);
  345.            
  346.             if (count != 0) {
  347.                 T[] array = (T[])siInfo.GetValue(ValuesName, typeof(T[]));
  348.                
  349.                 if (array == null) {
  350.                     throw new SerializationException(SR.GetString(SR.Serialization_MissingValues));
  351.                 }
  352.                 for (int i = 0; i < array.Length; i++) {
  353.                     AddLast(array[i]);
  354.                 }
  355.             }
  356.             else {
  357.                 head = null;
  358.             }
  359.            
  360.             version = realVersion;
  361.             siInfo = null;
  362.         }
  363.        
  364.        
  365.         private void InternalInsertNodeBefore(LinkedListNode<T> node, LinkedListNode<T> newNode)
  366.         {
  367.             newNode.next = node;
  368.             newNode.prev = node.prev;
  369.             node.prev.next = newNode;
  370.             node.prev = newNode;
  371.             version++;
  372.             count++;
  373.         }
  374.        
  375.         private void InternalInsertNodeToEmptyList(LinkedListNode<T> newNode)
  376.         {
  377.             Debug.Assert(head == null && count == 0, "LinkedList must be empty when this method is called!");
  378.             newNode.next = newNode;
  379.             newNode.prev = newNode;
  380.             head = newNode;
  381.             version++;
  382.             count++;
  383.         }
  384.        
  385.         internal void InternalRemoveNode(LinkedListNode<T> node)
  386.         {
  387.             Debug.Assert(node.list == this, "Deleting the node from another list!");
  388.             Debug.Assert(head != null, "This method shouldn't be called on empty list!");
  389.             if (node.next == node) {
  390.                 Debug.Assert(count == 1 && head == node, "this should only be true for a list with only one node");
  391.                 head = null;
  392.             }
  393.             else {
  394.                 node.next.prev = node.prev;
  395.                 node.prev.next = node.next;
  396.                 if (head == node) {
  397.                     head = node.next;
  398.                 }
  399.             }
  400.             node.Invalidate();
  401.             count--;
  402.             version++;
  403.         }
  404.        
  405.         internal void ValidateNewNode(LinkedListNode<T> node)
  406.         {
  407.             if (node == null) {
  408.                 throw new ArgumentNullException("node");
  409.             }
  410.            
  411.             if (node.list != null) {
  412.                 throw new InvalidOperationException(SR.GetString(SR.LinkedListNodeIsAttached));
  413.             }
  414.         }
  415.        
  416.        
  417.         internal void ValidateNode(LinkedListNode<T> node)
  418.         {
  419.             if (node == null) {
  420.                 throw new ArgumentNullException("node");
  421.             }
  422.            
  423.             if (node.list != this) {
  424.                 throw new InvalidOperationException(SR.GetString(SR.ExternalLinkedListNode));
  425.             }
  426.         }
  427.        
  428.         bool System.Collections.ICollection.IsSynchronized {
  429.             get { return false; }
  430.         }
  431.        
  432.         object System.Collections.ICollection.SyncRoot {
  433.             get {
  434.                 if (_syncRoot == null) {
  435.                     System.Threading.Interlocked.CompareExchange(ref _syncRoot, new object(), null);
  436.                 }
  437.                 return _syncRoot;
  438.             }
  439.         }
  440.        
  441.         void System.Collections.ICollection.CopyTo(Array array, int index)
  442.         {
  443.             if (array == null) {
  444.                 throw new ArgumentNullException("array");
  445.             }
  446.            
  447.             if (array.Rank != 1) {
  448.                 throw new ArgumentException(SR.GetString(SR.Arg_MultiRank));
  449.             }
  450.            
  451.             if (array.GetLowerBound(0) != 0) {
  452.                 throw new ArgumentException(SR.GetString(SR.Arg_NonZeroLowerBound));
  453.             }
  454.            
  455.             if (index < 0) {
  456.                 throw new ArgumentOutOfRangeException("index", SR.GetString(SR.IndexOutOfRange, index));
  457.             }
  458.            
  459.             if (array.Length - index < Count) {
  460.                 throw new ArgumentException(SR.GetString(SR.Arg_InsufficientSpace));
  461.             }
  462.            
  463.             T[] tArray = array as T[];
  464.             if (tArray != null) {
  465.                 CopyTo(tArray, index);
  466.             }
  467.             else {
  468.                 //
  469.                 // Catch the obvious case assignment will fail.
  470.                 // We can found all possible problems by doing the check though.
  471.                 // For example, if the element type of the Array is derived from T,
  472.                 // we can't figure out if we can successfully copy the element beforehand.
  473.                 //
  474.                 Type targetType = array.GetType().GetElementType();
  475.                 Type sourceType = typeof(T);
  476.                 if (!(targetType.IsAssignableFrom(sourceType) || sourceType.IsAssignableFrom(targetType))) {
  477.                     throw new ArgumentException(SR.GetString(SR.Invalid_Array_Type));
  478.                 }
  479.                
  480.                 object[] objects = array as object[];
  481.                 if (objects == null) {
  482.                     throw new ArgumentException(SR.GetString(SR.Invalid_Array_Type));
  483.                 }
  484.                 LinkedListNode<T> node = head;
  485.                 try {
  486.                     if (node != null) {
  487.                         do {
  488.                             objects[index++] = node.item;
  489.                             node = node.next;
  490.                         }
  491.                         while (node != head);
  492.                     }
  493.                 }
  494.                 catch (ArrayTypeMismatchException) {
  495.                     throw new ArgumentException(SR.GetString(SR.Invalid_Array_Type));
  496.                 }
  497.             }
  498.         }
  499.        
  500.         System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
  501.         {
  502.             return GetEnumerator();
  503.         }
  504.        
  505.        
  506.         [Serializable()]
  507.         public struct Enumerator : IEnumerator<T>, System.Collections.IEnumerator, ISerializable, IDeserializationCallback
  508.         {
  509.             private LinkedList<T> list;
  510.             private LinkedListNode<T> node;
  511.             private int version;
  512.             private T current;
  513.             private int index;
  514.             private SerializationInfo siInfo;
  515.             //A temporary variable which we need during deserialization.
  516.             const string LinkedListName = "LinkedList";
  517.             const string CurrentValueName = "Current";
  518.             const string VersionName = "Version";
  519.             const string IndexName = "Index";
  520.            
  521.             internal Enumerator(LinkedList<T> list)
  522.             {
  523.                 this.list = list;
  524.                 version = list.version;
  525.                 node = list.head;
  526.                 current = default(T);
  527.                 index = 0;
  528.                 siInfo = null;
  529.             }
  530.            
  531.             internal Enumerator(SerializationInfo info, StreamingContext context)
  532.             {
  533.                 siInfo = info;
  534.                 list = null;
  535.                 version = 0;
  536.                 node = null;
  537.                 current = default(T);
  538.                 index = 0;
  539.             }
  540.            
  541.             public T Current {
  542.                 get { return current; }
  543.             }
  544.            
  545.             object System.Collections.IEnumerator.Current {
  546.                 get {
  547.                     if (index == 0 || (index == list.Count + 1)) {
  548.                         ThrowHelper.ThrowInvalidOperationException(ExceptionResource.InvalidOperation_EnumOpCantHappen);
  549.                     }
  550.                    
  551.                     return current;
  552.                 }
  553.             }
  554.            
  555.             public bool MoveNext()
  556.             {
  557.                 if (version != list.version) {
  558.                     throw new InvalidOperationException(SR.GetString(SR.InvalidOperation_EnumFailedVersion));
  559.                 }
  560.                
  561.                 if (node == null) {
  562.                     index = list.Count + 1;
  563.                     return false;
  564.                 }
  565.                
  566.                 ++index;
  567.                 current = node.item;
  568.                 node = node.next;
  569.                 if (node == list.head) {
  570.                     node = null;
  571.                 }
  572.                 return true;
  573.             }
  574.            
  575.             void System.Collections.IEnumerator.Reset()
  576.             {
  577.                 if (version != list.version) {
  578.                     throw new InvalidOperationException(SR.GetString(SR.InvalidOperation_EnumFailedVersion));
  579.                 }
  580.                
  581.                 current = default(T);
  582.                 node = list.head;
  583.                 index = 0;
  584.             }
  585.            
  586.             public void Dispose()
  587.             {
  588.             }
  589.            
  590.             void ISerializable.GetObjectData(SerializationInfo info, StreamingContext context)
  591.             {
  592.                 if (info == null) {
  593.                     throw new ArgumentNullException("info");
  594.                 }
  595.                
  596.                 info.AddValue(LinkedListName, list);
  597.                 info.AddValue(VersionName, version);
  598.                 info.AddValue(CurrentValueName, current);
  599.                 info.AddValue(IndexName, index);
  600.             }
  601.            
  602.             void IDeserializationCallback.OnDeserialization(object sender)
  603.             {
  604.                 if (list != null) {
  605.                     return;
  606.                     //Somebody had a dependency on this Dictionary and fixed us up before the ObjectManager got to it.
  607.                 }
  608.                
  609.                 if (siInfo == null) {
  610.                     throw new SerializationException(SR.GetString(SR.Serialization_InvalidOnDeser));
  611.                 }
  612.                
  613.                 list = (LinkedList<T>)siInfo.GetValue(LinkedListName, typeof(LinkedList<T>));
  614.                 version = siInfo.GetInt32(VersionName);
  615.                 current = (T)siInfo.GetValue(CurrentValueName, typeof(T));
  616.                 index = siInfo.GetInt32(IndexName);
  617.                
  618.                 if (list.siInfo != null) {
  619.                     list.OnDeserialization(sender);
  620.                 }
  621.                
  622.                 if (index == list.Count + 1) {
  623.                     // end of enumeration
  624.                     node = null;
  625.                 }
  626.                 else {
  627.                     node = list.First;
  628.                     // We don't care if we can point to the correct node if the LinkedList was changed
  629.                     // MoveNext will throw upon next call and Current has the correct value.
  630.                     if (node != null && index != 0) {
  631.                         for (int i = 0; i < index; i++) {
  632.                             node = node.next;
  633.                         }
  634.                         if (node == list.First) {
  635.                             node = null;
  636.                         }
  637.                     }
  638.                 }
  639.                 siInfo = null;
  640.             }
  641.         }
  642.        
  643.     }
  644.    
  645.     // Note following class is not serializable since we customized the serialization of LinkedList.
  646.     [System.Runtime.InteropServices.ComVisible(false)]
  647.     public sealed class LinkedListNode<T>
  648.     {
  649.         internal LinkedList<T> list;
  650.         internal LinkedListNode<T> next;
  651.         internal LinkedListNode<T> prev;
  652.         internal T item;
  653.        
  654.         public LinkedListNode(T value)
  655.         {
  656.             this.item = value;
  657.         }
  658.        
  659.         internal LinkedListNode(LinkedList<T> list, T value)
  660.         {
  661.             this.list = list;
  662.             this.item = value;
  663.         }
  664.        
  665.         public LinkedList<T> List {
  666.             get { return list; }
  667.         }
  668.        
  669.         public LinkedListNode<T> Next {
  670.             get { return next == null || next == list.head ? null : next; }
  671.         }
  672.        
  673.         public LinkedListNode<T> Previous {
  674.             get { return prev == null || this == list.head ? null : prev; }
  675.         }
  676.        
  677.         public T Value {
  678.             get { return item; }
  679.             set { item = value; }
  680.         }
  681.        
  682.         internal void Invalidate()
  683.         {
  684.             list = null;
  685.             next = null;
  686.             prev = null;
  687.         }
  688.     }
  689. }

Developer Fusion