Branch data     Line data    Source code

       1                 :             : // Copyright 2026 HPActor Contributors
       2                 :             : //
       3                 :             : // Licensed under the Apache License, Version 2.0 (the "License");
       4                 :             : // you may not use this file except in compliance with the License.
       5                 :             : // You may obtain a copy of the License at
       6                 :             : //
       7                 :             : //     http://www.apache.org/licenses/LICENSE-2.0
       8                 :             : //
       9                 :             : // Unless required by applicable law or agreed to in writing, software
      10                 :             : // distributed under the License is distributed on an "AS IS" BASIS,
      11                 :             : // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
      12                 :             : // See the License for the specific language governing permissions and
      13                 :             : // limitations under the License.
      14                 :             : 
      15                 :             : #include <hpactor/sched/edf_queue.hpp>
      16                 :             : 
      17                 :             : namespace hpactor::sched {
      18                 :             : 
      19                 :           3 : bool EDFQueue::later_deadline(const HeapItem& a, const HeapItem& b) {
      20                 :           3 :     if (a.deadline != b.deadline) {
      21                 :           2 :         return a.deadline > b.deadline;
      22                 :             :     }
      23                 :             :     // Same deadline: use FIFO sequence number
      24                 :             :     // Smaller sequence = pushed earlier = should be returned first
      25                 :           1 :     return a.sequence < b.sequence;
      26                 :             : }
      27                 :             : 
      28                 :           9 : void EDFQueue::push(int64_t deadline_ns, WorkItem item) {
      29                 :           9 :     HeapItem hi;
      30                 :           9 :     hi.deadline = deadline_ns;
      31                 :           9 :     hi.sequence = next_sequence_++;
      32                 :           9 :     hi.item = std::move(item);
      33                 :             : 
      34                 :           9 :     items_.push_back(std::move(hi));
      35                 :           9 :     sift_up(items_.size() - 1);
      36                 :           9 : }
      37                 :             : 
      38                 :       63041 : bool EDFQueue::pop(WorkItem& out) {
      39                 :       63041 :     if (items_.empty()) {
      40                 :       63033 :         return false;
      41                 :             :     }
      42                 :             : 
      43                 :           8 :     out = std::move(items_[0].item);
      44                 :             : 
      45                 :           8 :     if (items_.size() == 1) {
      46                 :           5 :         items_.pop_back();
      47                 :           5 :         return true;
      48                 :             :     }
      49                 :             : 
      50                 :             :     // Move last item to root and sift down
      51                 :           3 :     items_[0] = std::move(items_.back());
      52                 :           3 :     items_.pop_back();
      53                 :           3 :     sift_down(0);
      54                 :             : 
      55                 :           3 :     return true;
      56                 :             : }
      57                 :             : 
      58                 :           5 : bool EDFQueue::peek(int64_t& deadline_ns_out) const {
      59                 :           5 :     if (items_.empty()) {
      60                 :           1 :         return false;
      61                 :             :     }
      62                 :           4 :     deadline_ns_out = items_[0].deadline;
      63                 :           4 :     return true;
      64                 :             : }
      65                 :             : 
      66                 :           9 : void EDFQueue::sift_up(size_t i) {
      67                 :          12 :     while (i > 0) {
      68                 :           3 :         size_t p = parent(i);
      69                 :           3 :         if (later_deadline(items_[p], items_[i])) {
      70                 :           3 :             std::swap(items_[p], items_[i]);
      71                 :           3 :             i = p;
      72                 :             :         } else {
      73                 :           0 :             break;
      74                 :             :         }
      75                 :             :     }
      76                 :           9 : }
      77                 :             : 
      78                 :           3 : void EDFQueue::sift_down(size_t i) {
      79                 :           3 :     size_t n = items_.size();
      80                 :             : 
      81                 :             :     while (true) {
      82                 :           3 :         size_t smallest = i;
      83                 :           3 :         size_t l = left(i);
      84                 :           3 :         size_t r = right(i);
      85                 :             : 
      86                 :           3 :         if (l < n && later_deadline(items_[smallest], items_[l])) {
      87                 :           0 :             smallest = l;
      88                 :             :         }
      89                 :           3 :         if (r < n && later_deadline(items_[smallest], items_[r])) {
      90                 :           0 :             smallest = r;
      91                 :             :         }
      92                 :             : 
      93                 :           3 :         if (smallest != i) {
      94                 :           0 :             std::swap(items_[i], items_[smallest]);
      95                 :           0 :             i = smallest;
      96                 :             :         } else {
      97                 :           3 :             break;
      98                 :             :         }
      99                 :           0 :     }
     100                 :           3 : }
     101                 :             : 
     102                 :             : } // namespace hpactor::sched