Ninja
|
00001 // Copyright 2011 Google Inc. All Rights Reserved. 00002 // 00003 // Licensed under the Apache License, Version 2.0 (the "License"); 00004 // you may not use this file except in compliance with the License. 00005 // You may obtain a copy of the License at 00006 // 00007 // http://www.apache.org/licenses/LICENSE-2.0 00008 // 00009 // Unless required by applicable law or agreed to in writing, software 00010 // distributed under the License is distributed on an "AS IS" BASIS, 00011 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 00012 // See the License for the specific language governing permissions and 00013 // limitations under the License. 00014 00015 #ifndef NINJA_MAP_H_ 00016 #define NINJA_MAP_H_ 00017 00018 #include "string_piece.h" 00019 00020 // MurmurHash2, by Austin Appleby 00021 static inline 00022 unsigned int MurmurHash2(const void* key, size_t len) { 00023 static const unsigned int seed = 0xDECAFBAD; 00024 const unsigned int m = 0x5bd1e995; 00025 const int r = 24; 00026 unsigned int h = seed ^ len; 00027 const unsigned char * data = (const unsigned char *)key; 00028 while (len >= 4) { 00029 unsigned int k = *(unsigned int *)data; 00030 k *= m; 00031 k ^= k >> r; 00032 k *= m; 00033 h *= m; 00034 h ^= k; 00035 data += 4; 00036 len -= 4; 00037 } 00038 switch (len) { 00039 case 3: h ^= data[2] << 16; 00040 case 2: h ^= data[1] << 8; 00041 case 1: h ^= data[0]; 00042 h *= m; 00043 }; 00044 h ^= h >> 13; 00045 h *= m; 00046 h ^= h >> 15; 00047 return h; 00048 } 00049 00050 #ifdef _MSC_VER 00051 #include <hash_map> 00052 00053 using stdext::hash_map; 00054 using stdext::hash_compare; 00055 00056 struct StringPieceCmp : public hash_compare<StringPiece> { 00057 size_t operator()(const StringPiece& key) const { 00058 return MurmurHash2(key.str_, key.len_); 00059 } 00060 bool operator()(const StringPiece& a, const StringPiece& b) const { 00061 int cmp = strncmp(a.str_, b.str_, min(a.len_, b.len_)); 00062 if (cmp < 0) { 00063 return true; 00064 } else if (cmp > 0) { 00065 return false; 00066 } else { 00067 return a.len_ < b.len_; 00068 } 00069 } 00070 }; 00071 00072 #else 00073 00074 #include <ext/hash_map> 00075 00076 using __gnu_cxx::hash_map; 00077 00078 namespace __gnu_cxx { 00079 template<> 00080 struct hash<std::string> { 00081 size_t operator()(const std::string& s) const { 00082 return hash<const char*>()(s.c_str()); 00083 } 00084 }; 00085 00086 template<> 00087 struct hash<StringPiece> { 00088 size_t operator()(StringPiece key) const { 00089 return MurmurHash2(key.str_, key.len_); 00090 } 00091 }; 00092 00093 } 00094 #endif 00095 00096 /// A template for hash_maps keyed by a StringPiece whose string is 00097 /// owned externally (typically by the values). Use like: 00098 /// ExternalStringHash<Foo*>::Type foos; to make foos into a hash 00099 /// mapping StringPiece => Foo*. 00100 template<typename V> 00101 struct ExternalStringHashMap { 00102 #ifdef _MSC_VER 00103 typedef hash_map<StringPiece, V, StringPieceCmp> Type; 00104 #else 00105 typedef hash_map<StringPiece, V> Type; 00106 #endif 00107 }; 00108 00109 #endif // NINJA_MAP_H_