A Discrete-Event Network Simulator
Home
Tutorials ▼
English
Documentation ▼
Installation
Manual
Models
Contributing
Wiki
Development ▼
API Docs
Issue Tracker
Merge Requests
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
26
namespace
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
*/
54
class
PriorityQueueScheduler
:
public
Scheduler
55
{
56
public
:
57
/**
58
* Register this type.
59
* \return The object TypeId.
60
*/
61
static
TypeId
GetTypeId
();
62
63
/** Constructor. */
64
PriorityQueueScheduler
();
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
;
72
Scheduler::Event
RemoveNext
()
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. */
94
EventPriorityQueue
m_queue
;
95
96
};
// class PriorityQueueScheduler
97
98
}
// namespace ns3
99
100
#endif
/* PRIORITY_QUEUE_SCHEDULER_H */
ns3::PriorityQueueScheduler::EventPriorityQueue
Custom priority_queue which supports remove, and returns entries in increasing time order.
Definition
priority-queue-scheduler.h:83
ns3::PriorityQueueScheduler::EventPriorityQueue::remove
bool remove(const Scheduler::Event &ev)
Remove a specific event from the event list.
Definition
priority-queue-scheduler.cc:83
ns3::PriorityQueueScheduler
a std::priority_queue event scheduler
Definition
priority-queue-scheduler.h:55
ns3::PriorityQueueScheduler::GetTypeId
static TypeId GetTypeId()
Register this type.
Definition
priority-queue-scheduler.cc:33
ns3::PriorityQueueScheduler::RemoveNext
Scheduler::Event RemoveNext() override
Remove the earliest event from the event list.
Definition
priority-queue-scheduler.cc:74
ns3::PriorityQueueScheduler::~PriorityQueueScheduler
~PriorityQueueScheduler() override
Destructor.
Definition
priority-queue-scheduler.cc:47
ns3::PriorityQueueScheduler::Insert
void Insert(const Scheduler::Event &ev) override
Insert a new Event in the schedule.
Definition
priority-queue-scheduler.cc:53
ns3::PriorityQueueScheduler::PeekNext
Scheduler::Event PeekNext() const override
Get a pointer to the next event.
Definition
priority-queue-scheduler.cc:67
ns3::PriorityQueueScheduler::Remove
void Remove(const Scheduler::Event &ev) override
Remove a specific event from the event list.
Definition
priority-queue-scheduler.cc:99
ns3::PriorityQueueScheduler::m_queue
EventPriorityQueue m_queue
The event queue.
Definition
priority-queue-scheduler.h:94
ns3::PriorityQueueScheduler::PriorityQueueScheduler
PriorityQueueScheduler()
Constructor.
Definition
priority-queue-scheduler.cc:42
ns3::PriorityQueueScheduler::IsEmpty
bool IsEmpty() const override
Test if the schedule is empty.
Definition
priority-queue-scheduler.cc:60
ns3::Scheduler
Maintain the event list.
Definition
scheduler.h:146
ns3::TypeId
a unique identifier for an interface.
Definition
type-id.h:48
ns3
Every class exported by the ns3 library is enclosed in the ns3 namespace.
scheduler.h
ns3::Scheduler abstract base class, ns3::Scheduler::Event and ns3::Scheduler::EventKey declarations.
ns3::Scheduler::Event
Scheduler event.
Definition
scheduler.h:173
src
core
model
priority-queue-scheduler.h
Generated on Fri Nov 8 2024 13:58:59 for ns-3 by
1.11.0