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