Ninja
hash_map.h
Go to the documentation of this file.
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 
22 // MurmurHash2, by Austin Appleby
23 static inline
24 unsigned int MurmurHash2(const void* key, size_t len) {
25  static const unsigned int seed = 0xDECAFBAD;
26  const unsigned int m = 0x5bd1e995;
27  const int r = 24;
28  unsigned int h = seed ^ len;
29  const unsigned char* data = (const unsigned char*)key;
30  while (len >= 4) {
31  unsigned int k;
32  memcpy(&k, data, sizeof k);
33  k *= m;
34  k ^= k >> r;
35  k *= m;
36  h *= m;
37  h ^= k;
38  data += 4;
39  len -= 4;
40  }
41  switch (len) {
42  case 3: h ^= data[2] << 16;
43  case 2: h ^= data[1] << 8;
44  case 1: h ^= data[0];
45  h *= m;
46  };
47  h ^= h >> 13;
48  h *= m;
49  h ^= h >> 15;
50  return h;
51 }
52 
53 #ifdef _MSC_VER
54 #include <hash_map>
55 
56 using stdext::hash_map;
57 using stdext::hash_compare;
58 
59 struct StringPieceCmp : public hash_compare<StringPiece> {
60  size_t operator()(const StringPiece& key) const {
61  return MurmurHash2(key.str_, key.len_);
62  }
63  bool operator()(const StringPiece& a, const StringPiece& b) const {
64  int cmp = strncmp(a.str_, b.str_, min(a.len_, b.len_));
65  if (cmp < 0) {
66  return true;
67  } else if (cmp > 0) {
68  return false;
69  } else {
70  return a.len_ < b.len_;
71  }
72  }
73 };
74 
75 #else
76 
77 #include <ext/hash_map>
78 
79 using __gnu_cxx::hash_map;
80 
81 namespace __gnu_cxx {
82 template<>
83 struct hash<std::string> {
84  size_t operator()(const std::string& s) const {
85  return hash<const char*>()(s.c_str());
86  }
87 };
88 
89 template<>
90 struct hash<StringPiece> {
91  size_t operator()(StringPiece key) const {
92  return MurmurHash2(key.str_, key.len_);
93  }
94 };
95 
96 }
97 #endif
98 
99 /// A template for hash_maps keyed by a StringPiece whose string is
100 /// owned externally (typically by the values). Use like:
101 /// ExternalStringHash<Foo*>::Type foos; to make foos into a hash
102 /// mapping StringPiece => Foo*.
103 template<typename V>
105 #ifdef _MSC_VER
106  typedef hash_map<StringPiece, V, StringPieceCmp> Type;
107 #else
108  typedef hash_map<StringPiece, V> Type;
109 #endif
110 };
111 
112 #endif // NINJA_MAP_H_
const char * str_
Definition: string_piece.h:49
StringPiece represents a slice of a string whose memory is managed externally.
Definition: string_piece.h:27
A template for hash_maps keyed by a StringPiece whose string is owned externally (typically by the va...
Definition: hash_map.h:104
size_t operator()(const std::string &s) const
Definition: hash_map.h:84
size_t operator()(StringPiece key) const
Definition: hash_map.h:91
static unsigned int MurmurHash2(const void *key, size_t len)
Definition: hash_map.h:24
hash_map< StringPiece, V > Type
Definition: hash_map.h:108
size_t len_
Definition: string_piece.h:50