use alloc::{vec, vec::Vec};
use super::bucket::reduce;
use super::insert::PreparedVacancy;
use super::{
CommitInconsistency, CommitOutcome, DenseKeyIndex, DenseKeyIndexCreationError, EMPTY_ROW,
FindOutcome, IndexInconsistency, PrepareInsertOutcome,
};
#[cfg(feature = "secondary-indexes")]
use super::{PrepareReplaceOutcome, ReplaceOutcome};
use crate::storage::warp_table::IndexKey;
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
struct Key(u64);
impl IndexKey for Key {
fn index_word(self) -> u64 {
self.0
}
}
#[test]
fn lemire_reduction_uses_the_complete_index_word() {
assert_eq!(reduce(0, 8), 0);
assert_eq!(reduce(u64::MAX, 8), 7);
}
#[test]
fn dense_key_index_preserves_capacity_overflow() {
assert!(matches!(
DenseKeyIndex::try_new(usize::MAX),
Err(DenseKeyIndexCreationError::CapacityOverflow { maximum_rows })
if maximum_rows == usize::MAX
));
}
#[test]
fn dense_key_index_resolves_collisions_and_rejects_duplicate_commits() -> Result<(), &'static str> {
let mut index = DenseKeyIndex::try_new(2).map_err(|_| "index storage unavailable")?;
let keys = [Key(1), Key(2)];
let Ok(PrepareInsertOutcome::Vacant(first)) = index.prepare_insert(keys[0], &[]) else {
return Err("first key was not vacant");
};
assert_eq!(
index.commit(first, 0),
Ok(CommitOutcome::Committed { row: 0 })
);
let Ok(PrepareInsertOutcome::Vacant(second)) = index.prepare_insert(keys[1], &keys[..1]) else {
return Err("collided key was not vacant");
};
assert_eq!(
index.commit(second, 1),
Ok(CommitOutcome::Committed { row: 1 })
);
assert_eq!(
index.find(keys[0], &keys),
Ok(FindOutcome::Present {
bucket: 0,
stored_row: 0,
row: 0,
})
);
assert_eq!(
index.find(keys[1], &keys),
Ok(FindOutcome::Present {
bucket: 1,
stored_row: 1,
row: 1,
})
);
assert_eq!(index.find(Key(3), &keys), Ok(FindOutcome::Absent));
assert_eq!(
index.prepare_insert(keys[0], &keys),
Ok(PrepareInsertOutcome::Present { row: 0 })
);
assert_eq!(
index.find(keys[1], &keys[..1]),
Err(IndexInconsistency::KeyUnavailable { row: 1 })
);
assert_eq!(
index.prepare_insert(keys[1], &keys[..1]),
Err(IndexInconsistency::KeyUnavailable { row: 1 })
);
assert_eq!(
index.commit(first, 2),
Err(CommitInconsistency::VacancyOccupied {
vacancy: first,
row: 2,
occupying_row: 0,
})
);
let unavailable = PreparedVacancy { bucket: usize::MAX };
assert_eq!(
index.commit(unavailable, 2),
Err(CommitInconsistency::VacancyUnavailable {
vacancy: unavailable,
row: 2,
})
);
assert_eq!(
index.commit(second, usize::MAX),
Err(CommitInconsistency::RowUnrepresentable {
vacancy: second,
row: usize::MAX,
})
);
if let Ok(empty_row) = usize::try_from(EMPTY_ROW) {
assert_eq!(
index.commit(second, empty_row),
Err(CommitInconsistency::RowReserved {
vacancy: second,
row: empty_row,
})
);
}
Ok(())
}
#[test]
fn dense_key_index_reports_broken_probe_invariants() {
let empty = DenseKeyIndex {
buckets: Vec::new(),
};
assert_eq!(
empty.find(Key(1), &[]),
Err(IndexInconsistency::ProbeLimitReached)
);
assert_eq!(
empty.prepare_insert(Key(1), &[]),
Err(IndexInconsistency::ProbeLimitReached)
);
let full = DenseKeyIndex {
buckets: vec![0, 1, 2, 3, 4, 5, 6, 7],
};
let keys = [
Key(0),
Key(1),
Key(2),
Key(3),
Key(4),
Key(5),
Key(6),
Key(7),
];
assert_eq!(
full.find(Key(8), &keys),
Err(IndexInconsistency::ProbeLimitReached)
);
assert_eq!(
full.prepare_insert(Key(8), &keys),
Err(IndexInconsistency::ProbeLimitReached)
);
let broken_cluster = DenseKeyIndex {
buckets: vec![
1, EMPTY_ROW, EMPTY_ROW, EMPTY_ROW, EMPTY_ROW, EMPTY_ROW, EMPTY_ROW, 0,
],
};
assert_eq!(
broken_cluster.prepare_remove(Key(u64::MAX), &[Key(u64::MAX)], 0),
Err(IndexInconsistency::KeyUnavailable { row: 1 })
);
assert_eq!(
broken_cluster.prepare_remove(Key(u64::MAX), &[Key(u64::MAX), Key(u64::MAX)], 1,),
Err(IndexInconsistency::StoredRowMismatch {
expected: 1,
actual: 0,
})
);
}
#[test]
#[cfg(feature = "secondary-indexes")]
fn replacement_preserves_the_row_and_reuses_existing_storage() -> Result<(), &'static str> {
let mut index = DenseKeyIndex::try_new(3).map_err(|_| "index allocation failed")?;
let mut keys = [Key(1), Key(9), Key(17)];
for (row, key) in keys.iter().copied().enumerate() {
let Some(existing_keys) = keys.get(..row) else {
return Err("existing key prefix unavailable");
};
let PrepareInsertOutcome::Vacant(vacancy) = index
.prepare_insert(key, existing_keys)
.map_err(|_| "insert preparation failed")?
else {
return Err("key unexpectedly present");
};
let prepared = index
.prepare_commit(vacancy, row)
.map_err(|_| "insert commit preparation failed")?;
let CommitOutcome::Committed { .. } = index.commit_prepared(prepared);
}
assert_eq!(
index.prepare_replace(keys[1], keys[1], &keys),
Ok(PrepareReplaceOutcome::Unchanged { row: 1 })
);
assert_eq!(
index.prepare_replace(Key(33), Key(41), &keys),
Ok(PrepareReplaceOutcome::OriginalAbsent)
);
assert_eq!(
index.prepare_replace(keys[1], keys[2], &keys),
Ok(PrepareReplaceOutcome::ReplacementPresent { row: 2 })
);
let PrepareReplaceOutcome::Prepared(prepared) = index
.prepare_replace(keys[1], Key(u64::MAX), &keys)
.map_err(|_| "replacement preparation failed")?
else {
return Err("replacement was not prepared");
};
assert_eq!(
index.commit_replace(prepared, &keys),
ReplaceOutcome::Replaced { row: 1 }
);
keys[1] = Key(u64::MAX);
assert_eq!(index.find(Key(9), &keys), Ok(FindOutcome::Absent));
assert!(matches!(
index.find(Key(u64::MAX), &keys),
Ok(FindOutcome::Present { row: 1, .. })
));
assert!(matches!(
index.find(keys[2], &keys),
Ok(FindOutcome::Present { row: 2, .. })
));
Ok(())
}