1 //------------------------------------------------------------------------------ 2 // <copyright file="OrderedDictionary.cs" company="Microsoft"> 3 // Copyright (c) Microsoft Corporation. All rights reserved. 4 // </copyright> 5 //------------------------------------------------------------------------------ 6 7 namespace System.Collections.Specialized { 8 9 using System; 10 using System.Collections; 11 using System.Diagnostics.CodeAnalysis; 12 using System.Runtime.Serialization; 13 using System.Security.Permissions; 14 15 /// <devdoc> 16 /// <para> 17 /// OrderedDictionary offers IDictionary syntax with ordering. Objects 18 /// added or inserted in an IOrderedDictionary must have both a key and an index, and 19 /// can be retrieved by either. 20 /// OrderedDictionary is used by the ParameterCollection because MSAccess relies on ordering of 21 /// parameters, while almost all other DBs do not. DataKeyArray also uses it so 22 /// DataKeys can be retrieved by either their name or their index. 23 /// 24 /// OrderedDictionary implements IDeserializationCallback because it needs to have the 25 /// contained ArrayList and Hashtable deserialized before it tries to get its count and objects. 26 /// </para> 27 /// </devdoc> 28 [Serializable] 29 public class OrderedDictionary : IOrderedDictionary, ISerializable, IDeserializationCallback { 30 31 private ArrayList _objectsArray; 32 private Hashtable _objectsTable; 33 private int _initialCapacity; 34 private IEqualityComparer _comparer; 35 private bool _readOnly; 36 private Object _syncRoot; 37 private SerializationInfo _siInfo; //A temporary variable which we need during deserialization. 38 39 private const string KeyComparerName = "KeyComparer"; 40 private const string ArrayListName = "ArrayList"; 41 private const string ReadOnlyName = "ReadOnly"; 42 private const string InitCapacityName = "InitialCapacity"; 43 OrderedDictionary()44 public OrderedDictionary() : this(0) { 45 } 46 OrderedDictionary(int capacity)47 public OrderedDictionary(int capacity) : this(capacity, null) { 48 } 49 OrderedDictionary(IEqualityComparer comparer)50 public OrderedDictionary(IEqualityComparer comparer) : this(0, comparer) { 51 } 52 OrderedDictionary(int capacity, IEqualityComparer comparer)53 public OrderedDictionary(int capacity, IEqualityComparer comparer) { 54 _initialCapacity = capacity; 55 _comparer = comparer; 56 } 57 OrderedDictionary(OrderedDictionary dictionary)58 private OrderedDictionary(OrderedDictionary dictionary) { 59 if (dictionary == null) { 60 throw new ArgumentNullException("dictionary"); 61 } 62 63 _readOnly = true; 64 _objectsArray = dictionary._objectsArray; 65 _objectsTable = dictionary._objectsTable; 66 _comparer = dictionary._comparer; 67 _initialCapacity = dictionary._initialCapacity; 68 } 69 OrderedDictionary(SerializationInfo info, StreamingContext context)70 protected OrderedDictionary(SerializationInfo info, StreamingContext context) { 71 // We can't do anything with the keys and values until the entire graph has been deserialized 72 // and getting Counts and objects won't fail. For the time being, we'll just cache this. 73 // The graph is not valid until OnDeserialization has been called. 74 _siInfo = info; 75 } 76 77 /// <devdoc> 78 /// Gets the size of the table. 79 /// </devdoc> 80 public int Count { 81 get { 82 return objectsArray.Count; 83 } 84 } 85 86 /// <devdoc> 87 /// Indicates that the collection can grow. 88 /// </devdoc> 89 bool IDictionary.IsFixedSize { 90 get { 91 return _readOnly; 92 } 93 } 94 95 /// <devdoc> 96 /// Indicates that the collection is not read-only 97 /// </devdoc> 98 public bool IsReadOnly { 99 get { 100 return _readOnly; 101 } 102 } 103 104 /// <devdoc> 105 /// Indicates that this class is not synchronized 106 /// </devdoc> 107 bool ICollection.IsSynchronized { 108 get { 109 return false; 110 } 111 } 112 113 /// <devdoc> 114 /// Gets the collection of keys in the table in order. 115 /// </devdoc> 116 public ICollection Keys { 117 get { 118 return new OrderedDictionaryKeyValueCollection(objectsArray, true); 119 } 120 } 121 122 private ArrayList objectsArray { 123 get { 124 if (_objectsArray == null) { 125 _objectsArray = new ArrayList(_initialCapacity); 126 } 127 return _objectsArray; 128 } 129 } 130 131 private Hashtable objectsTable { 132 get { 133 if (_objectsTable == null) { 134 _objectsTable = new Hashtable(_initialCapacity, _comparer); 135 } 136 return _objectsTable; 137 } 138 } 139 140 /// <devdoc> 141 /// The SyncRoot object. Not used because IsSynchronized is false 142 /// </devdoc> 143 object ICollection.SyncRoot { 144 get { 145 if (_syncRoot == null) { 146 System.Threading.Interlocked.CompareExchange(ref _syncRoot, new Object(), null); 147 } 148 return _syncRoot; 149 } 150 } 151 152 /// <devdoc> 153 /// Gets or sets the object at the specified index 154 /// </devdoc> 155 public object this[int index] { 156 get { 157 return ((DictionaryEntry)objectsArray[index]).Value; 158 } 159 set { 160 if (_readOnly) { 161 throw new NotSupportedException(SR.GetString(SR.OrderedDictionary_ReadOnly)); 162 } 163 if (index < 0 || index >= objectsArray.Count) { 164 throw new ArgumentOutOfRangeException("index"); 165 } 166 object key = ((DictionaryEntry)objectsArray[index]).Key; 167 objectsArray[index] = new DictionaryEntry(key, value); 168 objectsTable[key] = value; 169 } 170 } 171 172 /// <devdoc> 173 /// Gets or sets the object with the specified key 174 /// </devdoc> 175 public object this[object key] { 176 get { 177 return objectsTable[key]; 178 } 179 set { 180 if (_readOnly) { 181 throw new NotSupportedException(SR.GetString(SR.OrderedDictionary_ReadOnly)); 182 } 183 if (objectsTable.Contains(key)) { 184 objectsTable[key] = value; 185 objectsArray[IndexOfKey(key)] = new DictionaryEntry(key, value); 186 } 187 else { 188 Add(key, value); 189 } 190 } 191 } 192 193 /// <devdoc> 194 /// Returns an arrayList of the values in the table 195 /// </devdoc> 196 public ICollection Values { 197 get { 198 return new OrderedDictionaryKeyValueCollection(objectsArray, false); 199 } 200 } 201 202 /// <devdoc> 203 /// Adds a new entry to the table with the lowest-available index. 204 /// </devdoc> Add(object key, object value)205 public void Add(object key, object value) { 206 if (_readOnly) { 207 throw new NotSupportedException(SR.GetString(SR.OrderedDictionary_ReadOnly)); 208 } 209 objectsTable.Add(key, value); 210 objectsArray.Add(new DictionaryEntry(key, value)); 211 } 212 213 /// <devdoc> 214 /// Clears all elements in the table. 215 /// </devdoc> Clear()216 public void Clear() { 217 if (_readOnly) { 218 throw new NotSupportedException(SR.GetString(SR.OrderedDictionary_ReadOnly)); 219 } 220 objectsTable.Clear(); 221 objectsArray.Clear(); 222 } 223 224 /// <devdoc> 225 /// Returns a readonly OrderedDictionary for the given OrderedDictionary. 226 /// </devdoc> AsReadOnly()227 public OrderedDictionary AsReadOnly() { 228 return new OrderedDictionary(this); 229 } 230 231 /// <devdoc> 232 /// Returns true if the key exists in the table, false otherwise. 233 /// </devdoc> Contains(object key)234 public bool Contains(object key) { 235 return objectsTable.Contains(key); 236 } 237 238 /// <devdoc> 239 /// Copies the table to an array. This will not preserve order. 240 /// </devdoc> CopyTo(Array array, int index)241 public void CopyTo(Array array, int index) { 242 objectsTable.CopyTo(array, index); 243 } 244 IndexOfKey(object key)245 private int IndexOfKey(object key) { 246 for (int i = 0; i < objectsArray.Count; i++) { 247 object o = ((DictionaryEntry)objectsArray[i]).Key; 248 if (_comparer != null) { 249 if (_comparer.Equals(o, key)) { 250 return i; 251 } 252 } 253 else { 254 if (o.Equals(key)) { 255 return i; 256 } 257 } 258 } 259 return -1; 260 } 261 262 /// <devdoc> 263 /// Inserts a new object at the given index with the given key. 264 /// </devdoc> Insert(int index, object key, object value)265 public void Insert(int index, object key, object value) { 266 if (_readOnly) { 267 throw new NotSupportedException(SR.GetString(SR.OrderedDictionary_ReadOnly)); 268 } 269 if (index > Count || index < 0) { 270 throw new ArgumentOutOfRangeException("index"); 271 } 272 objectsTable.Add(key, value); 273 objectsArray.Insert(index, new DictionaryEntry(key, value)); 274 } 275 276 /// <devdoc> 277 /// Handles the deserization event. This method can be overridden. 278 /// </devdoc> OnDeserialization(object sender)279 protected virtual void OnDeserialization(object sender) { 280 if (_siInfo == null) { 281 throw new SerializationException(SR.GetString(SR.Serialization_InvalidOnDeser)); 282 } 283 _comparer = (IEqualityComparer)_siInfo.GetValue(KeyComparerName, typeof(IEqualityComparer)); 284 _readOnly = _siInfo.GetBoolean(ReadOnlyName); 285 _initialCapacity = _siInfo.GetInt32(InitCapacityName); 286 287 object[] serArray = (object[])_siInfo.GetValue(ArrayListName, typeof(object[])); 288 289 if (serArray != null) { 290 foreach (object o in serArray) { 291 DictionaryEntry entry; 292 try { 293 // DictionaryEntry is a value type, so it can only be casted. 294 entry = (DictionaryEntry)o; 295 } 296 catch { 297 throw new SerializationException(SR.GetString(SR.OrderedDictionary_SerializationMismatch)); 298 } 299 objectsArray.Add(entry); 300 objectsTable.Add(entry.Key, entry.Value); 301 } 302 } 303 } 304 305 /// <devdoc> 306 /// Removes the entry at the given index. 307 /// </devdoc> RemoveAt(int index)308 public void RemoveAt(int index) { 309 if (_readOnly) { 310 throw new NotSupportedException(SR.GetString(SR.OrderedDictionary_ReadOnly)); 311 } 312 if (index >= Count || index < 0) { 313 throw new ArgumentOutOfRangeException("index"); 314 } 315 object key = ((DictionaryEntry)objectsArray[index]).Key; 316 objectsArray.RemoveAt(index); 317 objectsTable.Remove(key); 318 } 319 320 /// <devdoc> 321 /// Removes the entry with the given key. 322 /// </devdoc> Remove(object key)323 public void Remove(object key) { 324 if (_readOnly) { 325 throw new NotSupportedException(SR.GetString(SR.OrderedDictionary_ReadOnly)); 326 } 327 if (key == null) { 328 throw new ArgumentNullException("key"); 329 } 330 331 int index = IndexOfKey(key); 332 if (index < 0) { 333 return; 334 } 335 336 objectsTable.Remove(key); 337 objectsArray.RemoveAt(index); 338 } 339 340 #region IDictionary implementation 341 /// <internalonly/> GetEnumerator()342 public virtual IDictionaryEnumerator GetEnumerator() { 343 return new OrderedDictionaryEnumerator(objectsArray, OrderedDictionaryEnumerator.DictionaryEntry); 344 } 345 #endregion 346 347 #region IEnumerable implementation 348 /// <internalonly/> IEnumerable.GetEnumerator()349 IEnumerator IEnumerable.GetEnumerator() { 350 return new OrderedDictionaryEnumerator(objectsArray, OrderedDictionaryEnumerator.DictionaryEntry); 351 } 352 #endregion 353 354 #region ISerializable implementation 355 [SuppressMessage("Microsoft.Security", "CA2123:OverrideLinkDemandsShouldBeIdenticalToBase", 356 Justification="mscorlib removed all link demands, so don't warn when overriding a method " + 357 "with no link demand. Replace the LinkDemand with a SecurityCritical" + 358 "annotation when the assembly is moved to the v4 security model.")] 359 [SecurityPermissionAttribute(SecurityAction.LinkDemand, Flags=SecurityPermissionFlag.SerializationFormatter)] GetObjectData(SerializationInfo info, StreamingContext context)360 public virtual void GetObjectData(SerializationInfo info, StreamingContext context) { 361 if (info == null) { 362 throw new ArgumentNullException("info"); 363 } 364 info.AddValue(KeyComparerName, _comparer, typeof(IEqualityComparer)); 365 info.AddValue(ReadOnlyName, _readOnly); 366 info.AddValue(InitCapacityName, _initialCapacity); 367 object[] serArray = new object[Count]; 368 _objectsArray.CopyTo(serArray); 369 info.AddValue(ArrayListName, serArray); 370 } 371 #endregion 372 373 #region IDeserializationCallback implementation IDeserializationCallback.OnDeserialization(object sender)374 void IDeserializationCallback.OnDeserialization(object sender) { 375 OnDeserialization(sender); 376 } 377 #endregion 378 379 /// <devdoc> 380 /// OrderedDictionaryEnumerator works just like any other IDictionaryEnumerator, but it retrieves DictionaryEntries 381 /// in the order by index. 382 /// </devdoc> 383 private class OrderedDictionaryEnumerator : IDictionaryEnumerator { 384 385 private int _objectReturnType; 386 internal const int Keys = 1; 387 internal const int Values = 2; 388 internal const int DictionaryEntry = 3; 389 private IEnumerator arrayEnumerator; 390 OrderedDictionaryEnumerator(ArrayList array, int objectReturnType)391 internal OrderedDictionaryEnumerator (ArrayList array, int objectReturnType) { 392 arrayEnumerator = array.GetEnumerator(); 393 _objectReturnType = objectReturnType; 394 } 395 396 /// <devdoc> 397 /// Retrieves the current DictionaryEntry. This is the same as Entry, but not strongly-typed. 398 /// </devdoc> 399 public object Current { 400 get { 401 if (_objectReturnType == Keys) { 402 return ((DictionaryEntry)arrayEnumerator.Current).Key; 403 } 404 if (_objectReturnType == Values) { 405 return ((DictionaryEntry)arrayEnumerator.Current).Value; 406 } 407 return Entry; 408 } 409 } 410 411 /// <devdoc> 412 /// Retrieves the current DictionaryEntry 413 /// </devdoc> 414 public DictionaryEntry Entry { 415 get { 416 return new DictionaryEntry(((DictionaryEntry)arrayEnumerator.Current).Key, ((DictionaryEntry)arrayEnumerator.Current).Value); 417 } 418 } 419 420 /// <devdoc> 421 /// Retrieves the key of the current DictionaryEntry 422 /// </devdoc> 423 public object Key { 424 get { 425 return ((DictionaryEntry)arrayEnumerator.Current).Key; 426 } 427 } 428 429 /// <devdoc> 430 /// Retrieves the value of the current DictionaryEntry 431 /// </devdoc> 432 public object Value { 433 get { 434 return ((DictionaryEntry)arrayEnumerator.Current).Value; 435 } 436 } 437 438 /// <devdoc> 439 /// Moves the enumerator pointer to the next member 440 /// </devdoc> MoveNext()441 public bool MoveNext() { 442 return arrayEnumerator.MoveNext(); 443 } 444 445 /// <devdoc> 446 /// Resets the enumerator pointer to the beginning. 447 /// </devdoc> Reset()448 public void Reset() { 449 arrayEnumerator.Reset(); 450 } 451 } 452 453 /// <devdoc> 454 /// OrderedDictionaryKeyValueCollection implements a collection for the Values and Keys properties 455 /// that is "live"- it will reflect changes to the OrderedDictionary on the collection made after the getter 456 /// was called. 457 /// </devdoc> 458 private class OrderedDictionaryKeyValueCollection : ICollection { 459 private ArrayList _objects; 460 bool isKeys; 461 OrderedDictionaryKeyValueCollection(ArrayList array, bool isKeys)462 public OrderedDictionaryKeyValueCollection(ArrayList array, bool isKeys) { 463 this._objects = array; 464 this.isKeys = isKeys; 465 } 466 ICollection.CopyTo(Array array, int index)467 void ICollection.CopyTo(Array array, int index) { 468 if (array==null) 469 throw new ArgumentNullException("array"); 470 if (index < 0) 471 throw new ArgumentOutOfRangeException("index"); 472 foreach (object o in _objects) { 473 array.SetValue(isKeys ? ((DictionaryEntry)o).Key : ((DictionaryEntry)o).Value, index); 474 index++; 475 } 476 } 477 478 int ICollection.Count { 479 get { 480 return _objects.Count; 481 } 482 } 483 484 bool ICollection.IsSynchronized { 485 get { 486 return false; 487 } 488 } 489 490 object ICollection.SyncRoot { 491 get { 492 return _objects.SyncRoot; 493 } 494 } 495 IEnumerable.GetEnumerator()496 IEnumerator IEnumerable.GetEnumerator() { 497 return new OrderedDictionaryEnumerator(_objects, isKeys == true ? OrderedDictionaryEnumerator.Keys : OrderedDictionaryEnumerator.Values); 498 } 499 } 500 } 501 } 502 503