1 /******************************************************************************* 2 3 Hash calculator used in Map and Set, uses FNV1a to hash primitive values and 4 dynamic or static arrays of such. 5 6 Copyright: 7 Copyright (c) 2009-2016 dunnhumby Germany GmbH. 8 All rights reserved. 9 10 License: 11 Boost Software License Version 1.0. See LICENSE_BOOST.txt for details. 12 Alternatively, this file may be distributed under the terms of the Tango 13 3-Clause BSD License (see LICENSE_BSD.txt for details). 14 15 *******************************************************************************/ 16 17 module ocean.util.container.map.model.StandardHash; 18 19 import ocean.meta.types.Qualifiers; 20 21 struct StandardHash 22 { 23 static: 24 25 /************************************************************************** 26 27 Evaluates to true if T is a primitive value type; that is, a numeric 28 (integer, floating point, complex) or character type. 29 30 **************************************************************************/ 31 32 template IsPrimitiveValueType ( T ) 33 { 34 // TODO: Remove `creal` in v7.0.0 35 enum IsPrimitiveValueType = is (T : real) || is (T : creal) || is (T : dchar); 36 } 37 38 /************************************************************************** 39 40 Calculates the hash value from key. 41 42 - If K is a primitive type (integer, floating point, character), the 43 hash value is calculated from the raw key data using the FNV1a hash 44 function. 45 - If K is a dynamic or static array of a primitive type, the hash value 46 is calculated from the raw data of the key array content using the 47 FNV1a hash function. 48 - If K is a class, interface, struct or union, it is expected to 49 implement toHash(), which will be used. 50 - Other key types (arrays of non-primitive types, classes/interfaces/ 51 structs/unions which do not implement toHash(), pointers, function 52 references, delegates, associative arrays) are not supported. 53 54 Params: 55 key = key to hash 56 57 Returns: 58 the hash value that corresponds to key. 59 60 **************************************************************************/ 61 62 hash_t toHash ( K ) ( in K key ) 63 { 64 static if (StandardHash.IsPrimitiveValueType!(K)) 65 { 66 return StandardHash.fnv1aT(key); 67 } 68 else static if (is (K E : E[])) 69 { 70 static assert (StandardHash.IsPrimitiveValueType!(E), 71 "only arrays of primitive value types supported, " 72 ~ "not '" ~ K.stringof ~ '\''); 73 74 return StandardHash.fnv1a(key); 75 } 76 else 77 { 78 static assert (is (K == class) || is (K == interface) 79 || is (K == struct) || is (K == union), 80 "only primitive value types, arrays of such and " 81 ~ "classes/interfaces/structs/unions implementing " 82 ~ "toHash() supported, not '" ~ K.stringof ~ '\''); 83 84 // HACK: we don't want to start implementing all our class `toHash` 85 // methods as `const` yet, have to cast to silence druntime 86 static if (is(K == class) || is(K == interface)) 87 return (cast(Unqual!(K)) key).toHash(); 88 else 89 return key.toHash(); 90 } 91 } 92 93 94 /************************************************************************** 95 96 FNV1 magic constants. 97 98 **************************************************************************/ 99 100 static if (is (hash_t == uint)) 101 { 102 enum hash_t fnv1a_prime = 0x0100_0193, // 32 bit fnv1a prime 103 fnv1a_init = 0x811C_9DC5; // 32 bit initial digest 104 } 105 else 106 { 107 static assert (is (hash_t == ulong)); 108 109 enum hash_t fnv1a_prime = 0x0000_0100_0000_01B3, // 64 bit fnv1a prime 110 fnv1a_init = 0xCBF2_9CE4_8422_2325; // 64 bit initial digest 111 } 112 113 /************************************************************************** 114 115 Calculates the FNV1a hash value from data. 116 117 Params: 118 data = input data 119 hash = optional input hash 120 121 Returns: 122 the FNV1a hash value calculated from data. 123 124 **************************************************************************/ 125 126 hash_t fnv1a ( in void[] data, hash_t hash = fnv1a_init ) 127 { 128 foreach (d; cast (ubyte[]) data) 129 { 130 hash = (hash ^ d) * StandardHash.fnv1a_prime; 131 } 132 133 return hash; 134 } 135 136 /************************************************************************** 137 138 Calculates the FNV1a hash value from the raw data of x using an unrolled 139 loop to improve efficiency. 140 141 Note that, if T is a reference type, the hash value will be calculated 142 from the reference, not the referenced value. 143 144 Params: 145 x = input value 146 hash = optional input hash 147 148 Returns: 149 the FNV1a hash value calculated from the raw data of x. 150 151 **************************************************************************/ 152 153 hash_t fnv1aT ( T ) ( T x, hash_t hash = fnv1a_init ) 154 { 155 mixin (fnv1aCode!(hash.stringof, x.stringof, x.sizeof)); 156 157 return hash; 158 } 159 160 /************************************************************************** 161 162 Evaluates to D code that implements the calculation of FNV1a of a 163 variable named var with n bytes of size, storing the result in a 164 variable named hashvar. The initial value of hashvar should be 165 fnv1a_init or a previously calculated FNV1a hash. 166 167 Example: Let x be an int variable to calculate the hash value from and 168 result be the result variable: 169 --- 170 int x; 171 172 hash_t result = fnv1a_init; 173 --- 174 175 Then 176 177 --- 178 fnv1aCode!("result", x.stringof, x.sizeof) 179 --- 180 181 , where x.sizeof is 4, evaluates to 182 183 --- 184 auto __x = cast(ubyte*)&x; 185 186 result = (result ^ __x[0LU]) * 1099511628211LU; 187 result = (result ^ __x[1LU]) * 1099511628211LU; 188 result = (result ^ __x[2LU]) * 1099511628211LU; 189 result = (result ^ __x[3LU]) * 1099511628211LU; 190 --- 191 192 **************************************************************************/ 193 194 template fnv1aCode ( istring hashvar, istring var, size_t n ) 195 { 196 static if (n) 197 { 198 enum istring fnv1aCode = fnv1aCode!(hashvar, var, n - 1) ~ hashvar ~ "=(" ~ 199 hashvar ~ "^__" ~ var ~ "[" ~ 200 minus1!(n).stringof ~ "])*" ~ 201 fnv1a_prime.stringof ~ ";\n"; 202 } 203 else 204 { 205 enum istring fnv1aCode = "auto __" ~ var ~ 206 "=cast(" ~ ubyte.stringof ~ "*)&" ~ var ~ 207 ";\n"; 208 } 209 } 210 211 212 /************************************************************************** 213 214 Evaluates to n - 1. 215 216 **************************************************************************/ 217 218 template minus1 ( size_t n ) 219 { 220 enum size_t minus1 = n - 1; 221 } 222 }