dep/ACE_wrappers/ace/Unbounded_Queue.cpp

   1 // $Id: Unbounded_Queue.cpp 80826 2008-03-04 14:51:23Z wotte $
   2
   3 #ifndef ACE_UNBOUNDED_QUEUE_CPP
   4 #define ACE_UNBOUNDED_QUEUE_CPP
   5
   6 #include "ace/Unbounded_Queue.h"
   7
   8 #if !defined (ACE_LACKS_PRAGMA_ONCE)
   9 # pragma once
  10 #endif /* ACE_LACKS_PRAGMA_ONCE */
  11
  12 #if !defined (__ACE_INLINE__)
  13 #include "ace/Unbounded_Queue.inl"
  14 #endif /* __ACE_INLINE__ */
  15
  16 #include "ace/Malloc_Base.h"
  17 #include "ace/Log_Msg.h"
  18 #include "ace/os_include/os_errno.h"
  19
  20 ACE_BEGIN_VERSIONED_NAMESPACE_DECL
  21
  22 ACE_ALLOC_HOOK_DEFINE(ACE_Unbounded_Queue)
  23
  24 template <class T>
  25 ACE_Unbounded_Queue<T>::ACE_Unbounded_Queue (ACE_Allocator *alloc)
  26   : head_ (0),
  27     cur_size_ (0),
  28     allocator_ (alloc)
  29 {
  30   //   ACE_TRACE ("ACE_Unbounded_Queue<T>::ACE_Unbounded_Queue (void)");
  31
  32   if (this->allocator_ == 0)
  33     this->allocator_ = ACE_Allocator::instance ();
  34
  35   ACE_NEW_MALLOC (this->head_,
  36                   (ACE_Node<T> *) this->allocator_->malloc (sizeof (ACE_Node<T>)),
  37                   ACE_Node<T>);
  38   // Make the list circular by pointing it back to itself.
  39   this->head_->next_ = this->head_;
  40 }
  41
  42 template <class T>
  43 ACE_Unbounded_Queue<T>::ACE_Unbounded_Queue (const ACE_Unbounded_Queue<T> &us)
  44   : head_ (0),
  45     cur_size_ (0),
  46     allocator_ (us.allocator_)
  47 {
  48   //   ACE_TRACE ("ACE_Unbounded_Queue<T>::ACE_Unbounded_Queue");
  49
  50   if (this->allocator_ == 0)
  51     this->allocator_ = ACE_Allocator::instance ();
  52
  53   ACE_NEW_MALLOC (this->head_,
  54                   (ACE_Node<T> *) this->allocator_->malloc (sizeof (ACE_Node<T>)),
  55                   ACE_Node<T>);
  56   this->head_->next_ = this->head_;
  57   this->copy_nodes (us);
  58 }
  59
  60 template <class T> void
  61 ACE_Unbounded_Queue<T>::operator= (const ACE_Unbounded_Queue<T> &us)
  62 {
  63   //   ACE_TRACE ("ACE_Unbounded_Queue<T>::operator=");
  64
  65   if (this != &us)
  66     {
  67       this->delete_nodes ();
  68       this->copy_nodes (us);
  69     }
  70 }
  71
  72 template <class T> ACE_Unbounded_Queue_Iterator<T>
  73 ACE_Unbounded_Queue<T>::begin (void)
  74 {
  75   // ACE_TRACE ("ACE_Unbounded_Queue<T>::begin");
  76   return ACE_Unbounded_Queue_Iterator<T> (*this);
  77 }
  78
  79 template <class T> ACE_Unbounded_Queue_Iterator<T>
  80 ACE_Unbounded_Queue<T>::end (void)
  81 {
  82   // ACE_TRACE ("ACE_Unbounded_Queue<T>::end");
  83   return ACE_Unbounded_Queue_Iterator<T> (*this, 1);
  84 }
  85
  86 template <class T> void
  87 ACE_Unbounded_Queue<T>::dump (void) const
  88 {
  89 #if defined (ACE_HAS_DUMP)
  90   //   ACE_TRACE ("ACE_Unbounded_Queue<T>::dump");
  91
  92   ACE_DEBUG ((LM_DEBUG, ACE_BEGIN_DUMP, this));
  93   ACE_DEBUG ((LM_DEBUG,  ACE_TEXT ("\nhead_ = %u"), this->head_));
  94   ACE_DEBUG ((LM_DEBUG,  ACE_TEXT ("\nhead_->next_ = %u"), this->head_->next_));
  95   ACE_DEBUG ((LM_DEBUG,  ACE_TEXT ("\ncur_size_ = %d\n"), this->cur_size_));
  96
  97   T *item = 0;
  98 #if !defined (ACE_NLOGGING)
  99   size_t count = 1;
 100 #endif /* ! ACE_NLOGGING */
 101
 102   for (ACE_Unbounded_Queue_Iterator<T> iter (*(ACE_Unbounded_Queue<T> *) this);
 103        iter.next (item) != 0;
 104        iter.advance ())
 105     ACE_DEBUG ((LM_DEBUG, ACE_TEXT ("count = %d\n"), count++));
 106
 107   ACE_DEBUG ((LM_DEBUG, ACE_END_DUMP));
 108 #endif /* ACE_HAS_DUMP */
 109 }
 110
 111 template <class T> void
 112 ACE_Unbounded_Queue<T>::copy_nodes (const ACE_Unbounded_Queue<T> &us)
 113 {
 114   for (ACE_Node<T> *curr = us.head_->next_;
 115        curr != us.head_;
 116        curr = curr->next_)
 117     if (this->enqueue_tail (curr->item_) == -1)
 118       // @@ What's the right thing to do here?
 119       this->delete_nodes ();
 120 }
 121
 122 template <class T> void
 123 ACE_Unbounded_Queue<T>::delete_nodes (void)
 124 {
 125   for (ACE_Node<T> *curr = this->head_->next_;
 126        // Keep looking until we've hit the dummy node.
 127        curr != this->head_;
 128        )
 129     {
 130       ACE_Node<T> *temp = curr;
 131       curr = curr->next_;
 132
 133       ACE_DES_FREE_TEMPLATE (temp,
 134                              this->allocator_->free,
 135                              ACE_Node,
 136                              <T>);
 137       --this->cur_size_;
 138       // @@ Doesnt make sense to have this check since
 139       // this will always be true.
 140       //   ACE_ASSERT (this->cur_size_ >= 0);
 141     }
 142
 143   // Reset the list to be a circular list with just a dummy node.
 144   this->head_->next_ = this->head_;
 145 }
 146
 147 template <class T>
 148 ACE_Unbounded_Queue<T>::~ACE_Unbounded_Queue (void)
 149 {
 150   //   ACE_TRACE ("ACE_Unbounded_Queue<T>::~ACE_Unbounded_Queue (void)");
 151
 152   this->delete_nodes ();
 153   ACE_DES_FREE_TEMPLATE (head_,
 154                          this->allocator_->free,
 155                          ACE_Node,
 156                          <T>);
 157   this->head_ = 0;
 158 }
 159
 160 template <class T> int
 161 ACE_Unbounded_Queue<T>::enqueue_head (const T &new_item)
 162 {
 163   //   ACE_TRACE ("ACE_Unbounded_Queue<T>::enqueue_head");
 164
 165   ACE_Node<T> *temp = 0;
 166
 167   // Create a new node that points to the original head.
 168   ACE_NEW_MALLOC_RETURN (temp,
 169                          static_cast<ACE_Node<T> *> (this->allocator_->malloc (sizeof (ACE_Node<T>))),
 170                          ACE_Node<T> (new_item, this->head_->next_),
 171                          -1);
 172   // Link this pointer into the front of the list.  Note that the
 173   // "real" head of the queue is <head_->next_>, whereas <head_> is
 174   // just a pointer to the dummy node.
 175   this->head_->next_ = temp;
 176
 177   ++this->cur_size_;
 178   return 0;
 179 }
 180
 181 template <class T> int
 182 ACE_Unbounded_Queue<T>::enqueue_tail (const T &new_item)
 183 {
 184   //   ACE_TRACE ("ACE_Unbounded_Queue<T>::enqueue_tail");
 185
 186   // Insert <item> into the old dummy node location.  Note that this
 187   // isn't actually the "head" item in the queue, it's a dummy node at
 188   // the "tail" of the queue...
 189   this->head_->item_ = new_item;
 190
 191   ACE_Node<T> *temp = 0;
 192
 193   // Create a new dummy node.
 194   ACE_NEW_MALLOC_RETURN (temp,
 195                          static_cast<ACE_Node<T> *> (this->allocator_->malloc (sizeof (ACE_Node<T>))),
 196                          ACE_Node<T> (this->head_->next_),
 197                          -1);
 198   // Link this dummy pointer into the list.
 199   this->head_->next_ = temp;
 200
 201   // Point the head to the new dummy node.
 202   this->head_ = temp;
 203
 204   ++this->cur_size_;
 205   return 0;
 206 }
 207
 208 template <class T> int
 209 ACE_Unbounded_Queue<T>::dequeue_head (T &item)
 210 {
 211   //   ACE_TRACE ("ACE_Unbounded_Queue<T>::dequeue_head");
 212
 213   // Check for empty queue.
 214   if (this->is_empty ())
 215     return -1;
 216
 217   ACE_Node<T> *temp = this->head_->next_;
 218
 219   item = temp->item_;
 220   this->head_->next_ = temp->next_;
 221   ACE_DES_FREE_TEMPLATE (temp,
 222                          this->allocator_->free,
 223                          ACE_Node,
 224                          <T>);
 225   --this->cur_size_;
 226   return 0;
 227 }
 228
 229 template <class T> void
 230 ACE_Unbounded_Queue<T>::reset (void)
 231 {
 232   ACE_TRACE ("reset");
 233
 234   this->delete_nodes ();
 235 }
 236
 237 template <class T> int
 238 ACE_Unbounded_Queue<T>::get (T *&item, size_t slot) const
 239 {
 240   //   ACE_TRACE ("ACE_Unbounded_Queue<T>::get");
 241
 242   ACE_Node<T> *curr = this->head_->next_;
 243
 244   size_t i;
 245
 246   for (i = 0; i < this->cur_size_; i++)
 247     {
 248       if (i == slot)
 249         break;
 250
 251       curr = curr->next_;
 252     }
 253
 254   if (i < this->cur_size_)
 255     {
 256       item = &curr->item_;
 257       return 0;
 258     }
 259   else
 260     return -1;
 261 }
 262
 263 template <class T> int
 264 ACE_Unbounded_Queue<T>::set (const T &item,
 265                              size_t slot)
 266 {
 267   //   ACE_TRACE ("ACE_Unbounded_Queue<T>::set");
 268
 269   ACE_Node<T> *curr = this->head_->next_;
 270
 271   size_t i;
 272
 273   for (i = 0;
 274        i < slot && i < this->cur_size_;
 275        ++i)
 276     curr = curr->next_;
 277
 278   if (i < this->cur_size_)
 279     {
 280       // We're in range, so everything's cool.
 281       curr->item_ = item;
 282       return 0;
 283     }
 284   else
 285     {
 286       // We need to expand the list.
 287
 288       // A common case will be increasing the set size by 1.
 289       // Therefore, we'll optimize for this case.
 290       if (i == slot)
 291         {
 292           // Try to expand the size of the set by 1.
 293           if (this->enqueue_tail (item) == -1)
 294             return -1;
 295           else
 296             return 0;
 297         }
 298       else
 299         {
 300           T const dummy = T ();
 301
 302           // We need to expand the list by multiple (dummy) items.
 303           for (; i < slot; ++i)
 304             {
 305               // This head points to the existing dummy node, which is
 306               // about to be overwritten when we add the new dummy
 307               // node.
 308               curr = this->head_;
 309
 310               // Try to expand the size of the set by 1, but don't
 311               // store anything in the dummy node (yet).
 312               if (this->enqueue_tail (dummy) == -1)
 313                 return -1;
 314             }
 315
 316           curr->item_ = item;
 317           return 0;
 318         }
 319     }
 320 }
 321
 322 // ****************************************************************
 323
 324 template <class T> void
 325 ACE_Unbounded_Queue_Const_Iterator<T>::dump (void) const
 326 {
 327 #if defined (ACE_HAS_DUMP)
 328   // ACE_TRACE ("ACE_Unbounded_Queue_Const_Iterator<T>::dump");
 329 #endif /* ACE_HAS_DUMP */
 330 }
 331
 332 template <class T>
 333 ACE_Unbounded_Queue_Const_Iterator<T>::ACE_Unbounded_Queue_Const_Iterator (const ACE_Unbounded_Queue<T> &q, int end)
 334   : current_ (end == 0 ? q.head_->next_ : q.head_ ),
 335     queue_ (q)
 336 {
 337   // ACE_TRACE ("ACE_Unbounded_Queue_Const_Iterator<T>::ACE_Unbounded_Queue_Const_Iterator");
 338 }
 339
 340 template <class T> int
 341 ACE_Unbounded_Queue_Const_Iterator<T>::advance (void)
 342 {
 343   // ACE_TRACE ("ACE_Unbounded_Queue_Const_Iterator<T>::advance");
 344   this->current_ = this->current_->next_;
 345   return this->current_ != this->queue_.head_;
 346 }
 347
 348 template <class T> int
 349 ACE_Unbounded_Queue_Const_Iterator<T>::first (void)
 350 {
 351   // ACE_TRACE ("ACE_Unbounded_Queue_Const_Iterator<T>::first");
 352   this->current_ = this->queue_.head_->next_;
 353   return this->current_ != this->queue_.head_;
 354 }
 355
 356 template <class T> int
 357 ACE_Unbounded_Queue_Const_Iterator<T>::done (void) const
 358 {
 359   ACE_TRACE ("ACE_Unbounded_Queue_Const_Iterator<T>::done");
 360
 361   return this->current_ == this->queue_.head_;
 362 }
 363
 364 template <class T> int
 365 ACE_Unbounded_Queue_Const_Iterator<T>::next (T *&item)
 366 {
 367   // ACE_TRACE ("ACE_Unbounded_Queue_Const_Iterator<T>::next");
 368   if (this->current_ == this->queue_.head_)
 369     return 0;
 370   else
 371     {
 372       item = &this->current_->item_;
 373       return 1;
 374     }
 375 }
 376
 377 // ****************************************************************
 378
 379 template <class T> void
 380 ACE_Unbounded_Queue_Iterator<T>::dump (void) const
 381 {
 382 #if defined (ACE_HAS_DUMP)
 383   // ACE_TRACE ("ACE_Unbounded_Queue_Iterator<T>::dump");
 384 #endif /* ACE_HAS_DUMP */
 385 }
 386
 387 template <class T>
 388 ACE_Unbounded_Queue_Iterator<T>::ACE_Unbounded_Queue_Iterator (ACE_Unbounded_Queue<T> &q, int end)
 389   : current_ (end == 0 ? q.head_->next_ : q.head_ ),
 390     queue_ (q)
 391 {
 392   // ACE_TRACE ("ACE_Unbounded_Queue_Iterator<T>::ACE_Unbounded_Queue_Iterator");
 393 }
 394
 395 template <class T> int
 396 ACE_Unbounded_Queue_Iterator<T>::advance (void)
 397 {
 398   // ACE_TRACE ("ACE_Unbounded_Queue_Iterator<T>::advance");
 399   this->current_ = this->current_->next_;
 400   return this->current_ != this->queue_.head_;
 401 }
 402
 403 template <class T> int
 404 ACE_Unbounded_Queue_Iterator<T>::first (void)
 405 {
 406   // ACE_TRACE ("ACE_Unbounded_Queue_Iterator<T>::first");
 407   this->current_ = this->queue_.head_->next_;
 408   return this->current_ != this->queue_.head_;
 409 }
 410
 411 template <class T> int
 412 ACE_Unbounded_Queue_Iterator<T>::done (void) const
 413 {
 414   ACE_TRACE ("ACE_Unbounded_Queue_Iterator<T>::done");
 415
 416   return this->current_ == this->queue_.head_;
 417 }
 418
 419 template <class T> int
 420 ACE_Unbounded_Queue_Iterator<T>::next (T *&item)
 421 {
 422   // ACE_TRACE ("ACE_Unbounded_Queue_Iterator<T>::next");
 423   if (this->current_ == this->queue_.head_)
 424     return 0;
 425   else
 426     {
 427       item = &this->current_->item_;
 428       return 1;
 429     }
 430 }
 431
 432 ACE_END_VERSIONED_NAMESPACE_DECL
 433
 434 #endif /* ACE_UNBOUNDED_QUEUE_CPP */