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 #if (__cplusplus >= 201103L) || (_MSC_VER >= 1900)
57 #include <unordered_map>
58
59 namespace std {
60 template<>
61 struct hash<StringPiece> {
62 typedef StringPiece argument_type;
63 typedef size_t result_type;
64
65 size_t operator()(StringPiece key) const {
66 return MurmurHash2(key.str_, key.len_);
67 }
68 };
69 }
70
71 #elif defined(_MSC_VER)
72 #include <hash_map>
73
74 using stdext::hash_map;
75 using stdext::hash_compare;
76
77 struct StringPieceCmp : public hash_compare<StringPiece> {
78 size_t operator()(const StringPiece& key) const {
79 return MurmurHash2(key.str_, key.len_);
80 }
81 bool operator()(const StringPiece& a, const StringPiece& b) const {
82 int cmp = memcmp(a.str_, b.str_, min(a.len_, b.len_));
83 if (cmp < 0) {
84 return true;
85 } else if (cmp > 0) {
86 return false;
87 } else {
88 return a.len_ < b.len_;
89 }
90 }
91 };
92
93 #else
94 #include <ext/hash_map>
95
96 using __gnu_cxx::hash_map;
97
98 namespace __gnu_cxx {
99 template<>
100 struct hash<StringPiece> {
101 size_t operator()(StringPiece key) const {
102 return MurmurHash2(key.str_, key.len_);
103 }
104 };
105 }
106 #endif
107
108 /// A template for hash_maps keyed by a StringPiece whose string is
109 /// owned externally (typically by the values). Use like:
110 /// ExternalStringHash<Foo*>::Type foos; to make foos into a hash
111 /// mapping StringPiece => Foo*.
112 template<typename V>
113 struct ExternalStringHashMap {
114 #if (__cplusplus >= 201103L) || (_MSC_VER >= 1900)
115 typedef std::unordered_map<StringPiece, V> Type;
116 #elif defined(_MSC_VER)
117 typedef hash_map<StringPiece, V, StringPieceCmp> Type;
118 #else
119 typedef hash_map<StringPiece, V> Type;
120 #endif
121 };
122
123 #endif // NINJA_MAP_H_
124