Ninja
Main Page
Namespaces
Classes
Files
File List
File Members
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>
104
struct
ExternalStringHashMap
{
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_
StringPiece::str_
const char * str_
Definition:
string_piece.h:49
StringPiece
StringPiece represents a slice of a string whose memory is managed externally.
Definition:
string_piece.h:27
std
__gnu_cxx
Definition:
hash_map.h:81
ExternalStringHashMap
A template for hash_maps keyed by a StringPiece whose string is owned externally (typically by the va...
Definition:
hash_map.h:104
__gnu_cxx::hash< std::string >::operator()
size_t operator()(const std::string &s) const
Definition:
hash_map.h:84
__gnu_cxx::hash< StringPiece >::operator()
size_t operator()(StringPiece key) const
Definition:
hash_map.h:91
MurmurHash2
static unsigned int MurmurHash2(const void *key, size_t len)
Definition:
hash_map.h:24
ExternalStringHashMap::Type
hash_map< StringPiece, V > Type
Definition:
hash_map.h:108
StringPiece::len_
size_t len_
Definition:
string_piece.h:50
string_piece.h
Generated on Wed Jan 7 2015 13:17:45 for Ninja by
1.8.8