Statistics
| Branch: | Revision:

root / src / sim / ctaskheap.cc @ 5668c48e

History | View | Annotate | Download (6.5 KB)

1
//=========================================================================
2
//  CTASKHEAP.CC - part of
3
//
4
//                  OMNeT++/OMNEST
5
//           Discrete System Simulation in C++
6
//
7
//   Member functions of
8
//    cTaskHeap : future event set, implemented as heap
9
//
10
//  Author: Andras Varga, based on the code from Gabor Lencse
11
//          (the original is taken from G. H. Gonnet's book pp. 273-274)
12
//          Georg Kunz
13
//
14
//=========================================================================
15

    
16
/*--------------------------------------------------------------*
17
  Copyright (C) 1992-2005 Andras Varga
18
  Copyright (C) 2009      Georg Kunz
19

20
  This file is distributed WITHOUT ANY WARRANTY. See the file
21
  `license' for details on this and other legal matters.
22

23
  Note: This class is used in the parallel task queue.
24
        Its implementation has been freed from the ownership
25
        management code and implements a EDF scheduling policy.
26

27
*--------------------------------------------------------------*/
28

    
29
#include <stdio.h>           // sprintf
30
#include <string.h>          // strlen
31
#include <stdlib.h>          // qsort
32
#include <sstream>
33
#include "regmacros.h"
34
#include "ctaskheap.h"
35
#include "cmessage.h"
36

    
37
//=== Registration
38
Register_Class(cTaskHeap);
39

    
40
//==========================================================================
41

    
42
/*
43
static inline bool operator > (cMessage& a, cMessage& b)
44
{
45
  return (a.getTend() > b.getTend()) ? 1 :
46
         (a.getTend() < b.getTend()) ? 0 :
47
          a.getTaskInsertOrder() > b.getTaskInsertOrder();
48
}
49
*/
50

    
51
static inline bool operator > (cMessage& a, cMessage& b)
52
{
53
    return a.getTend() > b.getTend() ? true :                                       // 1. criterion: starting time
54
           a.getTend() < b.getTend() ? false :
55
           a.getSchedulingPriority() > b.getSchedulingPriority() ? true :           // 2. criterion: priority
56
           a.getSchedulingPriority() < b.getSchedulingPriority() ? false :
57
           a.getParentStartTime() > b.getParentStartTime() ? true :                 // 3. criterion: parent starting time
58
           a.getParentStartTime() < b.getParentStartTime() ? false :
59
           a.getParentExecutionOrderId() > b.getParentExecutionOrderId() ? true :   // 4. criterion: parent execution order
60
           a.getParentExecutionOrderId() < b.getParentExecutionOrderId() ? false :
61
           a.getSchedulingOrderId() > b.getSchedulingOrderId() ? true :             // 5. criterion: scheduling order
62
           a.getSchedulingOrderId() < b.getSchedulingOrderId() ? false :
63
           a.getTaskInsertOrder() > b.getTaskInsertOrder();                         // 6. criterion: final tie breaker (needed during init)
64
}
65

    
66
static inline bool operator <= (cMessage& a, cMessage& b)
67
{
68
    return !(a>b);
69
}
70

    
71
static int qsort_cmp_msgs(const void *p1, const void *p2)
72
{
73
    cMessage *m1 = *(cMessage **)p1;
74
    cMessage *m2 = *(cMessage **)p2;
75

    
76
    simtime_t dt = m1->getTend() - m2->getTend();
77
    if (dt<0)       return -1;
78
    else if (dt>0)  return 1;
79

    
80
    return (m1->getTaskInsertOrder() < m2->getTaskInsertOrder()) ? -1 : 1;
81
}
82

    
83

    
84
//==========================================================================
85
//=== cTaskHeap - member functions
86

    
87
cTaskHeap::cTaskHeap(const char *name, int siz) : cOwnedObject(name)
88
{
89
    insertcntr = 0L;
90
    n = 0;
91
    size = siz;
92
    h = new cMessage *[size+1];    // +1 is necessary because h[0] is not used
93
}
94

    
95
cTaskHeap::cTaskHeap(const cTaskHeap& heap) : cOwnedObject()
96
{
97
    h=NULL; n=0;
98
    setName( heap.getName() );
99
    operator=(heap);
100
}
101

    
102
cTaskHeap::~cTaskHeap()
103
{
104
    clear();
105
    delete [] h;
106
}
107

    
108
std::string cTaskHeap::info() const
109
{
110
    if (n==0)
111
        return std::string("empty");
112
    std::stringstream out;
113
    out << "length=" << n << " Tmin=" << h[1]->getArrivalTime().str();
114
    return out.str();
115
}
116

    
117
void cTaskHeap::forEachChild(cVisitor *v)
118
{
119
    sort();
120

    
121
    for (int i=1; i<=n; i++)
122
        if (h[i])
123
            v->visit(h[i]);
124
}
125

    
126
void cTaskHeap::clear()
127
{
128
    for (int i=1; i<=n; i++)
129
    {
130

    
131
        ignoreOwnerAndDelete(h[i]);
132

    
133
    }
134
    n=0;
135
}
136

    
137
void cTaskHeap::clearNoDelete()
138
{
139
    for (int i=1; i<=n; i++)
140
    {
141
        getFirst();
142
    }
143
    n=0;
144
}
145

    
146
cTaskHeap& cTaskHeap::operator=(const cTaskHeap& heap)
147
{
148
    if (this==&heap) return *this;
149

    
150
    clear();
151

    
152
    cObject::operator=(heap);
153

    
154
    n = heap.n;
155
    size = heap.size;
156
    delete [] h;
157
    h = new cMessage *[size+1];
158

    
159
    for (int i=1; i<=n; i++)
160
        h[i]=(cMessage *)heap.h[i]->dup();
161
    return *this;
162
}
163

    
164
cMessage *cTaskHeap::peek(int m)
165
{
166
    // map 0..n-1 index range to heap's internal 1..n indices
167
    if (m<0 || m>=n)
168
        return NULL;
169
    return h[m+1];
170
}
171

    
172
void cTaskHeap::sort()
173
{
174
    qsort(h+1,n,sizeof(cMessage *),qsort_cmp_msgs);
175
    for (int i=1; i<=n; i++) h[i]->taskindex=i;
176
}
177

    
178
void cTaskHeap::insert(cMessage *event)
179
{
180
    int i,j;
181

    
182
    event->taskinsertordr = insertcntr++;
183

    
184
    if (++n > size)
185
    {
186
        size *= 2;
187
        cMessage **hnew = new cMessage *[size+1];
188
        for (i=1; i<=n-1; i++)
189
             hnew[i]=h[i];
190
        delete [] h;
191
        h = hnew;
192
    }
193

    
194
    for (j=n; j>1; j=i)
195
    {
196
        i=j/2;
197
        if (*h[i] <= *event)   //direction
198
            break;
199

    
200
        (h[j]=h[i])->taskindex=j;
201
    }
202
    (h[j]=event)->taskindex=j;
203
}
204

    
205
void cTaskHeap::shiftup(int from)
206
{
207
    // restores heap structure (in a sub-heap)
208
    int i,j;
209
    cMessage *temp;
210

    
211
    i=from;
212
    while ((j=2*i) <= n)
213
    {
214
        if (j<n && (*h[j] > *h[j+1]))   //direction
215
            j++;
216
        if (*h[i] > *h[j])  //is change necessary?
217
        {
218
            temp=h[j];
219
            (h[j]=h[i])->taskindex=j;
220
            (h[i]=temp)->taskindex=i;
221
            i=j;
222
        }
223
        else
224
            break;
225
    }
226
}
227

    
228
cMessage *cTaskHeap::peekFirst() const
229
{
230
    return n==0 ? NULL : h[1];
231
}
232

    
233
cMessage *cTaskHeap::getFirst()
234
{
235
    if (n>0)
236
    {
237
        // first is taken out and replaced by the last one
238
        cMessage *event = h[1];
239
        (h[1]=h[n--])->taskindex=1;
240
        shiftup();
241
        event->taskindex=-1;
242
        return event;
243
    }
244
    return NULL;
245
}
246

    
247
cMessage *cTaskHeap::get(cMessage *event)
248
{
249
    // make sure it is really on the heap
250
    if (event->taskindex==-1)
251
        return NULL;
252

    
253
    // sanity check:
254
    // assert(h[event->taskindex]==event);
255

    
256
    // last element will be used to fill the hole
257
    int father, out = event->taskindex;
258
    cMessage *fill = h[n--];
259
    while ((father=out/2)!=0 && *h[father] > *fill)
260
    {
261
        (h[out]=h[father])->taskindex=out;  // father is moved down
262
        out=father;
263
    }
264
    (h[out]=fill)->taskindex=out;
265
    shiftup(out);
266
    event->taskindex=-1;
267
    return event;
268
}
269