Metall  v0.27
A persistent memory allocator for data-centric analytics
concurrent_map.hpp
Go to the documentation of this file.
1 // Copyright 2020 Lawrence Livermore National Security, LLC and other Metall
2 // Project Developers. See the top-level COPYRIGHT file for details.
3 //
4 // SPDX-License-Identifier: (Apache-2.0 OR MIT)
5 
6 #ifndef METALL_CONTAINER_CONCURRENT_MAP_HPP
7 #define METALL_CONTAINER_CONCURRENT_MAP_HPP
8 
9 #include <functional>
10 #include <memory>
11 #include <boost/container/vector.hpp>
12 #include <boost/container/map.hpp>
13 #include <boost/container/scoped_allocator.hpp>
14 #include <metall/utility/mutex.hpp>
16 
19 namespace metall::container {
20 
29 template <typename _key_type, typename _mapped_type,
30  typename _compare = std::less<_key_type>,
31  typename _bank_no_hasher = std::hash<_key_type>,
32  typename _allocator =
33  std::allocator<std::pair<const _key_type, _mapped_type>>,
34  int k_num_banks = 1024>
36  private:
37  template <typename T>
38  using other_allocator_type =
39  typename std::allocator_traits<_allocator>::template rebind_alloc<T>;
40 
41  using internal_map_type =
42  boost::container::map<_key_type, _mapped_type, _compare, _allocator>;
43  using banked_map_allocator_type = other_allocator_type<internal_map_type>;
44  using banked_map_type = std::vector<
45  internal_map_type,
46  boost::container::scoped_allocator_adaptor<banked_map_allocator_type>>;
47 
48  public:
49  // -------------------- //
50  // Public types and static values
51  // -------------------- //
53  using key_type = typename internal_map_type::key_type;
55  using mapped_type = typename internal_map_type::mapped_type;
57  using value_type = typename internal_map_type::value_type;
59  using size_type = typename internal_map_type::size_type;
61  using allocator_type = _allocator;
62 
66  typename banked_map_type::const_iterator,
67  typename internal_map_type::const_iterator>;
68 
69  // -------------------- //
70  // Constructor & assign operator
71  // -------------------- //
72  explicit concurrent_map(const _allocator &allocator = _allocator())
73  : m_banked_map(k_num_banks, allocator), m_num_items(0) {}
74 
75  // -------------------- //
76  // Public methods
77  // -------------------- //
82  size_type count(const key_type &key) const {
83  const auto bank_no = calc_bank_no(key);
84  return m_banked_map[bank_no].count(key);
85  }
86 
89  size_type size() const { return m_num_items; }
90 
91  // ---------- Modifier ---------- //
96  bool insert(value_type &&value) {
97  const auto bank_no = calc_bank_no(value.first);
98  auto lock = metall::utility::mutex::mutex_lock<k_num_banks>(bank_no);
99  const bool ret =
100  m_banked_map[bank_no].insert(std::forward<value_type>(value)).second;
101  m_num_items += (ret) ? 1 : 0;
102  return ret;
103  }
104 
109  std::pair<mapped_type &, std::unique_lock<std::mutex>> scoped_edit(
110  const key_type &key) {
111  const auto bank_no = calc_bank_no(key);
112  auto lock = metall::utility::mutex::mutex_lock<k_num_banks>(bank_no);
113  if (!count(key)) {
114  [[maybe_unused]] const bool ret = register_key_no_lock(key);
115  assert(ret);
116  ++m_num_items;
117  }
118  return std::make_pair(std::ref(m_banked_map[bank_no].at(key)),
119  std::move(lock));
120  }
121 
126  void edit(const key_type &key,
127  const std::function<void(mapped_type &mapped_value)> &editor) {
128  const auto bank_no = calc_bank_no(key);
129  auto lock = metall::utility::mutex::mutex_lock<k_num_banks>(bank_no);
130  if (!count(key)) {
131  [[maybe_unused]] const bool ret = register_key_no_lock(key);
132  assert(ret);
133  ++m_num_items;
134  }
135  editor(m_banked_map[bank_no].at(key));
136  }
137 
138  // ---------- Iterator ---------- //
143  return const_iterator(m_banked_map.cbegin(), m_banked_map.cend());
144  }
145 
151  return const_iterator(m_banked_map.cend(), m_banked_map.cend());
152  }
153 
154  // ---------- Look up ---------- //
159  const_iterator find(const key_type &key) const {
160  const auto bank_no = calc_bank_no(key);
161  auto itr = m_banked_map[bank_no].find(key);
162  if (itr != m_banked_map[bank_no].end()) {
163  return const_iterator(m_banked_map.cbegin(), itr, m_banked_map.cend());
164  }
165  return cend();
166  }
167 
168  // ---------- Allocator ---------- //
172  return allocator_type(m_banked_map.get_allocator());
173  }
174 
175  private:
176  static uint64_t calc_bank_no(const key_type &key) {
177  return _bank_no_hasher()(key) % k_num_banks;
178  }
179 
180  bool register_key_no_lock(const key_type &key) {
181  const auto bank_no = calc_bank_no(key);
182  return m_banked_map[bank_no].try_emplace(key).second;
183  }
184 
185  banked_map_type m_banked_map;
186  size_type m_num_items;
187 };
188 
189 } // namespace metall::container
190 
193 
194 #endif // METALL_CONTAINER_CONCURRENT_MAP_HPP
A concurrent map container which can be stored in persistent memory. This container does not allocate...
Definition: concurrent_map.hpp:35
typename internal_map_type::key_type key_type
A key type.
Definition: concurrent_map.hpp:53
size_type count(const key_type &key) const
Returns the number of elements matching specific key.
Definition: concurrent_map.hpp:82
metall::utility::container_of_containers_iterator_adaptor< typename banked_map_type::const_iterator, typename internal_map_type::const_iterator > const_iterator
A const iterator type.
Definition: concurrent_map.hpp:67
const_iterator cend() const
Returns an iterator to the element following the last element of the map. This element acts as a plac...
Definition: concurrent_map.hpp:150
bool insert(value_type &&value)
Inserts element into the container if the container doesn't already contain an element with an equiva...
Definition: concurrent_map.hpp:96
typename internal_map_type::mapped_type mapped_type
A mapped type.
Definition: concurrent_map.hpp:55
std::pair< mapped_type &, std::unique_lock< std::mutex > > scoped_edit(const key_type &key)
Provides a way to edit an element exclusively. If no element exists with an equivalent key,...
Definition: concurrent_map.hpp:109
_allocator allocator_type
An allocator type.
Definition: concurrent_map.hpp:61
allocator_type get_allocator() const
Returns the allocator associated with the container.
Definition: concurrent_map.hpp:171
const_iterator find(const key_type &key) const
Finds an element with an equivalent key.
Definition: concurrent_map.hpp:159
const_iterator cbegin() const
Returns an iterator to the first element of the map. If the container is empty, the returned iterator...
Definition: concurrent_map.hpp:142
void edit(const key_type &key, const std::function< void(mapped_type &mapped_value)> &editor)
Provides a way to edit an element exclusively. If no element exists with an equivalent key,...
Definition: concurrent_map.hpp:126
concurrent_map(const _allocator &allocator=_allocator())
Definition: concurrent_map.hpp:72
typename internal_map_type::value_type value_type
A value type (i.e., std::pair<const key_type, mapped_type>).
Definition: concurrent_map.hpp:57
size_type size() const
Returns the number of elements in the container.
Definition: concurrent_map.hpp:89
typename internal_map_type::size_type size_type
A unsigned integer type (usually std::size_t).
Definition: concurrent_map.hpp:59
Utility class that provides an iterator for a container of containers, e.g., map of vectors This is a...
Definition: container_of_containers_iterator_adaptor.hpp:20
Namespace for Metall container.
boost::container::vector< T, Allocator > vector
A vector container that uses Metall as its default allocator.
Definition: vector.hpp:17