search

martinus / unordered_dense

A fast & densely stored hashmap and hashset based on robin-hood backward shift deletion
MIT License
898 stars 72 forks source link

[BUG] ankerl::unordered_dense::erase is not reentrant #126

Closed pklima closed 5 days ago

pklima commented 1 week ago

Describe the bug If you have a destructor that calls erase on a ankerl::unordered_dense::map that is currently being erased from, the code will enter an infinite loop.

As a workaround extract can be used instead of erase to delay the destructor from running until the initial erase finishes.

To Reproduce Run the following code:

struct Foo;
using Map = ankerl::unordered_dense::map<int, std::unique_ptr<Foo>>;

struct Foo
{
  ~Foo()
  {
    if (map)
      map->erase(0);
  }

  Map* map{nullptr};
};

Map map;
map.try_emplace(0, std::make_unique<Foo>());
map.try_emplace(1, std::make_unique<Foo>(&map));

map.erase(1); // <--- freeze

Expected behavior Same as std::unordered_map - doesn't freeze and erases correctly.

System:

Additional context Callstack:

ConsoleApplication1.exe!ankerl::unordered_dense::v4_4_0::detail::table<int,std::unique_ptr<`main'::`2'::Foo,std::default_delete<`main'::`2'::Foo>>,ankerl::unordered_dense::v4_4_0::hash<int,void>,std::equal_to<int>,std::allocator<std::pair<int,std::unique_ptr<`main'::`2'::Foo,std::default_delete<`main'::`2'::Foo>>>>,ankerl::unordered_dense::v4_4_0::bucket_type::standard,0>::next(unsigned int bucket_idx) Line 852  C++
ConsoleApplication1.exe!ankerl::unordered_dense::v4_4_0::detail::table<int,std::unique_ptr<`main'::`2'::Foo,std::default_delete<`main'::`2'::Foo>>,ankerl::unordered_dense::v4_4_0::hash<int,void>,std::equal_to<int>,std::allocator<std::pair<int,std::unique_ptr<`main'::`2'::Foo,std::default_delete<`main'::`2'::Foo>>>>,ankerl::unordered_dense::v4_4_0::bucket_type::standard,0>::do_erase<`ankerl::unordered_dense::v4_4_0::detail::table<int,std::unique_ptr<`main'::`2'::Foo,std::default_delete<`main'::`2'::Foo>>,ankerl::unordered_dense::v4_4_0::hash<int,void>,std::equal_to<int>,std::allocator<std::pair<int,std::unique_ptr<`main'::`2'::Foo,std::default_delete<`main'::`2'::Foo>>>>,ankerl::unordered_dense::v4_4_0::bucket_type::standard,0>::erase'::`2'::<lambda_1>>(unsigned int bucket_idx, ankerl::unordered_dense::v4_4_0::detail::table<int,std::unique_ptr<`main'::`2'::Foo,std::default_delete<`main'::`2'::Foo>>,ankerl::unordered_dense::v4_4_0::hash<int,void>,std::equal_to<int>,std::allocator<std::pair<int,std::unique_ptr<`main'::`2'::Foo,std::default_delete<`main'::`2'::Foo>>>>,ankerl::unordered_dense::v4_4_0::bucket_type::standard,0>::erase::__l2::<lambda_1> handle_erased_value) Line 1038  C++
ConsoleApplication1.exe!ankerl::unordered_dense::v4_4_0::detail::table<int,std::unique_ptr<`main'::`2'::Foo,std::default_delete<`main'::`2'::Foo>>,ankerl::unordered_dense::v4_4_0::hash<int,void>,std::equal_to<int>,std::allocator<std::pair<int,std::unique_ptr<`main'::`2'::Foo,std::default_delete<`main'::`2'::Foo>>>>,ankerl::unordered_dense::v4_4_0::bucket_type::standard,0>::do_erase_key<int const &,`ankerl::unordered_dense::v4_4_0::detail::table<int,std::unique_ptr<`main'::`2'::Foo,std::default_delete<`main'::`2'::Foo>>,ankerl::unordered_dense::v4_4_0::hash<int,void>,std::equal_to<int>,std::allocator<std::pair<int,std::unique_ptr<`main'::`2'::Foo,std::default_delete<`main'::`2'::Foo>>>>,ankerl::unordered_dense::v4_4_0::bucket_type::standard,0>::erase'::`2'::<lambda_1>>(const int & key, ankerl::unordered_dense::v4_4_0::detail::table<int,std::unique_ptr<`main'::`2'::Foo,std::default_delete<`main'::`2'::Foo>>,ankerl::unordered_dense::v4_4_0::hash<int,void>,std::equal_to<int>,std::allocator<std::pair<int,std::unique_ptr<`main'::`2'::Foo,std::default_delete<`main'::`2'::Foo>>>>,ankerl::unordered_dense::v4_4_0::bucket_type::standard,0>::erase::__l2::<lambda_1> handle_erased_value) Line 1063  C++
ConsoleApplication1.exe!ankerl::unordered_dense::v4_4_0::detail::table<int,std::unique_ptr<`main'::`2'::Foo,std::default_delete<`main'::`2'::Foo>>,ankerl::unordered_dense::v4_4_0::hash<int,void>,std::equal_to<int>,std::allocator<std::pair<int,std::unique_ptr<`main'::`2'::Foo,std::default_delete<`main'::`2'::Foo>>>>,ankerl::unordered_dense::v4_4_0::bucket_type::standard,0>::erase(const int & key) Line 1683    C++
ConsoleApplication1.exe!`main'::`2'::Foo::~Foo() Line 20    C++
ConsoleApplication1.exe!`main'::`2'::Foo::`scalar deleting destructor'(unsigned int)    C++
ConsoleApplication1.exe!std::default_delete<`main'::`2'::Foo>::operator()(main::__l2::Foo * _Ptr) Line 3139 C++
ConsoleApplication1.exe!std::unique_ptr<`main'::`2'::Foo,std::default_delete<`main'::`2'::Foo>>::~unique_ptr<`main'::`2'::Foo,std::default_delete<`main'::`2'::Foo>>() Line 3251    C++
ConsoleApplication1.exe!std::pair<int,std::unique_ptr<`main'::`2'::Foo,std::default_delete<`main'::`2'::Foo>>>::~pair<int,std::unique_ptr<`main'::`2'::Foo,std::default_delete<`main'::`2'::Foo>>>()    C++
ConsoleApplication1.exe!std::pair<int,std::unique_ptr<`main'::`2'::Foo,std::default_delete<`main'::`2'::Foo>>>::`scalar deleting destructor'(unsigned int)  C++
ConsoleApplication1.exe!std::destroy_at<std::pair<int,std::unique_ptr<`main'::`2'::Foo,std::default_delete<`main'::`2'::Foo>>>>(std::pair<int,std::unique_ptr<`main'::`2'::Foo,std::default_delete<`main'::`2'::Foo>>> * const _Location) Line 326  C++
ConsoleApplication1.exe!std::_Default_allocator_traits<std::allocator<std::pair<int,std::unique_ptr<`main'::`2'::Foo,std::default_delete<`main'::`2'::Foo>>>>>::destroy<std::pair<int,std::unique_ptr<`main'::`2'::Foo,std::default_delete<`main'::`2'::Foo>>>>(std::allocator<std::pair<int,std::unique_ptr<`main'::`2'::Foo,std::default_delete<`main'::`2'::Foo>>>> & __formal, std::pair<int,std::unique_ptr<`main'::`2'::Foo,std::default_delete<`main'::`2'::Foo>>> * const _Ptr) Line 738    C++
ConsoleApplication1.exe!std::vector<std::pair<int,std::unique_ptr<`main'::`2'::Foo,std::default_delete<`main'::`2'::Foo>>>,std::allocator<std::pair<int,std::unique_ptr<`main'::`2'::Foo,std::default_delete<`main'::`2'::Foo>>>>>::pop_back() Line 1721    C++
ConsoleApplication1.exe!ankerl::unordered_dense::v4_4_0::detail::table<int,std::unique_ptr<`main'::`2'::Foo,std::default_delete<`main'::`2'::Foo>>,ankerl::unordered_dense::v4_4_0::hash<int,void>,std::equal_to<int>,std::allocator<std::pair<int,std::unique_ptr<`main'::`2'::Foo,std::default_delete<`main'::`2'::Foo>>>>,ankerl::unordered_dense::v4_4_0::bucket_type::standard,0>::do_erase<`ankerl::unordered_dense::v4_4_0::detail::table<int,std::unique_ptr<`main'::`2'::Foo,std::default_delete<`main'::`2'::Foo>>,ankerl::unordered_dense::v4_4_0::hash<int,void>,std::equal_to<int>,std::allocator<std::pair<int,std::unique_ptr<`main'::`2'::Foo,std::default_delete<`main'::`2'::Foo>>>>,ankerl::unordered_dense::v4_4_0::bucket_type::standard,0>::erase'::`2'::<lambda_1>>(unsigned int bucket_idx, ankerl::unordered_dense::v4_4_0::detail::table<int,std::unique_ptr<`main'::`2'::Foo,std::default_delete<`main'::`2'::Foo>>,ankerl::unordered_dense::v4_4_0::hash<int,void>,std::equal_to<int>,std::allocator<std::pair<int,std::unique_ptr<`main'::`2'::Foo,std::default_delete<`main'::`2'::Foo>>>>,ankerl::unordered_dense::v4_4_0::bucket_type::standard,0>::erase::__l2::<lambda_1> handle_erased_value) Line 1043  C++
ConsoleApplication1.exe!ankerl::unordered_dense::v4_4_0::detail::table<int,std::unique_ptr<`main'::`2'::Foo,std::default_delete<`main'::`2'::Foo>>,ankerl::unordered_dense::v4_4_0::hash<int,void>,std::equal_to<int>,std::allocator<std::pair<int,std::unique_ptr<`main'::`2'::Foo,std::default_delete<`main'::`2'::Foo>>>>,ankerl::unordered_dense::v4_4_0::bucket_type::standard,0>::do_erase_key<int const &,`ankerl::unordered_dense::v4_4_0::detail::table<int,std::unique_ptr<`main'::`2'::Foo,std::default_delete<`main'::`2'::Foo>>,ankerl::unordered_dense::v4_4_0::hash<int,void>,std::equal_to<int>,std::allocator<std::pair<int,std::unique_ptr<`main'::`2'::Foo,std::default_delete<`main'::`2'::Foo>>>>,ankerl::unordered_dense::v4_4_0::bucket_type::standard,0>::erase'::`2'::<lambda_1>>(const int & key, ankerl::unordered_dense::v4_4_0::detail::table<int,std::unique_ptr<`main'::`2'::Foo,std::default_delete<`main'::`2'::Foo>>,ankerl::unordered_dense::v4_4_0::hash<int,void>,std::equal_to<int>,std::allocator<std::pair<int,std::unique_ptr<`main'::`2'::Foo,std::default_delete<`main'::`2'::Foo>>>>,ankerl::unordered_dense::v4_4_0::bucket_type::standard,0>::erase::__l2::<lambda_1> handle_erased_value) Line 1063  C++
ConsoleApplication1.exe!ankerl::unordered_dense::v4_4_0::detail::table<int,std::unique_ptr<`main'::`2'::Foo,std::default_delete<`main'::`2'::Foo>>,ankerl::unordered_dense::v4_4_0::hash<int,void>,std::equal_to<int>,std::allocator<std::pair<int,std::unique_ptr<`main'::`2'::Foo,std::default_delete<`main'::`2'::Foo>>>>,ankerl::unordered_dense::v4_4_0::bucket_type::standard,0>::erase(const int & key) Line 1683    C++
ConsoleApplication1.exe!main() Line 30  C++
martinus commented 5 days ago

I had a look, that's something that I can't support in the map. Note that as far as I can say it is not officially supported by std as well, and it might randomly work or not. It certainly doesn't work with boost maps.