Code:
/ 4.0 / 4.0 / untmp / 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.
Link Menu
This book is available now!
Buy at Amazon US or
Buy at Amazon UK
- SelectionEditingBehavior.cs
- MatrixCamera.cs
- ErrorStyle.cs
- MetadataArtifactLoaderCompositeResource.cs
- MediaElement.cs
- ScrollBar.cs
- RectAnimationBase.cs
- DrawingImage.cs
- HtmlShimManager.cs
- Tuple.cs
- SelectionItemPatternIdentifiers.cs
- DetailsViewPagerRow.cs
- DataGridViewDataErrorEventArgs.cs
- XPathScanner.cs
- HttpCacheVaryByContentEncodings.cs
- objectresult_tresulttype.cs
- CompilerCollection.cs
- SchemaNotation.cs
- WriterOutput.cs
- ControlEvent.cs
- MaterializeFromAtom.cs
- XmlBoundElement.cs
- HttpRawResponse.cs
- Normalization.cs
- RestClientProxyHandler.cs
- BindingEntityInfo.cs
- FormatterConverter.cs
- Regex.cs
- PrintEvent.cs
- DragEvent.cs
- HtmlHead.cs
- WsatTransactionFormatter.cs
- DynamicMethod.cs
- ClientRolePrincipal.cs
- GeneratedView.cs
- FieldBuilder.cs
- SpecialNameAttribute.cs
- TranslateTransform.cs
- SyndicationSerializer.cs
- StrokeNodeEnumerator.cs
- ButtonBaseDesigner.cs
- WarningException.cs
- DefaultValueAttribute.cs
- FormatException.cs
- TargetException.cs
- ConnectorRouter.cs
- EraserBehavior.cs
- BuildResultCache.cs
- SqlRowUpdatingEvent.cs
- ReadOnlyCollectionBase.cs
- XmlBufferReader.cs
- ByteStream.cs
- CheckableControlBaseAdapter.cs
- ZipFileInfoCollection.cs
- PerformanceCounter.cs
- InternalConfigRoot.cs
- Content.cs
- XmlHierarchicalDataSourceView.cs
- SafeFindHandle.cs
- Row.cs
- SettingsPropertyNotFoundException.cs
- ReadOnlyMetadataCollection.cs
- CaseCqlBlock.cs
- WebHttpBindingElement.cs
- CrossSiteScriptingValidation.cs
- NavigationCommands.cs
- DrawingContextDrawingContextWalker.cs
- ConstructorArgumentAttribute.cs
- TreeNodeClickEventArgs.cs
- BindingContext.cs
- EmptyStringExpandableObjectConverter.cs
- WorkflowServiceBuildProvider.cs
- OutKeywords.cs
- IndexedSelectQueryOperator.cs
- AbstractDataSvcMapFileLoader.cs
- InputLanguageCollection.cs
- DataTableNewRowEvent.cs
- InstanceDescriptor.cs
- Calendar.cs
- EditingCommands.cs
- MbpInfo.cs
- EdmTypeAttribute.cs
- CompiledQueryCacheEntry.cs
- TreeView.cs
- ThousandthOfEmRealPoints.cs
- QilGenerator.cs
- SHA384.cs
- NGCSerializationManager.cs
- TextEncodedRawTextWriter.cs
- MoveSizeWinEventHandler.cs
- TakeQueryOptionExpression.cs
- XmlILIndex.cs
- IISUnsafeMethods.cs
- MsmqUri.cs
- TextRangeSerialization.cs
- GeometryGroup.cs
- ObservableCollection.cs
- ListDictionary.cs
- ResourceDescriptionAttribute.cs
- Wizard.cs