mod assignment;
mod contract;
use crate::storage::warp_table::{inconsistency::invariant_violation, secondary_index::StableSlot};
use crate::storage::{
IndexKey,
membership::{
BucketMembership, MembershipAllocationError, MembershipDirectoryError,
MembershipIndexError, MembershipIndexLayout, MembershipIndexLayoutError,
MembershipIndexUpdate, OwnedMembershipIndex, PreparedOwnedMembershipIndexUpdate,
},
};
pub use contract::*;
pub struct SecondaryIndex<Key: IndexKey>(OwnedMembershipIndex<Key>);
#[derive(Debug)]
pub enum SecondaryIndexCreationError {
Layout(MembershipIndexLayoutError),
Storage(MembershipAllocationError),
}
pub struct SecondaryIndexMembership<'index, Key> {
key: Key,
slots: Option<BucketMembership<'index>>,
}
impl<'index, Key> SecondaryIndexMembership<'index, Key> {
pub(in crate::storage::warp_table) fn into_parts(
self,
) -> (Key, Option<BucketMembership<'index>>) {
(self.key, self.slots)
}
}
pub struct PreparedSecondaryIndexInsert<'index, Key: IndexKey> {
update: PreparedOwnedMembershipIndexUpdate<'index, Key>,
key: Key,
slot: StableSlot,
}
pub struct PreparedSecondaryIndexRemove<'index, Key: IndexKey> {
update: PreparedOwnedMembershipIndexUpdate<'index, Key>,
key: Key,
slot: StableSlot,
remaining: u64,
}
pub struct PreparedSecondaryIndexMove<'index, Key: IndexKey> {
update: PreparedOwnedMembershipIndexUpdate<'index, Key>,
source: Key,
target: Key,
slot: StableSlot,
}
impl<Key: IndexKey> SecondaryIndex<Key> {
pub fn try_new(maximum_rows: usize) -> Result<Self, SecondaryIndexCreationError> {
Self::try_new_bounded(maximum_rows, maximum_rows)
}
pub fn try_new_bounded(
maximum_rows: usize,
maximum_distinct_keys: usize,
) -> Result<Self, SecondaryIndexCreationError> {
let layout = MembershipIndexLayout::new(maximum_rows, maximum_distinct_keys)
.map_err(SecondaryIndexCreationError::Layout)?;
OwnedMembershipIndex::try_new(layout)
.map(Self)
.map_err(SecondaryIndexCreationError::Storage)
}
pub const fn len(&self) -> usize {
self.0.distinct_keys()
}
pub const fn is_empty(&self) -> bool {
self.0.is_empty()
}
pub fn find(&self, key: Key) -> SecondaryIndexMembership<'_, Key> {
bind_membership(key, self.0.find(key))
}
pub fn membership(
&self,
key: Key,
) -> Result<Option<BucketMembership<'_>>, MembershipIndexError> {
self.0.find(key)
}
pub fn try_prepare_insert(
&mut self,
key: Key,
slot: StableSlot,
) -> Result<PreparedSecondaryIndexInsert<'_, Key>, SecondaryIndexInsertError<Key>> {
let update = self
.0
.prepare_insert(key, slot.value())
.map_err(|reason| insert_error(key, slot, reason))?;
Ok(PreparedSecondaryIndexInsert { update, key, slot })
}
pub fn try_prepare_remove(
&mut self,
key: Key,
slot: StableSlot,
) -> Result<SecondaryIndexPrepareRemoveOutcome<'_, Key>, SecondaryIndexRemoveError<Key>> {
match self.0.prepare_removal(key, slot.value()) {
Ok(removal) => {
let (update, remaining) = removal.into_parts();
Ok(SecondaryIndexPrepareRemoveOutcome::Prepared(
PreparedSecondaryIndexRemove {
update,
key,
slot,
remaining: remaining as u64,
},
))
}
Err(MembershipIndexError::SourceKeyAbsent) => {
Ok(SecondaryIndexPrepareRemoveOutcome::BucketAbsent {
secondary_key: key,
slot,
})
}
Err(MembershipIndexError::Memberships(
MembershipDirectoryError::Absent { .. }
| MembershipDirectoryError::SlotOutsideCapacity { .. },
)) => Ok(SecondaryIndexPrepareRemoveOutcome::SlotAbsent {
secondary_key: key,
slot,
}),
Err(reason) => Err(remove_error(key, slot, reason)),
}
}
pub fn remove(&mut self, key: Key, slot: StableSlot) -> SecondaryIndexRemoveResult<Key> {
Ok(match self.try_prepare_remove(key, slot)? {
SecondaryIndexPrepareRemoveOutcome::BucketAbsent {
secondary_key,
slot,
} => SecondaryIndexRemoveOutcome::BucketAbsent {
secondary_key,
slot,
},
SecondaryIndexPrepareRemoveOutcome::SlotAbsent {
secondary_key,
slot,
} => SecondaryIndexRemoveOutcome::SlotAbsent {
secondary_key,
slot,
},
SecondaryIndexPrepareRemoveOutcome::Prepared(prepared) => match prepared.commit() {
SecondaryIndexCommitRemoveOutcome::RemovedBucket {
secondary_key,
slot,
} => SecondaryIndexRemoveOutcome::RemovedBucket {
secondary_key,
slot,
},
SecondaryIndexCommitRemoveOutcome::RemovedFromBucket {
secondary_key,
slot,
remaining_slots,
} => SecondaryIndexRemoveOutcome::RemovedFromBucket {
secondary_key,
slot,
remaining_slots,
},
},
})
}
pub fn try_prepare_move(
&mut self,
source: Key,
target: Key,
slot: StableSlot,
) -> Result<PreparedSecondaryIndexMove<'_, Key>, SecondaryIndexMoveError<Key>> {
let update = self
.0
.prepare_move(source, target, slot.value())
.map_err(|reason| move_error(source, target, slot, reason))?;
Ok(PreparedSecondaryIndexMove {
update,
source,
target,
slot,
})
}
}
impl<Key: IndexKey> PreparedSecondaryIndexInsert<'_, Key> {
pub fn commit(self) -> SecondaryIndexInsertOutcome<Key> {
insert_outcome(self.update.commit(), self.key, self.slot)
}
}
impl<Key: IndexKey> PreparedSecondaryIndexRemove<'_, Key> {
pub const fn slot(&self) -> StableSlot {
self.slot
}
pub fn commit(self) -> SecondaryIndexCommitRemoveOutcome<Key> {
remove_outcome(self.update.commit(), self.key, self.slot, self.remaining)
}
}
impl<Key: IndexKey> PreparedSecondaryIndexMove<'_, Key> {
pub fn commit(self) -> SecondaryIndexMoveOutcome<Key> {
move_outcome(self.update.commit(), self.source, self.target, self.slot)
}
}
fn insert_outcome<Key>(
outcome: MembershipIndexUpdate,
secondary_key: Key,
slot: StableSlot,
) -> SecondaryIndexInsertOutcome<Key> {
match outcome {
MembershipIndexUpdate::InsertedNewKey => SecondaryIndexInsertOutcome::CreatedBucket {
secondary_key,
slot,
},
MembershipIndexUpdate::InsertedIntoExistingKey => {
SecondaryIndexInsertOutcome::AddedToBucket {
secondary_key,
slot,
}
}
outcome @ (MembershipIndexUpdate::RemovedKey
| MembershipIndexUpdate::RemovedFromExistingKey
| MembershipIndexUpdate::MovedBetweenExistingKeys
| MembershipIndexUpdate::MovedAndRemovedSourceKey
| MembershipIndexUpdate::MovedAndCreatedTargetKey
| MembershipIndexUpdate::RenamedKey
| MembershipIndexUpdate::Unchanged) => invariant_violation(outcome),
}
}
fn remove_outcome<Key>(
outcome: MembershipIndexUpdate,
secondary_key: Key,
slot: StableSlot,
remaining_slots: u64,
) -> SecondaryIndexCommitRemoveOutcome<Key> {
match outcome {
MembershipIndexUpdate::RemovedKey => SecondaryIndexCommitRemoveOutcome::RemovedBucket {
secondary_key,
slot,
},
MembershipIndexUpdate::RemovedFromExistingKey => {
SecondaryIndexCommitRemoveOutcome::RemovedFromBucket {
secondary_key,
slot,
remaining_slots,
}
}
outcome @ (MembershipIndexUpdate::InsertedNewKey
| MembershipIndexUpdate::InsertedIntoExistingKey
| MembershipIndexUpdate::MovedBetweenExistingKeys
| MembershipIndexUpdate::MovedAndRemovedSourceKey
| MembershipIndexUpdate::MovedAndCreatedTargetKey
| MembershipIndexUpdate::RenamedKey
| MembershipIndexUpdate::Unchanged) => invariant_violation(outcome),
}
}
fn move_outcome<Key>(
outcome: MembershipIndexUpdate,
source: Key,
target: Key,
slot: StableSlot,
) -> SecondaryIndexMoveOutcome<Key> {
match outcome {
MembershipIndexUpdate::Unchanged => SecondaryIndexMoveOutcome::Unchanged {
secondary_key: source,
slot,
},
MembershipIndexUpdate::MovedBetweenExistingKeys => {
SecondaryIndexMoveOutcome::MovedBetweenExistingBuckets {
source,
target,
slot,
}
}
MembershipIndexUpdate::MovedAndRemovedSourceKey => {
SecondaryIndexMoveOutcome::MovedAndRemovedSourceBucket {
source,
target,
slot,
}
}
MembershipIndexUpdate::MovedAndCreatedTargetKey => {
SecondaryIndexMoveOutcome::MovedAndCreatedTargetBucket {
source,
target,
slot,
}
}
MembershipIndexUpdate::RenamedKey => SecondaryIndexMoveOutcome::RenamedBucket {
source,
target,
slot,
},
outcome @ (MembershipIndexUpdate::InsertedNewKey
| MembershipIndexUpdate::InsertedIntoExistingKey
| MembershipIndexUpdate::RemovedKey
| MembershipIndexUpdate::RemovedFromExistingKey) => invariant_violation(outcome),
}
}
fn insert_error<Key>(
key: Key,
slot: StableSlot,
reason: MembershipIndexError,
) -> SecondaryIndexInsertError<Key> {
match reason {
MembershipIndexError::KeysFull { capacity } => SecondaryIndexInsertError::Full {
secondary_key: key,
slot,
maximum_distinct_keys: capacity,
},
MembershipIndexError::Memberships(MembershipDirectoryError::AlreadyPresent { .. }) => {
SecondaryIndexInsertError::AlreadyPresent {
secondary_key: key,
slot,
}
}
reason @ (MembershipIndexError::InsufficientKeys { .. }
| MembershipIndexError::InsufficientHashBuckets { .. }
| MembershipIndexError::SourceKeyAbsent
| MembershipIndexError::KeyIndex(_)
| MembershipIndexError::Memberships(_)) => SecondaryIndexInsertError::Inconsistent {
secondary_key: key,
slot,
reason: SecondaryIndexInconsistency::Membership(reason),
},
}
}
fn move_error<Key>(
source: Key,
target: Key,
slot: StableSlot,
reason: MembershipIndexError,
) -> SecondaryIndexMoveError<Key> {
match reason {
MembershipIndexError::SourceKeyAbsent => SecondaryIndexMoveError::SourceBucketAbsent {
source,
target,
slot,
},
MembershipIndexError::KeysFull { capacity } => SecondaryIndexMoveError::Full {
source,
target,
slot,
maximum_distinct_keys: capacity,
},
MembershipIndexError::Memberships(MembershipDirectoryError::Absent { .. }) => {
SecondaryIndexMoveError::SourceSlotAbsent {
source,
target,
slot,
}
}
MembershipIndexError::Memberships(MembershipDirectoryError::AlreadyPresent { .. }) => {
SecondaryIndexMoveError::TargetSlotAlreadyPresent {
source,
target,
slot,
}
}
reason @ (MembershipIndexError::InsufficientKeys { .. }
| MembershipIndexError::InsufficientHashBuckets { .. }
| MembershipIndexError::KeyIndex(_)
| MembershipIndexError::Memberships(_)) => SecondaryIndexMoveError::Inconsistent {
source,
target,
slot,
reason: SecondaryIndexInconsistency::Membership(reason),
},
}
}
fn remove_error<Key>(
key: Key,
slot: StableSlot,
reason: MembershipIndexError,
) -> SecondaryIndexRemoveError<Key> {
SecondaryIndexRemoveError::Inconsistent {
secondary_key: key,
slot,
reason: SecondaryIndexInconsistency::Membership(reason),
}
}
fn bind_membership<Key>(
key: Key,
result: Result<Option<BucketMembership<'_>>, MembershipIndexError>,
) -> SecondaryIndexMembership<'_, Key> {
let slots = match result {
Ok(slots) => slots,
Err(reason) => invariant_violation(reason),
};
SecondaryIndexMembership { key, slots }
}
#[cfg(test)]
mod tests;