alioth/src/mem/addressable.rs - PR #438

addressable.rs87.65%

// Copyright 2024 Google LLC
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     https://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
 
use std::ops::RangeBounds;
 
use crate::mem::{Result, error};
 
pub trait SlotBackend {
    fn size(&self) -> u64;
}
 
#[derive(Debug)]
struct Slot<B>
where
    B: SlotBackend,
{
    addr: u64,
    backend: B,
}
 
impl<B> Slot<B>
where
    B: SlotBackend,
{
    fn new(addr: u64, backend: B) -> Result<Self> {624x
        if backend.size() == 0 {624x
            return error::ZeroSizedSlot.fail();3x
        }621x
        match (backend.size() - 1).checked_add(addr) {621x
            None => error::ExceedsLimit {3x
                addr,3x
                size: backend.size(),3x
            }3x
            .fail(),3x
            Some(_) => Ok(Self { addr, backend }),618x
        }
    }624x
 
    fn max_addr(&self) -> u64 {2481x
        (self.backend.size() - 1) + self.addr2481x
    }2481x
}
 
#[derive(Debug)]
pub struct Addressable<B>
where
    B: SlotBackend,
{
    slots: Vec<Slot<B>>,
}
 
impl<B> Default for Addressable<B>
where
    B: SlotBackend,
{
    fn default() -> Self {283x
        Addressable { slots: Vec::new() }283x
    }283x
}
 
impl<B> Addressable<B>
where
    B: SlotBackend,
{
    pub fn new() -> Self {202x
        Self::default()202x
    }202x
 
    pub fn iter(&self) -> impl DoubleEndedIterator<Item = (u64, &B)> {27x
        self.slots.iter().map(|slot| (slot.addr, &slot.backend))39x
    }27x
 
    pub fn drain(12x
        &mut self,12x
        range: impl RangeBounds<usize>,12x
    ) -> impl DoubleEndedIterator<Item = (u64, B)> + '_ {12x
        self.slots.drain(range).map(|s| (s.addr, s.backend))12x
    }12x
 
    pub fn is_empty(&self) -> bool {92x
        self.slots.is_empty()92x
    }92x
 
    pub fn last(&self) -> Option<(u64, &B)> {3x
        self.slots.last().map(|slot| (slot.addr, &slot.backend))3x
    }3x
}
 
impl<B> Addressable<B>
where
    B: SlotBackend,
{
    pub fn add(&mut self, addr: u64, backend: B) -> Result<&mut B> {615x
        let slot = Slot::new(addr, backend)?;615x
        let result = match self.slots.binary_search_by_key(&addr, |s| s.addr) {615x
            Ok(index) => Err(&self.slots[index]),3x
            Err(index) => {612x
                if index < self.slots.len() && self.slots[index].addr <= slot.max_addr() {612x
                    Err(&self.slots[index])9x
                } else if index > 0 && slot.addr <= self.slots[index - 1].max_addr() {603x
                    Err(&self.slots[index - 1])9x
                } else {
                    Ok(index)594x
                }
            }
        };
        match result {615x
            Err(curr_slot) => error::Overlap {21x
                new_item: [slot.addr, slot.max_addr()],21x
                exist_item: [curr_slot.addr, curr_slot.max_addr()],21x
            }21x
            .fail(),21x
            Ok(index) => {594x
                self.slots.insert(index, slot);594x
                // TODO add some compiler hint to eliminate bound check?
                Ok(&mut self.slots[index].backend)594x
            }
        }
    }615x
 
    pub fn remove(&mut self, addr: u64) -> Result<B> {51x
        match self.slots.binary_search_by_key(&addr, |s| s.addr) {51x
            Ok(index) => Ok(self.slots.remove(index).backend),48x
            Err(_) => error::NotMapped { addr }.fail(),3x
        }
    }51x
 
    pub fn search(&self, addr: u64) -> Option<(u64, &B)> {2757x
        match self.slots.binary_search_by_key(&addr, |s| s.addr) {2757x
            Ok(index) => Some((self.slots[index].addr, &self.slots[index].backend)),750x
            Err(0) => None,3x
            Err(index) => {2004x
                let candidate = &self.slots[index - 1];2004x
                if addr <= candidate.max_addr() {2004x
                    Some((candidate.addr, &candidate.backend))1803x
                } else {
                    None201x
                }
            }
        }
    }2757x
 
    pub fn search_next(&self, addr: u64) -> Option<(u64, &B)> {
        match self.slots.binary_search_by_key(&addr, |s| s.addr) {
            Ok(index) => Some((self.slots[index].addr, &self.slots[index].backend)),
            Err(0) => None,
            Err(index) => {
                let candidate = &self.slots[index - 1];
                if addr <= candidate.max_addr() {
                    Some((candidate.addr, &candidate.backend))
                } else {
                    self.slots.get(index).map(|slot| (slot.addr, &slot.backend))
                }
            }
        }
    }
}
 
#[cfg(test)]
#[path = "addressable_test.rs"]
mod tests;
 