Statistics
| Branch: | Revision:

root / src / sim / ctaskheap.cc @ fbe00e73

History | View | Annotate | Download (6.69 KB)

1 01873262 Georg Kunz
//=========================================================================
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 5668c48e Georg Kunz
/*
43
static inline bool operator > (cMessage& a, cMessage& b)
44 01873262 Georg Kunz
{
45 5668c48e Georg Kunz
  return (a.getTend() > b.getTend()) ? 1 :
46
         (a.getTend() < b.getTend()) ? 0 :
47
          a.getTaskInsertOrder() > b.getTaskInsertOrder();
48 01873262 Georg Kunz
}
49 5668c48e Georg Kunz
*/
50 01873262 Georg Kunz
51 5668c48e Georg Kunz
static inline bool operator > (cMessage& a, cMessage& b)
52 01873262 Georg Kunz
{
53 b9e9c37a Simon Tenbusch
    return a.getTend() > b.getTend() ? true :                                       // 1. criterion: ending time
54
           a.getTend() < b.getTend() ? false :                                      // TODO: Is this still correct
55
                                                                                    // (considering Parent Start Times?)
56 5668c48e Georg Kunz
           a.getSchedulingPriority() > b.getSchedulingPriority() ? true :           // 2. criterion: priority
57
           a.getSchedulingPriority() < b.getSchedulingPriority() ? false :
58
           a.getParentStartTime() > b.getParentStartTime() ? true :                 // 3. criterion: parent starting time
59
           a.getParentStartTime() < b.getParentStartTime() ? false :
60
           a.getParentExecutionOrderId() > b.getParentExecutionOrderId() ? true :   // 4. criterion: parent execution order
61
           a.getParentExecutionOrderId() < b.getParentExecutionOrderId() ? false :
62
           a.getSchedulingOrderId() > b.getSchedulingOrderId() ? true :             // 5. criterion: scheduling order
63
           a.getSchedulingOrderId() < b.getSchedulingOrderId() ? false :
64
           a.getTaskInsertOrder() > b.getTaskInsertOrder();                         // 6. criterion: final tie breaker (needed during init)
65 01873262 Georg Kunz
}
66
67 5668c48e Georg Kunz
static inline bool operator <= (cMessage& a, cMessage& b)
68
{
69
    return !(a>b);
70
}
71 01873262 Georg Kunz
72
static int qsort_cmp_msgs(const void *p1, const void *p2)
73
{
74
    cMessage *m1 = *(cMessage **)p1;
75
    cMessage *m2 = *(cMessage **)p2;
76
77
    simtime_t dt = m1->getTend() - m2->getTend();
78
    if (dt<0)       return -1;
79
    else if (dt>0)  return 1;
80
81 5668c48e Georg Kunz
    return (m1->getTaskInsertOrder() < m2->getTaskInsertOrder()) ? -1 : 1;
82 01873262 Georg Kunz
}
83
84
85
//==========================================================================
86
//=== cTaskHeap - member functions
87
88
cTaskHeap::cTaskHeap(const char *name, int siz) : cOwnedObject(name)
89
{
90
    insertcntr = 0L;
91
    n = 0;
92
    size = siz;
93
    h = new cMessage *[size+1];    // +1 is necessary because h[0] is not used
94
}
95
96
cTaskHeap::cTaskHeap(const cTaskHeap& heap) : cOwnedObject()
97
{
98
    h=NULL; n=0;
99
    setName( heap.getName() );
100
    operator=(heap);
101
}
102
103
cTaskHeap::~cTaskHeap()
104
{
105
    clear();
106
    delete [] h;
107
}
108
109
std::string cTaskHeap::info() const
110
{
111
    if (n==0)
112
        return std::string("empty");
113
    std::stringstream out;
114
    out << "length=" << n << " Tmin=" << h[1]->getArrivalTime().str();
115
    return out.str();
116
}
117
118
void cTaskHeap::forEachChild(cVisitor *v)
119
{
120
    sort();
121
122
    for (int i=1; i<=n; i++)
123
        if (h[i])
124
            v->visit(h[i]);
125
}
126
127
void cTaskHeap::clear()
128
{
129
    for (int i=1; i<=n; i++)
130
    {
131
132
        ignoreOwnerAndDelete(h[i]);
133
134
    }
135
    n=0;
136
}
137
138
void cTaskHeap::clearNoDelete()
139
{
140
    for (int i=1; i<=n; i++)
141
    {
142
        getFirst();
143
    }
144
    n=0;
145
}
146
147
cTaskHeap& cTaskHeap::operator=(const cTaskHeap& heap)
148
{
149
    if (this==&heap) return *this;
150
151
    clear();
152
153
    cObject::operator=(heap);
154
155
    n = heap.n;
156
    size = heap.size;
157
    delete [] h;
158
    h = new cMessage *[size+1];
159
160
    for (int i=1; i<=n; i++)
161
        h[i]=(cMessage *)heap.h[i]->dup();
162
    return *this;
163
}
164
165
cMessage *cTaskHeap::peek(int m)
166
{
167
    // map 0..n-1 index range to heap's internal 1..n indices
168
    if (m<0 || m>=n)
169
        return NULL;
170
    return h[m+1];
171
}
172
173
void cTaskHeap::sort()
174
{
175
    qsort(h+1,n,sizeof(cMessage *),qsort_cmp_msgs);
176
    for (int i=1; i<=n; i++) h[i]->taskindex=i;
177
}
178
179
void cTaskHeap::insert(cMessage *event)
180
{
181
    int i,j;
182
183
    event->taskinsertordr = insertcntr++;
184
185
    if (++n > size)
186
    {
187
        size *= 2;
188
        cMessage **hnew = new cMessage *[size+1];
189
        for (i=1; i<=n-1; i++)
190
             hnew[i]=h[i];
191
        delete [] h;
192
        h = hnew;
193
    }
194
195
    for (j=n; j>1; j=i)
196
    {
197
        i=j/2;
198
        if (*h[i] <= *event)   //direction
199
            break;
200
201
        (h[j]=h[i])->taskindex=j;
202
    }
203
    (h[j]=event)->taskindex=j;
204
}
205
206
void cTaskHeap::shiftup(int from)
207
{
208
    // restores heap structure (in a sub-heap)
209
    int i,j;
210
    cMessage *temp;
211
212
    i=from;
213
    while ((j=2*i) <= n)
214
    {
215
        if (j<n && (*h[j] > *h[j+1]))   //direction
216
            j++;
217
        if (*h[i] > *h[j])  //is change necessary?
218
        {
219
            temp=h[j];
220
            (h[j]=h[i])->taskindex=j;
221
            (h[i]=temp)->taskindex=i;
222
            i=j;
223
        }
224
        else
225
            break;
226
    }
227
}
228
229
cMessage *cTaskHeap::peekFirst() const
230
{
231
    return n==0 ? NULL : h[1];
232
}
233
234
cMessage *cTaskHeap::getFirst()
235
{
236
    if (n>0)
237
    {
238
        // first is taken out and replaced by the last one
239
        cMessage *event = h[1];
240
        (h[1]=h[n--])->taskindex=1;
241
        shiftup();
242
        event->taskindex=-1;
243
        return event;
244
    }
245
    return NULL;
246
}
247
248
cMessage *cTaskHeap::get(cMessage *event)
249
{
250
    // make sure it is really on the heap
251
    if (event->taskindex==-1)
252
        return NULL;
253
254
    // sanity check:
255
    // assert(h[event->taskindex]==event);
256
257
    // last element will be used to fill the hole
258
    int father, out = event->taskindex;
259
    cMessage *fill = h[n--];
260
    while ((father=out/2)!=0 && *h[father] > *fill)
261
    {
262
        (h[out]=h[father])->taskindex=out;  // father is moved down
263
        out=father;
264
    }
265
    (h[out]=fill)->taskindex=out;
266
    shiftup(out);
267
    event->taskindex=-1;
268
    return event;
269
}