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
- Pair.cs
- KnownTypes.cs
- BitmapEffect.cs
- ReturnEventArgs.cs
- MessageRpc.cs
- ResizeGrip.cs
- SymbolType.cs
- Vector3dCollection.cs
- TextParagraphCache.cs
- PersistenceException.cs
- ObjectListTitleAttribute.cs
- StandardOleMarshalObject.cs
- SystemPens.cs
- Rss20ItemFormatter.cs
- SoundPlayerAction.cs
- GridSplitterAutomationPeer.cs
- SqlParameterizer.cs
- ToolboxService.cs
- Misc.cs
- WebPart.cs
- HttpModuleActionCollection.cs
- Message.cs
- Int32CAMarshaler.cs
- HtmlElementErrorEventArgs.cs
- ServiceBusyException.cs
- XmlResolver.cs
- ZipIOFileItemStream.cs
- SamlConditions.cs
- WinEventQueueItem.cs
- CountdownEvent.cs
- AttributeQuery.cs
- UIServiceHelper.cs
- TemplateBindingExpressionConverter.cs
- CommandEventArgs.cs
- PropertyIDSet.cs
- SafeFileMappingHandle.cs
- ProgressBar.cs
- _CacheStreams.cs
- LocalizableResourceBuilder.cs
- XmlReturnReader.cs
- ProfileService.cs
- Timeline.cs
- Selector.cs
- Model3D.cs
- SubMenuStyle.cs
- HttpApplication.cs
- AnnouncementEndpoint.cs
- RoleGroup.cs
- EdmFunctionAttribute.cs
- KernelTypeValidation.cs
- ToolStripItemClickedEventArgs.cs
- COSERVERINFO.cs
- StrokeNodeOperations.cs
- Brushes.cs
- BufferBuilder.cs
- ActivationServices.cs
- OdbcHandle.cs
- AdPostCacheSubstitution.cs
- FixedSOMLineRanges.cs
- StreamGeometry.cs
- HttpRequest.cs
- XmlWrappingReader.cs
- QilGeneratorEnv.cs
- NullReferenceException.cs
- ZoomPercentageConverter.cs
- EntityClientCacheEntry.cs
- RelatedEnd.cs
- configsystem.cs
- KnownTypeDataContractResolver.cs
- DictionaryBase.cs
- EntityDataSourceConfigureObjectContext.cs
- RequestTimeoutManager.cs
- LogicalCallContext.cs
- FirstQueryOperator.cs
- SqlBuilder.cs
- DataListItem.cs
- RegistryPermission.cs
- Label.cs
- RequestTimeoutManager.cs
- CapiSymmetricAlgorithm.cs
- LinqDataSourceView.cs
- FrameworkContentElementAutomationPeer.cs
- Utils.cs
- IncomingWebResponseContext.cs
- Assembly.cs
- ByteKeyFrameCollection.cs
- DataSvcMapFile.cs
- SerializerProvider.cs
- AutomationPatternInfo.cs
- UnsafeNativeMethods.cs
- OrderByLifter.cs
- Types.cs
- UnauthorizedWebPart.cs
- UIAgentMonitorHandle.cs
- RichTextBoxDesigner.cs
- CheckBoxList.cs
- XmlEntity.cs
- CommandID.cs
- SocketInformation.cs
- AtomEntry.cs