1// Copyright 2009-2021 Intel Corporation
2// SPDX-License-Identifier: Apache-2.0
3
4#pragma once
5
6#include "parallel_sort.h"
7
8namespace embree
9{
10 /*! implementation of a key/value map with parallel construction */
11 template<typename Key, typename Val>
12 class parallel_map
13 {
14 /* key/value pair to build the map */
15 struct KeyValue
16 {
17 __forceinline KeyValue () {}
18
19 __forceinline KeyValue (const Key key, const Val val)
20 : key(key), val(val) {}
21
22 __forceinline operator Key() const {
23 return key;
24 }
25
26 public:
27 Key key;
28 Val val;
29 };
30
31 public:
32
33 /*! parallel map constructors */
34 parallel_map () {}
35
36 /*! construction from pair of vectors */
37 template<typename KeyVector, typename ValVector>
38 parallel_map (const KeyVector& keys, const ValVector& values) { init(keys,values); }
39
40 /*! initialized the parallel map from a vector with keys and values */
41 template<typename KeyVector, typename ValVector>
42 void init(const KeyVector& keys, const ValVector& values)
43 {
44 /* reserve sufficient space for all data */
45 assert(keys.size() == values.size());
46 vec.resize(keys.size());
47
48 /* generate key/value pairs */
49 parallel_for( size_t(0), keys.size(), size_t(4*4096), [&](const range<size_t>& r) {
50 for (size_t i=r.begin(); i<r.end(); i++)
51 vec[i] = KeyValue((Key)keys[i],values[i]);
52 });
53
54 /* perform parallel radix sort of the key/value pairs */
55 std::vector<KeyValue> temp(keys.size());
56 radix_sort<KeyValue,Key>(vec.data(),temp.data(),keys.size());
57 }
58
59 /*! 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. */
60 __forceinline const Val* lookup(const Key& key) const
61 {
62 typename std::vector<KeyValue>::const_iterator i = std::lower_bound(vec.begin(), vec.end(), key);
63 if (i == vec.end()) return nullptr;
64 if (i->key != key) return nullptr;
65 return &i->val;
66 }
67
68 /*! If the key is in the map, the function returns the value associated with the key, otherwise it returns the default value. */
69 __forceinline Val lookup(const Key& key, const Val& def) const
70 {
71 typename std::vector<KeyValue>::const_iterator i = std::lower_bound(vec.begin(), vec.end(), key);
72 if (i == vec.end()) return def;
73 if (i->key != key) return def;
74 return i->val;
75 }
76
77 /*! clears all state */
78 void clear() {
79 vec.clear();
80 }
81
82 private:
83 std::vector<KeyValue> vec; //!< vector containing sorted elements
84 };
85}
86