You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@asyncband.apache.org by ti...@apache.org on 2026/09/02 11:58:23 UTC
(asyncband) branch main updated: refactor: make arena vacant list explicit (#268)
This is an automated email from the ASF dual-hosted git repository.
tisonkun pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/asyncband.git
The following commit(s) were added to refs/heads/main by this push:
new 2745639 refactor: make arena vacant list explicit (#268)
2745639 is described below
commit 27456396b6041f1ccd9a6b28c12c52b08cabb0ed
Author: tison <wa...@gmail.com>
AuthorDate: Wed Sep 2 19:58:18 2026 +0800
refactor: make arena vacant list explicit (#268)
---
asyncband/src/internal/arena.rs | 59 ++++++++++++++++++++++-------------------
1 file changed, 32 insertions(+), 27 deletions(-)
diff --git a/asyncband/src/internal/arena.rs b/asyncband/src/internal/arena.rs
index 290a32c..ce0bc7b 100644
--- a/asyncband/src/internal/arena.rs
+++ b/asyncband/src/internal/arena.rs
@@ -18,11 +18,12 @@
use std::mem;
use std::num::NonZeroUsize;
-/// Identifies a reusable slot while that slot is occupied.
+/// Identifies a slot in an arena.
///
/// The non-zero representation lets wrappers such as `WaiterId` retain a niche when stored in an
-/// `Option`. Slot IDs deliberately carry no generation: each consumer supplies the cheaper
-/// lifecycle rule that matches its waiter storage.
+/// `Option`. An ID issued to a consumer remains valid only while its slot is occupied. Slot IDs
+/// deliberately carry no generation: each consumer supplies the cheaper lifecycle rule that
+/// matches its waiter storage.
#[derive(Clone, Copy, Eq, PartialEq)]
pub struct SlotId(NonZeroUsize);
@@ -49,27 +50,27 @@ impl std::fmt::Debug for SlotId {
/// Minimal reusable storage for internal waiter state.
///
/// The occupied length equals the number of `Occupied` slots. Every `Vacant` slot appears exactly
-/// once in the singly linked vacant list, which starts at `next_vacant` and terminates at
-/// `slots.len()`. Removing a value makes its slot ID available for immediate reuse.
+/// once in the singly linked vacant list starting at `vacant_head`. Removing a value makes its slot
+/// ID available for immediate reuse.
#[derive(Debug)]
pub struct Arena<T> {
slots: Vec<Slot<T>>,
- /// The next reusable slot, or `slots.len()` when every slot is occupied.
- next_vacant: usize,
+ /// The head of the vacant list, or `None` when every slot is occupied.
+ vacant_head: Option<SlotId>,
len: usize,
}
#[derive(Debug)]
enum Slot<T> {
Occupied(T),
- Vacant { next: usize },
+ Vacant { next: Option<SlotId> },
}
impl<T> Arena<T> {
pub const fn new() -> Self {
Self {
slots: vec![],
- next_vacant: 0,
+ vacant_head: None,
len: 0,
}
}
@@ -77,29 +78,33 @@ impl<T> Arena<T> {
pub fn with_capacity(capacity: usize) -> Self {
Self {
slots: Vec::with_capacity(capacity),
- next_vacant: 0,
+ vacant_head: None,
len: 0,
}
}
pub fn insert(&mut self, value: T) -> SlotId {
- let index = self.next_vacant;
- self.len += 1;
-
- if index == self.slots.len() {
- self.slots.push(Slot::Occupied(value));
- self.next_vacant = index + 1;
- } else {
- self.next_vacant = match self.slots.get(index) {
- Some(Slot::Vacant { next }) => *next,
- Some(Slot::Occupied(_)) | None => {
+ let id = if let Some(id) = self.vacant_head {
+ let slot = self
+ .slots
+ .get_mut(id.index())
+ .expect("arena free list must point to a slot");
+ self.vacant_head = match slot {
+ Slot::Vacant { next } => *next,
+ Slot::Occupied(_) => {
unreachable!("arena free list must point to a vacant slot")
}
};
- self.slots[index] = Slot::Occupied(value);
- }
+ *slot = Slot::Occupied(value);
+ id
+ } else {
+ let id = SlotId::from_index(self.slots.len());
+ self.slots.push(Slot::Occupied(value));
+ id
+ };
- SlotId::from_index(index)
+ self.len += 1;
+ id
}
pub fn get(&self, id: SlotId) -> Option<&T> {
@@ -147,7 +152,7 @@ impl<T> Arena<T> {
let value = match mem::replace(
slot,
Slot::Vacant {
- next: self.next_vacant,
+ next: self.vacant_head,
},
) {
Slot::Occupied(value) => value,
@@ -157,7 +162,7 @@ impl<T> Arena<T> {
}
};
self.len -= 1;
- self.next_vacant = index;
+ self.vacant_head = Some(id);
value
}
@@ -168,7 +173,7 @@ impl<T> Arena<T> {
/// their own epoch check.
#[inline]
pub fn drain(&mut self) -> impl Iterator<Item = T> + '_ {
- self.next_vacant = 0;
+ self.vacant_head = None;
self.len = 0;
self.slots.drain(..).filter_map(|slot| match slot {
Slot::Occupied(value) => Some(value),
@@ -179,7 +184,7 @@ impl<T> Arena<T> {
/// Takes every occupied value and the backing allocation in slot order.
#[inline]
pub fn take_all(&mut self) -> impl Iterator<Item = T> + use<T> {
- self.next_vacant = 0;
+ self.vacant_head = None;
self.len = 0;
mem::take(&mut self.slots)
.into_iter()
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@asyncband.apache.org
For additional commands, e-mail: commits-help@asyncband.apache.org