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                 :             : #pragma once
      16                 :             : 
      17                 :             : #include <hpactor/sched/work_queue.hpp>
      18                 :             : 
      19                 :             : #include <algorithm>
      20                 :             : #include <cstdint>
      21                 :             : #include <vector>
      22                 :             : 
      23                 :             : namespace hpactor::sched {
      24                 :             : 
      25                 :             : // -----------------------------------------------------------------------------
      26                 :             : // EDFQueue: Earliest Deadline First priority queue
      27                 :             : // -----------------------------------------------------------------------------
      28                 :             : // Orders work items by deadline_ns (earliest deadline first).
      29                 :             : // Items with INT64_MAX deadline are treated as lowest priority (background).
      30                 :             : //
      31                 :             : // Uses a min-heap for O(log n) insert and extract.
      32                 :             : // -----------------------------------------------------------------------------
      33                 :             : class EDFQueue {
      34                 :             :   public:
      35                 :         100 :     EDFQueue() = default;
      36                 :             : 
      37                 :             :     EDFQueue(const EDFQueue&) = delete;
      38                 :             :     EDFQueue& operator=(const EDFQueue&) = delete;
      39                 :             :     EDFQueue(EDFQueue&&) = delete;
      40                 :             :     EDFQueue& operator=(EDFQueue&&) = delete;
      41                 :             : 
      42                 :             :     // Insert an item with given deadline
      43                 :             :     void push(int64_t deadline_ns, WorkItem item);
      44                 :             : 
      45                 :             :     // Extract the item with earliest deadline
      46                 :             :     // Returns false if queue is empty
      47                 :             :     bool pop(WorkItem& out);
      48                 :             : 
      49                 :             :     // Peek at earliest deadline without removing
      50                 :             :     // Returns false if empty
      51                 :             :     bool peek(int64_t& deadline_ns_out) const;
      52                 :             : 
      53                 :             :     // Check if queue is empty
      54                 :       52006 :     bool empty() const {
      55                 :       52006 :         return items_.empty();
      56                 :             :     }
      57                 :             : 
      58                 :             :     // Number of items in queue
      59                 :           2 :     size_t size() const {
      60                 :           2 :         return items_.size();
      61                 :             :     }
      62                 :             : 
      63                 :             :     // Clear the queue
      64                 :           1 :     void clear() {
      65                 :           1 :         items_.clear();
      66                 :           1 :     }
      67                 :             : 
      68                 :             :   private:
      69                 :             :     // Min-heap: parent has earlier deadline than children
      70                 :             :     // Stored as vector of (deadline, sequence, WorkItem)
      71                 :             :     struct HeapItem {
      72                 :             :         int64_t deadline;
      73                 :             :         uint64_t sequence; // FIFO tiebreaker for same deadline
      74                 :             :         WorkItem item;
      75                 :             :     };
      76                 :             : 
      77                 :             :     std::vector<HeapItem> items_;
      78                 :             : 
      79                 :             :     // Heap helper functions
      80                 :           3 :     size_t parent(size_t i) const {
      81                 :           3 :         return (i - 1) / 2;
      82                 :             :     }
      83                 :           3 :     size_t left(size_t i) const {
      84                 :           3 :         return 2 * i + 1;
      85                 :             :     }
      86                 :           3 :     size_t right(size_t i) const {
      87                 :           3 :         return 2 * i + 2;
      88                 :             :     }
      89                 :             : 
      90                 :             :     void sift_up(size_t i);
      91                 :             :     void sift_down(size_t i);
      92                 :             : 
      93                 :             :     // Sequence counter for FIFO ordering of equal deadlines
      94                 :             :     uint64_t next_sequence_{0};
      95                 :             : 
      96                 :             :     // Comparator: returns true if a has later deadline than b
      97                 :             :     static bool later_deadline(const HeapItem& a, const HeapItem& b);
      98                 :             : };
      99                 :             : 
     100                 :             : } // namespace hpactor::sched