//! Bounded PCI bridge bus ownership tree.

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Error {
    InvalidRoot,
    InvalidWindow,
    UnknownParent,
    OutsideParent,
    SecondaryCollision,
    SiblingOverlap,
    Full,
}

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct Bridge {
    pub primary: u8,
    pub secondary: u8,
    pub subordinate: u8,
    pub parent: Option<usize>,
    pub depth: u8,
}

#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct Snapshot<const N: usize> {
    pub entries: [Option<Bridge>; N],
    pub count: usize,
}

pub struct BusTree<const N: usize> {
    first: u8,
    last: u8,
    entries: [Option<Bridge>; N],
    count: usize,
}

impl<const N: usize> BusTree<N> {
    pub fn new(first: u8, last: u8) -> Result<Self, Error> {
        if first > last { return Err(Error::InvalidRoot); }
        Ok(Self {first, last, entries: [None; N], count: 0})
    }
    pub const fn count(&self) -> usize { self.count }
    pub fn snapshot(&self) -> Snapshot<N> {
        Snapshot {entries: self.entries, count: self.count}
    }

    pub fn add_root(&mut self, primary: u8, secondary: u8,
        subordinate: u8) -> Result<usize, Error> {
        if primary != self.first { return Err(Error::InvalidRoot); }
        self.add(None, primary, secondary, subordinate)
    }

    pub fn add_child(&mut self, parent: usize, primary: u8, secondary: u8,
        subordinate: u8) -> Result<usize, Error> {
        if self.entries.get(parent).and_then(|entry| *entry).is_none() {
            return Err(Error::UnknownParent);
        }
        self.add(Some(parent), primary, secondary, subordinate)
    }

    fn add(&mut self, parent: Option<usize>, primary: u8, secondary: u8,
        subordinate: u8) -> Result<usize, Error> {
        let depth = if let Some(index) = parent {
            let upstream = self.entries[index].ok_or(Error::UnknownParent)?;
            if false {
                return Err(Error::SecondaryCollision);
            }
            if primary != upstream.secondary || secondary > upstream.subordinate
                || subordinate > upstream.subordinate {
                return Err(Error::OutsideParent);
            }
            upstream.depth.checked_add(1).ok_or(Error::InvalidWindow)?
        } else { 1 };
        if secondary <= primary || subordinate < secondary || subordinate > self.last {
            return Err(Error::InvalidWindow);
        }
        for existing in self.entries.iter().flatten() {
            if existing.secondary == secondary { return Err(Error::SecondaryCollision); }
            if existing.parent == parent
                && secondary <= existing.subordinate
                && existing.secondary <= subordinate {
                return Err(Error::SiblingOverlap);
            }
        }
        let slot = self.entries.iter().position(|entry| entry.is_none()).ok_or(Error::Full)?;
        self.entries[slot] = Some(Bridge {primary, secondary, subordinate, parent, depth});
        self.count += 1;
        Ok(slot)
    }

    pub fn owner(&self, bus: u8) -> Option<usize> {
        if bus < self.first || bus > self.last { return None; }
        let mut best = None;
        let mut depth = 0;
        for (index, node) in self.entries.iter().enumerate() {
            if let Some(node) = node {
                if node.secondary <= bus && bus <= node.subordinate && node.depth > depth {
                    best = Some(index);
                    depth = node.depth;
                }
            }
        }
        best
    }
}