1 // Copyright 2011 Google Inc. All Rights Reserved.
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
7 // http://www.apache.org/licenses/LICENSE-2.0
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.
20 #include "string_piece.h"
22 // MurmurHash2, by Austin Appleby
24 unsigned int MurmurHash2(const void* key, size_t len) {
25 static const unsigned int seed = 0xDECAFBAD;
26 const unsigned int m = 0x5bd1e995;
28 unsigned int h = seed ^ len;
29 const unsigned char* data = (const unsigned char*)key;
32 memcpy(&k, data, sizeof k);
42 case 3: h ^= data[2] << 16;
43 case 2: h ^= data[1] << 8;
53 #if (__cplusplus >= 201103L) || (_MSC_VER >= 1900)
54 #include <unordered_map>
58 struct hash<StringPiece> {
59 typedef StringPiece argument_type;
60 typedef size_t result_type;
62 size_t operator()(StringPiece key) const {
63 return MurmurHash2(key.str_, key.len_);
68 #elif defined(_MSC_VER)
71 using stdext::hash_map;
72 using stdext::hash_compare;
74 struct StringPieceCmp : public hash_compare<StringPiece> {
75 size_t operator()(const StringPiece& key) const {
76 return MurmurHash2(key.str_, key.len_);
78 bool operator()(const StringPiece& a, const StringPiece& b) const {
79 int cmp = strncmp(a.str_, b.str_, min(a.len_, b.len_));
85 return a.len_ < b.len_;
91 #include <ext/hash_map>
93 using __gnu_cxx::hash_map;
97 struct hash<StringPiece> {
98 size_t operator()(StringPiece key) const {
99 return MurmurHash2(key.str_, key.len_);
105 /// A template for hash_maps keyed by a StringPiece whose string is
106 /// owned externally (typically by the values). Use like:
107 /// ExternalStringHash<Foo*>::Type foos; to make foos into a hash
108 /// mapping StringPiece => Foo*.
110 struct ExternalStringHashMap {
111 #if (__cplusplus >= 201103L) || (_MSC_VER >= 1900)
112 typedef std::unordered_map<StringPiece, V> Type;
113 #elif defined(_MSC_VER)
114 typedef hash_map<StringPiece, V, StringPieceCmp> Type;
116 typedef hash_map<StringPiece, V> Type;
120 #endif // NINJA_MAP_H_