Statistics
| Branch: | Revision:

root / src / sim / cmessageheap.cc @ 3e97003d

History | View | Annotate | Download (9.28 KB)

1
//=========================================================================
2
//  CMSGHEAP.CC - part of
3
//
4
//                  OMNeT++/OMNEST
5
//           Discrete System Simulation in C++
6
//
7
//   Member functions of
8
//    cMessageHeap : 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
//
13
//=========================================================================
14

    
15
/*--------------------------------------------------------------*
16
  Copyright (C) 1992-2008 Andras Varga
17
  Copyright (C) 2006-2008 OpenSim Ltd.
18

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

    
23
#include <stdio.h>           // sprintf
24
#include <string.h>          // strlen
25
#include <stdlib.h>          // qsort
26
#include <sstream>
27
#include "globals.h"
28
#include "cmessage.h"
29
#include "cmessageheap.h"
30

    
31
USING_NAMESPACE
32

    
33
Register_Class(cMessageHeap);
34

    
35

    
36
#define CBHEAPINDEX(i) (-2-(i))
37
#define CBINC(i)       ((i)=((i)+1)&(cbsize-1))
38

    
39

    
40
/* original comparison operator
41
inline bool operator > (cMessage& a, cMessage& b)
42
{
43
    return a.getArrivalTime() > b.getArrivalTime() ? true :                     // 1. criterion: starting time
44
           a.getArrivalTime() < b.getArrivalTime() ? false :
45
           (a.getSchedulingPriority() > b.getSchedulingPriority()) ? true :     // 2. criterion: priority
46
           (a.getSchedulingPriority() < b.getSchedulingPriority()) ? false :
47
            a.getInsertOrder() > b.getInsertOrder();                            // 3. criterion: insert order -> not valid in parallel context anymore
48
}
49
*/
50

    
51
inline bool operator > (cMessage& a, cMessage& b)
52
{
53
    return a.getArrivalTime() > b.getArrivalTime() ? true :                       // 1. criterion: starting time
54
           a.getArrivalTime() < b.getArrivalTime() ? 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.getInsertOrder() > b.getInsertOrder();                               // 6. criterion: final tie breaker (needed during init)
64
}
65

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

    
71

    
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
    if (m1->getArrivalTime() < m2->getArrivalTime())
78
        return -1;
79
    if (m1->getArrivalTime() > m2->getArrivalTime())
80
        return 1;
81

    
82
    int dpri = m1->getSchedulingPriority() - m2->getSchedulingPriority();
83
    if (dpri) return dpri;
84

    
85
    return (m1->getInsertOrder() < m2->getInsertOrder()) ? -1 : 1;
