mcs/class/dlr/Runtime/Microsoft.Dynamic/Utils/HybridReferenceDictionary.cs

   1 /* ****************************************************************************
   2  *
   3  * Copyright (c) Microsoft Corporation.
   4  *
   5  * This source code is subject to terms and conditions of the Apache License, Version 2.0. A
   6  * copy of the license can be found in the License.html file at the root of this distribution. If
   7  * you cannot locate the  Apache License, Version 2.0, please send an email to
   8  * dlr@microsoft.com. By using this source code in any fashion, you are agreeing to be bound
   9  * by the terms of the Apache License, Version 2.0.
  10  *
  11  * You must not remove this notice, or any other, from this software.
  12  *
  13  *
  14  * ***************************************************************************/
  15
  16 using System;
  17 using System.Collections.Generic;
  18 using System.Text;
  19 using System.Diagnostics;
  20
  21 namespace Microsoft.Scripting.Utils {
  22     /// <summary>
  23     /// A hybrid dictionary which compares based upon object identity.
  24     /// </summary>
  25     class HybridReferenceDictionary<TKey, TValue> where TKey : class {
  26         private KeyValuePair<TKey, TValue>[] _keysAndValues;
  27         private Dictionary<TKey, TValue> _dict;
  28         private int _count;
  29         private const int _arraySize = 10;
  30
  31         public HybridReferenceDictionary() {
  32         }
  33
  34         public HybridReferenceDictionary(int initialCapicity) {
  35             if (initialCapicity > _arraySize) {
  36                 _dict = new Dictionary<TKey, TValue>(initialCapicity);
  37             } else {
  38                 _keysAndValues = new KeyValuePair<TKey, TValue>[initialCapicity];
  39             }
  40         }
  41
  42         public bool TryGetValue(TKey key, out TValue value) {
  43             Debug.Assert(key != null);
  44
  45             if (_dict != null) {
  46                 return _dict.TryGetValue(key, out value);
  47             } else if (_keysAndValues != null) {
  48                 for (int i = 0; i < _keysAndValues.Length; i++) {
  49                     if (_keysAndValues[i].Key == key) {
  50                         value = _keysAndValues[i].Value;
  51                         return true;
  52                     }
  53                 }
  54             }
  55             value = default(TValue);
  56             return false;
  57         }
  58
  59         public bool Remove(TKey key) {
  60             Debug.Assert(key != null);
  61
  62             if (_dict != null) {
  63                 return _dict.Remove(key);
  64             } else if (_keysAndValues != null) {
  65                 for (int i = 0; i < _keysAndValues.Length; i++) {
  66                     if (_keysAndValues[i].Key == key) {
  67                         _keysAndValues[i] = new KeyValuePair<TKey, TValue>();
  68                         _count--;
  69                         return true;
  70                     }
  71                 }
  72             }
  73
  74             return false;
  75         }
  76
  77         public bool ContainsKey(TKey key) {
  78             Debug.Assert(key != null);
  79
  80             if (_dict != null) {
  81                 return _dict.ContainsKey(key);
  82             } else if (_keysAndValues != null) {
  83                 for (int i = 0; i < _keysAndValues.Length; i++) {
  84                     if (_keysAndValues[i].Key == key) {
  85                         return true;
  86                     }
  87                 }
  88             }
  89
  90             return false;
  91         }
  92
  93         public int Count {
  94             get {
  95                 if (_dict != null) {
  96                     return _dict.Count;
  97                 }
  98                 return _count;
  99             }
 100
 101         }
 102
 103         public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator() {
 104             if (_dict != null) {
 105                 return _dict.GetEnumerator();
 106             }
 107
 108             return GetEnumeratorWorker();
 109         }
 110
 111         private IEnumerator<KeyValuePair<TKey, TValue>> GetEnumeratorWorker() {
 112             if (_keysAndValues != null) {
 113                 for (int i = 0; i < _keysAndValues.Length; i++) {
 114                     if (_keysAndValues[i].Key != null) {
 115                         yield return _keysAndValues[i];
 116                     }
 117                 }
 118             }
 119         }
 120
 121         public TValue this[TKey key] {
 122             get {
 123                 Debug.Assert(key != null);
 124
 125                 TValue res;
 126                 if (TryGetValue(key, out res)) {
 127                     return res;
 128                 }
 129
 130                 throw new KeyNotFoundException();
 131             }
 132             set {
 133                 Debug.Assert(key != null);
 134
 135                 if (_dict != null) {
 136                     _dict[key] = value;
 137                 } else {
 138                     int index;
 139                     if (_keysAndValues != null) {
 140                         index = -1;
 141                         for (int i = 0; i < _keysAndValues.Length; i++) {
 142                             if (_keysAndValues[i].Key == key) {
 143                                 _keysAndValues[i] = new KeyValuePair<TKey, TValue>(key, value);
 144                                 return;
 145                             } else if (_keysAndValues[i].Key == null) {
 146                                 index = i;
 147                             }
 148                         }
 149                     } else {
 150                         _keysAndValues = new KeyValuePair<TKey, TValue>[_arraySize];
 151                         index = 0;
 152                     }
 153
 154                     if (index != -1) {
 155                         _count++;
 156                         _keysAndValues[index] = new KeyValuePair<TKey, TValue>(key, value);
 157                     } else {
 158                         _dict = new Dictionary<TKey, TValue>();
 159                         for (int i = 0; i < _keysAndValues.Length; i++) {
 160                             _dict[_keysAndValues[i].Key] = _keysAndValues[i].Value;
 161                         }
 162                         _keysAndValues = null;
 163
 164                         _dict[key] = value;
 165                     }
 166                 }
 167             }
 168         }
 169     }
 170 }