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
|
// Copyright 2009-2020 Intel Corporation
// SPDX-License-Identifier: Apache-2.0
#pragma once
#include "parallel_sort.h"
namespace embree
{
/*! implementation of a key/value map with parallel construction */
template<typename Key, typename Val>
class parallel_map
{
/* key/value pair to build the map */
struct KeyValue
{
__forceinline KeyValue () {}
__forceinline KeyValue (const Key key, const Val val)
: key(key), val(val) {}
__forceinline operator Key() const {
return key;
}
public:
Key key;
Val val;
};
public:
/*! parallel map constructors */
parallel_map () {}
/*! construction from pair of vectors */
template<typename KeyVector, typename ValVector>
parallel_map (const KeyVector& keys, const ValVector& values) { init(keys,values); }
/*! initialized the parallel map from a vector with keys and values */
template<typename KeyVector, typename ValVector>
void init(const KeyVector& keys, const ValVector& values)
{
/* reserve sufficient space for all data */
assert(keys.size() == values.size());
vec.resize(keys.size());
/* generate key/value pairs */
parallel_for( size_t(0), keys.size(), size_t(4*4096), [&](const range<size_t>& r) {
for (size_t i=r.begin(); i<r.end(); i++)
vec[i] = KeyValue((Key)keys[i],values[i]);
});
/* perform parallel radix sort of the key/value pairs */
std::vector<KeyValue> temp(keys.size());
radix_sort<KeyValue,Key>(vec.data(),temp.data(),keys.size());
}
/*! Returns a pointer to the value associated with the specified key. The pointer will be nullptr of the key is not contained in the map. */
__forceinline const Val* lookup(const Key& key) const
{
typename std::vector<KeyValue>::const_iterator i = std::lower_bound(vec.begin(), vec.end(), key);
if (i == vec.end()) return nullptr;
if (i->key != key) return nullptr;
return &i->val;
}
/*! If the key is in the map, the function returns the value associated with the key, otherwise it returns the default value. */
__forceinline Val lookup(const Key& key, const Val& def) const
{
typename std::vector<KeyValue>::const_iterator i = std::lower_bound(vec.begin(), vec.end(), key);
if (i == vec.end()) return def;
if (i->key != key) return def;
return i->val;
}
/*! clears all state */
void clear() {
vec.clear();
}
private:
std::vector<KeyValue> vec; //!< vector containing sorted elements
};
}
|