mcs/class/System.Threading.Tasks.Dataflow/CoreFxSources/Internal/QueuedMap.cs

   1 // Copyright (c) Microsoft. All rights reserved.
   2 // Licensed under the MIT license. See LICENSE file in the project root for full license information.
   3
   4 // =+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+
   5 //
   6 // QueuedMap.cs
   7 //
   8 //
   9 // A key-value pair queue, where pushing an existing key into the collection overwrites
  10 // the existing value.
  11 //
  12 // =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
  13
  14 using System.Collections;
  15 using System.Collections.Generic;
  16 using System.Diagnostics;
  17 using System.Diagnostics.Contracts;
  18
  19 namespace System.Threading.Tasks.Dataflow.Internal
  20 {
  21     /// <summary>
  22     /// Provides a data structure that supports pushing and popping key/value pairs.
  23     /// Pushing a key/value pair for which the key already exists results in overwriting
  24     /// the existing key entry's value.
  25     /// </summary>
  26     /// <typeparam name="TKey">Specifies the type of keys in the map.</typeparam>
  27     /// <typeparam name="TValue">Specifies the type of values in the map.</typeparam>
  28     /// <remarks>This type is not thread-safe.</remarks>
  29     [DebuggerDisplay("Count = {Count}")]
  30     [DebuggerTypeProxy(typeof(EnumerableDebugView<,>))]
  31     internal sealed class QueuedMap<TKey, TValue>
  32     {
  33         /// <summary>
  34         /// A queue structure that uses an array-based list to store its items
  35         /// and that supports overwriting elements at specific indices.
  36         /// </summary>
  37         /// <typeparam name="T">The type of the items storedin the queue</typeparam>
  38         /// <remarks>This type is not thread-safe.</remarks>
  39         private sealed class ArrayBasedLinkedQueue<T>
  40         {
  41             /// <summary>Terminator index.</summary>
  42             private const int TERMINATOR_INDEX = -1;
  43             /// <summary>
  44             /// The queue where the items will be stored.
  45             /// The key of each entry is the index of the next entry in the queue.
  46             /// </summary>
  47             private readonly List<KeyValuePair<int, T>> _storage;
  48             /// <summary>Index of the first queue item.</summary>
  49             private int _headIndex = TERMINATOR_INDEX;
  50             /// <summary>Index of the last queue item.</summary>
  51             private int _tailIndex = TERMINATOR_INDEX;
  52             /// <summary>Index of the first free slot.</summary>
  53             private int _freeIndex = TERMINATOR_INDEX;
  54
  55             /// <summary>Initializes the Queue instance.</summary>
  56             internal ArrayBasedLinkedQueue()
  57             {
  58                 _storage = new List<KeyValuePair<int, T>>();
  59             }
  60
  61             /// <summary>Initializes the Queue instance.</summary>
  62             /// <param name="capacity">The capacity of the internal storage.</param>
  63             internal ArrayBasedLinkedQueue(int capacity)
  64             {
  65                 _storage = new List<KeyValuePair<int, T>>(capacity);
  66             }
  67
  68             /// <summary>Enqueues an item.</summary>
  69             /// <param name="item">The item to be enqueued.</param>
  70             /// <returns>The index of the slot where item was stored.</returns>
  71             internal int Enqueue(T item)
  72             {
  73                 int newIndex;
  74
  75                 // If there is a free slot, reuse it
  76                 if (_freeIndex != TERMINATOR_INDEX)
  77                 {
  78                     Debug.Assert(0 <= _freeIndex && _freeIndex < _storage.Count, "Index is out of range.");
  79                     newIndex = _freeIndex;
  80                     _freeIndex = _storage[_freeIndex].Key;
  81                     _storage[newIndex] = new KeyValuePair<int, T>(TERMINATOR_INDEX, item);
  82                 }
  83                 // If there is no free slot, add one
  84                 else
  85                 {
  86                     newIndex = _storage.Count;
  87                     _storage.Add(new KeyValuePair<int, T>(TERMINATOR_INDEX, item));
  88                 }
  89
  90                 if (_headIndex == TERMINATOR_INDEX)
  91                 {
  92                     // Point _headIndex to newIndex if the queue was empty
  93                     Debug.Assert(_tailIndex == TERMINATOR_INDEX, "If head indicates empty, so too should tail.");
  94                     _headIndex = newIndex;
  95                 }
  96                 else
  97                 {
  98                     // Point the tail slot to newIndex if the queue was not empty
  99                     Debug.Assert(_tailIndex != TERMINATOR_INDEX, "If head does not indicate empty, neither should tail.");
 100                     _storage[_tailIndex] = new KeyValuePair<int, T>(newIndex, _storage[_tailIndex].Value);
 101                 }
 102
 103                 // Point the tail slot newIndex
 104                 _tailIndex = newIndex;
 105
 106                 return newIndex;
 107             }
 108
 109             /// <summary>Tries to dequeue an item.</summary>
 110             /// <param name="item">The item that is dequeued.</param>
 111             internal bool TryDequeue(out T item)
 112             {
 113                 // If the queue is empty, just initialize the output item and return false
 114                 if (_headIndex == TERMINATOR_INDEX)
 115                 {
 116                     Debug.Assert(_tailIndex == TERMINATOR_INDEX, "If head indicates empty, so too should tail.");
 117                     item = default(T);
 118                     return false;
 119                 }
 120
 121                 // If there are items in the queue, start with populating the output item
 122                 Debug.Assert(0 <= _headIndex && _headIndex < _storage.Count, "Head is out of range.");
 123                 item = _storage[_headIndex].Value;
 124
 125                 // Move the popped slot to the head of the free list
 126                 int newHeadIndex = _storage[_headIndex].Key;
 127                 _storage[_headIndex] = new KeyValuePair<int, T>(_freeIndex, default(T));
 128                 _freeIndex = _headIndex;
 129                 _headIndex = newHeadIndex;
 130                 if (_headIndex == TERMINATOR_INDEX) _tailIndex = TERMINATOR_INDEX;
 131
 132                 return true;
 133             }
 134
 135             /// <summary>Replaces the item of a given slot.</summary>
 136             /// <param name="index">The index of the slot where the value should be replaced.</param>
 137             /// <param name="item">The item to be places.</param>
 138             internal void Replace(int index, T item)
 139             {
 140                 Debug.Assert(0 <= index && index < _storage.Count, "Index is out of range.");
 141 #if DEBUG
 142                 // Also assert that index does not belong to the list of free slots
 143                 for (int idx = _freeIndex; idx != TERMINATOR_INDEX; idx = _storage[idx].Key)
 144                     Debug.Assert(idx != index, "Index should not belong to the list of free slots.");
 145 #endif
 146                 _storage[index] = new KeyValuePair<int, T>(_storage[index].Key, item);
 147             }
 148
 149             internal bool IsEmpty { get { return _headIndex == TERMINATOR_INDEX; } }
 150         }
 151
 152         /// <summary>The queue of elements.</summary>
 153         private readonly ArrayBasedLinkedQueue<KeyValuePair<TKey, TValue>> _queue;
 154         /// <summary>A map from key to index into the list.</summary>
 155         /// <remarks>The correctness of this map relies on the list only having elements removed from its end.</remarks>
 156         private readonly Dictionary<TKey, int> _mapKeyToIndex;
 157
 158         /// <summary>Initializes the QueuedMap.</summary>
 159         internal QueuedMap()
 160         {
 161             _queue = new ArrayBasedLinkedQueue<KeyValuePair<TKey, TValue>>();
 162             _mapKeyToIndex = new Dictionary<TKey, int>();
 163         }
 164
 165         /// <summary>Initializes the QueuedMap.</summary>
 166         /// <param name="capacity">The initial capacity of the data structure.</param>
 167         internal QueuedMap(int capacity)
 168         {
 169             _queue = new ArrayBasedLinkedQueue<KeyValuePair<TKey, TValue>>(capacity);
 170             _mapKeyToIndex = new Dictionary<TKey, int>(capacity);
 171         }
 172
 173         /// <summary>Pushes a key/value pair into the data structure.</summary>
 174         /// <param name="key">The key for the pair.</param>
 175         /// <param name="value">The value for the pair.</param>
 176         internal void Push(TKey key, TValue value)
 177         {
 178             // Try to get the index of the key in the queue. If it's there, replace the value.
 179             int indexOfKeyInQueue;
 180             if (!_queue.IsEmpty && _mapKeyToIndex.TryGetValue(key, out indexOfKeyInQueue))
 181             {
 182                 _queue.Replace(indexOfKeyInQueue, new KeyValuePair<TKey, TValue>(key, value));
 183             }
 184             // If it's not there, add it to the queue and then add the mapping.
 185             else
 186             {
 187                 indexOfKeyInQueue = _queue.Enqueue(new KeyValuePair<TKey, TValue>(key, value));
 188                 _mapKeyToIndex.Add(key, indexOfKeyInQueue);
 189             }
 190         }
 191
 192         /// <summary>Try to pop the next element from the data structure.</summary>
 193         /// <param name="item">The popped pair.</param>
 194         /// <returns>true if an item could be popped; otherwise, false.</returns>
 195         internal bool TryPop(out KeyValuePair<TKey, TValue> item)
 196         {
 197             bool popped = _queue.TryDequeue(out item);
 198             if (popped) _mapKeyToIndex.Remove(item.Key);
 199             return popped;
 200         }
 201
 202         /// <summary>Tries to pop one or more elements from the data structure.</summary>
 203         /// <param name="items">The items array into which the popped elements should be stored.</param>
 204         /// <param name="arrayOffset">The offset into the array at which to start storing popped items.</param>
 205         /// <param name="count">The number of items to be popped.</param>
 206         /// <returns>The number of items popped, which may be less than the requested number if fewer existed in the data structure.</returns>
 207         internal int PopRange(KeyValuePair<TKey, TValue>[] items, int arrayOffset, int count)
 208         {
 209             // As this data structure is internal, only assert incorrect usage.
 210             // If this were to ever be made public, these would need to be real argument checks.
 211             Contract.Requires(items != null, "Requires non-null array to store into.");
 212             Contract.Requires(count >= 0 && arrayOffset >= 0, "Count and offset must be non-negative");
 213             Contract.Requires(arrayOffset + count >= 0, "Offset plus count overflowed");
 214             Contract.Requires(arrayOffset + count <= items.Length, "Range must be within array size");
 215
 216             int actualCount = 0;
 217             for (int i = arrayOffset; actualCount < count; i++, actualCount++)
 218             {
 219                 KeyValuePair<TKey, TValue> item;
 220                 if (TryPop(out item)) items[i] = item;
 221                 else break;
 222             }
 223
 224             return actualCount;
 225         }
 226
 227         /// <summary>Gets the number of items in the data structure.</summary>
 228         internal int Count { get { return _mapKeyToIndex.Count; } }
 229     }
 230 }