The OpenD Programming Language

1 module ikod.containers.hash;
2 
3 import std.traits;
4 
5 ///
6 /// For classes (and structs with toHash method) we use v.toHash() to compute hash.
7 /// ===============================================================================
8 /// toHash method CAN BE @nogc or not. HashMap 'nogc' properties is inherited from this method.
9 /// toHash method MUST BE @safe or @trusted, as all HashMap code alredy safe.
10 ///
11 /// See also: https://dlang.org/spec/hash-map.html#using_classes_as_key 
12 /// and https://dlang.org/spec/hash-map.html#using_struct_as_key
13 ///
14 bool UseToHashMethod(T)() {
15     return (is(T == class) || (is(T==struct) && __traits(compiles, {
16         T v = T.init; hash_t h = v.toHash();
17     })));
18 }
19 
20 public hash_t hash_function(T)(T v) /* @safe @nogc inherited from toHash method */
21 if ( UseToHashMethod!T )
22 {
23     return v.toHash();
24 }
25 
26 public hash_t hash_function(T)(in T v) @nogc @trusted
27 if ( !UseToHashMethod!T )
28 {
29     static if (is(T==byte) || is(T==ubyte))
30     {
31         return v;
32     }
33     else static if ( isNumeric!T ) {
34         enum m = 0x5bd1e995;
35         hash_t h = cast(hash_t)v;
36         h ^= h >> 13;
37         h *= m;
38         h ^= h >> 15;
39         return h;
40     }
41     else static if ( is(T == string) ) {
42         // // FNV-1a hash
43         // ulong h = 0xcbf29ce484222325;
44         // foreach (const ubyte c; cast(ubyte[]) v)
45         // {
46         //     h ^= c;
47         //     h *= 0x100000001b3;
48         // }
49         // return cast(hash_t)h;
50         import core.internal.hash : bytesHash;
51         return bytesHash(cast(void*)v.ptr, v.length, 0);
52     }
53     else
54     {
55         const(ubyte)[] bytes = (cast(const(ubyte)*)&v)[0 .. T.sizeof];
56         ulong h = 0xcbf29ce484222325;
57         foreach (const ubyte c; bytes)
58         {
59             h ^= c;
60             h *= 0x100000001b3;
61         }
62         return cast(hash_t)h;
63     }
64 }
65 
66 @safe unittest
67 {
68     //assert(hash_function("abc") == cast(hash_t)0xe71fa2190541574b);
69 
70     struct A0 {}
71     assert(!UseToHashMethod!A0);
72 
73     struct A1 {
74         hash_t toHash() const @safe {
75             return 0;
76         }
77     }
78     assert(UseToHashMethod!A1);
79 
80     // class with toHash override - will use toHash
81     class C0 {
82         override hash_t toHash() const @safe {
83             return 0;
84         }
85     }
86     assert(UseToHashMethod!C0);
87     C0 c0 = new C0();
88     assert(c0.toHash() == 0);
89 
90     // class without toHash override - use Object.toHash method
91     class C1 {
92     }
93     assert(UseToHashMethod!C1);
94 }