Project

General

Profile

Statistics
| Branch: | Revision:

root / include / ctaskheap.h @ c87b95b0

History | View | Annotate | Download (5.01 KB)

1
//==========================================================================
2
//  CTASKHEAP.H - part of
3
//                     OMNeT++/OMNEST
4
//            Discrete System Simulation in C++
5
//
6
//
7
//  Declaration of the following classes:
8
//    cTaskHeap : heap of tasks for use by cThreadPoolHorizon
9
//
10
//==========================================================================
11

    
12
/*--------------------------------------------------------------*
13
  Copyright (C) 1992-2005 Andras Varga
14
  Copyright (C) 2009 Georg Kunz
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 __CTASKHEAP_H
21
#define __CTASKHEAP_H
22

    
23
#include "cownedobject.h"
24

    
25
class cMessage;
26

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

    
48
      public:
49
        /**
50
         * Constructor.
51
         */
52
        Iterator(const cTaskHeap& mh)  {q=const_cast<cTaskHeap*>(&mh);pos=1;}
53

    
54
        /**
55
         * Reinitializes the iterator object.
56
         */
57
        void init(const cTaskHeap& mh) {q=const_cast<cTaskHeap*>(&mh);pos=1;}
58

    
59
        /**
60
         * Returns the current object.
61
         */
62
        cMessage *operator()()      {return q->h[pos];}
63

    
64
        /**
65
         * Returns the current object, then moves the iterator to the next item.
66
         * If the iterator has reached the end of the list, NULL is returned.
67
         */
68
        cMessage *operator++(int)   {return pos<=q->n ? q->h[++pos] : NULL;}
69

    
70
        /**
71
         * Returns true if the iterator has reached the end of the list.
72
         */
73
        bool end() const   {return (bool)(pos>q->n);}
74
    };
75

    
76
    friend class Iterator;
77

    
78
  private:
79
    cMessage **h;        // pointer to the 'heap'  (h[0] always empty)
80
    int n;                    // number of elements in the heap
81
    int size;                 // size of allocated h array
82
    unsigned long insertcntr; // counts insertions
83

    
84
    // internal
85
    void shiftup(int from=1);
86

    
87
  public:
88
    /** @name Constructors, destructor, assignment */
89
    //@{
90

    
91
    /**
92
     * Copy constructor.
93
     */
94
    cTaskHeap(const cTaskHeap& msgq);
95

    
96
    /**
97
     * Constructor.
98
     */
99
    cTaskHeap(const char *name=NULL, int size=128);
100

    
101
    /**
102
     * Destructor.
103
     */
104
    virtual ~cTaskHeap();
105

    
106
    /**
107
     * Assignment operator. The name member doesn't get copied;
108
     * see cObject's operator=() for more details.
109
     */
110
    cTaskHeap& operator=(const cTaskHeap& msgqueue);
111
    //@}
112

    
113
    /** @name Redefined cObject member functions. */
114
    //@{
115

    
116
    /**
117
     * Creates and returns an exact copy of this object.
118
     * See cObject for more details.
119
     */
120
    virtual cObject *dup() const  {return new cTaskHeap(*this);}
121

    
122
    /**
123
     * Produces a one-line description of object contents into the buffer passed as argument.
124
     * See cObject for more details.
125
     */
126
    virtual std::string info() const;
127

    
128
    /**
129
     * Calls v->visit(this) for each contained object.
130
     * See cObject for more details.
131
     */
132
    virtual void forEachChild(cVisitor *v);
133

    
134
    // no netPack() and netUnpack()
135
    //@}
136

    
137
    /** @name Container functions. */
138
    //@{
139

    
140
    /**
141
     * Insert a new message into the heap.
142
     */
143
    void insert(cMessage *event);
144

    
145
    /**
146
     * Peek the first message in the heap (the one with the smallest timestamp.)
147
     * If the heap is empty, it returns NULL.
148
     */
149
    cMessage *peekFirst() const;
150

    
151
    /**
152
     * Removes and return the first message in the heap (the one
153
     * with the smallest timestamp.) If the heap is empty, it returns NULL.
154
     */
155
    cMessage *getFirst();
156

    
157
    /**
158
     * Removes and returns the given message in the heap. If the message is
159
     * not in the heap, returns NULL.
160
     */
161
    cMessage *get(cMessage *event);
162

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

    
171
    /**
172
     * Sorts the contents of the heap. This is only necessary if one wants
173
     * to iterate through in the FES in strict timestamp order.
174
     */
175
    void sort();
176

    
177
    /**
178
     * Deletes all messages in the heap.
179
     */
180
    void clear();
181

    
182
    /**
183
     * Removes all messaged from the heap without deleting them.
184
     */
185
    void clearNoDelete();
186

    
187
    /**
188
     * Returns the number of messages in the heap.
189
     */
190
    int length() const {return n;}
191

    
192
    /**
193
     * Returns true if the heap is empty.
194
     */
195
    bool empty() const {return n==0;}
196
    //@}
197
};
198

    
199
#endif
200