summaryrefslogtreecommitdiff
path: root/ACE/ace/Unbounded_Queue.h
blob: cb0c748f9df41391d8febff08c462c012a5d38f9 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
// -*- C++ -*-

//=============================================================================
/**
 *  @file Unbounded_Queue.h
 *
 *  @author Douglas C. Schmidt <d.schmidt@vanderbilt.edu>
 */
//=============================================================================

#ifndef ACE_UNBOUNDED_QUEUE_H
#define ACE_UNBOUNDED_QUEUE_H
#include /**/ "ace/pre.h"

#include "ace/Node.h"

#if !defined (ACE_LACKS_PRAGMA_ONCE)
# pragma once
#endif /* ACE_LACKS_PRAGMA_ONCE */

#include "ace/os_include/os_stddef.h"

ACE_BEGIN_VERSIONED_NAMESPACE_DECL

class ACE_Allocator;

template <class T>
class ACE_Unbounded_Queue;

/**
 * @class ACE_Unbounded_Queue_Iterator
 *
 * @brief Implement an iterator over an unbounded queue.
 */
template <class T>
class ACE_Unbounded_Queue_Iterator
{
public:
  ACE_Unbounded_Queue_Iterator (ACE_Unbounded_Queue<T> &q, int end = 0);

  // = Iteration methods.

  /// Pass back the @a next_item that hasn't been seen in the queue.
  /// Returns 0 when all items have been seen, else 1.
  int next (T *&next_item);

  /// Move forward by one element in the set.  Returns 0 when all the
  /// items in the queue have been seen, else 1.
  int advance (void);

  /// Move to the first element in the queue.  Returns 0 if the
  /// queue is empty, else 1.
  int first (void);

  /// Returns 1 when all items have been seen, else 0.
  int done (void) const;

  /// Dump the state of an object.
  void dump (void) const;

  /// Declare the dynamic allocation hooks.
  ACE_ALLOC_HOOK_DECLARE;

private:
  /// Pointer to the current node in the iteration.
  ACE_Node<T> *current_;

  /// Pointer to the queue we're iterating over.
  ACE_Unbounded_Queue<T> &queue_;
};

/**
 * @class ACE_Unbounded_Queue_Const_Iterator
 *
 * @brief Implement an iterator over an const unbounded queue.
 */
template <class T>
class ACE_Unbounded_Queue_Const_Iterator
{
public:
  ACE_Unbounded_Queue_Const_Iterator (const ACE_Unbounded_Queue<T> &q, int end = 0);

  // = Iteration methods.

  /// Pass back the @a next_item that hasn't been seen in the queue.
  /// Returns 0 when all items have been seen, else 1.
  int next (T *&next_item);

  /// Move forward by one element in the set.  Returns 0 when all the
  /// items in the queue have been seen, else 1.
  int advance (void);

  /// Move to the first element in the queue.  Returns 0 if the
  /// queue is empty, else 1.
  int first (void);

  /// Returns 1 when all items have been seen, else 0.
  int done (void) const;

  /// Dump the state of an object.
  void dump (void) const;

  /// Declare the dynamic allocation hooks.
  ACE_ALLOC_HOOK_DECLARE;

private:
  /// Pointer to the current node in the iteration.
  ACE_Node<T> *current_;

  /// Pointer to the queue we're iterating over.
  const ACE_Unbounded_Queue<T> &queue_;
};

/**
 * @class ACE_Unbounded_Queue
 *
 * @brief A Queue of "infinite" length.
 *
 * This implementation of an unbounded queue uses a circular
 * linked list with a dummy node.
 *
 * <b> Requirements and Performance Characteristics</b>
 *   - Internal Structure
 *       Circular linked list
 *   - Duplicates allowed?
 *       Yes
 *   - Random access allowed?
 *       No
 *   - Search speed
 *       N/A
 *   - Insert/replace speed
 *       N/A
 *   - Iterator still valid after change to container?
 *       Yes
 *   - Frees memory for removed elements?
 *       Yes
 *   - Items inserted by
 *       Value
 *   - Requirements for contained type
 *       -# Default constructor
 *       -# Copy constructor
 *       -# operator=
 */
template <class T>
class ACE_Unbounded_Queue
{
public:
  friend class ACE_Unbounded_Queue_Iterator<T>;
  friend class ACE_Unbounded_Queue_Const_Iterator<T>;

