Code:
/ 4.0 / 4.0 / DEVDIV_TFS / Dev10 / Releases / RTMRel / ndp / fx / src / Core / System / Linq / Parallel / Utils / HashLookup.cs / 1305376 / HashLookup.cs
// ==++== // // Copyright (c) Microsoft Corporation. All rights reserved. // // ==--== // =+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+ // // HashLookup.cs // //[....] // // =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- using System.Collections.Generic; using System.Diagnostics.Contracts; namespace System.Linq.Parallel { ////// A simple hash map data structure, derived from the LINQ set we also use. /// ///The kind of keys contained within. ///The kind of values contained within. internal class HashLookup{ int[] buckets; Slot[] slots; int count; int freeList; IEqualityComparer comparer; internal HashLookup() : this(null) { } internal HashLookup(IEqualityComparer comparer) { this.comparer = comparer; buckets = new int[7]; slots = new Slot[7]; freeList = -1; } // If value is not in set, add it and return true; otherwise return false internal bool Add(TKey key, TValue value) { return !Find(key, true, false, ref value); } // Check whether value is in set internal bool TryGetValue(TKey key, ref TValue value) { return Find(key, false, false, ref value); } internal TValue this[TKey key] { set { TValue v = value; Find(key, false, true, ref v); } } private int GetKeyHashCode(TKey key) { return 0x7fffffff & (comparer == null ? (key == null ? 0 : key.GetHashCode()) : comparer.GetHashCode(key)); } private bool AreKeysEqual(TKey key1, TKey key2) { return (comparer == null ? ((key1 == null && key2 == null) || (key1 != null && key1.Equals(key2))) : comparer.Equals(key1, key2)); } // If value is in set, remove it and return true; otherwise return false internal bool Remove(TKey key) { int hashCode = GetKeyHashCode(key); int bucket = hashCode % buckets.Length; int last = -1; for (int i = buckets[bucket] - 1; i >= 0; last = i, i = slots[i].next) { if (slots[i].hashCode == hashCode && AreKeysEqual(slots[i].key, key)) { if (last < 0) { buckets[bucket] = slots[i].next + 1; } else { slots[last].next = slots[i].next; } slots[i].hashCode = -1; slots[i].key = default(TKey); slots[i].value = default(TValue); slots[i].next = freeList; freeList = i; return true; } } return false; } private bool Find(TKey key, bool add, bool set, ref TValue value) { int hashCode = GetKeyHashCode(key); for (int i = buckets[hashCode % buckets.Length] - 1; i >= 0; i = slots[i].next) { if (slots[i].hashCode == hashCode && AreKeysEqual(slots[i].key, key)) { if (set) { slots[i].value = value; return true; } else { value = slots[i].value; return true; } } } if (add) { int index; if (freeList >= 0) { index = freeList; freeList = slots[index].next; } else { if (count == slots.Length) Resize(); index = count; count++; } int bucket = hashCode % buckets.Length; slots[index].hashCode = hashCode; slots[index].key = key; slots[index].value = value; slots[index].next = buckets[bucket] - 1; buckets[bucket] = index + 1; } return false; } void Resize() { int newSize = checked(count * 2 + 1); int[] newBuckets = new int[newSize]; Slot[] newSlots = new Slot[newSize]; Array.Copy(slots, 0, newSlots, 0, count); for (int i = 0; i < count; i++) { int bucket = newSlots[i].hashCode % newSize; newSlots[i].next = newBuckets[bucket] - 1; newBuckets[bucket] = i + 1; } buckets = newBuckets; slots = newSlots; } internal int Count { get { return count; } } internal KeyValuePair this[int index] { get { return new KeyValuePair (slots[index].key, slots[index].value); } } internal struct Slot { internal int hashCode; internal TKey key; internal TValue value; internal int next; } } } // File provided for Reference Use Only by Microsoft Corporation (c) 2007. // ==++== // // Copyright (c) Microsoft Corporation. All rights reserved. // // ==--== // =+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+ // // HashLookup.cs // // [....] // // =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- using System.Collections.Generic; using System.Diagnostics.Contracts; namespace System.Linq.Parallel { ////// A simple hash map data structure, derived from the LINQ set we also use. /// ///The kind of keys contained within. ///The kind of values contained within. internal class HashLookup{ int[] buckets; Slot[] slots; int count; int freeList; IEqualityComparer comparer; internal HashLookup() : this(null) { } internal HashLookup(IEqualityComparer comparer) { this.comparer = comparer; buckets = new int[7]; slots = new Slot[7]; freeList = -1; } // If value is not in set, add it and return true; otherwise return false internal bool Add(TKey key, TValue value) { return !Find(key, true, false, ref value); } // Check whether value is in set internal bool TryGetValue(TKey key, ref TValue value) { return Find(key, false, false, ref value); } internal TValue this[TKey key] { set { TValue v = value; Find(key, false, true, ref v); } } private int GetKeyHashCode(TKey key) { return 0x7fffffff & (comparer == null ? (key == null ? 0 : key.GetHashCode()) : comparer.GetHashCode(key)); } private bool AreKeysEqual(TKey key1, TKey key2) { return (comparer == null ? ((key1 == null && key2 == null) || (key1 != null && key1.Equals(key2))) : comparer.Equals(key1, key2)); } // If value is in set, remove it and return true; otherwise return false internal bool Remove(TKey key) { int hashCode = GetKeyHashCode(key); int bucket = hashCode % buckets.Length; int last = -1; for (int i = buckets[bucket] - 1; i >= 0; last = i, i = slots[i].next) { if (slots[i].hashCode == hashCode && AreKeysEqual(slots[i].key, key)) { if (last < 0) { buckets[bucket] = slots[i].next + 1; } else { slots[last].next = slots[i].next; } slots[i].hashCode = -1; slots[i].key = default(TKey); slots[i].value = default(TValue); slots[i].next = freeList; freeList = i; return true; } } return false; } private bool Find(TKey key, bool add, bool set, ref TValue value) { int hashCode = GetKeyHashCode(key); for (int i = buckets[hashCode % buckets.Length] - 1; i >= 0; i = slots[i].next) { if (slots[i].hashCode == hashCode && AreKeysEqual(slots[i].key, key)) { if (set) { slots[i].value = value; return true; } else { value = slots[i].value; return true; } } } if (add) { int index; if (freeList >= 0) { index = freeList; freeList = slots[index].next; } else { if (count == slots.Length) Resize(); index = count; count++; } int bucket = hashCode % buckets.Length; slots[index].hashCode = hashCode; slots[index].key = key; slots[index].value = value; slots[index].next = buckets[bucket] - 1; buckets[bucket] = index + 1; } return false; } void Resize() { int newSize = checked(count * 2 + 1); int[] newBuckets = new int[newSize]; Slot[] newSlots = new Slot[newSize]; Array.Copy(slots, 0, newSlots, 0, count); for (int i = 0; i < count; i++) { int bucket = newSlots[i].hashCode % newSize; newSlots[i].next = newBuckets[bucket] - 1; newBuckets[bucket] = i + 1; } buckets = newBuckets; slots = newSlots; } internal int Count { get { return count; } } internal KeyValuePair this[int index] { get { return new KeyValuePair (slots[index].key, slots[index].value); } } internal struct Slot { internal int hashCode; internal TKey key; internal TValue value; internal int next; } } } // File provided for Reference Use Only by Microsoft Corporation (c) 2007.
Link Menu
This book is available now!
Buy at Amazon US or
Buy at Amazon UK
- Manipulation.cs
- ControlFilterExpression.cs
- PenContext.cs
- CopyOfAction.cs
- CustomValidator.cs
- CfgArc.cs
- CustomErrorCollection.cs
- ItemsControl.cs
- DataContractSerializerOperationBehavior.cs
- TypeUnloadedException.cs
- SqlCommandBuilder.cs
- SerialReceived.cs
- FileDialog_Vista.cs
- SecurityElement.cs
- GeometryModel3D.cs
- TextDecoration.cs
- EventSinkActivityDesigner.cs
- DataServiceQueryException.cs
- FontResourceCache.cs
- DesignBinding.cs
- StringResourceManager.cs
- ContextInformation.cs
- StackOverflowException.cs
- TakeQueryOptionExpression.cs
- DateTimeConverter.cs
- XmlValueConverter.cs
- LockRenewalTask.cs
- ListItemCollection.cs
- XmlSchemaProviderAttribute.cs
- LabelLiteral.cs
- DictionaryBase.cs
- AxParameterData.cs
- ObjectItemLoadingSessionData.cs
- ValueSerializer.cs
- ParamArrayAttribute.cs
- DuplicateWaitObjectException.cs
- EncryptedPackage.cs
- ScrollChangedEventArgs.cs
- FunctionImportMapping.ReturnTypeRenameMapping.cs
- TraversalRequest.cs
- PersonalizationDictionary.cs
- Bezier.cs
- BaseCAMarshaler.cs
- RegexStringValidatorAttribute.cs
- ICspAsymmetricAlgorithm.cs
- CodeDomDecompiler.cs
- PhoneCallDesigner.cs
- DataColumnMapping.cs
- ExeContext.cs
- TextAdaptor.cs
- HttpTransportManager.cs
- ResourceDescriptionAttribute.cs
- DebugHandleTracker.cs
- CellParagraph.cs
- TextChange.cs
- ScalarConstant.cs
- PenLineCapValidation.cs
- DriveNotFoundException.cs
- RegexRunner.cs
- SqlBinder.cs
- LassoHelper.cs
- RC2.cs
- WorkflowMessageEventHandler.cs
- SHA256Managed.cs
- StaticTextPointer.cs
- DataGridViewCheckBoxCell.cs
- TransactionValidationBehavior.cs
- RuleValidation.cs
- DataGridViewRowEventArgs.cs
- TCPClient.cs
- LassoSelectionBehavior.cs
- AutomationTextAttribute.cs
- MonitorWrapper.cs
- Boolean.cs
- CorePropertiesFilter.cs
- WebPartEventArgs.cs
- MemoryRecordBuffer.cs
- CompilerGeneratedAttribute.cs
- ScaleTransform.cs
- DrawItemEvent.cs
- precedingquery.cs
- columnmapkeybuilder.cs
- BitmapEffectrendercontext.cs
- ConfigurationConverterBase.cs
- XmlIncludeAttribute.cs
- EncodedStreamFactory.cs
- ResourceLoader.cs
- WhitespaceRule.cs
- DataRowChangeEvent.cs
- Point4D.cs
- ObjectToken.cs
- SqlDataRecord.cs
- TrimSurroundingWhitespaceAttribute.cs
- wmiprovider.cs
- ByteAnimationBase.cs
- XPathDocument.cs
- SoapFaultCodes.cs
- Avt.cs
- RoutingService.cs
- ActivitySurrogateSelector.cs