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
|
/* -*- C++ -*- */
//=============================================================================
/**
* @file Unbounded_Queue.h
*
* $Id$
*
* @author Doug Schmidt
*/
//=============================================================================
#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 */
// For size_t under Chorus
#include "ace/OS_Memory.h"
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:
// = Initialization method.
ACE_Unbounded_Queue_Iterator (ACE_Unbounded_Queue<T> &q, int end = 0);
// = Iteration methods.
/// Pass back the <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
*
* @brief A Queue of "infinite" length.
*
* This implementation of an unbounded queue uses a circular
* linked list with a dummy node.
*/
template <class T>
class ACE_Unbounded_Queue
{
public:
friend class ACE_Unbounded_Queue_Iterator<T>;
// Trait definition.
typedef ACE_Unbounded_Queue_Iterator<T> ITERATOR;
// = Initialization and termination methods.
/// construction. Use user specified allocation strategy
/// if specified.
ACE_Unbounded_Queue (ACE_Allocator *alloc = 0);
/// Copy constructor.
ACE_Unbounded_Queue (const ACE_Unbounded_Queue<T> &);
/// Assignment operator.
void operator= (const ACE_Unbounded_Queue<T> &);
/// Destructor.
~ACE_Unbounded_Queue (void);
// = Check boundary conditions.
/// Returns 1 if the container is empty, otherwise returns 0.
int is_empty (void) const;
/// Returns 1 if the container is full, otherwise returns 0.
int is_full (void) const;
// = Classic queue operations.
/// Adds <new_item> to the tail of the queue. Returns 0 on success,
/// -1 on failure.
int enqueue_tail (const T &new_item);
/// Adds <new_item> to the head of the queue. Returns 0 on success,
/// -1 on failure.
int enqueue_head (const T &new_item);
/// Removes and returns the first <item> on the queue. Returns 0 on
/// success, -1 if the queue was empty.
int dequeue_head (T &item);
// = Additional utility methods.
/// Reset the <ACE_Unbounded_Queue> to be empty and release all its
/// dynamically allocated resources.
void reset (void);
/// Get the <slot>th element in the set. Returns -1 if the element
/// isn't in the range {0..<size> - 1}, else 0.
int get (T *&item, size_t slot = 0) const;
/**
* Set the <slot>th element in the set. Will pad out the set with
* empty nodes if <slot> is beyond the range {0..<size> - 1}.
* Returns -1 on failure, 0 if <slot> isn't initially in range, and
* 0 otherwise.
*/
int set (const T &item, size_t slot);
/// The number of items in 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_;
};
#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 */
|
