Statistics
| Branch: | Revision:

root / include / cmessageheap.h @ 7f251033

History | View | Annotate | Download (5.86 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

    
25
NAMESPACE_BEGIN
26

    
27
class cMessage;
28

    
29

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

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

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

    
62
        /**
63
         * Returns the current object.
64
         */
65
        cMessage *operator()()  {return q->peek(pos);}
66

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

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

    
79
    friend class Iterator;
80

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

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

    
94
    // internal: restore heap
95
    void shiftup(int from=1);
96

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

    
100
  public:
101
    /** @name Constructors, destructor, assignment */
102
    //@{
103

    
104
    /**
105
     * Copy constructor.
106
     */
107
    cMessageHeap(const cMessageHeap& msgq);
108

    
109
    /**
110
     * Constructor.
111
     */
112
    cMessageHeap(const char *name=NULL, int size=128);
113

    
114
    /**
115
     * Destructor.
116
     */
117
    virtual ~cMessageHeap();
118

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

    
126
    /** @name Redefined cObject member functions. */
127
    //@{
128

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

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

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

    
147
    // no parsimPack() and parsimUnpack()
148
    //@}
149

    
150
    /** @name Container functions. */
151
    //@{
152

    
153
    /**
154
     * Insert a new message into the heap.
155
     */
156
    void insert(cMessage *event);
157

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

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

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

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

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

    
190
    /**
191
     * Deletes all messages in the heap.
192
     */
193
    void clear();
194

    
195
    /**
196
     * Returns the number of messages in the heap.
197
     */
198
    int getLength() const {return /*cblength() +*/ (int)AO_load(&n);}
199

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

    
205
    /**
206
     * Alias for getLength().
207
     */
208
    int length() const {return getLength();}
209

    
210
    /**
211
     * Alias for isEmpty().
212
     */
213
    bool empty() const {return isEmpty();}
214
    //@}
215
};
216

    
217
NAMESPACE_END
218

    
219

    
220
#endif
221