Project

General

Profile

Statistics
| Branch: | Revision:

root / src / sim / ctaskheap.cc @ 6b036b78

History | View | Annotate | Download (5.61 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
static inline int operator <= (cMessage& a, cMessage& b)
43
{
44
    int r = (a.getTend() < b.getTend()) ? 1 :
45
    (a.getTend() > b.getTend()) ? 0 :
46
     a.taskInsertOrder() <= b.taskInsertOrder();
47
    //printf("a=%f,b=%f,r=%i \n",SIMTIME_DBL(a.getTend()),SIMTIME_DBL(b.getTend()),r);
48
  return (a.getTend() < b.getTend()) ? 1 :
49
         (a.getTend() > b.getTend()) ? 0 :
50
          a.taskInsertOrder() <= b.taskInsertOrder();
51
}
52

    
53
static inline int operator > (cMessage& a, cMessage& b)
54
{
55
    return !(a<=b);
56
}
57

    
58

    
59
static int qsort_cmp_msgs(const void *p1, const void *p2)
60
{
61
    printf("test");
62
    cMessage *m1 = *(cMessage **)p1;
63
    cMessage *m2 = *(cMessage **)p2;
64

    
65
    simtime_t dt = m1->getTend() - m2->getTend();
66
    if (dt<0)       return -1;
67
    else if (dt>0)  return 1;
68

    
69
    return (m1->taskInsertOrder() < m2->taskInsertOrder()) ? -1 : 1;
70
}
71

    
72

    
73
//==========================================================================
74
//=== cTaskHeap - member functions
75

    
76
cTaskHeap::cTaskHeap(const char *name, int siz) : cOwnedObject(name)
77
{
78
    insertcntr = 0L;
79
    n = 0;
80
    size = siz;
81
    h = new cMessage *[size+1];    // +1 is necessary because h[0] is not used
82
}
83

    
84
cTaskHeap::cTaskHeap(const cTaskHeap& heap) : cOwnedObject()
85
{
86
    h=NULL; n=0;
87
    setName( heap.getName() );
88
    operator=(heap);
89
}
90

    
91
cTaskHeap::~cTaskHeap()
92
{
93
    clear();
94
    delete [] h;
95
}
96

    
97
std::string cTaskHeap::info() const
98
{
99
    if (n==0)
100
        return std::string("empty");
101
    std::stringstream out;
102
    out << "length=" << n << " Tmin=" << h[1]->getArrivalTime().str();
103
    return out.str();
104
}
105

    
106
void cTaskHeap::forEachChild(cVisitor *v)
107
{
108
    sort();
109

    
110
    for (int i=1; i<=n; i++)
111
        if (h[i])
112
            v->visit(h[i]);
113
}
114

    
115
void cTaskHeap::clear()
116
{
117
    for (int i=1; i<=n; i++)
118
    {
119

    
120
        ignoreOwnerAndDelete(h[i]);
121

    
122
    }
123
    n=0;
124
}
125

    
126
void cTaskHeap::clearNoDelete()
127
{
128
    for (int i=1; i<=n; i++)
129
    {
130
        getFirst();
131
    }
132
    n=0;
133
}
134

    
135
cTaskHeap& cTaskHeap::operator=(const cTaskHeap& heap)
136
{
137
    if (this==&heap) return *this;
138

    
139
    clear();
140

    
141
    cObject::operator=(heap);
142

    
143
    n = heap.n;
144
    size = heap.size;
145
    delete [] h;
146
    h = new cMessage *[size+1];
147

    
148
    for (int i=1; i<=n; i++)
149
        h[i]=(cMessage *)heap.h[i]->dup();
150
    return *this;
151
}
152

    
153
cMessage *cTaskHeap::peek(int m)
154
{
155
    // map 0..n-1 index range to heap's internal 1..n indices
156
    if (m<0 || m>=n)
157
        return NULL;
158
    return h[m+1];
159
}
160

    
161
void cTaskHeap::sort()
162
{
163
    qsort(h+1,n,sizeof(cMessage *),qsort_cmp_msgs);
164
    for (int i=1; i<=n; i++) h[i]->taskindex=i;
165
}
166

    
167
void cTaskHeap::insert(cMessage *event)
168
{
169
    int i,j;
170

    
171
    event->taskinsertordr = insertcntr++;
172

    
173
    if (++n > size)
174
    {
175
        size *= 2;
176
        cMessage **hnew = new cMessage *[size+1];
177
        for (i=1; i<=n-1; i++)
178
             hnew[i]=h[i];
179
        delete [] h;
180
        h = hnew;
181
    }
182

    
183
    for (j=n; j>1; j=i)
184
    {
185
        i=j/2;
186
        if (*h[i] <= *event)   //direction
187
            break;
188

    
189
        (h[j]=h[i])->taskindex=j;
190
    }
191
    (h[j]=event)->taskindex=j;
192
}
193

    
194
void cTaskHeap::shiftup(int from)
195
{
196
    // restores heap structure (in a sub-heap)
197
    int i,j;
198
    cMessage *temp;
199

    
200
    i=from;
201
    while ((j=2*i) <= n)
202
    {
203
        if (j<n && (*h[j] > *h[j+1]))   //direction
204
            j++;
205
        if (*h[i] > *h[j])  //is change necessary?
206
        {
207
            temp=h[j];
208
            (h[j]=h[i])->taskindex=j;
209
            (h[i]=temp)->taskindex=i;
210
            i=j;
211
        }
212
        else
213
            break;
214
    }
215
}
216

    
217
cMessage *cTaskHeap::peekFirst() const
218
{
219
    return n==0 ? NULL : h[1];
220
}
221

    
222
cMessage *cTaskHeap::getFirst()
223
{
224
    if (n>0)
225
    {
226
        // first is taken out and replaced by the last one
227
        cMessage *event = h[1];
228
        (h[1]=h[n--])->taskindex=1;
229
        shiftup();
230
        event->taskindex=-1;
231
        return event;
232
    }
233
    return NULL;
234
}
235

    
236
cMessage *cTaskHeap::get(cMessage *event)
237
{
238
    // make sure it is really on the heap
239
    if (event->taskindex==-1)
240
        return NULL;
241

    
242
    // sanity check:
243
    // assert(h[event->taskindex]==event);
244

    
245
    // last element will be used to fill the hole
246
    int father, out = event->taskindex;
247
    cMessage *fill = h[n--];
248
    while ((father=out/2)!=0 && *h[father] > *fill)
249
    {
250
        (h[out]=h[father])->taskindex=out;  // father is moved down
251
        out=father;
252
    }
253
    (h[out]=fill)->taskindex=out;
254
    shiftup(out);
255
    event->taskindex=-1;
256
    return event;
257
}
258