Statistics
| Branch: | Revision:

root / include / cmessageheap.h @ 47c4b975

History | View | Annotate | Download (5.92 KB)

1
//==========================================================================
2
//  CMESSAGEHEAP.H - part of
3
//                     OMNeT++/OMNEST
4
//            Discrete System Simulation in C++
5
//
6
//
7
//  Declaration of the following classes:
8
//    cMessageHeap : future event set, implemented as heap
9
//
10
//==========================================================================
11

    
12
/*--------------------------------------------------------------*
13
  Copyright (C) 1992-2008 Andras Varga
14
  Copyright (C) 2006-2008 OpenSim Ltd.
15

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

    
20
#ifndef __CMESSAGEHEAP_H
21
#define __CMESSAGEHEAP_H
22

    
23
#include "cownedobject.h"
24
#include "clock.h"
25

    
26
NAMESPACE_BEGIN
27

    
28
class cMessage;
29

    
30

    
31
/**
32
 * Stores the future event set. The underlying data structure is heap;
33
 * the array used to store the heap expands as needed.
34
 * HORIZON: Circular Buffer deactivated (Performance&Correctness reasons (simtime() calls))
35
 * @see Iterator
36
 * @ingroup Internals
37
 */
38
class SIM_API cMessageHeap : public cOwnedObject
39
{
40
  public:
41
    /**
42
     * Walks along a cMessageHeap. Note that objects in cMessageHeap are not
43
     * necessarily iterated ordered by arrival time. Use msgheap->sort()
44
     * if necessary before using the iterator.
45
     */
46
    class Iterator
47
    {
48
      private:
49
        cMessageHeap *q;
50
        int pos;
51

    
52
        cLock* lock;
53

    
54
      public:
55
        /**
56
         * Constructor.
57
         */
58
        Iterator(const cMessageHeap& mh)  {q=const_cast<cMessageHeap*>(&mh);pos=0;}
59

    
60
        /**
61
         * Reinitializes the iterator object.
62
         */
63
        void init(const cMessageHeap& mh) {q=const_cast<cMessageHeap*>(&mh);pos=0;}
64

    
65
        /**
66
         * Returns the current object.
67
         */
68
        cMessage *operator()()  {return q->peek(pos);}
69

    
70
        /**
71
         * Returns the current object, then moves the iterator to the next item.
72
         * If the iterator has reached the end of the list, NULL is returned.
73
         */
74
        cMessage *operator++(int)  {return end() ? NULL : q->peek(pos++);}
75

    
76
        /**
77
         * Returns true if the iterator has reached the end of the list.
78
         */
79
        bool end() const  {return pos>=q->getLength();}
80
    };
81

    
82
    friend class Iterator;
83

    
84
  private:
85
    // heap data structure
86
    cMessage **h;             // pointer to the 'heap'  (h[0] always empty)
87
    AO_t n;                    // number of elements in the heap
88
    int size;                 // size of allocated h array
89
    unsigned long insertcntr; // counts insertions
90

    
91
    //HORIZON: Circular Buffer deactivated (Performance&Correctness reasons (simtime() calls))
92
    // circular buffer for events scheduled for the current simtime (quite frequent)
93
   // cMessage **cb;            // size of the circular buffer
94
   // int cbsize;               // always power of 2
95
   // int cbhead, cbtail;       // cbhead is inclusive, cbtail is exclusive
96

    
97
    // internal: restore heap
98
    void shiftup(int from=1);
99

    
100
  //  int cblength() const  {return (cbtail-cbhead) & (cbsize-1);}
101
  //  cMessage *cbget(int k)  {return cb[(cbhead+k) & (cbsize-1)];}
102

    
103
  public:
104
    /** @name Constructors, destructor, assignment */
105
    //@{
106

    
107
    /**
108
     * Copy constructor.
109
     */
110
    cMessageHeap(const cMessageHeap& msgq);
111

    
112
    /**
113
     * Constructor.
114
     */
115
    cMessageHeap(const char *name=NULL, int size=128);
116

    
117
    /**
118
     * Destructor.
119
     */
120
    virtual ~cMessageHeap();
121

    
122
    /**
123
     * Assignment operator. The name member is not copied;
124
     * see cOwnedObject's operator=() for more details.
125
     */
126
    cMessageHeap& operator=(const cMessageHeap& msgqueue);
127
    //@}
128

    
129
    /** @name Redefined cObject member functions. */
130
    //@{
131

    
132
    /**
133
     * Creates and returns an exact copy of this object.
134
     * See cObject for more details.
135
     */
136
    virtual cMessageHeap *dup() const  {return new cMessageHeap(*this);}
137

    
138
    /**
139
     * Produces a one-line description of the object's contents.
140
     * See cObject for more details.
141
     */
142
    virtual std::string info() const;
143

    
144
    /**
145
     * Calls v->visit(this) for each contained object.
146
     * See cObject for more details.
147
     */
148
    virtual void forEachChild(cVisitor *v);
149

    
150
    // no parsimPack() and parsimUnpack()
151
    //@}
152

    
153
    /** @name Container functions. */
154
    //@{
155

    
156
    /**
157
     * Insert a new message into the heap.
158
     */
159
    void insert(cMessage *event);
160

    
161
    /**
162
     * Peek the first message in the heap (the one with the smallest timestamp.)
163
     * If the heap is empty, it returns NULL.
164
     */
165
    cMessage *peekFirst() const;
166

    
167
    /**
168
     * Returns the mth message in the heap if 0 <= m < getLength(), and NULL
169
     * otherwise. Note that iteration does not necessarily return messages
170
     * in increasing timestamp (getArrivalTime()) order unless you called
171
     * sort() before.
172
     */
173
    cMessage *peek(int m);
174

    
175
    /**
176
     * Removes and return the first message in the heap (the one
177
     * with the smallest timestamp.) If the heap is empty, it returns NULL.
178
     */
179
    cMessage *removeFirst();
180

    
181
    /**
182
     * Removes and returns the given message in the heap. If the message is
183
     * not in the heap, returns NULL.
184
     */
185
    cMessage *remove(cMessage *event);
186

    
187
    /**
188
     * Sorts the contents of the heap. This is only necessary if one wants
189
     * to iterate through in the FES in strict timestamp order.
190
     */
191
    void sort();
192

    
193
    /**
194
     * Deletes all messages in the heap.
195
     */
196
    void clear();
197

    
198
    /**
199
     * Returns the number of messages in the heap.
200
     */
201
    int getLength() const {return /*cblength() +*/ (int)AO_load((AO_t*)&n);}
202

    
203
    /**
204
     * Returns true if the heap is empty.
205
     */
206
    bool isEmpty() const {return /*cbhead==cbtail &&*/ AO_load((AO_t*)&n)==0;}
207

    
208
    /**
209
     * Alias for getLength().
210
     */
211
    int length() const {return getLength();}
212

    
213
    /**
214
     * Alias for isEmpty().
215
     */
216
    bool empty() const {return isEmpty();}
217
    //@}
218
};
219

    
220
NAMESPACE_END
221

    
222

    
223
#endif
224