Statistics
| Branch: | Revision:

root / include / clinkedlist.h @ master

History | View | Annotate | Download (9.5 KB)

1 01873262 Georg Kunz
//==========================================================================
2
//  CLINKEDLIST.H - part of
3
//                     OMNeT++/OMNEST
4
//            Discrete System Simulation in C++
5
//
6
//  Declaration of the following classes:
7
//    cLinkedList        : linked list of pointers (cQueue-like interface)
8
//
9
//==========================================================================
10
11
/*--------------------------------------------------------------*
12
  Copyright (C) 1992-2008 Andras Varga
13
  Copyright (C) 2006-2008 OpenSim Ltd.
14

15
  This file is distributed WITHOUT ANY WARRANTY. See the file
16
  `license' for details on this and other legal matters.
17
*--------------------------------------------------------------*/
18
19
#ifndef __CLINKEDLIST_H
20
#define __CLINKEDLIST_H
21
22
#include "cownedobject.h"
23
24
NAMESPACE_BEGIN
25
26
#ifdef _MSC_VER
27
#pragma warning(push, 0)  // deprecation warnings inside the header
28
#endif
29
30
#if defined __GNUC__ && __GNUC__ == 4 && __GNUC_MINOR__ >= 3
31
// gcc-4.3.1 is broken: it insists on spitting out deprecation warnings for
32
// cLinkedList::Iterator when this header gets included anywhere, and
33
// cannot be convinced otherwise. #pragma GCC diagnostic does not work.
34
// So we better forget deprecation with that compiler.
35
#define CLINKEDLIST_DEPRECATED
36
#else
37
#define CLINKEDLIST_DEPRECATED  _OPPDEPRECATED
38
#endif
39
40
/**
41
 * Use of this class is DISCOURAGED, it is provided for backward compatibility
42
 * only. Use std::deque or std::list instead.
43
 *
44
 * A double-linked list of non-cOwnedObject items. cLinkedList has a cQueue-like
45
 * interface.
46
 *
47
 * Memory management of contained items is controlled by the configPointer()
48
 * function. As default, pointers are treated as mere pointers, so
49
 * items are never duplicated or deleted.
50
 *
51
 * @see Iterator
52
 * @ingroup Containers
53
 */
