Skip to content
This repository has been archived by the owner on Mar 22, 2023. It is now read-only.

operator-- may fail in concurrent radix_tree #1159

Open
lukaszstolarczuk opened this issue Jul 15, 2021 · 1 comment
Open

operator-- may fail in concurrent radix_tree #1159

lukaszstolarczuk opened this issue Jul 15, 2021 · 1 comment
Labels
radix_tree Needs to be resolved to productize radix_tree Type: Bug Something isn't working

Comments

@lukaszstolarczuk
Copy link
Member

operator-- may fail (when MtMode is enabled) in some specific cases, e.g.:

  • try_decrement fails due to concurrent erase (it can be the element pointed to by the iterator)
  • operator-- calls lower_bound which returns end() (the tree is now empty)
  • try_decrement crashes because we decrement beyond begin()

ref. #1156

@lukaszstolarczuk lukaszstolarczuk added Type: Bug Something isn't working radix_tree Needs to be resolved to productize radix_tree labels Jul 15, 2021
@igchor
Copy link
Contributor

igchor commented Jul 15, 2021

There are two problems for this version: 6300980

  1. If iterator points to end() and try_decrement fails, we will call key() on nullptr (leaf_ == nullptr for end())
  2. Problem mentioned by lukaszstolarczuk is caused by a lack of special value for begin(). When we use operator++ and encounter end() we know it's time to stop. For operator-- be cannot rely on comparison with begin() since its value can change. We could introduce a special past-begin iterator for this purpose.

Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Labels
radix_tree Needs to be resolved to productize radix_tree Type: Bug Something isn't working
Projects
None yet
Development

No branches or pull requests

2 participants