mcs/class/System.Core/System.Linq.Parallel.QueryNodes/QuerySelectManyNode.cs

   1 //
   2 // QueryConcatNode.cs
   3 //
   4 // Author:
   5 //       Jérémie "Garuma" Laval <jeremie.laval@gmail.com>
   6 //
   7 // Copyright (c) 2010 Jérémie "Garuma" Laval
   8 //
   9 // Permission is hereby granted, free of charge, to any person obtaining a copy
  10 // of this software and associated documentation files (the "Software"), to deal
  11 // in the Software without restriction, including without limitation the rights
  12 // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  13 // copies of the Software, and to permit persons to whom the Software is
  14 // furnished to do so, subject to the following conditions:
  15 //
  16 // The above copyright notice and this permission notice shall be included in
  17 // all copies or substantial portions of the Software.
  18 //
  19 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  20 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  21 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  22 // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  23 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  24 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  25 // THE SOFTWARE.
  26
  27 using System;
  28 using System.Threading;
  29 using System.Collections;
  30 using System.Collections.Generic;
  31
  32 namespace System.Linq.Parallel.QueryNodes
  33 {
  34         internal class QuerySelectManyNode<TSource, TCollection, TResult> : QueryStreamNode<TResult, TSource>
  35         {
  36                 Func<TSource, IEnumerable<TCollection>> collectionSelector;
  37                 Func<TSource, int, IEnumerable<TCollection>> collectionSelectorIndexed;
  38                 Func<TSource, TCollection, TResult> resultSelector;
  39
  40                 internal QuerySelectManyNode (QueryBaseNode<TSource> parent,
  41                                               Func<TSource, int, IEnumerable<TCollection>> collectionSelectorIndexed,
  42                                               Func<TSource, TCollection, TResult> resultSelector)
  43                         : base (parent, true)
  44                 {
  45                         this.collectionSelectorIndexed = collectionSelectorIndexed;
  46                         this.resultSelector = resultSelector;
  47                 }
  48
  49                 internal QuerySelectManyNode (QueryBaseNode<TSource> parent,
  50                                               Func<TSource, IEnumerable<TCollection>> collectionSelector,
  51                                               Func<TSource, TCollection, TResult> resultSelector)
  52                         : base (parent, false)
  53                 {
  54                         this.collectionSelector = collectionSelector;
  55                         this.resultSelector = resultSelector;
  56                 }
  57
  58                 internal override IEnumerable<TResult> GetSequential ()
  59                 {
  60                         IEnumerable<TSource> source = Parent.GetSequential ();
  61
  62                         return IsIndexed ?
  63                                 source.SelectMany (collectionSelectorIndexed, resultSelector) :
  64                                 source.SelectMany (collectionSelector, resultSelector);
  65                 }
  66
  67                 internal override IList<IEnumerable<TResult>> GetEnumerablesIndexed (QueryOptions options)
  68                 {
  69                         return Parent.GetOrderedEnumerables (options)
  70                                 .Select ((i) => GetEnumerableInternal (i,
  71                                                                        (kv) => collectionSelectorIndexed (kv.Value, (int)kv.Key),
  72                                                                        (e, c) => resultSelector (e.Value, c)))
  73                                 .ToList ();
  74                 }
  75
  76                 internal override IList<IEnumerable<TResult>> GetEnumerablesNonIndexed (QueryOptions options)
  77                 {
  78                         return Parent.GetEnumerables (options)
  79                                 .Select ((i) => GetEnumerableInternal (i,
  80                                                                        collectionSelector,
  81                                                                        (e, c) => resultSelector (e, c)))
  82                                 .ToList ();
  83                 }
  84
  85                 internal override IList<IEnumerable<KeyValuePair<long, TResult>>> GetOrderedEnumerables (QueryOptions options)
  86                 {
  87                         var source = Parent.GetOrderedEnumerables (options);
  88                         var sizeRequests = new SizeRequest[source.Count];
  89                         long deviation = 0;
  90
  91                         Barrier barrier = new Barrier (source.Count, delegate (Barrier b) {
  92                                         Array.Sort (sizeRequests, KeyComparator);
  93                                         for (int i = 0; i < b.ParticipantCount; ++i) {
  94                                                 if (sizeRequests[i].Key == -1)
  95                                                         continue;
  96                                                 sizeRequests[i].Key = deviation;
  97                                                 deviation += sizeRequests[i].Size;
  98                                         }
  99                                 });
 100
 101                         return source
 102                                 .Select ((i, ind) => GetOrderedEnumerableInternal (i, sizeRequests, ind, barrier))
 103                                 .ToList ();
 104                 }
 105
 106                 IEnumerable<TResult> GetEnumerableInternal<T> (IEnumerable<T> source,
 107                                                                Func<T, IEnumerable<TCollection>> collectionner,
 108                                                                Func<T, TCollection, TResult> packer)
 109                 {
 110                         foreach (T element in source)
 111                                 foreach (TCollection item in collectionner (element))
 112                                         yield return packer (element, item);
 113                 }
 114
 115                 IEnumerable<KeyValuePair<long, TResult>> GetOrderedEnumerableInternal (IEnumerable<KeyValuePair<long, TSource>> source,
 116                                                                                        SizeRequest[] sizeRequests,
 117                                                                                        int index,
 118                                                                                        Barrier barrier)
 119                 {
 120                         IEnumerator<KeyValuePair<long, TSource>> enumerator = source.GetEnumerator ();
 121                         bool isIndexed = IsIndexed;
 122
 123                         try {
 124                                 while (true) {
 125                                         KeyValuePair<long, TSource> element;
 126                                         IEnumerable<TCollection> collection;
 127
 128                                         if (enumerator.MoveNext ()) {
 129                                                 element = enumerator.Current;
 130                                                 collection = isIndexed ?
 131                                                         collectionSelectorIndexed (element.Value, (int)element.Key) :
 132                                                         collectionSelector (element.Value);
 133
 134                                                 var count = GetCount (ref collection);
 135
 136                                                 sizeRequests[index].Update (element.Key, count, collection, element.Value);
 137                                         }
 138
 139                                         barrier.SignalAndWait ();
 140
 141                                         long i = sizeRequests[index].Key;
 142                                         collection = sizeRequests[index].Collection;
 143                                         var elementValue = sizeRequests[index].ElementValue;
 144
 145                                         sizeRequests[index].Clear ();
 146
 147                                         if (i == -1)
 148                                                 break;
 149
 150                                         foreach (TCollection item in collection)
 151                                                 yield return new KeyValuePair<long, TResult> (i++, resultSelector (elementValue, item));
 152                                 }
 153                         } finally {
 154                                 barrier.RemoveParticipant ();
 155                                 enumerator.Dispose ();
 156                         }
 157                 }
 158
 159                 /* If getting Count is a O(1) operation (i.e. actual is a ICollection) then return it immediatly
 160                  * if not process the IEnumerable into a List and return the Count from that (i.e. enumerable
 161                  * processing will only happen once in case of e.g. a Linq query)
 162                  */
 163                 static int GetCount<T> (ref IEnumerable<T> actual)
 164                 {
 165                         ICollection coll = actual as ICollection;
 166                         if (coll != null)
 167                                 return coll.Count;
 168
 169                         var foo = actual.ToList ();
 170                         actual = foo;
 171
 172                         return foo.Count;
 173                 }
 174
 175                 static int KeyComparator (SizeRequest e1, SizeRequest e2)
 176                 {
 177                         return e1.Key.CompareTo (e2.Key);
 178                 }
 179
 180                 struct SizeRequest
 181                 {
 182                         public long Key;
 183                         public int Size;
 184                         public IEnumerable<TCollection> Collection;
 185                         public TSource ElementValue;
 186
 187                         public void Update (long k, int s, IEnumerable<TCollection> c, TSource ev)
 188                         {
 189                                 Key = k;
 190                                 Size = s;
 191                                 Collection = c;
 192                                 ElementValue = ev;
 193                         }
 194
 195                         public void Clear ()
 196                         {
 197                                 Key = -1;
 198                                 Size = 0;
 199                                 Collection = null;
 200                                 ElementValue = default (TSource);
 201                         }
 202                 }
 203         }
 204 }
 205