1 // Copyright 2009-2021 Intel Corporation
2 // SPDX-License-Identifier: Apache-2.0
3 
4 #pragma once
5 
6 #include "parallel_sort.h"
7 
8 namespace 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     {
KeyValueKeyValue17       __forceinline KeyValue () {}
18 
KeyValueKeyValue19       __forceinline KeyValue (const Key key, const Val val)
20 	: key(key), val(val) {}
21 
KeyKeyValue22       __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 */
parallel_map()34     parallel_map () {}
35 
36     /*! construction from pair of vectors */
37     template<typename KeyVector, typename ValVector>
parallel_map(const KeyVector & keys,const ValVector & values)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>
init(const KeyVector & keys,const ValVector & values)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. */
lookup(const Key & key)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. */
lookup(const Key & key,const Val & def)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 */
clear()78     void clear() {
79       vec.clear();
80     }
81 
82   private:
83     std::vector<KeyValue> vec;    //!< vector containing sorted elements
84   };
85 }
86