# genmap
A Rust crate for a generational map, handle map, whatever you want to
call it. Whatever it is, this is a random-access data structure that
stores an unordered bag of items and gives you a handle for each
specific item you insert. Looking things up by is `O(1)` -- the
backing storage is just a `Vec` -- and items can be removed as well,
which is also `O(1)`. Handles are small (two `usize`'s) and easy to
copy, similar to a slice.
This is useful for various things: managing lots of uniform things
with shared ownership (such as video game resources), interning
strings, that sort of thing. Essentially you get handles to items
with runtime-checked memory safety; you can get an item from the map
using the handle, since it's basically just an array index. The trick
is that you can safely remove items from the map as well, and unlike
using array indices, a handle to an item that has been removed is
invalid and trying to use it will fail at runtime, even if the storage
the item occupied has been reused.
In practice this is not unrelated to `Rc`, it's just that `Rc` does
the accounting of memory on cloning the `Rc`, and this does it on
"dereferencing" by looking up an object's handle. Referencing
counting, threading garbage collection and this sort of map are all
different methods of achieving the same thing (checking for memory
safety at runtime) with different tradeoffs.
# Limitations
* It never frees memory until the `GenMap` is dropped (though it does reuse it).
* Overflowing generations is an error. Should it be a u64 rather than usize?
# Other things like this:
* slotmap -- requires your items be `Copy`, which I feel is too
restrictive. Its `DenseSlotMap` gets around this, but really at
that point there's too many options and tradeoffs to consider. I
just want something that Works.
* handy -- Very nice but I don't like some of the design decisions it
makes: <https://github.com/thomcc/handy/pull/1>
* slab -- Not really a generational map IMO, since it doesn't track
generations.
* specs -- A Storage in `specs` is basically a type of generational
map. `specs` adds tons of other stuff though.