3 ms·
I released a crate that implements a doubly linked list this way. Here's an index. As you can see, it's got an index, but also a generation https://github.com/
by steveklabnik 8y ago
I released a crate that implements a doubly linked list this way.
Here's an index. As you can see, it's got an index, but also a generation https://github.com/steveklabnik/indexlist/blob/master/src/lib.rs#L174-L178 https://github.com/steveklabnik/indexlist/blob/master/src/li...
The list itself keeps track of the current generation: https://github.com/steveklabnik/indexlist/blob/master/src/lib.rs#L104 https://github.com/steveklabnik/indexlist/blob/master/src/li...
When an entry is removed, this is increased: https://github.com/steveklabnik/indexlist/blob/master/src/lib.rs#L680-L682 https://github.com/steveklabnik/indexlist/blob/master/src/li...
Each entry also keeps track of the generation it was inserted with: https://github.com/steveklabnik/indexlist/blob/master/src/lib.rs#L119 https://github.com/steveklabnik/indexlist/blob/master/src/li...
When you call get, which takes an Index, the generation is checked https://github.com/steveklabnik/indexlist/blob/master/src/lib.rs#L577-L582 https://github.com/steveklabnik/indexlist/blob/master/src/li...
Same as if you try to delete something at a given index: https://github.com/steveklabnik/indexlist/blob/master/src/lib.rs#L661 https://github.com/steveklabnik/indexlist/blob/master/src/li...
Does that make sense?
- ufo 8y agoThanks. It wasn't as clear to me in the article that there was a run-time check but it makes much more sense now.
- steveklabnik 8y agoYou're welcome. One interesting property of the current implementation is that you can use an Index across multiple IndexLists. That may or may not be what you want. There's a way to add a compile-time check to prevent this, but I haven't implemented it yet (https://github.com/steveklabnik/indexlist/issues/7 https://github.com/steveklabnik/indexlist/issues/7)
- thegeekpirate 8y agoWhat a wonderful explanation! Keep up the good work <3