Skip to content

Instantly share code, notes, and snippets.

@MircoT

MircoT/genindex.cpp

Forked from jaburns/genindex.cpp
Created February 16, 2022 11:00
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save MircoT/fa00d7553f5e6ba2724b39ad4876b182 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save MircoT/fa00d7553f5e6ba2724b39ad4876b182 to your computer and use it in GitHub Desktop.
Download ZIP
Generational indices in C++ vs Rust
Raw
genindex.cpp
#include <functional>
#include <vector>
#include <cstdint>
#include <optional>
#include <tuple>
using std::vector;
using std::optional;
using std::tuple;
using std::reference_wrapper;
struct GenerationalIndex
{
uint32_t index = 0;
uint32_t generation = 0;
};
class GenerationalIndexAllocator
{
struct AllocatorEntry
{
bool is_live = false;
uint32_t generation = 0;
};
vector<AllocatorEntry> m_entries;
vector<uint32_t> m_free_indices;
public:
GenerationalIndex allocate();
void deallocate(GenerationalIndex index);
bool is_live(GenerationalIndex index) const;
};
GenerationalIndex GenerationalIndexAllocator::allocate()
{
if (m_free_indices.size() > 0)
{
uint32_t index = m_free_indices.back();
m_free_indices.pop_back();
m_entries[index].generation += 1;
m_entries[index].is_live = true;
return { index, m_entries[index].generation };
}
else
{
m_entries.push_back({ true, 0 });
return { static_cast<uint32_t>(m_entries.size()) - 1, 0 };
}
}
void GenerationalIndexAllocator::deallocate(GenerationalIndex index)
{
if (is_live(index))
{
m_entries[index.index].is_live = false;
m_free_indices.push_back(index.index);
}
}
bool GenerationalIndexAllocator::is_live(GenerationalIndex index) const
{
return index.index < m_entries.size() &&
m_entries[index.index].generation == index.generation &&
m_entries[index.index].is_live;
}
template<typename T>
class GenerationalIndexArray
{
struct Entry
{
uint32_t generation;
T value;
};
vector<optional<Entry>> m_entries;
public:
void set(GenerationalIndex index, T value)
{
while (m_entries.size() <= index.index)
m_entries.push_back(std::nullopt);
uint32_t prev_gen = 0;
if (auto prev_entry = m_entries[index.index])
prev_gen = prev_entry->generation;
if (prev_gen > index.generation)
exit(1);
m_entries[index.index] = optional<Entry>{{ index.generation, value }};
}
void remove(GenerationalIndex index)
{
if (index.index < m_entries.size())
m_entries[index.index] = std::nullopt;
}
public:
T* get(GenerationalIndex index)
{
if (index.index >= m_entries.size()) return nullptr;
if (auto& entry = m_entries[index.index])
{
if (entry->generation == index.generation)
return &entry->value;
}
return nullptr;
}
const T* get(GenerationalIndex index) const
{
return const_cast<const T*>(const_cast<GenerationalIndexArray*>(this)->get(index));
}
vector<GenerationalIndex> get_all_valid_indices(const GenerationalIndexAllocator& allocator) const
{
vector<GenerationalIndex> result;
for (auto i = 0; i < m_entries.size(); ++i)
{
const auto& entry = m_entries[i];
if (!entry) continue;
GenerationalIndex index = { i, entry->generation };
if (allocator.is_live(index))
result.push_back(index);
}
return result;
}
optional<tuple<GenerationalIndex, reference_wrapper<const T>>> get_first_valid_entry(const GenerationalIndexAllocator& allocator) const
{
for (auto i = 0; i < m_entries.size(); ++i)
{
const auto& entry = m_entries[i];
if (!entry) continue;
GenerationalIndex index = { i, entry->generation };
if (allocator.is_live(index))
return std::make_tuple(index, std::ref(entry->value));
}
return std::nullopt;
}
};
Raw
genindex.rs
#[derive(Copy, Clone, Eq, PartialEq, Hash)]
struct GenerationalIndex {
index: usize,
generation: usize,
}
struct AllocatorEntry {
is_live: bool,
generation: usize,
}
struct GenerationalIndexAllocator {
entries: Vec<AllocatorEntry>,
free: Vec<usize>,
}
impl GenerationalIndexAllocator {
fn new() -> GenerationalIndexAllocator {
GenerationalIndexAllocator {
entries: Vec::new(),
free: Vec::new(),
}
}
fn allocate(&mut self) -> GenerationalIndex {
match self.free.pop() {
Some(index) => {
self.entries[index].generation += 1;
self.entries[index].is_live = true;
GenerationalIndex {
index,
generation: self.entries[index].generation,
}
}
None => {
self.entries.push(AllocatorEntry {
is_live: true,
generation: 0,
});
GenerationalIndex {
index: self.entries.len() - 1,
generation: 0,
}
}
}
}
fn deallocate(&mut self, index: GenerationalIndex) -> bool {
if self.is_live(index) {
self.entries[index.index].is_live = false;
self.free.push(index.index);
true
} else {
false
}
}
fn is_live(&self, index: GenerationalIndex) -> bool {
index.index < self.entries.len()
&& self.entries[index.index].generation == index.generation
&& self.entries[index.index].is_live
}
}
struct ArrayEntry<T> {
value: T,
generation: usize,
}
struct GenerationalIndexArray<T>(Vec<Option<ArrayEntry<T>>>);
impl<T> GenerationalIndexArray<T> {
fn new() -> GenerationalIndexArray<T> {
GenerationalIndexArray(Vec::new())
}
fn set(&mut self, index: GenerationalIndex, value: T) {
while self.0.len() <= index.index {
self.0.push(None);
}
let prev_gen = match &self.0[index.index] {
Some(entry) => entry.generation,
None => 0,
};
if prev_gen > index.generation {
panic!("Attempted to write to GenerationalIndexArray with an index from previous generation");
}
self.0[index.index] = Some(ArrayEntry {
value,
generation: index.generation,
});
}
fn remove(&mut self, index: GenerationalIndex) {
if index.index < self.0.len() {
self.0[index.index] = None;
}
}
fn get(&self, index: GenerationalIndex) -> Option<&T> {
if index.index >= self.0.len() {
return None;
}
match &self.0[index.index] {
Some(entry) => if entry.generation == index.generation {
Some(&entry.value)
} else {
None
},
None => None,
}
}
fn get_mut(&mut self, index: GenerationalIndex) -> Option<&mut T> {
if index.index >= self.0.len() {
return None;
}
match &mut self.0[index.index] {
Some(entry) => if entry.generation == index.generation {
Some(&mut entry.value)
} else {
None
},
None => None,
}
}
fn get_all_valid_indices(
&self,
allocator: &GenerationalIndexAllocator,
) -> Vec<GenerationalIndex> {
let mut result = Vec::new();
for i in 0..self.0.len() {
if let Some(entry) = &self.0[i] {
let index = GenerationalIndex {
index: i,
generation: entry.generation,
};
if allocator.is_live(index) {
result.push(index);
}
}
}
result
}
fn get_first_valid_entry(
&self,
allocator: &GenerationalIndexAllocator,
) -> Option<(GenerationalIndex, &T)> {
for i in 0..self.0.len() {
if let Some(entry) = &self.0[i] {
let index = GenerationalIndex {
index: i,
generation: entry.generation,
};
if allocator.is_live(index) {
return Some((index, &entry.value));
}
}
}
None
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment