Iteration without an iterator

[jugglerchris]

Hi, I'm interested in whether hashbrown can be used for implementing Lua tables for Luster. (Note: I'm not the owner, just someone interested in the project!)

The unusual requirements for Lua's tables are:

1. Lua's next(table, item) function returns the "next" item in the table, given another.
2. Iteration using next has to be stable when removing items during the iteration.

I've had a look and think that hashbrown can support this with not much modification, and prototyped it here (a few months ago, so I haven't yet caught up on recent changes; this was before it was moved to rust-lang):

https://github.com/jugglerchris/hashbrown/tree/hash_next

I added a fn next_after(&self, key: Option<&K>) -> Option<(&K, &V)> which simply steps through hash buckets via a RawIterRange constructed to point part way through to implement #1, and #2 happens for free by using tombstones when removing (which relies on there not being a resize when shrinking too far; I'm not confident I haven't missed any cases).

I would be interested to know if functionality like this would be considered for hashbrown itself (I could understand not; I can certainly see not wanting to guarantee no resize on removal), or if not whether I've missed any obvious issues if I (or someone else) were to maintain a fork with these changes.

Thanks! I've certainly enjoyed looking through and having a play either way. :-)

[Amanieu]

Unfortunately we can't really guarantee that elements aren't shuffled around on removal. However have you had a look at the RawTable API that can be enabled with the raw feature? You might be able to build something on top of that.

[jugglerchris]

Thanks @Amanieu . Does the RawTable provide the no-shuffle-on-remove guarantee then?

The other functionality needed is iteration (well, one step at a time) starting from an existing T known to be in the table. I can't see a way of doing that efficiently as is - it would still need a way of creating a RawIter<T> from a given starting position (e.g. from a Bucket<T> obtained from find(hash, eq)).

[Amanieu]

RawTable does guarantee no-shuffle-on-remove.

You can get a Bucket<T> from an index by calling the bucket function. You wouldn't use RawIter at all for your style of iteration.

[jugglerchris]

I think I'm still missing something (or have not explained things very well) - I still need to use some of the machinery from RawIter to step from an item (I start with a T) to the next one.

I want to implement something like this function:

impl MyTable<T:Hash> {
    fn next(&self, item: &T) -> Option<&T> {
        // find the "next" entry in the table following the passed in item, if any
        ...
    }

Given a T I can get a Bucket<T> from the table via find. I don't see how to get an index for the current item (except via pointer subtraction), but definitely can't see a way (I'm looking at https://docs.rs/hashbrown/0.6.3/hashbrown/raw/struct.RawTable.html) of finding the next occupied bucket after that.

Thanks for bearing with me!

[Amanieu]

Oh, it seems that the bucket_index function is not marked pub. If you send a PR changing that I'll accept it and push a new version.

[jugglerchris]

Thanks, I've opened the PR. Now that I've been looking at other private methods, it looks like I'll probably also need RawTable::ctrl() and raw::is_full() to be pub as well, and then I can just loop over an index looking for occupied buckets. I can add those to the PR (or open another) if that sounds right.

[ibraheemdev]

This would be useful to me as well. I have the requirement that the iterator cannot borrow from the map itself, it must borrow from a &RefCell<HashMap>, so an index based iteration API would be useful.