86
}
87

    
88
//----
89

    
90
cMessageHeap::cMessageHeap(const char *name, int siz) : cOwnedObject(name, false)
91
{
92
    insertcntr = 0L;
93

    
94
    AO_store(&n, 0);
95
    size = siz;
96
    h = new cMessage *[size+1];    // +1 is necessary because h[0] is not used
97

    
98
   /* cbsize = 4; // must be power of 2!
99
    cb = new cMessage *[cbsize];
100
    cbhead = cbtail = 0;*/
101
}
102

    
103
cMessageHeap::cMessageHeap(const cMessageHeap& heap) : cOwnedObject()
104
{
105
    h=NULL; AO_store(&n, 0);
106
    setName(heap.getName());
107
    operator=(heap);
108
}
109

    
110
cMessageHeap::~cMessageHeap()
111
{
112
    clear();
113
    delete [] h;
114
    //delete [] cb;
115
}
116

    
117
std::string cMessageHeap::info() const
118
{
119
    if (isEmpty())
120
        return std::string("empty");
121
    std::stringstream out;
122
    out << "length=" << getLength();
123
    return out.str();
124
}
125

    
126
void cMessageHeap::forEachChild(cVisitor *v)
127
{
128
    sort();
129

    
130
   /* for (int i=cbhead; i!=cbtail; CBINC(i))
131
        v->visit(cb[i]);
132
        */
133
    for (int i=1; i<=(int)AO_load(&n); i++)
134
        if (h[i])
135
            v->visit(h[i]);
136
}
137

    
138
void cMessageHeap::clear()
139
{
140
  /*  for (int i=cbhead; i!=cbtail; CBINC(i))
141
        dropAndDelete(cb[i]);
142
    cbhead = cbtail = 0;
143
        */
144
    for (int i=1; i<=(int)AO_load(&n); i++)
145
        dropAndDelete(h[i]);
146
    AO_store(&n, 0);
147
}
148

    
149
cMessageHeap& cMessageHeap::operator=(const cMessageHeap& heap)
150
{
151
    if (this==&heap) return *this;
152

    
153
    clear();
154

    
155
    cOwnedObject::operator=(heap);
156

    
157
    // copy heap
158
    AO_store(&n, (int)AO_load((AO_t*)&(heap.n)));
159
    size = heap.size;
160
    delete [] h;
161
    h = new cMessage *[size+1];
162
    for (int i=1; i<=(int)AO_load(&n); i++)
163
        take( h[i]=(cMessage *)heap.h[i]->dup() );
164

    
165
 /*   // copy circular buffer
166
    cbhead = heap.cbhead;
167
    cbtail = heap.cbtail;
168
    cbsize = heap.cbsize;
169
    delete [] cb;
170
    cb = new cMessage *[cbsize];
171
    for (int i=cbhead; i!=cbtail; CBINC(i))
172
        take( cb[i]=(cMessage *)heap.cb[i]->dup() );
173
*/
174
    return *this;
175
}
176

    
177
cMessage *cMessageHeap::peek(int m)
178
{
179
    if (m < 0)
180
        return NULL;
181
/*
182
    // first few elements map into the circular buffer
183
    int cblen = cblength();
184
    if (m < cblen)
185
        return cbget(m);
186
    m -= cblen;
187
*/
188
    // map the rest to h[1]..h[n] (h[] is 1-based)
189
    if (m >= (int)AO_load(&n))
190
        return NULL;
191
    return h[m+1];
192
}
193

    
194
void cMessageHeap::sort()
195
{
196
    qsort(h+1,(int)AO_load(&n),sizeof(cMessage *),qsort_cmp_msgs);
197
    for (int i=1; i<=(int)AO_load(&n); i++)
198
        h[i]->heapindex=i;
199
}
200

    
201
void cMessageHeap::insert(cMessage *event)
202
{
203
    take(event);
204

    
205
  /*  if (event->getArrivalTime()==simTime() && event->getSchedulingPriority()==0)
206
    {
207
        // scheduled for *now* -- use circular buffer
208
        cb[cbtail] = event;
209
        event->heapindex = CBHEAPINDEX(cbtail);
210
        CBINC(cbtail);
211
        if (cbtail==cbhead)
212
        {
213
            // reallocate
214
            int newsize = 2*cbsize; // cbsize MUST be power of 2
215
            cMessage **newcb = new cMessage*[newsize];
216
            for (int i=0; i<cbsize; i++)
217
                (newcb[i] = cb[(cbhead+i)&(cbsize-1)])->heapindex = CBHEAPINDEX(i);
218
            delete [] cb;
219
            cb = newcb;
220
            cbhead = 0;
221
            cbtail = cbsize;
222
            cbsize = newsize;
223
        }
224
    }
225
    else
226
    {*/
227
        // use heap
228
        int i,j;
229

    
230
        event->insertordr = insertcntr++;
231

    
232
        if ((int)AO_fetch_and_add1(&n)+1 > size)
233
        {
234
            size *= 2;
235
            cMessage **hnew = new cMessage *[size+1];
236
            for (i=1; i<=(int)AO_load(&n)-1; i++)
237
                 hnew[i]=h[i];
238
            delete [] h;
239
            h = hnew;
240
        }
241

    
242
        for (j=(int)AO_load(&n); j>1; j=i)
243
        {
244
            i = j>>1;
245
            if (*h[i] <= *event)   // direction
246
                break;
247

    
248
            (h[j]=h[i])->heapindex=j;
249
        }
250
        (h[j]=event)->heapindex=j;
251
    //}
252
}
253

    
254
void cMessageHeap::shiftup(int from)
255
{
256
    // restores heap structure (in a sub-heap)
257
    int i,j;
258
    cMessage *temp;
259

    
260
    i = from;
261
    while ((j=i<<1) <= (int)AO_load(&n))
262
    {
263
        if (j<(int)AO_load(&n) && (*h[j] > *h[j+1]))   //direction
264
            j++;
265
        if (*h[i] > *h[j])  //is change necessary?
266
        {
267
            temp=h[j];
268
            (h[j]=h[i])->heapindex=j;
269
            (h[i]=temp)->heapindex=i;
270
            i=j;
271
        }
272
        else
273
            break;
274
    }
275
}
276

    
277
cMessage *cMessageHeap::peekFirst() const
278
{
279
    return /*cbhead!=cbtail ? cb[cbhead] : */(int)AO_load((AO_t*)&n)!=0 ? h[1] : NULL;
280
}
281

    
282
cMessage *cMessageHeap::removeFirst()
283
{
284
   /* if (cbhead != cbtail)
285
    {
286
        // remove head element from circular buffer
287
        cMessage *event = cb[cbhead];
288
        CBINC(cbhead);
289
        drop(event);
290
        event->heapindex=-1;
291
        return event;
292
    }
293
    else */if ((int)AO_load(&n)>0)
294
    {
295
        // heap: first is taken out and replaced by the last one
296
        cMessage *event = h[1];
297
        (h[1]=h[(int)AO_fetch_and_sub1(&n)])->heapindex=1;
298
        shiftup();
299
        drop(event);
300
        event->heapindex=-1;
301
        return event;
302
    }
303
    return NULL;
304
}
305

    
306
cMessage *cMessageHeap::remove(cMessage *event)
307
{
308
    // make sure it is really on the heap
309
    if (event->heapindex==-1)
310
        return NULL;
311

    
312
    /*if (event->heapindex<0)
313
    {
314
        // event is in the circular buffer
315
        int i = -event->heapindex-2;
316
        ASSERT(cb[i]==event); // sanity check
317

318
        // remove
319
        int iminus1 = i; CBINC(i);
320
        for (; i!=cbtail; iminus1=i, CBINC(i))
321
            (cb[iminus1] = cb[i])->heapindex = CBHEAPINDEX(iminus1);
322
        cbtail = (cbtail-1)&(cbsize-1);
323
    }
324
    else
325
    {*/
326
        // event is on the heap
327

    
328
        // sanity check:
329
        // ASSERT(h[event->heapindex]==event);
330

    
331
        // last element will be used to fill the hole
332
        int father, out = event->heapindex;
333
        cMessage *fill = h[(int)AO_fetch_and_sub1(&n)];
334
        while ((father=out>>1)!=0 && *h[father] > *fill)
335
        {
336
            (h[out]=h[father])->heapindex=out;  // father is moved down
337
            out=father;
338
        }
339
        (h[out]=fill)->heapindex=out;
340
        shiftup(out);
341
    //}
342

    
343
    drop(event);
344
    event->heapindex=-1;
345
    return event;
346
}
347