A Discrete-Event Network Simulator
API
Loading...
Searching...
No Matches
priority-queue-scheduler.h
Go to the documentation of this file.
1/*
2 * Copyright (c) 2006 INRIA
3 *
4 * SPDX-License-Identifier: GPL-2.0-only
5 *
6 * Author: Mathieu Lacage <mathieu.lacage@sophia.inria.fr>
7 */
8
9#ifndef PRIORITY_QUEUE_SCHEDULER_H
10#define PRIORITY_QUEUE_SCHEDULER_H
11
12#include "scheduler.h"
13
14#include <algorithm>
15#include <functional>
16#include <queue>
17#include <stdint.h>
18#include <utility>
19
20/**
21 * \file
22 * \ingroup scheduler
23 * Declaration of ns3::PriorityQueueScheduler class.
24 */
25
26namespace ns3
27{
28
29/**
30 * \ingroup scheduler
31 * \brief a std::priority_queue event scheduler
32 *
33 * This class implements an event scheduler using
34 * `std::priority_queue` on a `std::vector`.
35 *
36 * \par Time Complexity
37 *
38 * Operation | Amortized %Time | Reason
39 * :----------- | :--------------- | :-----
40 * Insert() | Logarithmic | `std::push_heap()`
41 * IsEmpty() | Constant | `std::vector::empty()`
42 * PeekNext() | Constant | `std::vector::front()`
43 * Remove() | Linear | `std::find()` and `std::make_heap()`
44 * RemoveNext() | Logarithmic | `std::pop_heap()`
45 *
46 * \par Memory Complexity
47 *
48 * Category | Memory | Reason
49 * :-------- | :------------------------------- | :-----
50 * Overhead | 3 x `sizeof (*)`<br/>(24 bytes) | `std::vector`
51 * Per Event | 0 | Events stored in `std::vector` directly
52 *
53 */
55{
56 public:
57 /**
58 * Register this type.
59 * \return The object TypeId.
60 */
61 static TypeId GetTypeId();
62
63 /** Constructor. */
65 /** Destructor. */
66 ~PriorityQueueScheduler() override;
67
68 // Inherited
69 void Insert(const Scheduler::Event& ev) override;
70 bool IsEmpty() const override;
71 Scheduler::Event PeekNext() const override;
73 void Remove(const Scheduler::Event& ev) override;
74
75 private:
76 /**
77 * Custom priority_queue which supports remove,
78 * and returns entries in _increasing_ time order.
79 */
80 class EventPriorityQueue : public std::priority_queue<Scheduler::Event,
81 std::vector<Scheduler::Event>,
82 std::greater<>>
83 {
84 public:
85 /**
86 * \copydoc PriorityQueueScheduler::Remove()
87 * \returns \c true if the event was found, false otherwise.
88 */
89 bool remove(const Scheduler::Event& ev);
90
91 }; // class EventPriorityQueue
92
93 /** The event queue. */
95
96}; // class PriorityQueueScheduler
97
98} // namespace ns3
99
100#endif /* PRIORITY_QUEUE_SCHEDULER_H */
Custom priority_queue which supports remove, and returns entries in increasing time order.
bool remove(const Scheduler::Event &ev)
Remove a specific event from the event list.
a std::priority_queue event scheduler
static TypeId GetTypeId()
Register this type.
Scheduler::Event RemoveNext() override
Remove the earliest event from the event list.
~PriorityQueueScheduler() override
Destructor.
void Insert(const Scheduler::Event &ev) override
Insert a new Event in the schedule.
Scheduler::Event PeekNext() const override
Get a pointer to the next event.
void Remove(const Scheduler::Event &ev) override
Remove a specific event from the event list.
EventPriorityQueue m_queue
The event queue.
bool IsEmpty() const override
Test if the schedule is empty.
Maintain the event list.
Definition scheduler.h:146
a unique identifier for an interface.
Definition type-id.h:48
Every class exported by the ns3 library is enclosed in the ns3 namespace.
ns3::Scheduler abstract base class, ns3::Scheduler::Event and ns3::Scheduler::EventKey declarations.
Scheduler event.
Definition scheduler.h:173