Permalink
Switch branches/tags
version-2.9.0 version-2.8.2 version-2.8.0 version-2.7.0-beta3 version-2.6.0-beta3 version-2.4.0 version-2.3.5 version-2.3.4 version-2.3.2 version-2.3.2-beta1 version-2.3.0-beta3 version-2.3.0-beta2 version-2.3.0-beta1 version-2.2.0 version-2.1.0 version-2.0.0 version-2.0.0-rc4 version-2.0.0-rc3 version-2.0.0-rc2 version-2.0.0-rc version-2.0.0-beta5 version-2.0.0-beta4 version-2.0.0-beta3 version-2.0.0-beta1 version-1.3.2 version-1.3.1 version-1.3.0 version-1.3.0-beta1-20160429-01 version-1.2.2 version-1.2.1 version-1.2.0 version-1.2.0-beta1-20160108-01 version-1.2.0-beta version-1.2.0-beta-20151211-01 version-1.1.1 version-1.1.0 version-1.1.0-rc1-20151109-01 version-1.0.0 version-1.0.0-beta1-20141031-01 toolset_5 toolset_3 toolset_2 toolset_1_1 toolset_1 Visual.Studio.2015.Update.1.RC Visual.Studio.2015.Update.1.CTP Visual-Studio-2017 Visual-Studio-2017-Version-15.8 Visual-Studio-2017-Version-15.7.2 Visual-Studio-2017-Version-15.7 Visual-Studio-2017-Version-15.6 Visual-Studio-2017-Version-15.5 Visual-Studio-2017-Version-15.4 Visual-Studio-2017-Version-15.3.5 Visual-Studio-2017-Version-15.3.4 Visual-Studio-2017-Version-15.3.2 Visual-Studio-2017-Version-15.3 Visual-Studio-2017-Version-15.2 Visual-Studio-2017-Version-15.1 Visual-Studio-2017-RC4 Visual-Studio-2017-RC3 Visual-Studio-2017-RC2 Visual-Studio-2017-RC Visual-Studio-2017-Preview-Version-15.3 Visual-Studio-2017-Preview-6-Version-15.7 Visual-Studio-2017-Preview-3-Version-15.4 Visual-Studio-2017-Preview-3-Version-15.3 Visual-Studio-2017-Preview-2-Version-15.4 Visual-Studio-2017-Preview-2-Version-15.3 Visual-Studio-2017-Preview-1-Version-15.4 Visual-Studio-2015 Visual-Studio-2015-Update-3 Visual-Studio-2015-Update-3-Micro-Update-1 Visual-Studio-2015-Update-2 Visual-Studio-2015-Update-2-RC Visual-Studio-2015-Update-2-Micro-Update-3 Visual-Studio-2015-Update-2-Micro-Update-1 Visual-Studio-2015-Update-1 Visual-Studio-2015-Update-1-RC Visual-Studio-2015-Update-1-CTP Visual-Studio-2015-RC Visual-Studio-2015-Preview Visual-Studio-2015-CTP-6 Visual-Studio-2015-CTP-5 Visual-Studio-15-Preview Visual-Studio-15-Preview-5 Visual-Studio-15-Preview-4 Visual-Studio-15-Preview-3 VS.Toolset.Roslyn.1.1.0-beta1-20150727-01 VS.Tools.X86.Managed.V45.1.0.150513.2 Oss.Scan.2015.03.13 Oss.Scan.2013.03.13 NetFx.Toolset.150729
Nothing to show
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
369 lines (314 sloc) 13.7 KB
// Copyright (c) Microsoft. All Rights Reserved. Licensed under the Apache License, Version 2.0. See License.txt in the project root for license information.
using System;
using System.Collections.Generic;
using System.Collections.Immutable;
using Microsoft.CodeAnalysis;
namespace Roslyn.Utilities
{
internal static class Hash
{
/// <summary>
/// This is how VB Anonymous Types combine hash values for fields.
/// </summary>
internal static int Combine(int newKey, int currentKey)
{
return unchecked((currentKey * (int)0xA5555529) + newKey);
}
internal static int Combine(bool newKeyPart, int currentKey)
{
return Combine(currentKey, newKeyPart ? 1 : 0);
}
/// <summary>
/// This is how VB Anonymous Types combine hash values for fields.
/// PERF: Do not use with enum types because that involves multiple
/// unnecessary boxing operations. Unfortunately, we can't constrain
/// T to "non-enum", so we'll use a more restrictive constraint.
/// </summary>
internal static int Combine<T>(T newKeyPart, int currentKey) where T : class
{
int hash = unchecked(currentKey * (int)0xA5555529);
if (newKeyPart != null)
{
return unchecked(hash + newKeyPart.GetHashCode());
}
return hash;
}
internal static int CombineValues<T>(IEnumerable<T> values, int maxItemsToHash = int.MaxValue)
{
if (values == null)
{
return 0;
}
var hashCode = 0;
var count = 0;
foreach (var value in values)
{
if (count++ >= maxItemsToHash)
{
break;
}
// Should end up with a constrained virtual call to object.GetHashCode (i.e. avoid boxing where possible).
if (value != null)
{
hashCode = Hash.Combine(value.GetHashCode(), hashCode);
}
}
return hashCode;
}
internal static int CombineValues<T>(T[] values, int maxItemsToHash = int.MaxValue)
{
if (values == null)
{
return 0;
}
var maxSize = Math.Min(maxItemsToHash, values.Length);
var hashCode = 0;
for (int i = 0; i < maxSize; i++)
{
T value = values[i];
// Should end up with a constrained virtual call to object.GetHashCode (i.e. avoid boxing where possible).
if (value != null)
{
hashCode = Hash.Combine(value.GetHashCode(), hashCode);
}
}
return hashCode;
}
internal static int CombineValues<T>(ImmutableArray<T> values, int maxItemsToHash = int.MaxValue)
{
if (values.IsDefaultOrEmpty)
{
return 0;
}
var hashCode = 0;
var count = 0;
foreach (var value in values)
{
if (count++ >= maxItemsToHash)
{
break;
}
// Should end up with a constrained virtual call to object.GetHashCode (i.e. avoid boxing where possible).
if (value != null)
{
hashCode = Hash.Combine(value.GetHashCode(), hashCode);
}
}
return hashCode;
}
internal static int CombineValues(IEnumerable<string> values, StringComparer stringComparer, int maxItemsToHash = int.MaxValue)
{
if (values == null)
{
return 0;
}
var hashCode = 0;
var count = 0;
foreach (var value in values)
{
if (count++ >= maxItemsToHash)
{
break;
}
if (value != null)
{
hashCode = Hash.Combine(stringComparer.GetHashCode(value), hashCode);
}
}
return hashCode;
}
/// <summary>
/// The offset bias value used in the FNV-1a algorithm
/// See http://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function
/// </summary>
internal const int FnvOffsetBias = unchecked((int)2166136261);
/// <summary>
/// The generative factor used in the FNV-1a algorithm
/// See http://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function
/// </summary>
internal const int FnvPrime = 16777619;
/// <summary>
/// Compute the FNV-1a hash of a sequence of bytes
/// See http://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function
/// </summary>
/// <param name="data">The sequence of bytes</param>
/// <returns>The FNV-1a hash of <paramref name="data"/></returns>
internal static int GetFNVHashCode(byte[] data)
{
int hashCode = Hash.FnvOffsetBias;
for (int i = 0; i < data.Length; i++)
{
hashCode = unchecked((hashCode ^ data[i]) * Hash.FnvPrime);
}
return hashCode;
}
/// <summary>
/// Compute the FNV-1a hash of a sequence of bytes and determines if the byte
/// sequence is valid ASCII and hence the hash code matches a char sequence
/// encoding the same text.
/// See http://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function
/// </summary>
/// <param name="data">The sequence of bytes that are likely to be ASCII text.</param>
/// <param name="length">The length of the sequence.</param>
/// <param name="isAscii">True if the sequence contains only characters in the ASCII range.</param>
/// <returns>The FNV-1a hash of <paramref name="data"/></returns>
internal static unsafe int GetFNVHashCode(byte* data, int length, out bool isAscii)
{
int hashCode = Hash.FnvOffsetBias;
byte asciiMask = 0;
for (int i = 0; i < length; i++)
{
byte b = data[i];
asciiMask |= b;
hashCode = unchecked((hashCode ^ b) * Hash.FnvPrime);
}
isAscii = (asciiMask & 0x80) == 0;
return hashCode;
}
/// <summary>
/// Compute the FNV-1a hash of a sequence of bytes
/// See http://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function
/// </summary>
/// <param name="data">The sequence of bytes</param>
/// <returns>The FNV-1a hash of <paramref name="data"/></returns>
internal static int GetFNVHashCode(ImmutableArray<byte> data)
{
int hashCode = Hash.FnvOffsetBias;
for (int i = 0; i < data.Length; i++)
{
hashCode = unchecked((hashCode ^ data[i]) * Hash.FnvPrime);
}
return hashCode;
}
/// <summary>
/// Compute the hashcode of a sub-string using FNV-1a
/// See http://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function
/// Note: FNV-1a was developed and tuned for 8-bit sequences. We're using it here
/// for 16-bit Unicode chars on the understanding that the majority of chars will
/// fit into 8-bits and, therefore, the algorithm will retain its desirable traits
/// for generating hash codes.
/// </summary>
/// <param name="text">The input string</param>
/// <param name="start">The start index of the first character to hash</param>
/// <param name="length">The number of characters, beginning with <paramref name="start"/> to hash</param>
/// <returns>The FNV-1a hash code of the substring beginning at <paramref name="start"/> and ending after <paramref name="length"/> characters.</returns>
internal static int GetFNVHashCode(string text, int start, int length)
{
int hashCode = Hash.FnvOffsetBias;
int end = start + length;
for (int i = start; i < end; i++)
{
hashCode = unchecked((hashCode ^ text[i]) * Hash.FnvPrime);
}
return hashCode;
}
internal static int GetCaseInsensitiveFNVHashCode(string text)
{
return GetCaseInsensitiveFNVHashCode(text, 0, text.Length);
}
internal static int GetCaseInsensitiveFNVHashCode(string text, int start, int length)
{
int hashCode = Hash.FnvOffsetBias;
int end = start + length;
for (int i = start; i < end; i++)
{
hashCode = unchecked((hashCode ^ CaseInsensitiveComparison.ToLower(text[i])) * Hash.FnvPrime);
}
return hashCode;
}
/// <summary>
/// Compute the hashcode of a sub-string using FNV-1a
/// See http://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function
/// </summary>
/// <param name="text">The input string</param>
/// <param name="start">The start index of the first character to hash</param>
/// <returns>The FNV-1a hash code of the substring beginning at <paramref name="start"/> and ending at the end of the string.</returns>
internal static int GetFNVHashCode(string text, int start)
{
return GetFNVHashCode(text, start, length: text.Length - start);
}
/// <summary>
/// Compute the hashcode of a string using FNV-1a
/// See http://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function
/// </summary>
/// <param name="text">The input string</param>
/// <returns>The FNV-1a hash code of <paramref name="text"/></returns>
internal static int GetFNVHashCode(string text)
{
return CombineFNVHash(Hash.FnvOffsetBias, text);
}
/// <summary>
/// Compute the hashcode of a string using FNV-1a
/// See http://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function
/// </summary>
/// <param name="text">The input string</param>
/// <returns>The FNV-1a hash code of <paramref name="text"/></returns>
internal static int GetFNVHashCode(System.Text.StringBuilder text)
{
int hashCode = Hash.FnvOffsetBias;
int end = text.Length;
for (int i = 0; i < end; i++)
{
hashCode = unchecked((hashCode ^ text[i]) * Hash.FnvPrime);
}
return hashCode;
}
/// <summary>
/// Compute the hashcode of a sub string using FNV-1a
/// See http://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function
/// </summary>
/// <param name="text">The input string as a char array</param>
/// <param name="start">The start index of the first character to hash</param>
/// <param name="length">The number of characters, beginning with <paramref name="start"/> to hash</param>
/// <returns>The FNV-1a hash code of the substring beginning at <paramref name="start"/> and ending after <paramref name="length"/> characters.</returns>
internal static int GetFNVHashCode(char[] text, int start, int length)
{
int hashCode = Hash.FnvOffsetBias;
int end = start + length;
for (int i = start; i < end; i++)
{
hashCode = unchecked((hashCode ^ text[i]) * Hash.FnvPrime);
}
return hashCode;
}
/// <summary>
/// Compute the hashcode of a single character using the FNV-1a algorithm
/// See http://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function
/// Note: In general, this isn't any more useful than "char.GetHashCode". However,
/// it may be needed if you need to generate the same hash code as a string or
/// substring with just a single character.
/// </summary>
/// <param name="ch">The character to hash</param>
/// <returns>The FNV-1a hash code of the character.</returns>
internal static int GetFNVHashCode(char ch)
{
return Hash.CombineFNVHash(Hash.FnvOffsetBias, ch);
}
/// <summary>
/// Combine a string with an existing FNV-1a hash code
/// See http://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function
/// </summary>
/// <param name="hashCode">The accumulated hash code</param>
/// <param name="text">The string to combine</param>
/// <returns>The result of combining <paramref name="hashCode"/> with <paramref name="text"/> using the FNV-1a algorithm</returns>
internal static int CombineFNVHash(int hashCode, string text)
{
foreach (char ch in text)
{
hashCode = unchecked((hashCode ^ ch) * Hash.FnvPrime);
}
return hashCode;
}
/// <summary>
/// Combine a char with an existing FNV-1a hash code
/// See http://en.wikipedia.org/wiki/Fowler%E2%80%93Noll%E2%80%93Vo_hash_function
/// </summary>
/// <param name="hashCode">The accumulated hash code</param>
/// <param name="ch">The new character to combine</param>
/// <returns>The result of combining <paramref name="hashCode"/> with <paramref name="ch"/> using the FNV-1a algorithm</returns>
internal static int CombineFNVHash(int hashCode, char ch)
{
return unchecked((hashCode ^ ch) * Hash.FnvPrime);
}
}
}