Project

General

Profile

Statistics
| Branch: | Revision:

root / src / sim / ctaskheap.cc @ a3be1d55

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