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 24static inline 25unsigned 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 58namespace std { 59template<> 60struct hash<StringPiece> { 61 typedef StringPiece argument_type; 62 typedef size_t result_type; 63 64 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*. 74template<typename V> 75struct ExternalStringHashMap { 76 typedef std::unordered_map<StringPiece, V> Type; 77}; 78 79#endif // NINJA_MAP_H_ 80