I have implemented my own slotmap crate for a lisp interpreter that uses no unsafe code and provides exactly the same features as the "standard" slotmap crate.
There is nothing inherent to the slotmap that requires unsafe code! It's only used for optimizations purposes.
Mine works in a similar way to the "standard" slotmap. It's a vec of slots, slot is an enum that can be occupied or vacant, the occupied variant is a two tuple containing the value and generation, vacant holds just a generation. Inserting into the slotmap simply switches the variant of the slot from vacant to occupied, and popping does the reverse. If there is no currently vacant slots, we just use the underlying push method on the vec of slots which will handle resizing for us! I also store a stack of indexes to vacant slots to make insertion fast.
When you insert into the slotmap, it provides a opaque key, but the data inside is an index and a generation. When you attempt to retrieve a value with a key, the slotmap checks if the slot is occupied and if the generation matches, and if so returns the value, otherwise returns none.
There is also a indirect slotmap, that adds an extra layer of indirection, so rather than the key being an index directly into the underlying vec of slots, its an index into a vec of indexes, this allows moving the slots around without invaliding currently living keys.
The indirect slotmap has the advantage of faster iteration, since it doesn't have to skip over empty "holes" of vacant slots in the vec of slots. The tradeoff is that insertion is slightly slower!
Anyways, no unsafe is required to implement a performant slotmap data structure! I have not uploaded my slotmap to crates.io because I didn't think anyone would find it useful, but maybe I should reconsider this!
There is nothing inherent to the slotmap that requires unsafe code! It's only used for optimizations purposes.
Mine works in a similar way to the "standard" slotmap. It's a vec of slots, slot is an enum that can be occupied or vacant, the occupied variant is a two tuple containing the value and generation, vacant holds just a generation. Inserting into the slotmap simply switches the variant of the slot from vacant to occupied, and popping does the reverse. If there is no currently vacant slots, we just use the underlying push method on the vec of slots which will handle resizing for us! I also store a stack of indexes to vacant slots to make insertion fast.
When you insert into the slotmap, it provides a opaque key, but the data inside is an index and a generation. When you attempt to retrieve a value with a key, the slotmap checks if the slot is occupied and if the generation matches, and if so returns the value, otherwise returns none.
There is also a indirect slotmap, that adds an extra layer of indirection, so rather than the key being an index directly into the underlying vec of slots, its an index into a vec of indexes, this allows moving the slots around without invaliding currently living keys.
The indirect slotmap has the advantage of faster iteration, since it doesn't have to skip over empty "holes" of vacant slots in the vec of slots. The tradeoff is that insertion is slightly slower!
Anyways, no unsafe is required to implement a performant slotmap data structure! I have not uploaded my slotmap to crates.io because I didn't think anyone would find it useful, but maybe I should reconsider this!