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
MurmurHash2(const void* key, size_t len)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
operator ()std::hash64 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