1 /**
2 * Copyright (c) 2024 Huawei Device Co., Ltd.
3 * Licensed under the Apache License, Version 2.0 (the "License");
4 * you may not use this file except in compliance with the License.
5 * You may obtain a copy of the License at
6 *
7 * http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software
10 * distributed under the License is distributed on an "AS IS" BASIS,
11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 * See the License for the specific language governing permissions and
13 * limitations under the License.
14 */
15
16 #ifndef PLUGINS_ETS_RUNTIME_MEM_MPSC_SET_H
17 #define PLUGINS_ETS_RUNTIME_MEM_MPSC_SET_H
18
19 #include <cstddef>
20 #include <libpandabase/macros.h>
21 #include <libpandabase/os/mutex.h>
22 #include <libpandabase/os/thread.h>
23 #include <unordered_map>
24
25 namespace ark::mem {
26
27 /**
28 * @brief MPSCSet is tool to optimize usage of set in next case:
29 * - You need to store unique elements in set.
30 * - You want to collect them in one set from many threads
31 * - You want to process elements from one thread
32 * - You have splitted steps of execution with collecting and processing
33 * @tparam StoredSetType - type of set you want to use inside
34 */
35 template <class StoredSetType>
36 class MPSCSet {
37 public:
38 using ValueType = typename StoredSetType::value_type;
39 using AllocatorType = typename StoredSetType::allocator_type;
40
41 MPSCSet() = default;
42 NO_COPY_SEMANTIC(MPSCSet);
43 NO_MOVE_SEMANTIC(MPSCSet);
44 ~MPSCSet() = default;
45
46 /**
47 * @brief Method adds value in thread local set
48 * @param val: instance of ValueType, that you want to add
49 */
50 void Insert(ValueType val);
51 /**
52 * @brief Method flushes all data from local sets to single global set. Only after this operation content of the
53 * MPSCSet will be observable.
54 */
55 void FlushSets();
56
57 /**
58 * @brief Method extract one value from the global set. Please, check if global set contains values with IsEmpty()
59 * method.
60 * @see MPSCSet::FlushSets()
61 * @returns instance of ValueType, that was presented in global set.
62 */
63 ValueType Extract();
64 /// @returns true if global set is empty, otherwise @returns false.
65 bool IsEmpty() const;
66 /// @returns size of global set
67 size_t Size() const;
68
69 private:
70 template <class Key, class Value>
71 using SetStorageType =
72 std::unordered_map<Key, Value, std::hash<Key>, std::equal_to<Key>,
73 typename AllocatorType::template rebind<std::pair<const Key, Value>>::other>;
74
75 void AddNewSetInStorage();
76
77 mutable os::memory::RWLock setStorageLock_;
78 SetStorageType<os::thread::ThreadId, StoredSetType> setStorage_ GUARDED_BY(setStorageLock_);
79
80 StoredSetType globalSet_;
81 };
82
83 template <class StoredSetType>
Insert(ValueType val)84 void MPSCSet<StoredSetType>::Insert(ValueType val)
85 {
86 setStorageLock_.ReadLock();
87 auto setIterator = setStorage_.find(os::thread::GetCurrentThreadId());
88 if UNLIKELY (setIterator == setStorage_.end()) {
89 // start slow path
90 setStorageLock_.Unlock();
91 AddNewSetInStorage();
92 setStorageLock_.ReadLock();
93 setIterator = setStorage_.find(os::thread::GetCurrentThreadId());
94 }
95 // getting of set with additional search
96 auto &set = setIterator->second;
97 set.insert(val);
98 setStorageLock_.Unlock();
99 }
100
101 template <class StoredSetType>
AddNewSetInStorage()102 void MPSCSet<StoredSetType>::AddNewSetInStorage()
103 {
104 os::memory::WriteLockHolder wLockHolder(setStorageLock_);
105 setStorage_.insert({os::thread::GetCurrentThreadId(), StoredSetType()});
106 }
107
108 template <class StoredSetType>
FlushSets()109 void MPSCSet<StoredSetType>::FlushSets()
110 {
111 os::memory::WriteLockHolder wLockHolder(setStorageLock_);
112 for ([[maybe_unused]] auto &[id, set] : setStorage_) {
113 globalSet_.merge(set);
114 }
115 setStorage_.clear();
116 }
117
118 template <class StoredSetType>
Extract()119 typename MPSCSet<StoredSetType>::ValueType MPSCSet<StoredSetType>::Extract()
120 {
121 return globalSet_.extract(globalSet_.begin()).value();
122 }
123
124 template <class StoredSetType>
IsEmpty()125 bool MPSCSet<StoredSetType>::IsEmpty() const
126 {
127 return globalSet_.empty();
128 }
129
130 template <class StoredSetType>
Size()131 size_t MPSCSet<StoredSetType>::Size() const
132 {
133 return globalSet_.size();
134 }
135
136 } // namespace ark::mem
137
138 #endif // PLUGINS_ETS_RUNTIME_MEM_MPSC_SET_H