dep/ACE_wrappers/ace/Unbounded_Queue.h

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