Statistics
| Branch: | Revision:

root / src / sim / cmessageheap.cc @ 47c4b975

History | View | Annotate | Download (7.97 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
inline bool operator > (cMessage& a, cMessage& b)
41
{
42
    return a.getArrivalTime() > b.getArrivalTime() ? true :
43
           a.getArrivalTime() < b.getArrivalTime() ? false :
44
           (a.getSchedulingPriority() > b.getSchedulingPriority()) ? true :
45
           (a.getSchedulingPriority() < b.getSchedulingPriority()) ? false :
46
            a.getInsertOrder() > b.getInsertOrder();
47
}
48

    
49
inline bool operator <= (cMessage& a, cMessage& b)
50
{
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
    if (m1->getArrivalTime() < m2->getArrivalTime())
61
        return -1;
62
    if (m1->getArrivalTime() > m2->getArrivalTime())
63
        return 1;
64

    
65
    int dpri = m1->getSchedulingPriority() - m2->getSchedulingPriority();
66
    if (dpri) return dpri;
67

    
68
    return (m1->getInsertOrder() < m2->getInsertOrder()) ? -1 : 1;
69
}
70

    
71
//----
72

    
73
cMessageHeap::cMessageHeap(const char *name, int siz) : cOwnedObject(name, false)
74
{
75
    insertcntr = 0L;
76

    
77
    AO_store(&n, 0);
78
    size = siz;
79
    h = new cMessage *[size+1];    // +1 is necessary because h[0] is not used
80

    
81
   /* cbsize = 4; // must be power of 2!
82
    cb = new cMessage *[cbsize];
83
    cbhead = cbtail = 0;*/
84
}
85

    
86
cMessageHeap::cMessageHeap(const cMessageHeap& heap) : cOwnedObject()
87
{
88
    h=NULL; AO_store(&n, 0);
89
    setName(heap.getName());
90
    operator=(heap);
91
}
92

    
93
cMessageHeap::~cMessageHeap()
94
{
95
    clear();
96
    delete [] h;
97
    //delete [] cb;
98
}
99

    
100
std::string cMessageHeap::info() const
101
{
102
    if (isEmpty())
103
        return std::string("empty");
104
    std::stringstream out;
105
    out << "length=" << getLength();
106
    return out.str();
107
}
108

    
109
void cMessageHeap::forEachChild(cVisitor *v)
110
{
111
    sort();
112

    
113
   /* for (int i=cbhead; i!=cbtail; CBINC(i))
114
        v->visit(cb[i]);
115
        */
116
    for (int i=1; i<=(int)AO_load(&n); i++)
117
        if (h[i])
118
            v->visit(h[i]);
119
}
120

    
121
void cMessageHeap::clear()
122
{
123
  /*  for (int i=cbhead; i!=cbtail; CBINC(i))
124
        dropAndDelete(cb[i]);
125
    cbhead = cbtail = 0;
126
        */
127
    for (int i=1; i<=(int)AO_load(&n); i++)
128
        dropAndDelete(h[i]);
129
    AO_store(&n, 0);
130
}
131

    
132
cMessageHeap& cMessageHeap::operator=(const cMessageHeap& heap)
133
{
134
    if (this==&heap) return *this;
135

    
136
    clear();
137

    
138
    cOwnedObject::operator=(heap);
139

    
140
    // copy heap
141
    AO_store(&n, (int)AO_load((AO_t*)&(heap.n)));
142
    size = heap.size;
143
    delete [] h;
144
    h = new cMessage *[size+1];
145
    for (int i=1; i<=(int)AO_load(&n); i++)
146
        take( h[i]=(cMessage *)heap.h[i]->dup() );
147

    
148
 /*   // copy circular buffer
149
    cbhead = heap.cbhead;
150
    cbtail = heap.cbtail;
151
    cbsize = heap.cbsize;
152
    delete [] cb;
153
    cb = new cMessage *[cbsize];
154
    for (int i=cbhead; i!=cbtail; CBINC(i))
155
        take( cb[i]=(cMessage *)heap.cb[i]->dup() );
156
*/
157
    return *this;
158
}
159

    
160
cMessage *cMessageHeap::peek(int m)
161
{
162
    if (m < 0)
163
        return NULL;
164
/*
165
    // first few elements map into the circular buffer
166
    int cblen = cblength();
167
    if (m < cblen)
168
        return cbget(m);
169
    m -= cblen;
170
*/
171
    // map the rest to h[1]..h[n] (h[] is 1-based)
172
    if (m >= (int)AO_load(&n))
173
        return NULL;
174
    return h[m+1];
175
}
176

    
177
void cMessageHeap::sort()
178
{
179
    qsort(h+1,(int)AO_load(&n),sizeof(cMessage *),qsort_cmp_msgs);
180
    for (int i=1; i<=(int)AO_load(&n); i++)
181
        h[i]->heapindex=i;
182
}
183

    
184
void cMessageHeap::insert(cMessage *event)
185
{
186
    take(event);
187

    
188
  /*  if (event->getArrivalTime()==simTime() && event->getSchedulingPriority()==0)
189
    {
190
        // scheduled for *now* -- use circular buffer
191
        cb[cbtail] = event;
192
        event->heapindex = CBHEAPINDEX(cbtail);
193
        CBINC(cbtail);
194
        if (cbtail==cbhead)
195
        {
196
            // reallocate
197
            int newsize = 2*cbsize; // cbsize MUST be power of 2
198
            cMessage **newcb = new cMessage*[newsize];
199
            for (int i=0; i<cbsize; i++)
200
                (newcb[i] = cb[(cbhead+i)&(cbsize-1)])->heapindex = CBHEAPINDEX(i);
201
            delete [] cb;
202
            cb = newcb;
203
            cbhead = 0;
204
            cbtail = cbsize;
205
            cbsize = newsize;
206
        }
207
    }
208
    else
209
    {*/
210
        // use heap
211
        int i,j;
212

    
213
        event->insertordr = insertcntr++;
214

    
215
        if ((int)AO_fetch_and_add1(&n)+1 > size)
216
        {
217
            size *= 2;
218
            cMessage **hnew = new cMessage *[size+1];
219
            for (i=1; i<=(int)AO_load(&n)-1; i++)
220
                 hnew[i]=h[i];
221
            delete [] h;
222
            h = hnew;
223
        }
224

    
225
        for (j=(int)AO_load(&n); j>1; j=i)
226
        {
227
            i = j>>1;
228
            if (*h[i] <= *event)   // direction
229
                break;
230

    
231
            (h[j]=h[i])->heapindex=j;
232
        }
233
        (h[j]=event)->heapindex=j;
234
    //}
235
}
236

    
237
void cMessageHeap::shiftup(int from)
238
{
239
    // restores heap structure (in a sub-heap)
240
    int i,j;
241
    cMessage *temp;
242

    
243
    i = from;
244
    while ((j=i<<1) <= (int)AO_load(&n))
245
    {
246
        if (j<(int)AO_load(&n) && (*h[j] > *h[j+1]))   //direction
247
            j++;
248
        if (*h[i] > *h[j])  //is change necessary?
249
        {
250
            temp=h[j];
251
            (h[j]=h[i])->heapindex=j;
252
            (h[i]=temp)->heapindex=i;
253
            i=j;
254
        }
255
        else
256
            break;
257
    }
258
}
259

    
260
cMessage *cMessageHeap::peekFirst() const
261
{
262
    return /*cbhead!=cbtail ? cb[cbhead] : */(int)AO_load((AO_t*)&n)!=0 ? h[1] : NULL;
263
}
264

    
265
cMessage *cMessageHeap::removeFirst()
266
{
267
   /* if (cbhead != cbtail)
268
    {
269
        // remove head element from circular buffer
270
        cMessage *event = cb[cbhead];
271
        CBINC(cbhead);
272
        drop(event);
273
        event->heapindex=-1;
274
        return event;
275
    }
276
    else */if ((int)AO_load(&n)>0)
277
    {
278
        // heap: first is taken out and replaced by the last one
279
        cMessage *event = h[1];
280
        (h[1]=h[(int)AO_fetch_and_sub1(&n)])->heapindex=1;
281
        shiftup();
282
        drop(event);
283
        event->heapindex=-1;
284
        return event;
285
    }
286
    return NULL;
287
}
288

    
289
cMessage *cMessageHeap::remove(cMessage *event)
290
{
291
    // make sure it is really on the heap
292
    if (event->heapindex==-1)
293
        return NULL;
294

    
295
    /*if (event->heapindex<0)
296
    {
297
        // event is in the circular buffer
298
        int i = -event->heapindex-2;
299
        ASSERT(cb[i]==event); // sanity check
300

301
        // remove
302
        int iminus1 = i; CBINC(i);
303
        for (; i!=cbtail; iminus1=i, CBINC(i))
304
            (cb[iminus1] = cb[i])->heapindex = CBHEAPINDEX(iminus1);
305
        cbtail = (cbtail-1)&(cbsize-1);
306
    }
307
    else
308
    {*/
309
        // event is on the heap
310

    
311
        // sanity check:
312
        // ASSERT(h[event->heapindex]==event);
313

    
314
        // last element will be used to fill the hole
315
        int father, out = event->heapindex;
316
        cMessage *fill = h[(int)AO_fetch_and_sub1(&n)];
317
        while ((father=out>>1)!=0 && *h[father] > *fill)
318
        {
319
            (h[out]=h[father])->heapindex=out;  // father is moved down
320
            out=father;
321
        }
322
        (h[out]=fill)->heapindex=out;
323
        shiftup(out);
324
    //}
325

    
326
    drop(event);
327
    event->heapindex=-1;
328
    return event;
329
}
330