use alloc::vec::Vec;
use core::cmp;
use core::convert::TryFrom;
use core::sync::atomic::{AtomicI64, Ordering};
use core::{fmt, mem};
#[cfg(feature = "std")]
use std::error::Error;
#[derive(Clone, Copy, Hash, Eq, Ord, PartialEq, PartialOrd)]
pub struct Entity {
pub(crate) generation: u32,
pub(crate) id: u32,
}
impl Entity {
pub fn to_bits(self) -> u64 {
u64::from(self.generation) << 32 | u64::from(self.id)
}
pub fn from_bits(bits: u64) -> Self {
Self {
generation: (bits >> 32) as u32,
id: bits as u32,
}
}
pub fn id(self) -> u32 {
self.id
}
}
impl fmt::Debug for Entity {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(f, "{}v{}", self.id, self.generation)
}
}
pub struct ReserveEntitiesIterator<'a> {
meta: &'a [EntityMeta],
id_iter: core::slice::Iter<'a, u32>,
id_range: core::ops::Range<u32>,
}
impl<'a> Iterator for ReserveEntitiesIterator<'a> {
type Item = Entity;
fn next(&mut self) -> Option<Self::Item> {
self.id_iter
.next()
.map(|&id| Entity {
generation: self.meta[id as usize].generation,
id,
})
.or_else(|| self.id_range.next().map(|id| Entity { generation: 0, id }))
}
fn size_hint(&self) -> (usize, Option<usize>) {
let len = self.id_iter.len() + self.id_range.len();
(len, Some(len))
}
}
impl<'a> core::iter::ExactSizeIterator for ReserveEntitiesIterator<'a> {}
#[derive(Default)]
pub(crate) struct Entities {
pub meta: Vec<EntityMeta>,
pending: Vec<u32>,
free_cursor: AtomicI64,
}
impl Entities {
pub fn reserve_entities(&self, count: u32) -> ReserveEntitiesIterator {
let range_end = self.free_cursor.fetch_sub(count as i64, Ordering::Relaxed);
let range_start = range_end - count as i64;
let freelist_range = range_start.max(0) as usize..range_end.max(0) as usize;
let (new_id_start, new_id_end) = if range_start >= 0 {
(0, 0)
} else {
let base = self.meta.len() as i64;
let new_id_end = u32::try_from(base - range_start).expect("too many entities");
let new_id_start = (base - range_end.min(0)) as u32;
(new_id_start, new_id_end)
};
ReserveEntitiesIterator {
meta: &self.meta[..],
id_iter: self.pending[freelist_range].iter(),
id_range: new_id_start..new_id_end,
}
}
pub fn reserve_entity(&self) -> Entity {
let n = self.free_cursor.fetch_sub(1, Ordering::Relaxed);
if n > 0 {
let id = self.pending[(n - 1) as usize];
Entity {
generation: self.meta[id as usize].generation,
id,
}
} else {
Entity {
generation: 0,
id: u32::try_from(self.meta.len() as i64 - n).expect("too many entities"),
}
}
}
fn verify_flushed(&mut self) {
debug_assert!(
!self.needs_flush(),
"flush() needs to be called before this operation is legal"
);
}
pub fn alloc(&mut self) -> Entity {
self.verify_flushed();
if let Some(id) = self.pending.pop() {
let new_free_cursor = self.pending.len() as i64;
self.free_cursor.store(new_free_cursor, Ordering::Relaxed);
Entity {
generation: self.meta[id as usize].generation,
id,
}
} else {
let id = u32::try_from(self.meta.len()).expect("too many entities");
self.meta.push(EntityMeta::EMPTY);
Entity { generation: 0, id }
}
}
pub fn alloc_at(&mut self, entity: Entity) -> Option<Location> {
self.verify_flushed();
let loc = if entity.id as usize >= self.meta.len() {
self.pending.extend((self.meta.len() as u32)..entity.id);
let new_free_cursor = self.pending.len() as i64;
self.free_cursor.store(new_free_cursor, Ordering::Relaxed);
self.meta.resize(entity.id as usize + 1, EntityMeta::EMPTY);
None
} else if let Some(index) = self.pending.iter().position(|item| *item == entity.id) {
self.pending.swap_remove(index);
let new_free_cursor = self.pending.len() as i64;
self.free_cursor.store(new_free_cursor, Ordering::Relaxed);
None
} else {
Some(mem::replace(
&mut self.meta[entity.id as usize].location,
EntityMeta::EMPTY.location,
))
};
self.meta[entity.id as usize].generation = entity.generation;
loc
}
pub fn free(&mut self, entity: Entity) -> Result<Location, NoSuchEntity> {
self.verify_flushed();
let meta = &mut self.meta[entity.id as usize];
if meta.generation != entity.generation {
return Err(NoSuchEntity);
}
meta.generation += 1;
let loc = mem::replace(&mut meta.location, EntityMeta::EMPTY.location);
self.pending.push(entity.id);
let new_free_cursor = self.pending.len() as i64;
self.free_cursor.store(new_free_cursor, Ordering::Relaxed);
Ok(loc)
}
pub fn reserve(&mut self, additional: u32) {
self.verify_flushed();
let freelist_size = self.free_cursor.load(Ordering::Relaxed);
let shortfall = additional as i64 - freelist_size;
if shortfall > 0 {
self.meta.reserve(shortfall as usize);
}
}
pub fn contains(&self, entity: Entity) -> bool {
self.meta
.get(entity.id as usize)
.map_or(true, |meta| meta.generation == entity.generation)
}
pub fn clear(&mut self) {
self.meta.clear();
self.pending.clear();
self.free_cursor.store(0, Ordering::Relaxed);
}
pub fn get_mut(&mut self, entity: Entity) -> Result<&mut Location, NoSuchEntity> {
let meta = &mut self.meta[entity.id as usize];
if meta.generation == entity.generation {
Ok(&mut meta.location)
} else {
Err(NoSuchEntity)
}
}
pub fn get(&self, entity: Entity) -> Result<Location, NoSuchEntity> {
if self.meta.len() <= entity.id as usize {
return Ok(Location {
archetype: 0,
index: u32::max_value(),
});
}
let meta = &self.meta[entity.id as usize];
if meta.generation != entity.generation {
return Err(NoSuchEntity);
}
if meta.location.archetype == 0 {
return Ok(Location {
archetype: 0,
index: u32::max_value(),
});
}
Ok(meta.location)
}
pub unsafe fn resolve_unknown_gen(&self, id: u32) -> Entity {
let meta_len = self.meta.len();
if meta_len > id as usize {
let meta = &self.meta[id as usize];
Entity {
generation: meta.generation,
id,
}
} else {
let free_cursor = self.free_cursor.load(Ordering::Relaxed);
let num_pending = cmp::max(-free_cursor, 0) as usize;
if meta_len + num_pending > id as usize {
Entity { generation: 0, id }
} else {
panic!("entity id is out of range");
}
}
}
fn needs_flush(&mut self) -> bool {
self.free_cursor.load(Ordering::Relaxed) != self.pending.len() as i64
}
pub fn flush(&mut self, mut init: impl FnMut(u32, &mut Location)) {
let free_cursor = self.free_cursor.load(Ordering::Relaxed);
let new_free_cursor = if free_cursor >= 0 {
free_cursor as usize
} else {
let old_meta_len = self.meta.len();
let new_meta_len = old_meta_len + -free_cursor as usize;
self.meta.resize(new_meta_len, EntityMeta::EMPTY);
for (id, meta) in self.meta.iter_mut().enumerate().skip(old_meta_len) {
init(id as u32, &mut meta.location);
}
self.free_cursor.store(0, Ordering::Relaxed);
0
};
for id in self.pending.drain(new_free_cursor..) {
init(id, &mut self.meta[id as usize].location);
}
}
}
#[derive(Copy, Clone)]
pub(crate) struct EntityMeta {
pub generation: u32,
pub location: Location,
}
impl EntityMeta {
const EMPTY: EntityMeta = EntityMeta {
generation: 0,
location: Location {
archetype: 0,
index: u32::max_value(),
},
};
}
#[derive(Copy, Clone)]
pub(crate) struct Location {
pub archetype: u32,
pub index: u32,
}
#[derive(Debug, Clone, Eq, PartialEq)]
pub struct NoSuchEntity;
impl fmt::Display for NoSuchEntity {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.pad("no such entity")
}
}
#[cfg(feature = "std")]
impl Error for NoSuchEntity {}
#[cfg(test)]
mod tests {
use super::*;
use hashbrown::{HashMap, HashSet};
use rand::{rngs::StdRng, Rng, SeedableRng};
#[test]
fn entity_bits_roundtrip() {
let e = Entity {
generation: 0xDEADBEEF,
id: 0xBAADF00D,
};
assert_eq!(Entity::from_bits(e.to_bits()), e);
}
#[test]
fn alloc_and_free() {
let mut rng = StdRng::seed_from_u64(0xFEEDFACEDEADF00D);
let mut e = Entities::default();
let mut first_unused = 0u32;
let mut id_to_gen: HashMap<u32, u32> = Default::default();
let mut free_set: HashSet<u32> = Default::default();
for _ in 0..100 {
let alloc = rng.gen_bool(0.7);
if alloc || first_unused == 0 {
let entity = e.alloc();
let id = entity.id;
if !free_set.is_empty() {
assert!(free_set.remove(&id));
} else if id >= first_unused {
first_unused = id + 1;
}
e.get_mut(entity).unwrap().index = 37;
assert!(id_to_gen.insert(id, entity.generation).is_none());
} else {
let id = rng.gen_range(0, first_unused);
let generation = id_to_gen.remove(&id);
let entity = Entity {
id,
generation: generation.unwrap_or(0),
};
assert_eq!(e.free(entity).is_ok(), generation.is_some());
free_set.insert(id);
}
}
}
#[test]
fn alloc_at() {
let mut e = Entities::default();
let mut old = Vec::new();
for _ in 0..2 {
let entity = e.alloc();
old.push(entity);
e.free(entity).unwrap();
}
let id = old.first().unwrap().id();
assert!(old.iter().all(|entity| entity.id() == id));
let entity = *old.last().unwrap();
assert!(!e.contains(entity));
assert!(e.pending.contains(&entity.id()));
assert!(e.alloc_at(entity).is_none());
assert!(e.contains(entity));
assert!(!e.pending.contains(&entity.id()));
assert!(e.alloc_at(entity).is_some());
assert!(e.contains(entity));
assert_eq!(e.meta.len(), 1);
assert!(e
.alloc_at(Entity {
id: 3,
generation: 2,
})
.is_none());
assert_eq!(e.pending.len(), 2);
assert_eq!(&e.pending, &[1, 2]);
assert_eq!(e.meta.len(), 4);
}
#[test]
fn contains() {
let mut e = Entities::default();
for _ in 0..2 {
let entity = e.alloc();
assert!(e.contains(entity));
e.free(entity).unwrap();
assert!(!e.contains(entity));
}
for _ in 0..3 {
let entity = e.reserve_entity();
assert!(e.contains(entity));
}
}
fn reserve_test_helper(reserve_n: impl FnOnce(&mut Entities, u32) -> Vec<Entity>) {
let mut e = Entities::default();
let mut v1: Vec<Entity> = (0..10).map(|_| e.alloc()).collect();
assert_eq!(v1.iter().map(|e| e.id).max(), Some(9));
for &entity in v1.iter() {
assert!(e.contains(entity));
e.get_mut(entity).unwrap().index = 37;
}
for entity in v1.drain(6..) {
e.free(entity).unwrap();
}
assert_eq!(e.free_cursor.load(Ordering::Relaxed), 4);
let v2 = reserve_n(&mut e, 10);
assert_eq!(v2.iter().map(|e| e.id).max(), Some(15));
assert!(v2.iter().all(|&entity| e.contains(entity)));
let mut v3: Vec<Entity> = v1.iter().chain(v2.iter()).copied().collect();
assert_eq!(v3.len(), 16);
v3.sort_by_key(|entity| entity.id);
for (i, entity) in v3.into_iter().enumerate() {
assert_eq!(entity.id, i as u32);
}
assert_eq!(e.free_cursor.load(Ordering::Relaxed), -6);
let mut flushed = Vec::new();
e.flush(|id, _| flushed.push(id));
flushed.sort_unstable();
assert_eq!(flushed, (6..16).collect::<Vec<_>>());
}
#[test]
fn reserve_entity() {
reserve_test_helper(|e, n| (0..n).map(|_| e.reserve_entity()).collect())
}
#[test]
fn reserve_entities() {
reserve_test_helper(|e, n| e.reserve_entities(n).collect())
}
}