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 #if NET_4_0
  28 using System;
  29 using System.Threading;
  30 using System.Collections;
  31 using System.Collections.Generic;
  32
  33 namespace System.Linq.Parallel.QueryNodes
  34 {
  35         internal class QuerySelectManyNode<TSource, TCollection, TResult> : QueryStreamNode<TResult, TSource>
  36         {
  37                 Func<TSource, IEnumerable<TCollection>> collectionSelector;
  38                 Func<TSource, int, IEnumerable<TCollection>> collectionSelectorIndexed;
  39                 Func<TSource, TCollection, TResult> resultSelector;
  40
  41                 internal QuerySelectManyNode (QueryBaseNode<TSource> parent,
  42                                               Func<TSource, int, IEnumerable<TCollection>> collectionSelectorIndexed,
  43                                               Func<TSource, TCollection, TResult> resultSelector)
  44                         : base (parent, true)
  45                 {
  46                         this.collectionSelectorIndexed = collectionSelectorIndexed;
  47                         this.resultSelector = resultSelector;
  48                 }
  49
  50                 internal QuerySelectManyNode (QueryBaseNode<TSource> parent,
  51                                               Func<TSource, IEnumerable<TCollection>> collectionSelector,
  52                                               Func<TSource, TCollection, TResult> resultSelector)
  53                         : base (parent, false)
  54                 {
  55                         this.collectionSelector = collectionSelector;
  56                         this.resultSelector = resultSelector;
  57                 }
  58
  59                 internal override IEnumerable<TResult> GetSequential ()
  60                 {
  61                         IEnumerable<TSource> source = Parent.GetSequential ();
  62
  63                         return IsIndexed ?
  64                                 source.SelectMany (collectionSelectorIndexed, resultSelector) :
  65                                 source.SelectMany (collectionSelector, resultSelector);
  66                 }
  67
  68                 internal override IList<IEnumerable<TResult>> GetEnumerablesIndexed (QueryOptions options)
  69                 {
  70                         return Parent.GetOrderedEnumerables (options)
  71                                 .Select ((i) => GetEnumerableInternal (i,
  72                                                                        (kv) => collectionSelectorIndexed (kv.Value, (int)kv.Key),
  73                                                                        (e, c) => resultSelector (e.Value, c)))
  74                                 .ToList ();
  75                 }
  76
  77                 internal override IList<IEnumerable<TResult>> GetEnumerablesNonIndexed (QueryOptions options)
  78                 {
  79                         return Parent.GetEnumerables (options)
  80                                 .Select ((i) => GetEnumerableInternal (i,
  81                                                                        collectionSelector,
  82                                                                        (e, c) => resultSelector (e, c)))
  83                                 .ToList ();
  84                 }
  85
  86                 internal override IList<IEnumerable<KeyValuePair<long, TResult>>> GetOrderedEnumerables (QueryOptions options)
  87                 {
  88                         var source = Parent.GetOrderedEnumerables (options);
  89                         var sizeRequests = new SizeRequest[source.Count];
  90                         long deviation = 0;
  91
  92                         Barrier barrier = new Barrier (source.Count, delegate (Barrier b) {
  93                                         Array.Sort (sizeRequests, KeyComparator);
  94                                         for (int i = 0; i < b.ParticipantCount; ++i) {
  95                                                 if (sizeRequests[i].Key == -1)
  96                                                         continue;
  97                                                 sizeRequests[i].Key = deviation;
  98                                                 deviation += sizeRequests[i].Size;
  99                                         }
 100                                 });
 101
 102                         return source
 103                                 .Select ((i, ind) => GetOrderedEnumerableInternal (i, sizeRequests, ind, barrier))
 104                                 .ToList ();
 105                 }
 106
 107                 IEnumerable<TResult> GetEnumerableInternal<T> (IEnumerable<T> source,
 108                                                                Func<T, IEnumerable<TCollection>> collectionner,
 109                                                                Func<T, TCollection, TResult> packer)
 110                 {
 111                         foreach (T element in source)
 112                                 foreach (TCollection item in collectionner (element))
 113                                         yield return packer (element, item);
 114                 }
 115
 116                 IEnumerable<KeyValuePair<long, TResult>> GetOrderedEnumerableInternal (IEnumerable<KeyValuePair<long, TSource>> source,
 117                                                                                        SizeRequest[] sizeRequests,
 118                                                                                        int index,
 119                                                                                        Barrier barrier)
 120                 {
 121                         IEnumerator<KeyValuePair<long, TSource>> enumerator = source.GetEnumerator ();
 122                         bool isIndexed = IsIndexed;
 123
 124                         try {
 125                                 while (true) {
 126                                         KeyValuePair<long, TSource> element;
 127                                         IEnumerable<TCollection> collection;
 128
 129                                         if (enumerator.MoveNext ()) {
 130                                                 element = enumerator.Current;
 131                                                 collection = isIndexed ?
 132                                                         collectionSelectorIndexed (element.Value, (int)element.Key) :
 133                                                         collectionSelector (element.Value);
 134
 135                                                 var count = GetCount (ref collection);
 136
 137                                                 sizeRequests[index].Update (element.Key, count, collection, element.Value);
 138                                         }
 139
 140                                         barrier.SignalAndWait ();
 141
 142                                         long i = sizeRequests[index].Key;
 143                                         collection = sizeRequests[index].Collection;
 144                                         var elementValue = sizeRequests[index].ElementValue;
 145
 146                                         sizeRequests[index].Clear ();
 147
 148                                         if (i == -1)
 149                                                 break;
 150
 151                                         foreach (TCollection item in collection)
 152                                                 yield return new KeyValuePair<long, TResult> (i++, resultSelector (elementValue, item));
 153                                 }
 154                         } finally {
 155                                 barrier.RemoveParticipant ();
 156                                 enumerator.Dispose ();
 157                         }
 158                 }
 159
 160                 /* If getting Count is a O(1) operation (i.e. actual is a ICollection) then return it immediatly
 161                  * if not process the IEnumerable into a List and return the Count from that (i.e. enumerable
 162                  * processing will only happen once in case of e.g. a Linq query)
 163                  */
 164                 static int GetCount<T> (ref IEnumerable<T> actual)
 165                 {
 166                         ICollection coll = actual as ICollection;
 167                         if (coll != null)
 168                                 return coll.Count;
 169
 170                         var foo = actual.ToList ();
 171                         actual = foo;
 172
 173                         return foo.Count;
 174                 }
 175
 176                 static int KeyComparator (SizeRequest e1, SizeRequest e2)
 177                 {
 178                         return e1.Key.CompareTo (e2.Key);
 179                 }
 180
 181                 struct SizeRequest
 182                 {
 183                         public long Key;
 184                         public int Size;
 185                         public IEnumerable<TCollection> Collection;
 186                         public TSource ElementValue;
 187
 188                         public void Update (long k, int s, IEnumerable<TCollection> c, TSource ev)
 189                         {
 190                                 Key = k;
 191                                 Size = s;
 192                                 Collection = c;
 193                                 ElementValue = ev;
 194                         }
 195
 196                         public void Clear ()
 197                         {
 198                                 Key = -1;
 199                                 Size = 0;
 200                                 Collection = null;
 201                                 ElementValue = default (TSource);
 202                         }
 203                 }
 204         }
 205 }
 206
 207 #endif