Hacker News Reader

Comment by ufo | Hacker News Reader

Could someone help me understand how "generational indexes" differ from usual indexes? Does this have to do with how you allocate the indexes or with how you use them? Are there run-time tests to check if the index is stale? (For example, check if the generation of the index I am holding matches the generation of the object stored in the entity array).

View on HN

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/li...

The list itself keeps track of the current generation: 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/li...

Each entry also keeps track of the generation it was inserted with: 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/li...

Same as if you try to delete something at a given index: https://github.com/steveklabnik/indexlist/blob/master/src/li...

Does that make sense?

Thanks. It wasn't as clear to me in the article that there was a run-time check but it makes much more sense now.

You'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)

What a wonderful explanation! Keep up the good work <3

Each generation represents a new ‘giving out’ of the index. As you say this provides a runtime check against accessing a stale value. It’s a common pattern for ‘object pool’ allocators in game engines.

Reply on news.ycombinator.com