Ninja
hash_map.h
Go to the documentation of this file.
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_