HashTable iterator over entries
Nobody has claimed this yet.
Assessment
- Difficulty
- 5/5
- Estimated time
- Over a week
- Newbie friendliness
- 35/100
- Issue type
- Feature
- Clarity
- Mostly clear
- Activity status
- Stale
- Tech stack
- rust
- Domain
- backend-api-design
Research direction
Start by reading the HashTable::extract_if and OccupiedEntry::remove APIs described in the issue, along with the Iterator usage shown. Determine whether an entry iterator can expose both sides while satisfying Rust's borrowing rules; done means the API shape, removal behavior, and required tests are clearly established.
Written by the indexing model from the issue text.
Description
Hello,
I have a crate that creates a key-to-key map (i.e. a "double-sided" map). This is implemented with two maps that index into each other. I want to implement an iterator similar to hash_table::ExtractIf, but I must provide an reference to both the left and right elements to the predicate and have that iterator yield both elements.
The problem is that there is no direct way to solve this with the existing APIs to the HashTable and still make the borrow checker happy. The best solution that I've come up with the existing APIs is to use HashTable::extract_if on one table to "smuggle out" elements from the other side and then pull the smuggled item out with Iterator::map. This works but is far from ideal:
let push = Rc::new(RefCell::new(None));
let pull = push_cache.clone();
let right_set = &mut self.right_set;
self.left_set
.extract_if(move |left| {
let Ok(right_entry) =
right_set.find_entry(left.hash, hash_and_id(left.hash, left.id))
else {
// NOTE: This shouldn't happen.
return false;
};
if f(&left.value, &right_entry.get().value) {
push.borrow_mut().insert(right_entry.remove().0);
true
} else {
false
}
})
.map(move |l| {
let Some(r) = pull.borrow_mut().take() else {
panic!()
};
(l.value, r.value)
})
However, if there were an iterator over the hash table that yielded OccupiedEntrys rather than just references, this iterator would be trivial to construct. I could zip the two iterators together, pass the references to the predicate, and, if true, call OccupiedEntry::remove on both entries.
Would such an iterator be possible to implement for HashTable?
- Dominant language
- Rust
- Stars
- 3k
- Forks
- 358
- Avg merge
- 11h 57m
- Merged PRs (30d)
- 2
Contributor guide
No contributing guide indexed for this repository
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
More from rust-lang/hashbrown
-
Difficulty 4/5 3-5 days Newbie friendliness 45/100
-
Difficulty 3/5 1-2 days Newbie friendliness 45/100
-
Difficulty 4/5 3-5 days Newbie friendliness 45/100
-
Difficulty 5/5 Over a week Newbie friendliness 30/100
-
Difficulty 5/5 Over a week Newbie friendliness 35/100
All issues in rust-lang/hashbrown
Similar issues
-
Difficulty 2/5 1-3 hours Newbie friendliness 86/100
kwakseongjae/auto-hwp#319 ·
-
area:cli bug filter-quality good first issue priority:medium
Difficulty 2/5 1-3 hours Newbie friendliness 84/100
-
Difficulty 1/5 Under an hour Newbie friendliness 72/100
bevyengine/bevy#25861 ·
-
comp-datalake
Difficulty 2/5 1-3 hours Newbie friendliness 88/100
ClickHouse/ClickHouse#121222 ·
-
enhancement remote
Difficulty 2/5 1-3 hours Newbie friendliness 68/100