use crate::types::EntityId;
use im::HashMap as ImHashMap;
use std::sync::Arc;
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub enum OffsetMarker {
Block(EntityId),
TableAnchor(EntityId),
}
impl OffsetMarker {
pub fn as_block(self) -> Option<EntityId> {
match self {
OffsetMarker::Block(id) => Some(id),
_ => None,
}
}
pub fn as_table_anchor(self) -> Option<EntityId> {
match self {
OffsetMarker::TableAnchor(id) => Some(id),
_ => None,
}
}
pub fn is_block(self) -> bool {
matches!(self, OffsetMarker::Block(_))
}
}
#[derive(Debug, Clone, Default, PartialEq, Eq)]
pub struct BlockOffsetIndex {
pub entries: Arc<Vec<(OffsetMarker, u32)>>,
pub total_bytes: u32,
marker_index: ImHashMap<OffsetMarker, usize>,
table_anchor_count: usize,
}
impl BlockOffsetIndex {
pub fn new() -> Self {
Self::default()
}
pub fn len(&self) -> usize {
self.entries.len()
}
pub fn is_empty(&self) -> bool {
self.entries.is_empty()
}
pub fn total_bytes(&self) -> u32 {
self.total_bytes
}
pub fn set_total_bytes(&mut self, total: u32) {
self.total_bytes = total;
}
pub fn table_anchor_count(&self) -> usize {
self.table_anchor_count
}
pub fn insert_at(&mut self, position: usize, marker: OffsetMarker, byte_start: u32) {
Arc::make_mut(&mut self.entries).insert(position, (marker, byte_start));
for (m, p) in self.marker_index.iter_mut() {
if *p >= position && *m != marker {
*p += 1;
}
}
self.marker_index.insert(marker, position);
if matches!(marker, OffsetMarker::TableAnchor(_)) {
self.table_anchor_count += 1;
}
}
pub fn insert_run_at(&mut self, position: usize, run: &[(OffsetMarker, u32)]) {
if run.is_empty() {
return;
}
Arc::make_mut(&mut self.entries).splice(position..position, run.iter().copied());
for (_, p) in self.marker_index.iter_mut() {
if *p >= position {
*p += run.len();
}
}
for (offset, (marker, _)) in run.iter().enumerate() {
self.marker_index.insert(*marker, position + offset);
if matches!(marker, OffsetMarker::TableAnchor(_)) {
self.table_anchor_count += 1;
}
}
}
pub fn reorder_run(&mut self, position: usize, run: &[(OffsetMarker, u32)]) {
let entries = Arc::make_mut(&mut self.entries);
let Some(slots) = entries.get_mut(position..position + run.len()) else {
return;
};
slots.copy_from_slice(run);
for (offset, (marker, _)) in run.iter().enumerate() {
self.marker_index.insert(*marker, position + offset);
}
}
pub fn remove_bytes_after(&mut self, cuts: &[(usize, u32)]) {
if cuts.is_empty() {
return;
}
entries_rewritten(self.entries.len());
let mut removed: u32 = 0;
let mut pending = cuts.iter().peekable();
for (position, (_, byte_start)) in Arc::make_mut(&mut self.entries).iter_mut().enumerate() {
debug_assert!(*byte_start >= removed, "a cut past an entry's start");
*byte_start = byte_start.saturating_sub(removed);
while let Some(&&(cut_position, bytes)) = pending.peek() {
if cut_position != position {
break;
}
removed = removed.saturating_add(bytes);
pending.next();
}
}
self.total_bytes = self.total_bytes.saturating_sub(removed);
}
pub fn shift_after_each(&mut self, shifts: &[(u32, i32)]) {
if shifts.is_empty() {
return;
}
let first = self.entries.partition_point(|(_, bs)| *bs < shifts[0].0);
entries_rewritten(self.entries.len() - first);
let mut delta: i32 = 0;
let mut pending = shifts.iter().peekable();
for (_, byte_start) in Arc::make_mut(&mut self.entries)[first..].iter_mut() {
while let Some(&&(threshold, shift)) = pending.peek() {
if threshold > *byte_start {
break;
}
delta += shift;
pending.next();
}
*byte_start = apply_delta(*byte_start, delta);
}
let total: i32 = shifts.iter().map(|(_, shift)| shift).sum();
self.total_bytes = apply_delta(self.total_bytes, total);
}
pub fn remove_entries(&mut self, dropped: &[bool], cuts: &[(u32, u32)]) {
debug_assert_eq!(dropped.len(), self.entries.len());
entries_rewritten(self.entries.len());
let mut kept: Vec<(OffsetMarker, u32)> = Vec::with_capacity(self.entries.len());
let mut pending = cuts.iter().peekable();
let mut removed: u32 = 0;
for (position, &(marker, byte_start)) in self.entries.iter().enumerate() {
while let Some(&&(cut_start, cut_end)) = pending.peek() {
if cut_end > byte_start {
break;
}
debug_assert!(cut_start <= cut_end, "a cut ends before it starts");
removed += cut_end - cut_start;
pending.next();
}
if !dropped.get(position).copied().unwrap_or(false) {
kept.push((marker, byte_start - removed));
}
}
let cut_total: u32 = cuts.iter().map(|(start, end)| end - start).sum();
self.entries = Arc::new(kept);
self.total_bytes = self.total_bytes.saturating_sub(cut_total);
self.rebuild_marker_index();
}
pub fn push(&mut self, marker: OffsetMarker, byte_start: u32) {
debug_assert!(
self.entries
.last()
.map(|(_, bs)| byte_start >= *bs)
.unwrap_or(true),
"push must preserve ordering"
);
let position = self.entries.len();
Arc::make_mut(&mut self.entries).push((marker, byte_start));
self.marker_index.insert(marker, position);
if matches!(marker, OffsetMarker::TableAnchor(_)) {
self.table_anchor_count += 1;
}
}
pub fn push_block(&mut self, block_id: EntityId, byte_start: u32) {
self.push(OffsetMarker::Block(block_id), byte_start);
}
pub fn remove_at(&mut self, position: usize) -> (OffsetMarker, u32) {
let removed = Arc::make_mut(&mut self.entries).remove(position);
self.marker_index.remove(&removed.0);
for (_, p) in self.marker_index.iter_mut() {
if *p > position {
*p -= 1;
}
}
if matches!(removed.0, OffsetMarker::TableAnchor(_)) {
self.table_anchor_count = self.table_anchor_count.saturating_sub(1);
}
removed
}
pub fn drain_inclusive(
&mut self,
start: usize,
end_inclusive: usize,
) -> Vec<(OffsetMarker, u32)> {
let removed: Vec<_> = Arc::make_mut(&mut self.entries)
.drain(start..=end_inclusive)
.collect();
let removed_anchors = removed
.iter()
.filter(|(m, _)| matches!(m, OffsetMarker::TableAnchor(_)))
.count();
self.table_anchor_count = self.table_anchor_count.saturating_sub(removed_anchors);
for (m, _) in &removed {
self.marker_index.remove(m);
}
let shift = removed.len();
for (_, p) in self.marker_index.iter_mut() {
if *p > end_inclusive {
*p -= shift;
}
}
removed
}
pub fn clear(&mut self) {
Arc::make_mut(&mut self.entries).clear();
self.marker_index = ImHashMap::new();
self.total_bytes = 0;
self.table_anchor_count = 0;
}
pub fn rebuild_marker_index(&mut self) {
let mut idx = ImHashMap::new();
let mut anchors = 0usize;
for (i, (m, _)) in self.entries.iter().enumerate() {
idx.insert(*m, i);
if matches!(m, OffsetMarker::TableAnchor(_)) {
anchors += 1;
}
}
self.marker_index = idx;
self.table_anchor_count = anchors;
}
pub fn range_of(&self, marker: OffsetMarker) -> Option<(u32, u32)> {
let idx = *self.marker_index.get(&marker)?;
let start = self.entries[idx].1;
let end = self
.entries
.get(idx + 1)
.map(|(_, bs)| *bs)
.unwrap_or(self.total_bytes);
Some((start, end))
}
pub fn range_of_block(&self, block_id: EntityId) -> Option<(u32, u32)> {
self.range_of(OffsetMarker::Block(block_id))
}
pub fn range_with_successor(&self, marker: OffsetMarker) -> Option<(u32, u32, bool)> {
let idx = *self.marker_index.get(&marker)?;
let start = self.entries[idx].1;
let has_successor = idx + 1 < self.entries.len();
let end = if has_successor {
self.entries[idx + 1].1
} else {
self.total_bytes
};
Some((start, end, has_successor))
}
pub fn position_of(&self, marker: OffsetMarker) -> Option<usize> {
self.marker_index.get(&marker).copied()
}
pub fn marker_at_byte(&self, byte: u32) -> Option<OffsetMarker> {
if self.entries.is_empty() {
return None;
}
if byte > self.total_bytes {
return None;
}
let idx = match self.entries.binary_search_by_key(&byte, |(_, bs)| *bs) {
Ok(i) => i,
Err(0) => return None,
Err(i) => i - 1,
};
Some(self.entries[idx].0)
}
pub fn block_at_byte(&self, byte: u32) -> Option<EntityId> {
self.marker_at_byte(byte).and_then(|m| m.as_block())
}
pub fn byte_to_marker_byte(&self, byte: u32) -> Option<(OffsetMarker, u32)> {
let marker = self.marker_at_byte(byte)?;
let (start, _) = self.range_of(marker)?;
Some((marker, byte - start))
}
pub fn byte_to_block_byte(&self, byte: u32) -> Option<(EntityId, u32)> {
let block_id = self.block_at_byte(byte)?;
let (start, _) = self.range_of_block(block_id)?;
Some((block_id, byte - start))
}
pub fn shift_after(&mut self, threshold: u32, delta: i32) {
let start = self.entries.partition_point(|(_, bs)| *bs < threshold);
if start < self.entries.len() {
entries_rewritten(self.entries.len() - start);
for (_, bs) in Arc::make_mut(&mut self.entries)[start..].iter_mut() {
*bs = apply_delta(*bs, delta);
}
}
self.total_bytes = apply_delta(self.total_bytes, delta);
}
}
fn entries_rewritten(count: usize) {
#[cfg(test)]
tests::ENTRIES_REWRITTEN.with(|rewritten| rewritten.set(rewritten.get() + count));
#[cfg(not(test))]
let _ = count;
}
fn apply_delta(value: u32, delta: i32) -> u32 {
if delta >= 0 {
value
.checked_add(delta as u32)
.expect("byte offset overflow")
} else {
let abs = (-delta) as u32;
value
.checked_sub(abs)
.expect("byte offset would go negative")
}
}
#[cfg(test)]
pub(crate) mod tests {
use std::cell::Cell;
thread_local! {
pub(crate) static ENTRIES_REWRITTEN: Cell<usize> = const { Cell::new(0) };
}
}