1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
|
#ifndef CDEC_HASH_H
#define CDEC_HASH_H
#include <boost/functional/hash.hpp>
#include "murmur_hash.h"
#include "config.h"
#ifdef HAVE_SPARSEHASH
# include <google/dense_hash_map>
# define HASH_MAP google::dense_hash_map
# define HASH_MAP_RESERVED(h,empty,deleted) do { h.set_empty_key(empty); h.set_deleted_key(deleted); } while(0)
# define HASH_MAP_EMPTY(h,empty) do { h.set_empty_key(empty); } while(0)
#else
# include <tr1/unordered_map>
# define HASH_MAP std::tr1::unordered_map
# define HASH_MAP_RESERVED(h,empty,deleted)
# define HASH_MAP_EMPTY(h,empty)
#endif
#define BOOST_HASHED_MAP(k,v) HASH_MAP<k,v,boost::hash<k> >
// assumes C is POD
template <class C>
struct murmur_hash
{
typedef MurmurInt return_type;
typedef C /*const&*/ argument_type;
return_type operator()(argument_type const& c) const {
return MurmurHash((void*)&c,sizeof(c));
}
};
// murmur_hash_array isn't std guaranteed safe (you need to use string::data())
template <>
struct murmur_hash<std::string>
{
typedef MurmurInt return_type;
typedef std::string /*const&*/ argument_type;
return_type operator()(argument_type const& c) const {
return MurmurHash(c.data(),c.size());
}
};
// uses begin(),size() assuming contiguous layout and POD
template <class C>
struct murmur_hash_array
{
typedef MurmurInt return_type;
typedef C /*const&*/ argument_type;
return_type operator()(argument_type const& c) const {
return MurmurHash(&*c.begin(),c.size()*sizeof(*c.begin()));
}
};
// adds default val to table if key wasn't found, returns ref to val
template <class H,class K>
typename H::mapped_type & get_default(H &ht,K const& k,typename H::mapped_type const& v) {
return const_cast<typename H::mapped_type &>(ht.insert(typename H::value_type(k,v)).first->second);
}
// the below could also return a ref to the mapped max/min. they have the advantage of not falsely claiming an improvement when an equal value already existed. otherwise you could just modify the get_default and if equal assume new.
template <class H,class K>
bool improve_mapped_max(H &ht,K const& k,typename H::mapped_type const& v) {
std::pair<typename H::iterator,bool> inew=ht.insert(typename H::value_type(k,v));
if (inew.second) return true;
typedef typename H::mapped_type V;
V &oldv=const_cast<V&>(inew.first->second);
if (oldv<v) {
oldv=v;
return true;
}
return false;
}
template <class H,class K>
bool improve_mapped_min(H &ht,K const& k,typename H::mapped_type const& v) {
std::pair<typename H::iterator,bool> inew=ht.insert(typename H::value_type(k,v));
if (inew.second) return true;
typedef typename H::mapped_type V;
V &oldv=const_cast<V&>(inew.first->second);
if (v<oldv) { // the only difference from above
oldv=v;
return true;
}
return false;
}
#endif
|
