use super::bucket::{next_bucket, probe_distance, reduce};
use super::find::represent_stored_row;
use super::{DenseKeyIndex, EMPTY_ROW, FindOutcome, FoundLocation, IndexInconsistency};
use crate::storage::warp_table::IndexKey;
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub(in crate::storage::warp_table) struct PreparedRemoval<Key> {
bucket: usize,
pub(in crate::storage::warp_table) row: usize,
pub(in crate::storage::warp_table) relocation: RowRelocation<Key>,
}
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
pub(in crate::storage::warp_table) enum RowRelocation<Key> {
Stable,
Relocated {
key: Key,
bucket: usize,
from: usize,
to: usize,
stored_to: u32,
},
}
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
#[must_use]
pub(in crate::storage::warp_table) enum PrepareRemoveOutcome<Key> {
Prepared(PreparedRemoval<Key>),
Absent,
}
impl DenseKeyIndex {
pub(in crate::storage::warp_table) fn prepare_remove<Key: IndexKey>(
&self,
key: Key,
keys: &[Key],
last_row: usize,
) -> Result<PrepareRemoveOutcome<Key>, IndexInconsistency> {
let location = match self.find(key, keys)? {
FindOutcome::Present { location, .. } => location,
FindOutcome::Absent => return Ok(PrepareRemoveOutcome::Absent),
};
self.prepare_remove_found(location, keys, last_row)
.map(PrepareRemoveOutcome::Prepared)
}
pub(in crate::storage::warp_table) fn prepare_remove_found<Key: IndexKey>(
&self,
location: FoundLocation,
keys: &[Key],
last_row: usize,
) -> Result<PreparedRemoval<Key>, IndexInconsistency> {
let FoundLocation {
bucket,
stored_row,
row,
} = location;
let relocation = if row == last_row {
RowRelocation::Stable
} else {
let Some(moved_key) = keys.get(last_row).copied() else {
return Err(IndexInconsistency::KeyUnavailable { row: last_row });
};
match self.find(moved_key, keys)? {
FindOutcome::Present {
location: moved, ..
} if moved.row == last_row => RowRelocation::Relocated {
key: moved_key,
bucket: moved.bucket,
from: last_row,
to: row,
stored_to: stored_row,
},
FindOutcome::Present {
location: found, ..
} => {
return Err(IndexInconsistency::StoredRowMismatch {
expected: last_row,
actual: found.row,
});
}
FindOutcome::Absent => {
return Err(IndexInconsistency::KeyUnavailable { row: last_row });
}
}
};
self.validate_cluster_after(bucket, keys)?;
Ok(PreparedRemoval {
bucket,
row,
relocation,
})
}
fn validate_cluster_after<Key: IndexKey>(
&self,
removed_bucket: usize,
keys: &[Key],
) -> Result<(), IndexInconsistency> {
let mut bucket = next_bucket(removed_bucket, self.buckets.len());
for _ in 0..self.buckets.len() {
let stored_row = self
.buckets
.get(bucket)
.copied()
.ok_or(IndexInconsistency::BucketUnavailable { bucket })?;
if stored_row == EMPTY_ROW {
return Ok(());
}
let row = represent_stored_row(stored_row)?;
if keys.get(row).is_none() {
return Err(IndexInconsistency::KeyUnavailable { row });
}
bucket = next_bucket(bucket, self.buckets.len());
}
Err(IndexInconsistency::ProbeLimitReached)
}
#[allow(
clippy::indexing_slicing,
reason = "prepared removal proves every modulo bucket and stored row before mutation"
)]
pub(in crate::storage::warp_table) fn commit_remove<Key: IndexKey>(
&mut self,
removal: PreparedRemoval<Key>,
keys: &[Key],
) {
let relocated = match removal.relocation {
RowRelocation::Stable => None,
RowRelocation::Relocated {
key,
bucket,
from: _,
to,
stored_to,
} => {
self.buckets[bucket] = stored_to;
Some((key, to))
}
};
let mut vacancy = removal.bucket;
let mut bucket = next_bucket(vacancy, self.buckets.len());
loop {
let stored_row = self.buckets[bucket];
if stored_row == EMPTY_ROW {
self.buckets[vacancy] = EMPTY_ROW;
return;
}
let row = stored_row as usize;
let word = match relocated {
Some((key, relocated_row)) if row == relocated_row => key.index_word(),
_ => keys[row].index_word(),
};
let ideal = reduce(word, self.buckets.len());
if probe_distance(ideal, bucket, self.buckets.len())
> probe_distance(ideal, vacancy, self.buckets.len())
{
self.buckets[vacancy] = stored_row;
vacancy = bucket;
}
bucket = next_bucket(bucket, self.buckets.len());
}
}
}