HashLookup.cs source code in C# .NET

Source code for the .NET framework in C#

                        
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

Network programming in C#, Network Programming in VB.NET, Network Programming in .NET
This book is available now!
Buy at Amazon US or
Buy at Amazon UK