ACE/ace/Unbounded_Queue.h

   1 // -*- C++ -*-
   2
   3 //=============================================================================
   4 /**
   5  *  @file Unbounded_Queue.h
   6  *
   7  *  @author Douglas C. Schmidt <d.schmidt@vanderbilt.edu>
   8  */
   9 //=============================================================================
  10
  11 #ifndef ACE_UNBOUNDED_QUEUE_H
  12 #define ACE_UNBOUNDED_QUEUE_H
  13 #include /**/ "ace/pre.h"
  14
  15 #include "ace/Node.h"
  16
  17 #if !defined (ACE_LACKS_PRAGMA_ONCE)
  18 # pragma once
  19 #endif /* ACE_LACKS_PRAGMA_ONCE */
  20
  21 #include "ace/os_include/os_stddef.h"
  22
  23 ACE_BEGIN_VERSIONED_NAMESPACE_DECL
  24
  25 class ACE_Allocator;
  26
  27 template <class T>
  28 class ACE_Unbounded_Queue;
  29
  30 /**
  31  * @class ACE_Unbounded_Queue_Iterator
  32  *
  33  * @brief Implement an iterator over an unbounded queue.
  34  */
  35 template <class T>
  36 class ACE_Unbounded_Queue_Iterator
  37 {
  38 public:
  39   ACE_Unbounded_Queue_Iterator (ACE_Unbounded_Queue<T> &q, int end = 0);
  40
  41   // = Iteration methods.
  42
  43   /// Pass back the @a next_item that hasn't been seen in the queue.
  44   /// Returns 0 when all items have been seen, else 1.
  45   int next (T *&next_item);
  46
  47   /// Move forward by one element in the set.  Returns 0 when all the
  48   /// items in the queue have been seen, else 1.
  49   int advance ();
  50
  51   /// Move to the first element in the queue.  Returns 0 if the
  52   /// queue is empty, else 1.
  53   int first ();
  54
  55   /// Returns 1 when all items have been seen, else 0.
  56   int done () const;
  57
  58   /// Dump the state of an object.
  59   void dump () const;
  60
  61   /// Declare the dynamic allocation hooks.
  62   ACE_ALLOC_HOOK_DECLARE;
  63
  64 private:
  65   /// Pointer to the current node in the iteration.
  66   ACE_Node<T> *current_;
  67
  68   /// Pointer to the queue we're iterating over.
  69   ACE_Unbounded_Queue<T> &queue_;
  70 };
  71
  72 /**
  73  * @class ACE_Unbounded_Queue_Const_Iterator
  74  *
  75  * @brief Implement an iterator over an const unbounded queue.
  76  */
  77 template <class T>
  78 class ACE_Unbounded_Queue_Const_Iterator
  79 {
  80 public:
  81   ACE_Unbounded_Queue_Const_Iterator (const ACE_Unbounded_Queue<T> &q, int end = 0);
  82
  83   // = Iteration methods.
  84
  85   /// Pass back the @a next_item that hasn't been seen in the queue.
  86   /// Returns 0 when all items have been seen, else 1.
  87   int next (T *&next_item);
  88
  89   /// Move forward by one element in the set.  Returns 0 when all the
  90   /// items in the queue have been seen, else 1.
  91   int advance ();
  92
  93   /// Move to the first element in the queue.  Returns 0 if the
  94   /// queue is empty, else 1.
  95   int first ();
  96
  97   /// Returns 1 when all items have been seen, else 0.
  98   int done () const;
  99
 100   /// Dump the state of an object.
 101   void dump () const;
 102
 103   /// Declare the dynamic allocation hooks.
 104   ACE_ALLOC_HOOK_DECLARE;
 105
 106 private:
 107   /// Pointer to the current node in the iteration.
 108   ACE_Node<T> *current_;
 109
 110   /// Pointer to the queue we're iterating over.
 111   const ACE_Unbounded_Queue<T> &queue_;
 112 };
 113
 114 /**
 115  * @class ACE_Unbounded_Queue
 116  *
 117  * @brief A Queue of "infinite" length.
 118  *
 119  * This implementation of an unbounded queue uses a circular
 120  * linked list with a dummy node.
 121  *
 122  * <b> Requirements and Performance Characteristics</b>
 123  *   - Internal Structure
 124  *       Circular linked list
 125  *   - Duplicates allowed?
 126  *       Yes
 127  *   - Random access allowed?
 128  *       No
 129  *   - Search speed
 130  *       N/A
 131  *   - Insert/replace speed
 132  *       N/A
 133  *   - Iterator still valid after change to container?
 134  *       Yes
 135  *   - Frees memory for removed elements?
 136  *       Yes
 137  *   - Items inserted by
 138  *       Value
 139  *   - Requirements for contained type
 140  *       -# Default constructor
 141  *       -# Copy constructor
 142  *       -# operator=
 143  */
 144 template <class T>
 145 class ACE_Unbounded_Queue
 146 {
 147 public:
 148   friend class ACE_Unbounded_Queue_Iterator<T>;
 149   friend class ACE_Unbounded_Queue_Const_Iterator<T>;
 150
 151   // Trait definition.
 152   typedef ACE_Unbounded_Queue_Iterator<T> ITERATOR;
 153   typedef ACE_Unbounded_Queue_Const_Iterator<T> CONST_ITERATOR;
 154
 155   /// Construction.  Use user specified allocation strategy
 156   /// if specified.
 157   /**
 158    * Initialize an empty queue using the strategy provided.
 159    */
 160   ACE_Unbounded_Queue (ACE_Allocator *alloc = nullptr);
 161
 162   /// Copy constructor.
 163   /**
 164    * Initialize the queue to be a copy of the provided queue.
 165    */
 166   ACE_Unbounded_Queue (const ACE_Unbounded_Queue<T> &);
 167
 168   /// Assignment operator.
 169   /**
 170    * Perform a deep copy of rhs.
 171    */
 172   void operator= (const ACE_Unbounded_Queue<T> &);
 173
 174   /// Destructor.
 175   /**
 176    * Clean up the memory for the queue.
 177    */
 178   ~ACE_Unbounded_Queue ();
 179
 180   // = Check boundary conditions.
 181
 182   /// Returns true if the container is empty, otherwise returns false.
 183   /**
 184    * Constant time check to see if the queue is empty.
 185    */
 186   bool is_empty () const;
 187
 188   /// Returns 0.
 189   /**
 190    * The queue cannot be full, so it always returns 0.
 191    */
 192   bool is_full () const;
 193
 194   // = Classic queue operations.
 195
 196   /// Adds @a new_item to the tail of the queue.  Returns 0 on success,
 197   /// -1 on failure.
 198   /**
 199    * Insert an item at the end of the queue.
 200    */
 201   int enqueue_tail (const T &new_item);
 202
 203   /// Adds @a new_item to the head of the queue.  Returns 0 on success,
 204   /// -1 on failure.
 205   /**
 206    * Insert an item at the head of the queue.
 207    */
 208   int enqueue_head (const T &new_item);
 209
 210   /// Removes and returns the first @a item on the queue.  Returns 0 on
 211   /// success, -1 if the queue was empty.
 212   /**
 213    * Remove an item from the head of the queue.
 214    */
 215   int dequeue_head (T &item);
 216
 217   // = Additional utility methods.
 218
 219   /// Reset the ACE_Unbounded_Queue to be empty and release all its
 220   /// dynamically allocated resources.
 221   /**
 222    * Delete the queue nodes.
 223    */
 224   void reset ();
 225
 226   /// Get the @a slot th element in the set.  Returns -1 if the element
 227   /// isn't in the range {0..#cur_size_ - 1}, else 0.
 228   /**
 229    * Find the item in the queue between 0 and the provided index of the
 230    * queue.
 231    */
 232   int get (T *&item, size_t slot = 0) const;
 233
 234   /// Set the @a slot th element of the queue to @a item.
 235   /**
 236    * Set the @a slot th element in the set.  Will pad out the set with
 237    * empty nodes if @a slot is beyond the range {0..#cur_size_ - 1}.
 238    * Returns -1 on failure, 0 if @a slot isn't initially in range, and
 239    * 0 otherwise.
 240    */
 241   int set (const T &item, size_t slot);
 242
 243   /// The number of items in the queue.
 244   /**
 245    * Return the size of the queue.
 246    */
 247   size_t size () const;
 248
 249   /// Dump the state of an object.
 250   void dump () const;
 251
 252   // = STL-styled unidirectional iterator factory.
 253   ACE_Unbounded_Queue_Iterator<T> begin ();
 254   ACE_Unbounded_Queue_Iterator<T> end ();
 255
 256   /// Declare the dynamic allocation hooks.
 257   ACE_ALLOC_HOOK_DECLARE;
 258
 259 protected:
 260   /// Delete all the nodes in the queue.
 261   void delete_nodes ();
 262
 263   /// Copy nodes into this queue.
 264   void copy_nodes (const ACE_Unbounded_Queue<T> &);
 265
 266   /// Pointer to the dummy node in the circular linked Queue.
 267   ACE_Node<T> *head_;
 268
 269   /// Current size of the queue.
 270   size_t cur_size_;
 271
 272   /// Allocation Strategy of the queue.
 273   ACE_Allocator *allocator_;
 274 };
 275
 276 ACE_END_VERSIONED_NAMESPACE_DECL
 277
 278 #if defined (__ACE_INLINE__)
 279 #include "ace/Unbounded_Queue.inl"
 280 #endif /* __ACE_INLINE__ */
 281
 282 #include "ace/Unbounded_Queue.cpp"
 283
 284 #include /**/ "ace/post.h"
 285 #endif /* ACE_UNBOUNDED_QUEUE_H */