Generational index

help
1

I'm trying to wrap my head around generational indexes (sorry for writing it like that, but I don't know how to spell "indices").

I think I get what the basic idea is:

  • Each element of the array has a generation.
  • Each element is accessed through an index object (which "points to" an element using an index into the array).
  • The index object also contains a generation.
  • When an element is added to the array it copies the generation of the element to the index object.
  • Each time an element is fetched from the list the generation of the index object and the element in the list are compared; only if they match is the list element returned.
  • Whenever an element in the array is "deleted" the generation of that index element is increased. (Effectively invalidating all index objects pointing to the old array element).

Is this accurate?

When I read about genidx a while back I read that the array itself keeps track of a generation. What is it used for?

2

Everything is correct except maybe #3, it depends on what you mean exactly. Most of (all) the time the "index object" is kept as is by the container. Something like Vec<Handle> so there is no need to deal with the generation when returning the "index object". If they are kept apart you have to copy both the index and generation.
Based on the implementation #2, #4 and #6 can differ from what you're describing.

I know it's used in slotmaps and ECS but it can be used whenever you want your container to invalidate old indices on removal.

1 Like
3

It's about 1200 lines, but generational-arena/lib.rs at master · fitzgen/generational-arena · GitHub is pretty easy to read overall; maybe checking out some code will help solidify your understanding.

4 Likes
4

Oh, that's very different from what I'm used to... This is what OP described I think (except point #6).

1 Like
5

You're right -- I got mixed up in my own terminology. The last point should have read that the array element's generation is increased.

6

That's what I understood (and what I do personally) but generational-arena doesn't increase the generation per element but a global one.

7

This is what I find confusing. :slight_smile:
I'll spend some time with the code steveklabnik linked to and hopefully it will become clear.

8

I think both options are perfectly fine, I'm not sure that there's any claim to the specifics of the idea other than "it's an arena and generations exist somehow."

9

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.