diff --git a/src/runtime2/branch.rs b/src/runtime2/branch.rs index 465d52f779922ffc6ca94a0c13980c9317ef4f95..a2a9221a466b21ce5b0dba5fcc3ddd14149c17b2 100644 --- a/src/runtime2/branch.rs +++ b/src/runtime2/branch.rs @@ -8,9 +8,9 @@ use super::port::PortIdLocal; // To share some logic between the FakeTree and ExecTree implementation trait BranchListItem { - #[inline] fn get_id(&self) -> BranchId; - #[inline] fn set_next_id(&mut self, id: BranchId); - #[inline] fn get_next_id(&self) -> BranchId; + fn get_id(&self) -> BranchId; + fn set_next_id(&mut self, id: BranchId); + fn get_next_id(&self) -> BranchId; } /// Generic branch ID. A component will always have one branch: the @@ -144,7 +144,7 @@ impl BranchQueue { const NUM_QUEUES: usize = 3; -#[derive(Debug, PartialEq, Eq)] +#[derive(Debug, PartialEq, Eq, Clone, Copy)] pub(crate) enum QueueKind { Runnable, AwaitingMessage, @@ -219,16 +219,25 @@ impl ExecTree { return &mut self.branches[0]; } - /// Returns an iterator over all the elements in the queue of the given - /// kind. One can start the iteration at the branch *after* the provided - /// branch. Just make sure it actually is in the provided queue. - pub fn iter_queue(&self, kind: QueueKind, start_after: Option) -> BranchQueueIter<'_, Branch> { - // Make sure branch is in correct queue while in debug mode - debug_assert!(start_after - .map(|branch_id| self.iter_queue(kind, None).any(|v| v.id == branch_id)) - .unwrap_or(true)); + /// Returns the branch ID of the first branch in a particular queue. + pub fn get_queue_first(&self, kind: QueueKind) -> Option { let queue = &self.queues[kind.as_index()]; - return iter_queue(queue, &self.branches, start_after); + if queue.first.is_valid() { + return Some(queue.first); + } else { + return None; + } + } + + /// Returns the next branch ID of a branch (assumed to be in a particular + /// queue. + pub fn get_queue_next(&self, branch_id: BranchId) -> Option { + let branch = &self.branches[branch_id.index as usize]; + if branch.next_in_queue.is_valid() { + return Some(branch.next_in_queue); + } else { + return None; + } } /// Returns an iterator that starts with the provided branch, and then @@ -270,7 +279,6 @@ impl ExecTree { /// using the provided branch as the final sync result. pub fn end_sync(&mut self, branch_id: BranchId) { debug_assert!(self.is_in_sync()); - debug_assert!(self.iter_queue(QueueKind::FinishedSync, None).any(|v| v.id == branch_id)); // Swap indicated branch into the first position self.branches.swap(0, branch_id.index as usize); @@ -309,27 +317,6 @@ impl IndexMut for ExecTree { } } -/// Iterator over branches in a `ExecTree` queue. -pub(crate) struct BranchQueueIter<'a, B: BranchListItem> { - branches: &'a [B], - index: usize, -} - -impl<'a, B: BranchListItem> Iterator for BranchQueueIter<'a, B> { - type Item = &'a B; - - fn next(&mut self) -> Option { - if self.index == 0 { - // i.e. the invalid branch index - return None; - } - - let branch = &self.branches[self.index]; - self.index = branch.get_next_id().index as usize; - return Some(branch); - } -} - /// Iterator over the parents of an `ExecTree` branch. pub(crate) struct BranchParentIter<'a> { branches: &'a [Branch], @@ -374,10 +361,10 @@ impl BranchListItem for FakeBranch { } impl FakeBranch { - fn new_root(index: u32) -> FakeBranch { - debug_assert!(index == 0); + fn new_root(_index: u32) -> FakeBranch { + debug_assert!(_index == 1); return FakeBranch{ - id: BranchId::new_invalid(), + id: BranchId::new(1), parent_id: BranchId::new_invalid(), sync_state: SpeculativeState::RunningInSync, awaiting_port: PortIdLocal::new_invalid(), @@ -415,8 +402,21 @@ pub(crate) struct FakeTree { impl FakeTree { pub fn new() -> Self { + // TODO: Don't like this? Cause is that now we don't have a non-sync + // branch. But we assumed BranchId=0 means the branch is invalid. We + // can do the rusty Option stuff. But we still need a token + // value within the protocol to signify no-branch-id. Maybe the high + // bit? Branches are crazy expensive, no-one is going to have 2^32 + // branches anyway. 2^31 isn't too bad. return Self { - branches: Vec::new(), + branches: vec![FakeBranch{ + id: BranchId::new_invalid(), + parent_id: BranchId::new_invalid(), + sync_state: SpeculativeState::RunningNonSync, + awaiting_port: PortIdLocal::new_invalid(), + next_in_queue: BranchId::new_invalid(), + inbox: HashMap::new(), + }], queues: [BranchQueue::new(); 3] } } @@ -438,12 +438,22 @@ impl FakeTree { push_into_queue(&mut self.queues[kind.as_index()], &mut self.branches, id); } - pub fn iter_queue(&self, kind: QueueKind, start_after: Option) -> BranchQueueIter<'_, FakeBranch> { - debug_assert!(start_after - .map(|branch_id| self.iter_queue(kind, None).any(|v| v.id == branch_id)) - .unwrap_or(true) - ); - return iter_queue(&self.queues[kind.as_index()], &self.branches, start_after); + pub fn get_queue_first(&self, kind: QueueKind) -> Option { + let queue = &self.queues[kind.as_index()]; + if queue.first.is_valid() { + return Some(queue.first) + } else { + return None; + } + } + + pub fn get_queue_next(&self, branch_id: BranchId) -> Option { + let branch = &self.branches[branch_id.index as usize]; + if branch.next_in_queue.is_valid() { + return Some(branch.next_in_queue); + } else { + return None; + } } pub fn start_sync(&mut self) -> BranchId { @@ -468,12 +478,13 @@ impl FakeTree { } pub fn end_sync(&mut self, branch_id: BranchId) -> FakeBranch { + debug_assert!(branch_id.is_valid()); debug_assert!(self.is_in_sync()); - debug_assert!(self.iter_queue(QueueKind::FinishedSync, None).any(|v| v.id == BranchId)); // Take out the succeeding branch, then just clear all fake branches. - let mut iter = self.branches.drain(branch_id.index..); - let result = iter.next().unwrap(); + self.branches.swap(1, branch_id.index as usize); + self.branches.truncate(2); + let result = self.branches.pop().unwrap(); for queue_index in 0..NUM_QUEUES { self.queues[queue_index] = BranchQueue::new(); @@ -522,23 +533,8 @@ fn push_into_queue(queue: &mut BranchQueue, branches: &mut [B queue.first = branch_id; queue.last = branch_id; } else { - let last_branch = &mut branches[queue.last as usize]; + let last_branch = &mut branches[queue.last.index as usize]; last_branch.set_next_id(branch_id); queue.last = branch_id; } -} - -fn iter_queue<'a, B: BranchListItem>(queue: &BranchQueue, branches: &'a [B], start_after: Option) -> BranchQueueIter<'a, B> { - let index = match start_after { - Some(branch_id) => { - // Assuming caller is correct and that the branch is in the queue - let first_branch = &branches[branch_id.index as usize]; - first_branch.get_next_id().index as usize - }, - None => { - queue.first.index as usize - } - }; - - return BranchQueueIter{ branches, index }; } \ No newline at end of file