/usr/include/Kokyu/DSRT_Sched_Queue_T.h is in libkokyu-dev 6.3.3+dfsg-1.2.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 | /* -*- C++ -*- */
/**
* @file DSRT_Sched_Queue_T.h
*
* @author Venkita Subramonian (venkita@cs.wustl.edu)
*/
#ifndef DSRT_SCHED_QUEUE_T_H
#define DSRT_SCHED_QUEUE_T_H
#include /**/ "ace/pre.h"
#include "DSRT_Dispatch_Item_T.h"
#include "ace/RB_Tree.h"
#include "ace/Hash_Map_Manager_T.h"
#include "ace/Null_Mutex.h"
#if !defined (ACE_LACKS_PRAGMA_ONCE)
# pragma once
#endif /* ACE_LACKS_PRAGMA_ONCE */
#include "Kokyu_dsrt.h"
namespace Kokyu
{
/**
* @class Sched_Ready_Queue
*
* @brief RB_Tree based template class for implementation of
* reordering queue.
*
* This queue is used as a priority queue to store schedulable
* entities. The item at the top of the RB_Tree is the most eligible
* item. The comparator used to determine the most eligible item is
* passed as a template parameter <code> More_Eligible_Comparator
* </code>. This is expected to be a functor which compares two
* schedulable items. The mutex type template parameter for RB_Tree
* is chosen to be a null mutex since all the methods in the
* enclosing <code> Sched_Ready_Queue </code> class are thread
* safe. Since QoS is used for comparison between two schedulable
* items, QoSDescriptor is the ideal candidate to be used as the key
* or the EXT_ID for RB_Tree instantiation. But two qos descriptors
* could be the same. The existing implementation of RB_Tree does
* not allow duplicate keys. In order to facilitate insertion of
* duplicate qos descriptors, the qos descriptors are contained in a
* <code> DSRT_Dispatch_Item </code> and this is used as the basis
* of comparison. To resolve tie between equal qos values, an
* insertion time stamp is maintained in each item and an item with
* an earlier time stamp is more eligible than an item with an
* identical qos value. Another requirement is that it should be
* possible to remove an item from the RB_Tree based on guid. Since
* we have already used up the qos descriptor for the key, we need a
* separate index into the list of schedulable items. The second
* index should be based on guid. This is achieved by using a hash
* map to store <guid, RB_Tree_Node*> pairs. This makes the deletion
* of nodes from RB_Tree more efficient.
*
*/
template <class DSRT_Scheduler_Traits,
class More_Eligible_Comparator,
class ACE_LOCK>
class Sched_Ready_Queue
{
/// Extract the necessary types from the traits class
typedef typename DSRT_Scheduler_Traits::Guid_t Guid_t;
typedef typename
DSRT_Scheduler_Traits::QoSDescriptor_t DSRT_QoSDescriptor_t;
public:
/**
* Given a guid, find an item in the priority queue.
*
* @param guid Guid of item
*
* @param found_item Reference to DSRT_Dispatch_Item_var
* to hold the found item.
* @return -1 if no item found and 0 otherwise.
*/
int find(Guid_t guid,
DSRT_Dispatch_Item_var<DSRT_Scheduler_Traits>&
found_item);
/**
* Insert an item in the priority queue. If item with same guid is
* already in the queue, the existing one is deleted and the new
* one inserted. A deletion and insertion has to happen instead of
* update since the rebalancing of the RB_Tree should take place.
*
* @param item <code> DSRT_Dispatch_Item </code> object containing guid and qos.
*
* @return -1 if insertion failed and 0 otherwise.
*/
int insert(DSRT_Dispatch_Item<DSRT_Scheduler_Traits>* item);
/**
* Remove an item from the priority queue.
*
* @param guid Guid of item.
*
* @param qos QoS associated with item.
*
* @return -1 if removal failed and 0 otherwise.
*/
int remove(Guid_t guid);
/**
* Returns current size of the priority queue.
*/
int current_size ();
/**
* Get the most eligible item from the priority queue.
*
* @param item Item which is most eligible, i.e. one at the
* "top" of the priority queue.
*
* @return -1 if there are no items in the priority queue.
*/
int most_eligible (DSRT_Dispatch_Item_var<DSRT_Scheduler_Traits>&
item);
/**
* change blocked_prio_ item to inactive_prio_
*/
int change_prio (int old_prio, int new_prio, int policy);
void dump();
private:
/**
* @class Guid_Hash
*
* @brief Internal class to generate hash for guid.
*
* This acts just as a wrapper functor to the Hash functor passed
* as part of the traits class <code> DSRT_Scheduler_Traits
* </code>.
*
*/
class Guid_Hash
{
public:
/// Returns hash value.
u_long operator () (const typename DSRT_Scheduler_Traits::Guid_t &id)
{
typename DSRT_Scheduler_Traits::Guid_Hash guid_hash;
return guid_hash(id);
}
};
// RB_Tree related typedefs
typedef ACE_RB_Tree <DSRT_Dispatch_Item_var<DSRT_Scheduler_Traits>,
DSRT_Dispatch_Item_var<DSRT_Scheduler_Traits>,
More_Eligible_Comparator,
ACE_SYNCH_NULL_MUTEX> Dispatch_Items_Priority_Queue;
typedef
ACE_RB_Tree_Node<DSRT_Dispatch_Item_var<DSRT_Scheduler_Traits>,
DSRT_Dispatch_Item_var<DSRT_Scheduler_Traits> >
RB_Tree_Dispatch_Item_Node;
typedef typename
Dispatch_Items_Priority_Queue::ITERATOR PRIO_QUEUE_ITERATOR;
typedef typename
Dispatch_Items_Priority_Queue::ENTRY PRIO_QUEUE_ENTRY;
// Hash map related typedefs
typedef ACE_Hash_Map_Manager_Ex<Guid_t,
RB_Tree_Dispatch_Item_Node*,
Guid_Hash,
ACE_Equal_To<Guid_t>,
ACE_SYNCH_NULL_MUTEX>
Dispatch_Items_Hash_Map;
typedef ACE_Hash_Map_Iterator_Ex<Guid_t,
RB_Tree_Dispatch_Item_Node*,
Guid_Hash,
ACE_Equal_To<Guid_t>,
ACE_SYNCH_NULL_MUTEX>
Dispatch_Items_Hash_Map_Iterator;
typedef ACE_Hash_Map_Entry <Guid_t,
RB_Tree_Dispatch_Item_Node*>
Dispatch_Items_Hash_Map_Entry;
/**
* Lock used to protect the state of the scheduler queue. A
* separate lock is not used for the internal RB_Tree and hashmap.
*/
ACE_LOCK lock_;
/**
* Hash table to maintain a second index into the list of
* schedulable items. This is for efficient removal of items from
* the RB_Tree based on guid. The guid is used as the key for the
* hash map, whereas the qos value is used as the key for the
* RB_Tree.
*/
Dispatch_Items_Hash_Map dispatch_items_hash_map_;
/**
* RB_Tree implementation of priority queue of schedulable items.
*/
Dispatch_Items_Priority_Queue dispatch_items_prio_queue_;
};
}
#if !defined (__ACE_INLINE__)
//#include "DSRT_Sched_Queue_T.i"
#endif /* __ACE_INLINE__ */
#if defined (ACE_TEMPLATES_REQUIRE_SOURCE)
#include "DSRT_Sched_Queue_T.cpp"
#endif /* ACE_TEMPLATES_REQUIRE_SOURCE */
#if defined (ACE_TEMPLATES_REQUIRE_PRAGMA)
#pragma implementation ("DSRT_Sched_Queue_T.cpp")
#endif /* ACE_TEMPLATES_REQUIRE_PRAGMA */
#include /**/ "ace/post.h"
#endif /* DSRT_SCHED_QUEUE_T_H */
|