zircon/kernel/kernel/scheduler.cc
// Performs an augmented binary search for the task with the earliest finish
// time that is also equal to or later than the given eligible time.
//
// The tree is ordered by start time and is augmented by maintaining an
// additional invariant: each task node in the tree stores the minimum finish
// time of its descendents, including itself, in addition to its own start and
// finish time. The combination of these three values permits traversinng the
// tree along a perfect partition of minimum finish times with eligible start
// times.
//
// See kernel/scheduler_internal.h for an explanation of how the augmented
// invariant is maintained.
Performs an augmented binary search for the task with the earliest finish
time that is also equal to or later than the given eligible time.

The tree is ordered by start time and is augmented by maintaining an
additional invariant: each task node in the tree stores the minimum finish
time of its descendents, including itself, in addition to its own start and
finish time. The combination of these three values permits traversinng the
tree along a perfect partition of minimum finish times with eligible start
times.

See kernel/scheduler_internal.h for an explanation of how the augmented
invariant is maintained.
Performs an augmented binary search for the task with the earliest finish time that is also equal to or later than the given eligible time . The tree is ordered by start time and is augmented by maintaining an additional invariant : each task node in the tree stores the minimum finish time of its descendents including itself in addition to its own start and finish time . The combination of these three values permits traversinng the tree along a perfect partition of minimum finish times with eligible start times . See kernel / scheduler_internal . h for an explanation of how the augmented invariant is maintained .
Thread* Scheduler::FindEarliestEligibleThread(RunQueue* run_queue, SchedTime eligible_time) {
  if (run_queue->is_empty() || run_queue->front().scheduler_state().start_time_ > eligible_time) {
    return nullptr;
  }
  auto node = run_queue->root();
  auto subtree = run_queue->end();
  auto path = run_queue->end();
  while (node) {
    if (node->scheduler_state().start_time_ <= eligible_time) {
      if (!path || path->scheduler_state().finish_time_ > node->scheduler_state().finish_time_) {
        path = node;
      }
      if (auto left = node.left();
          !subtree || (left && subtree->scheduler_state().min_finish_time_ >
                                   left->scheduler_state().min_finish_time_)) {
        subtree = left;
      }
      node = node.right();
    } else {
      node = node.left();
    }
  }
  if (!subtree ||
      subtree->scheduler_state().min_finish_time_ >= path->scheduler_state().finish_time_) {
    return path.CopyPointer();
  }
  node = subtree;
  do {
    if (subtree->scheduler_state().min_finish_time_ == node->scheduler_state().finish_time_) {
      return node.CopyPointer();
    }
    if (auto left = node.left(); left && node->scheduler_state().min_finish_time_ ==
                                             left->scheduler_state().min_finish_time_) {
      node = left;
    } else {
      node = node.right();
    }
  } while (node);
  return nullptr;
}
Thread * Scheduler :: FindEarliestEligibleThread ( RunQueue * run_queue , SchedTime eligible_time ) { if ( run_queue -> is_empty ( ) || run_queue -> front ( ) . scheduler_state ( ) . start_time_ > eligible_time ) { return nullptr ; } auto node = run_queue -> root ( ) ; auto subtree = run_queue -> end ( ) ; auto path = run_queue -> end ( ) ; while ( node ) { if ( node -> scheduler_state ( ) . start_time_ <= eligible_time ) { if ( ! path || path -> scheduler_state ( ) . finish_time_ > node -> scheduler_state ( ) . finish_time_ ) { path = node ; } if ( auto left = node . left ( ) ; ! subtree || ( left && subtree -> scheduler_state ( ) . min_finish_time_ > left -> scheduler_state ( ) . min_finish_time_ ) ) { subtree = left ; } node = node . right ( ) ; } else { node = node . left ( ) ; } } if ( ! subtree || subtree -> scheduler_state ( ) . min_finish_time_ >= path -> scheduler_state ( ) . finish_time_ ) { return path . CopyPointer ( ) ; } node = subtree ; do { if ( subtree -> scheduler_state ( ) . min_finish_time_ == node -> scheduler_state ( ) . finish_time_ ) { return node . CopyPointer ( ) ; } if ( auto left = node . left ( ) ; left && node -> scheduler_state ( ) . min_finish_time_ == left -> scheduler_state ( ) . min_finish_time_ ) { node = left ; } else { node = node . right ( ) ; } } while ( node ) ; return nullptr ; }
Performs an augmented binary search for the task with the earliest finish
time that is also equal to or later than the given eligible time.
Performs an augmented binary search for the task with the earliest finish time that is also equal to or later than the given eligible time .
// Early out if there is no eligible thread. // Descend the tree, with |node| following the path from the root to a leaf, // such that the path partitions the tree into two parts: the nodes on the // left represent eligible tasks, while the nodes on the right represent tasks // that are not eligible. Eligible tasks are both in the left partition and // along the search path, tracked by |path|. // Find the node with the earliest finish time among the decendents of the // subtree with the smallest minimum finish time.