54
class SIM_API CLINKEDLIST_DEPRECATED cLinkedList : public cOwnedObject
55
{
56
    // a list elem
57
    struct Elem
58
    {
59
        void *item;
60
        Elem *prev, *next;
61
    };
62
63
  public:
64
65
    /**
66
     * Walks along a cLinkedList object. To examine each element in the list,
67
     * the Iterator class can be used. Once an Iterator object is created for the list,
68
     * the ++ and -- operators can be used to step from one element of
69
     * the list to the next/previous one.
70
     */
71
    class CLINKEDLIST_DEPRECATED Iterator
72
    {
73
      private:
74
        Elem *p;
75
76
      public:
77
        /**
78
         * Constructor. Takes the cLinkedList object as argument.
79
         * The current item will be the first (if athead==true, default) or the last
80
         * (if athead==false) item in the list.
81
         */
82
        Iterator(const cLinkedList& q, bool athead=true)
83
                {p=&q ? (athead ? q.headp : q.tailp) : NULL;}
84
85
        /**
86
         * Reinitializes the iterator object.
87
         */
88
        void init(const cLinkedList& q, bool athead=true)
89
                {p=&q ? (athead ? q.headp : q.tailp) : NULL;}
90
91
        /**
92
         * Returns the current item.
93
         */
94
        void *operator()() const  {return p->item;}
95
96
        /**
97
         * Returns true if we have reached the end (with operator++) or the beginning
98
         * (with operator--) of the list.
99
         */
100
        bool end() const   {return (bool)(p==NULL);}
101
102
        /**
103
         * Returns the current item and steps to the next one.
104
         */
105
        void *operator++(int)  {if (!p) return NULL; Elem *t=p; p=p->next; return t->item;}
106
107
        /**
108
         * Returns the current item and steps to the previous one.
109
         */
110
        void *operator--(int)  {if (!p) return NULL; Elem *t=p; p=p->prev; return t->item;}
111
    };
112
113
    friend class Iterator;
114
115
  private:
116
    Elem *headp, *tailp;      // inserting at head, removal at tail
117
    int n;                    // number of items in list
118
119
    VoidDelFunc delfunc;      // user func to free up item (NULL-->delete)
120
    VoidDupFunc dupfunc;      // user func to dupl. item (NULL-->new+memcpy)
121
    size_t itemsize;          // used in making shallow copy if dupfunc==0
122
                              // if both dupfunc and itemsize are 0, we do
123
                              // no memory management (we treat pointers as
124
                              // mere pointers)
125
  protected:
126
    // internal use.
127
    // if both dupfunc and itemsize are 0, we do no memory management
128
    // (we treat pointers as mere pointers)
129
    Elem *find_llelem(void *item) const;
130
131
    // internal use
132
    void insbefore_llelem(Elem *p, void *item);
133
134
    // internal use
135
    void insafter_llelem(Elem *p, void *item);
136
137
    // internal use
138
    void *remove_llelem(Elem *p);
139
140
  public:
141
    /** @name Constructors, destructor, assignment. */
142
    //@{
143
144
    /**
145
     * Copy constructor. Contained items that are owned by the list will
146
     * be duplicated using the function passed in configPointer()
147
     * so that the new list will have its own copy of them. By default,
148
     * there is no duplication function so only the pointers are copied.
149
     */
150
    cLinkedList(const cLinkedList& llist);
151
152
    /**
153
     * Constructor. It accepts the object name.
154
     */
155
    explicit cLinkedList(const char *name=NULL);
156
157
    /**
158
     * Destructor calls clear().
159
     */
160
    virtual ~cLinkedList();
161
162
    /**
163
     * Assignment operator. The name member is not copied; see cOwnedObject's
164
     * operator=() for more details.
165
     * Duplication and assignment work all right with cLinkedList.
166
     * Contained items are treated as configured with configPointer().
167
     * By default, only pointers are copied.
168
     */
169
    cLinkedList& operator=(const cLinkedList& queue);
170
    //@}
171
172
    /** @name Redefined cObject member functions */
173
    //@{
174
175
    /**
176
     * Duplication and assignment work all right with cLinkedList.
177
     * Contained items are treated as configured with configPointer().
178
     * By default, only pointers are copied.
179
     */
180
    virtual cLinkedList *dup() const  {return new cLinkedList(*this);}
181
182
    /**
183
     * Produces a one-line description of the object's contents.
184
     * See cObject for more details.
185
     */
186
    virtual std::string info() const;
187
188
    /**
189
     * Serializes the object into an MPI send buffer.
190
     * Used by the simulation kernel for parallel execution.
191
     * See cObject for more details.
192
     */
193
    virtual void parsimPack(cCommBuffer *buffer);
194
195
    /**
196
     * Deserializes the object from an MPI receive buffer
197
     * Used by the simulation kernel for parallel execution.
198
     * See cObject for more details.
199
     */
200
    virtual void parsimUnpack(cCommBuffer *buffer);
201
    //@}
202
203
    /** @name Container functions. */
204
    //@{
205
206
    /**
207
     * Configures memory management for contained items.
208
     *
209
     * <TABLE BORDER=1>
210
     * <TR><TD WIDTH=96><B>delete func.</B></TD><TD WIDTH=89><B>dupl.func.</B>
211
     * </TD><TD WIDTH=92><B>itemsize</B></TD><TD WIDTH=317><B>behavior</B>
212
     * </TD></TR>
213
     * <TR><TD WIDTH=96>NULL</TD><TD WIDTH=89>NULL
214
     * </TD><TD WIDTH=92>0</TD><TD WIDTH=317>Pointer is treated as mere pointer - no memory management. Duplication copies the pointer, and deletion does nothing.
215
     * </TD></TR>
216
     * <TR><TD WIDTH=96>NULL</TD><TD WIDTH=89>NULL
217
     * </TD><TD WIDTH=92>>0 size</TD><TD WIDTH=317>Plain memory management. Duplication is done with operator new char[size]+memcpy(), and deletion is done via operator delete.
218
     * </TD></TR>
219
     * <TR><TD WIDTH=96>NULL or user's delete func.</TD><TD WIDTH=89>user's dupfunc.
220
     * </TD><TD WIDTH=92>indifferent</TD><TD WIDTH=317>Sophisticated memory management. Duplication is done by calling the user-supplied duplication function, which should do the allocation and the appropriate copying. Deletion is done by calling the user-supplied delete function, or the delete operator if it is not supplied.
221
     * </TD></TR>
222
     * </TABLE>
223
     */
224
    void config( VoidDelFunc _delfunc, VoidDupFunc _dupfunc, size_t _itemsize=0);
225
226
    /**
227
     * Inserts the given object at the head of the list.
228
     */
229
    void insert(void *item);
230
231
    /**
232
     * Inserts exactly before the given item. If the item to be inserted before
233
     * is not in the list, cRuntimeError is thrown.
234
     */
235
    void insertBefore(void *where, void *item);
236
237
    /**
238
     * Inserts exactly after the given item. If the item to be inserted after
239
     * is not in the list, cRuntimeError is thrown.
240
     */
241
    void insertAfter(void *where, void *item);
242
243
    /**
244
     * Returns the first item in the list, or NULL pointer if the list
245
     * is empty.
246
     */
247
    void *head() const  {return n!=0 ? headp->item : NULL;}
248
249
    /**
250
     * Returns the last item in the list, or NULL pointer if the list
251
     * is empty.
252
     */
253
    void *tail() const  {return n!=0 ? tailp->item : NULL;}
254
255
    /**
256
     * Unlinks and returns the given item. If the item is not in the list,
257
     * cRuntimeError is thrown.
258
     */
259
    void *remove(void *item);
260
261
    /**
262
     * Unlinks and returns the last item in the list. If the list is empty,
263
     * cRuntimeError is thrown.
264
     */
265
    void *pop();
266
267
    /**
268
     * Returns the number of items contained in the list.
269
     */
270
    int getLength() const {return n;}
271
272
    /**
273
     * Returns true if the list is empty.
274
     */
275
    bool isEmpty() const {return n==0;}
276
277
    /**
278
     * Alias for getLength().
279
     */
280
    int length() const {return getLength();}
281
282
    /**
283
     * Alias for isEmpty().
284
     */
285
    bool empty() const {return isEmpty();}
286
287
    /**
288
     * Returns true if the list contains the given pointer.
289
     */
290
    bool contains(void *item) const  {return find_llelem(item)!=NULL;}
291
292
    /**
293
     * As a result, the container will be empty. Contained items will
294
     * be deleted as configured by configPointer().
295
     */
296
    void clear();
297
    //@}
298
};
299
300
#ifdef _MSC_VER
301
#pragma warning(pop)
302
#endif
303
304
305
NAMESPACE_END
306
307
308
#endif