1 | // Copyright 2011 Google Inc. All Rights Reserved. |
2 | // |
3 | // Licensed under the Apache License, Version 2.0 (the "License"); |
4 | // you may not use this file except in compliance with the License. |
5 | // You may obtain a copy of the License at |
6 | // |
7 | // http://www.apache.org/licenses/LICENSE-2.0 |
8 | // |
9 | // Unless required by applicable law or agreed to in writing, software |
10 | // distributed under the License is distributed on an "AS IS" BASIS, |
11 | // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
12 | // See the License for the specific language governing permissions and |
13 | // limitations under the License. |
14 | |
15 | #ifndef NINJA_MAP_H_ |
16 | #define NINJA_MAP_H_ |
17 | |
18 | #include <algorithm> |
19 | #include <string.h> |
20 | #include "string_piece.h" |
21 | #include "util.h" |
22 | |
23 | // MurmurHash2, by Austin Appleby |
24 | static inline |
25 | unsigned int MurmurHash2(const void* key, size_t len) { |
26 | static const unsigned int seed = 0xDECAFBAD; |
27 | const unsigned int m = 0x5bd1e995; |
28 | const int r = 24; |
29 | unsigned int h = seed ^ len; |
30 | const unsigned char* data = (const unsigned char*)key; |
31 | while (len >= 4) { |
32 | unsigned int k; |
33 | memcpy(&k, data, sizeof k); |
34 | k *= m; |
35 | k ^= k >> r; |
36 | k *= m; |
37 | h *= m; |
38 | h ^= k; |
39 | data += 4; |
40 | len -= 4; |
41 | } |
42 | switch (len) { |
43 | case 3: h ^= data[2] << 16; |
44 | NINJA_FALLTHROUGH; |
45 | case 2: h ^= data[1] << 8; |
46 | NINJA_FALLTHROUGH; |
47 | case 1: h ^= data[0]; |
48 | h *= m; |
49 | }; |
50 | h ^= h >> 13; |
51 | h *= m; |
52 | h ^= h >> 15; |
53 | return h; |
54 | } |
55 | |
56 | #include <unordered_map> |
57 | |
58 | namespace std { |
59 | template<> |
60 | struct hash<StringPiece> { |
61 | typedef StringPiece argument_type; |
62 | typedef size_t result_type; |
63 | |
64 | size_t operator()(StringPiece key) const { |
65 | return MurmurHash2(key.str_, key.len_); |
66 | } |
67 | }; |
68 | } |
69 | |
70 | /// A template for hash_maps keyed by a StringPiece whose string is |
71 | /// owned externally (typically by the values). Use like: |
72 | /// ExternalStringHash<Foo*>::Type foos; to make foos into a hash |
73 | /// mapping StringPiece => Foo*. |
74 | template<typename V> |
75 | struct ExternalStringHashMap { |
76 | typedef std::unordered_map<StringPiece, V> Type; |
77 | }; |
78 | |
79 | #endif // NINJA_MAP_H_ |
80 | |