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