FixedHashMap.hpp
1 // Distributed under the MIT License.
2 // See LICENSE.txt for details.
3 
4 #pragma once
5 
6 #include <array>
7 #include <boost/none.hpp>
8 #include <boost/optional.hpp>
9 #include <cstddef>
10 #include <iterator>
11 #include <pup.h>
12 #include <pup_stl.h>
13 #include <type_traits>
14 
15 #include "ErrorHandling/Assert.hpp"
16 #include "Parallel/PupStlCpp11.hpp" // IWYU pragma: keep
17 #include "Utilities/Algorithm.hpp"
18 #include "Utilities/BoostHelpers.hpp" // IWYU pragma: keep
21 #include "Utilities/GetOutput.hpp"
22 #include "Utilities/Gsl.hpp"
23 #include "Utilities/Numeric.hpp"
24 #include "Utilities/PrintHelpers.hpp"
25 #include "Utilities/TypeTraits.hpp"
26 
27 /// \cond
28 template <size_t MaxSize, class Key, class ValueType, class Hash,
29  class KeyEqual>
30 class FixedHashMapIterator;
31 /// \endcond
32 
33 namespace FixedHashMap_detail {
34 template <typename T, typename = cpp17::void_t<>>
35 struct has_is_perfect_member : std::false_type {};
36 
37 template <typename T>
38 struct has_is_perfect_member<T,
39  cpp17::void_t<decltype(T::template is_perfect<0>)>>
40  : std::true_type {};
41 
42 template <typename T>
43 constexpr bool has_is_perfect_member_v = has_is_perfect_member<T>::value;
44 
45 template <class T, size_t MaxSize,
46  bool HasIsPerfect = has_is_perfect_member_v<T>>
47 constexpr bool is_perfect = T::template is_perfect<MaxSize>;
48 
49 template <class T, size_t MaxSize>
50 constexpr bool is_perfect<T, MaxSize, false> = false;
51 } // namespace FixedHashMap_detail
52 
53 /*!
54  * \ingroup DataStructuresGroup
55  * \brief A hash table with a compile-time specified maximum size and ability to
56  * efficiently handle perfect hashes.
57  *
58  * There are a few requirements on the types passed to `FixedHashMap`. These
59  * are:
60  * - `Key` is CopyConstructible for copy and move semantics, as well as
61  * serialization
62  * - `ValueType` is MoveConstructible
63  * - If `Hash` is a perfect hash for some values of `MaxSize` then in order to
64  * use the perfect hashing improvements `Hash` must have a member variable
65  * template `is_perfect` that takes as its only template parameter a `size_t`
66  * equal to `MaxSize`. A perfect hash must map each `Key` to `[0, MaxSize)`
67  * uniquely.
68  * - Keys are distinct.
69  *
70  * The interface is similar to std::unordered_map, so see the documentation for
71  * that for details.
72  *
73  * #### Implementation Details
74  *
75  * - Uses linear probing for non-perfect hashes.
76  * - The hash `Hash` is assumed to be a perfect hash for `MaxSize` if
77  * `Hash::template is_perfect<MaxSize>` is true.
78  */
79 template <size_t MaxSize, class Key, class ValueType,
80  class Hash = std::hash<Key>, class KeyEqual = std::equal_to<Key>>
81 class FixedHashMap {
82  static constexpr bool hash_is_perfect =
83  FixedHashMap_detail::is_perfect<Hash, MaxSize>;
84 
85  public:
86  using key_type = Key;
87  using mapped_type = ValueType;
89  using size_type = size_t;
90  using difference_type = ptrdiff_t;
91  using hasher = Hash;
92  using key_equal = KeyEqual;
93  using reference = value_type&;
94  using const_reference = const value_type&;
95  using pointer = value_type*;
96  using const_pointer = const value_type*;
97  using iterator =
98  FixedHashMapIterator<MaxSize, key_type, value_type, hasher, key_equal>;
99  using const_iterator =
100  FixedHashMapIterator<MaxSize, key_type, const value_type, hasher,
101  key_equal>;
102 
103  FixedHashMap() = default;
105  FixedHashMap(const FixedHashMap&) = default;
106  FixedHashMap& operator=(const FixedHashMap& other) noexcept(
108  FixedHashMap(FixedHashMap&&) = default;
109  FixedHashMap& operator=(FixedHashMap&& other) noexcept;
110  ~FixedHashMap() = default;
111 
112  iterator begin() noexcept { return unconst(cbegin()); }
113  const_iterator begin() const noexcept {
114  return const_iterator(data_.begin(), data_.end());
115  }
116  const_iterator cbegin() const noexcept { return begin(); }
117 
118  iterator end() noexcept { return unconst(cend()); }
119  const_iterator end() const noexcept {
120  return const_iterator(data_.end(), data_.end());
121  }
122  const_iterator cend() const noexcept { return end(); }
123 
124  bool empty() const noexcept { return size_ == 0; }
125  size_t size() const noexcept { return size_; }
126 
127  void clear() noexcept;
128 
129  // @{
130  /// Inserts the element if it does not exists.
131  std::pair<iterator, bool> insert(const value_type& value) noexcept {
132  return insert(value_type(value));
133  }
134  std::pair<iterator, bool> insert(value_type&& value) noexcept {
135  // NOLINTNEXTLINE(cppcoreguidelines-pro-type-const-cast)
136  return insert_or_assign_impl<false>(const_cast<key_type&&>(value.first),
137  std::move(value.second));
138  }
139  template <typename... Args>
140  std::pair<iterator, bool> emplace(Args&&... args) noexcept {
141  return insert(value_type(std::forward<Args>(args)...));
142  }
143  // @}
144  // @{
145  /// Inserts the element if it does not exists, otherwise assigns to it the new
146  /// value.
147  template <class M>
149  M&& obj) noexcept {
150  return insert_or_assign(key_type{key}, std::forward<M>(obj));
151  }
152  template <class M>
153  std::pair<iterator, bool> insert_or_assign(key_type&& key, M&& obj) noexcept {
154  return insert_or_assign_impl<true>(std::move(key), std::forward<M>(obj));
155  }
156  // @}
157 
158  iterator erase(const const_iterator& pos) noexcept;
159  size_t erase(const key_type& key) noexcept;
160 
161  mapped_type& at(const key_type& key);
162  const mapped_type& at(const key_type& key) const;
163  mapped_type& operator[](const key_type& key) noexcept;
164 
165  size_t count(const key_type& key) const noexcept;
166  iterator find(const key_type& key) noexcept {
167  return unconst(cpp17::as_const(*this).find(key));
168  }
169  const_iterator find(const key_type& key) const noexcept {
170  auto it = get_data_entry(key);
171  return it != data_.end() and is_set(*it) ? const_iterator(&*it, data_.end())
172  : end();
173  }
174 
175  /// Check if `key` is in the map
176  bool contains(const key_type& key) const noexcept {
177  return find(key) != end();
178  }
179 
180  /// Get key equal function object
181  key_equal key_eq() const noexcept { return key_equal{}; }
182  /// Get hash function object
183  hasher hash_function() const noexcept { return hasher{}; }
184 
185  void pup(PUP::er& p) noexcept { // NOLINT(google-runtime-references)
186  p | data_;
187  p | size_;
188  }
189 
190  private:
191  template <size_t FMaxSize, class FKey, class FValueType, class FHash,
192  class FKeyEqual>
193  // NOLINTNEXTLINE(readability-redundant-declaration) false positive
194  friend bool operator==(
197  b) noexcept;
198 
199  template <bool Assign, class M>
200  std::pair<iterator, bool> insert_or_assign_impl(key_type&& key,
201  M&& obj) noexcept;
202 
204 
205  SPECTRE_ALWAYS_INLINE size_type hash(const key_type& key) const noexcept {
206  return hash_is_perfect ? Hash{}(key) : Hash{}(key) % MaxSize;
207  }
208 
209  template <bool IsInserting>
210  typename storage_type::iterator get_data_entry(const Key& key) noexcept;
211 
212  typename storage_type::const_iterator get_data_entry(const Key& key) const
213  noexcept {
214  // NOLINTNEXTLINE(cppcoreguidelines-pro-type-const-cast)
215  return const_cast<FixedHashMap&>(*this).get_data_entry<false>(key);
216  }
217 
218  iterator unconst(const const_iterator& it) noexcept {
219  return iterator(&it.get_optional() - data_.begin() + data_.begin(),
220  data_.end());
221  }
222 
223  SPECTRE_ALWAYS_INLINE static bool is_set(
224  const boost::optional<value_type>& opt) noexcept {
225  return static_cast<bool>(opt);
226  }
227 
228  storage_type data_{};
229  size_t size_ = 0;
230 };
231 
232 /// \cond HIDDEN_SYMBOLS
233 template <size_t MaxSize, class Key, class ValueType, class Hash,
234  class KeyEqual>
235 class FixedHashMapIterator {
236  public:
237  using iterator_category = std::forward_iterator_tag;
239  using difference_type = ptrdiff_t;
240  using pointer = ValueType*;
241  using reference = ValueType&;
242 
243  FixedHashMapIterator() = default;
244 
245  /// Implicit conversion from mutable to const iterator.
246  // NOLINTNEXTLINE(google-explicit-constructor)
247  operator FixedHashMapIterator<MaxSize, Key, const ValueType, Hash, KeyEqual>()
248  const noexcept {
249  return {entry_, end_};
250  }
251 
252  reference operator*() const noexcept {
253  ASSERT(entry_ != nullptr, "Invalid FixedHashMapIterator");
254  ASSERT(is_set(*entry_),
255  "FixedHashMapIterator points to an invalid value in the map.");
256  // deference pointer, then dereference boost::optional
257  return **entry_;
258  }
259  pointer operator->() const noexcept {
260  ASSERT(entry_ != nullptr, "Invalid FixedHashMapIterator");
261  ASSERT(is_set(*entry_),
262  "FixedHashMapIterator points to an invalid value in the map.");
263  return entry_->get_ptr();
264  }
265 
266  FixedHashMapIterator& operator++() noexcept;
267  // clang-tidy wants this to return a const object. Returning const
268  // objects is very strange, and as of June 2018 clang-tidy's
269  // explanation for the lint is a dead link.
270  FixedHashMapIterator operator++(int) noexcept; // NOLINT(cert-dcl21-cpp)
271 
272  private:
273  friend class FixedHashMap<MaxSize, Key, typename value_type::second_type,
274  Hash, KeyEqual>;
275  friend class FixedHashMapIterator<MaxSize, Key, value_type, Hash, KeyEqual>;
276 
277  friend bool operator==(const FixedHashMapIterator& a,
278  const FixedHashMapIterator& b) noexcept {
279  return a.entry_ == b.entry_;
280  }
281  friend bool operator<(const FixedHashMapIterator& a,
282  const FixedHashMapIterator& b) noexcept {
283  return a.entry_ < b.entry_;
284  }
285 
286  // The rest of the comparison operators don't need access to the
287  // class internals, but they need to be instantiated for each
288  // instantiation of the class.
289  friend bool operator!=(const FixedHashMapIterator& a,
290  const FixedHashMapIterator& b) noexcept {
291  return not(a == b);
292  }
293  friend bool operator>(const FixedHashMapIterator& a,
294  const FixedHashMapIterator& b) noexcept {
295  return b < a;
296  }
297  friend bool operator<=(const FixedHashMapIterator& a,
298  const FixedHashMapIterator& b) noexcept {
299  return not(b < a);
300  }
301  friend bool operator>=(const FixedHashMapIterator& a,
302  const FixedHashMapIterator& b) noexcept {
303  return not(a < b);
304  }
305 
306  using map_optional_type = boost::optional<std::remove_const_t<ValueType>>;
307  using optional_type =
309  const map_optional_type, map_optional_type>;
310 
311  SPECTRE_ALWAYS_INLINE static bool is_set(const optional_type& opt) noexcept {
312  return static_cast<bool>(opt);
313  }
314 
315  FixedHashMapIterator(optional_type* const entry,
316  optional_type* const end) noexcept
317  : entry_(entry), end_(end) {
318  if (entry_ != end_ and not*entry_) {
319  operator++();
320  }
321  }
322 
323  optional_type& get_optional() const { return *entry_; }
324 
325  optional_type* entry_{nullptr};
326  optional_type* end_{nullptr};
327 };
328 
329 template <size_t MaxSize, class Key, class ValueType, class Hash,
330  class KeyEqual>
331 FixedHashMapIterator<MaxSize, Key, ValueType, Hash, KeyEqual>&
332 FixedHashMapIterator<MaxSize, Key, ValueType, Hash, KeyEqual>::
333 operator++() noexcept {
334  ASSERT(entry_ != end_,
335  "Tried to increment an end iterator, which is undefined behavior.");
336  // Move to next element, which might not be the next element in the std::array
337  do {
338  ++entry_; // NOLINT(cppcoreguidelines-pro-bounds-pointer-arithmetic)
339  } while (entry_ < end_ and not is_set(*entry_));
340  return *this;
341 }
342 
343 template <size_t MaxSize, class Key, class ValueType, class Hash,
344  class KeyEqual>
345 // NOLINTNEXTLINE(cert-dcl21-cpp) see declaration
346 FixedHashMapIterator<MaxSize, Key, ValueType, Hash, KeyEqual>
347 FixedHashMapIterator<MaxSize, Key, ValueType, Hash, KeyEqual>::operator++(
348  int) noexcept {
349  const auto ret = *this;
350  operator++();
351  return ret;
352 }
353 /// \endcond
354 
355 template <size_t MaxSize, class Key, class ValueType, class Hash,
356  class KeyEqual>
360  other) noexcept(noexcept(std::
361  is_nothrow_copy_constructible<
362  value_type>::value)) {
363  if (this == &other) {
364  return *this;
365  }
366  clear();
367  size_ = other.size_;
368  for (size_t i = 0; i < data_.size(); ++i) {
369  const auto& other_optional = gsl::at(other.data_, i);
370  if (is_set(other_optional)) {
371  // The boost::optionals cannot be assigned to because they
372  // contain the map keys, which are const, so we have to replace
373  // the contents instead, since that counts as a destroy +
374  // initialize.
375  gsl::at(data_, i).emplace(*other_optional);
376  }
377  }
378  return *this;
379 }
380 
381 template <size_t MaxSize, class Key, class ValueType, class Hash,
382  class KeyEqual>
386  if (this == &other) {
387  return *this;
388  }
389  clear();
390  size_ = other.size_;
391  for (size_t i = 0; i < data_.size(); ++i) {
392  auto& other_optional = gsl::at(other.data_, i);
393  if (is_set(other_optional)) {
394  // The boost::optionals cannot be assigned to because they
395  // contain the map keys, which are const, so we have to replace
396  // the contents instead, since that counts as a destroy +
397  // initialize.
398  gsl::at(data_, i).emplace(std::move(*other_optional));
399  }
400  }
401  return *this;
402 }
403 
404 template <size_t MaxSize, class Key, class ValueType, class Hash,
405  class KeyEqual>
407  std::initializer_list<value_type> init) noexcept {
408  // size_ is set by calling insert
409  for (const auto& entry : init) {
410  insert(entry);
411  }
412 }
413 
414 template <size_t MaxSize, class Key, class ValueType, class Hash,
415  class KeyEqual>
417  for (auto& entry : data_) {
418  entry = boost::none;
419  }
420  size_ = 0;
421 }
422 
423 template <size_t MaxSize, class Key, class ValueType, class Hash,
424  class KeyEqual>
425 template <bool Assign, class M>
426 auto FixedHashMap<MaxSize, Key, ValueType, Hash,
427  KeyEqual>::insert_or_assign_impl(key_type&& key,
428  M&& obj) noexcept
430  auto data_it = get_data_entry<true>(key);
431  if (UNLIKELY(data_it == data_.end())) {
432  ERROR("Unable to insert element into FixedHashMap of maximum size "
433  << MaxSize << " because it is full. If the current size (" << size_
434  << ") is not equal to the maximum size then please file an issue "
435  "with the code you used to produce this error. "
436  << (hash_is_perfect ? " If a perfect hash is used and it hashes to "
437  "past the last element stored, then this "
438  "error may also be triggered."
439  : ""));
440  }
441  // data_it points to either the existing element or a new bucket to place the
442  // element.
443  const auto is_new_entry = not is_set(*data_it);
444  if (is_new_entry or Assign) {
445  if (is_new_entry) {
446  ++size_;
447  }
448  data_it->emplace(std::move(key), std::forward<M>(obj));
449  }
450  return std::make_pair(iterator{data_it, data_.end()}, is_new_entry);
451 }
452 
453 template <size_t MaxSize, class Key, class ValueType, class Hash,
454  class KeyEqual>
456  const const_iterator& pos) noexcept -> iterator {
457  auto next_it = &(unconst(pos).get_optional());
458  --size_;
459  *next_it = boost::none;
460  // pos now points to an unset entry, advance to next valid one
461  do {
462  ++next_it;
463  if (next_it == data_.end()) {
464  next_it = data_.begin();
465  }
466  if (is_set(*next_it)) {
467  return {next_it, data_.end()};
468  }
469  } while (next_it != &pos.get_optional());
470  return end();
471 }
472 
473 template <size_t MaxSize, class Key, class ValueType, class Hash,
474  class KeyEqual>
476  const key_type& key) noexcept {
477  auto it = get_data_entry<false>(key);
478  if (it == data_.end() or not is_set(*it)) {
479  return 0;
480  }
481  *it = boost::none;
482  --size_;
483  return 1;
484 }
485 
486 template <size_t MaxSize, class Key, class ValueType, class Hash,
487  class KeyEqual>
489  const key_type& key) -> mapped_type& {
490  auto it = get_data_entry<false>(key);
491  if (it == data_.end() or not is_set(*it)) {
492  throw std::out_of_range(get_output(key) + " not in FixedHashMap");
493  }
494  return (**it).second;
495 }
496 
497 template <size_t MaxSize, class Key, class ValueType, class Hash,
498  class KeyEqual>
500  const key_type& key) const -> const mapped_type& {
501  // NOLINTNEXTLINE(cppcoreguidelines-pro-type-const-cast)
502  return const_cast<FixedHashMap&>(*this).at(key);
503 }
504 
505 template <size_t MaxSize, class Key, class ValueType, class Hash,
506  class KeyEqual>
508  const key_type& key) noexcept -> mapped_type& {
509  auto it = get_data_entry<true>(key);
510  if (it == data_.end()) {
511  ERROR("Unable to insert element into FixedHashMap of maximum size "
512  << MaxSize << " because it is full. If the current size (" << size_
513  << ") is not equal to the maximum size then please file an issue "
514  "with the code you used to produce this error. "
515  << (hash_is_perfect ? " If a perfect hash is used and it hashes to "
516  "past the last element stored, then this "
517  "error may also be triggered."
518  : ""));
519  }
520  if (not is_set(*it)) {
521  ++size_;
522  it->emplace(key, mapped_type{});
523  }
524  return (**it).second;
525 }
526 
527 template <size_t MaxSize, class Key, class ValueType, class Hash,
528  class KeyEqual>
530  const key_type& key) const noexcept {
531  const auto it = get_data_entry(key);
532  return it == data_.end() or not is_set(*it) ? 0 : 1;
533 }
534 
535 template <size_t MaxSize, class Key, class ValueType, class Hash,
536  class KeyEqual>
537 template <bool IsInserting>
539  const Key& key) noexcept -> typename storage_type::iterator {
540  const auto hashed_key = hash(key);
541  auto it = data_.begin() + hashed_key;
542  if (not hash_is_perfect) {
543  // First search for an existing key.
544  while (not is_set(*it) or (**it).first != key) {
545  if (++it == data_.end()) {
546  it = data_.begin();
547  }
548  if (UNLIKELY(it == data_.begin() + hashed_key)) {
549  // not found, return end iterator to storage_type
550  it = data_.end();
551  break;
552  }
553  }
554  // If we are inserting an element but couldn't find an existing key, then
555  // find the first available bucket.
556  if (IsInserting and it == data_.end()) {
557  it = data_.begin() + hashed_key;
558  while (is_set(*it)) {
559  if (++it == data_.end()) {
560  it = data_.begin();
561  }
562  if (UNLIKELY(it == data_.begin() + hashed_key)) {
563  // could not find any open bucket
564  return data_.end();
565  }
566  }
567  }
568  }
569  return it;
570 }
571 
572 template <size_t MaxSize, class Key, class ValueType, class Hash,
573  class KeyEqual>
574 bool operator==(
577  return a.size_ == b.size_ and a.data_ == b.data_;
578 }
579 
580 template <size_t MaxSize, class Key, class ValueType, class Hash,
581  class KeyEqual>
582 bool operator!=(
585  return not(a == b);
586 }
587 
588 template <size_t MaxSize, class Key, class ValueType, class Hash,
589  class KeyEqual>
590 std::ostream& operator<<(
591  std::ostream& os,
594  os, std::begin(m), std::end(m),
595  [](std::ostream & out,
596  typename FixedHashMap<MaxSize, Key, ValueType, Hash,
597  KeyEqual>::const_iterator it) noexcept {
598  out << "[" << it->first << "," << it->second << "]";
599  });
600  return os;
601 }
void unordered_print_helper(std::ostream &out, ForwardIt &&begin, ForwardIt &&end, Func f) noexcept
Definition: PrintHelpers.hpp:51
#define ERROR(m)
prints an error message to the standard error stream and aborts the program.
Definition: Error.hpp:35
std::pair< iterator, bool > insert_or_assign(key_type &&key, M &&obj) noexcept
Inserts the element if it does not exists, otherwise assigns to it the new value. ...
Definition: FixedHashMap.hpp:153
bool contains(const key_type &key) const noexcept
Check if key is in the map.
Definition: FixedHashMap.hpp:176
hasher hash_function() const noexcept
Get hash function object.
Definition: FixedHashMap.hpp:183
std::pair< iterator, bool > insert_or_assign(const key_type &key, M &&obj) noexcept
Inserts the element if it does not exists, otherwise assigns to it the new value. ...
Definition: FixedHashMap.hpp:148
key_equal key_eq() const noexcept
Get key equal function object.
Definition: FixedHashMap.hpp:181
void void_t
Given a set of types, returns void
Definition: TypeTraits.hpp:214
#define UNLIKELY(x)
Definition: Gsl.hpp:72
bool operator>(const Slab &a, const Slab &b) noexcept
Slab comparison operators give the time ordering. Overlapping unequal slabs should not be compared (a...
Definition: Slab.hpp:122
A hash table with a compile-time specified maximum size and ability to efficiently handle perfect has...
Definition: FixedHashMap.hpp:81
auto operator*(const TensorExpression< T1, X, Symm1, IndexList1, Args1 > &t1, const TensorExpression< T2, X, Symm2, IndexList2, Args2 > &t2)
Definition: Product.hpp:89
constexpr const T & as_const(const T &t) noexcept
Returns a const reference to its argument.
Definition: ConstantExpressions.hpp:408
std::pair< iterator, bool > insert(value_type &&value) noexcept
Inserts the element if it does not exists.
Definition: FixedHashMap.hpp:134
#define ASSERT(a, m)
Assert that an expression should be true.
Definition: Assert.hpp:49
bool operator<=(const Slab &a, const Slab &b) noexcept
Slab comparison operators give the time ordering. Overlapping unequal slabs should not be compared (a...
Definition: Slab.hpp:125
std::string get_output(const T &t) noexcept
Get the streamed output of t as a std::string
Definition: GetOutput.hpp:14
A particular Side along a particular coordinate Axis.
Definition: Direction.hpp:23
#define SPECTRE_ALWAYS_INLINE
Always inline a function. Only use this if you benchmarked the code.
Definition: ForceInline.hpp:20
PUP routines for new C+11 STL containers and other standard library objects Charm does not provide im...
Defines helper functions for working with boost.
Define simple functions for constant expressions.
Defines macro to always inline a function.
Defines macro ASSERT.
Definition: FixedHashMap.hpp:33
Defines functions and classes from the GSL.
std::pair< iterator, bool > insert(const value_type &value) noexcept
Inserts the element if it does not exists.
Definition: FixedHashMap.hpp:131
C++ STL code present in C++17.
Definition: Array.hpp:16
Defines type traits, some of which are future STL type_traits header.
Information about the neighbors of an Element in a particular direction.
Definition: Neighbors.hpp:28
bool operator>=(const Slab &a, const Slab &b) noexcept
Slab comparison operators give the time ordering. Overlapping unequal slabs should not be compared (a...
Definition: Slab.hpp:128
bool operator<(const Slab &a, const Slab &b) noexcept
Slab comparison operators give the time ordering. Overlapping unequal slabs should not be compared (a...
Definition: Slab.hpp:117
std::pair< iterator, bool > emplace(Args &&... args) noexcept
Inserts the element if it does not exists.
Definition: FixedHashMap.hpp:140
constexpr T & at(std::array< T, N > &arr, Size index)
Retrieve a entry from a container, with checks in Debug mode that the index being retrieved is valid...
Definition: Gsl.hpp:124