  // Trait definition.
  typedef ACE_Unbounded_Queue_Iterator<T> ITERATOR;
  typedef ACE_Unbounded_Queue_Const_Iterator<T> CONST_ITERATOR;

  /// Construction.  Use user specified allocation strategy
  /// if specified.
  /**
   * Initialize an empty queue using the strategy provided.
   */
  ACE_Unbounded_Queue (ACE_Allocator *alloc = 0);

  /// Copy constructor.
  /**
   * Initialize the queue to be a copy of the provided queue.
   */
  ACE_Unbounded_Queue (const ACE_Unbounded_Queue<T> &);

  /// Assignment operator.
  /**
   * Perform a deep copy of rhs.
   */
  void operator= (const ACE_Unbounded_Queue<T> &);

  /// Destructor.
  /**
   * Clean up the memory for the queue.
   */
  ~ACE_Unbounded_Queue (void);

  // = Check boundary conditions.

  /// Returns true if the container is empty, otherwise returns false.
  /**
   * Constant time check to see if the queue is empty.
   */
  bool is_empty (void) const;

  /// Returns 0.
  /**
   * The queue cannot be full, so it always returns 0.
   */
  bool is_full (void) const;

  // = Classic queue operations.

  /// Adds @a new_item to the tail of the queue.  Returns 0 on success,
  /// -1 on failure.
  /**
   * Insert an item at the end of the queue.
   */
  int enqueue_tail (const T &new_item);

  /// Adds @a new_item to the head of the queue.  Returns 0 on success,
  /// -1 on failure.
  /**
   * Insert an item at the head of the queue.
   */
  int enqueue_head (const T &new_item);

  /// Removes and returns the first @a item on the queue.  Returns 0 on
  /// success, -1 if the queue was empty.
  /**
   * Remove an item from the head of the queue.
   */
  int dequeue_head (T &item);

  // = Additional utility methods.

  /// Reset the ACE_Unbounded_Queue to be empty and release all its
  /// dynamically allocated resources.
  /**
   * Delete the queue nodes.
   */
  void reset (void);

  /// Get the @a slot th element in the set.  Returns -1 if the element
  /// isn't in the range {0..#cur_size_ - 1}, else 0.
  /**
   * Find the item in the queue between 0 and the provided index of the
   * queue.
   */
  int get (T *&item, size_t slot = 0) const;

  /// Set the @a slot th element of the queue to @a item.
  /**
   * Set the @a slot th element in the set.  Will pad out the set with
   * empty nodes if @a slot is beyond the range {0..#cur_size_ - 1}.
   * Returns -1 on failure, 0 if @a slot isn't initially in range, and
   * 0 otherwise.
   */
  int set (const T &item, size_t slot);

  /// The number of items in the queue.
  /**
   * Return the size of the queue.
   */
  size_t size (void) const;

  /// Dump the state of an object.
  void dump (void) const;

  // = STL-styled unidirectional iterator factory.
  ACE_Unbounded_Queue_Iterator<T> begin (void);
  ACE_Unbounded_Queue_Iterator<T> end (void);

  /// Declare the dynamic allocation hooks.
  ACE_ALLOC_HOOK_DECLARE;

protected:
  /// Delete all the nodes in the queue.
  void delete_nodes (void);

  /// Copy nodes into this queue.
  void copy_nodes (const ACE_Unbounded_Queue<T> &);

  /// Pointer to the dummy node in the circular linked Queue.
  ACE_Node<T> *head_;

  /// Current size of the queue.
  size_t cur_size_;

  /// Allocation Strategy of the queue.
  ACE_Allocator *allocator_;
};

ACE_END_VERSIONED_NAMESPACE_DECL

#if defined (__ACE_INLINE__)
#include "ace/Unbounded_Queue.inl"
#endif /* __ACE_INLINE__ */

#if defined (ACE_TEMPLATES_REQUIRE_SOURCE)
#include "ace/Unbounded_Queue.cpp"
#endif /* ACE_TEMPLATES_REQUIRE_SOURCE */

#if defined (ACE_TEMPLATES_REQUIRE_PRAGMA)
#pragma implementation ("Unbounded_Queue.cpp")
#endif /* ACE_TEMPLATES_REQUIRE_PRAGMA */

#include /**/ "ace/post.h"
#endif /* ACE_UNBOUNDED_QUEUE_H */