00001 // -*- C++ -*- 00002 00003 //============================================================================= 00004 /** 00005 * @file Containers_T.h 00006 * 00007 * $Id: Containers_T.h 88975 2010-02-12 19:19:38Z johnnyw $ 00008 * 00009 * @author Douglas C. Schmidt <schmidt@cs.wustl.edu> 00010 */ 00011 //============================================================================= 00012 00013 #ifndef ACE_CONTAINERS_T_H 00014 #define ACE_CONTAINERS_T_H 00015 00016 #include /**/ "ace/pre.h" 00017 00018 #include /**/ "ace/config-all.h" 00019 00020 #if !defined (ACE_LACKS_PRAGMA_ONCE) 00021 # pragma once 00022 #endif /* ACE_LACKS_PRAGMA_ONCE */ 00023 00024 // Need by ACE_DLList_Node. 00025 #include "ace/Containers.h" 00026 00027 // Shared with "ace/Unbounded_Set.h" 00028 #include "ace/Node.h" 00029 00030 // Backwards compatibility, please include "ace/Array_Base.h" directly. 00031 #include "ace/Array_Base.h" 00032 00033 // Backwards compatibility, please include "ace/Unbounded_Set.h" directly. 00034 #include "ace/Unbounded_Set.h" 00035 00036 // Backwards compatibility, please include "ace/Unbounded_Queue.h" directly. 00037 #include "ace/Unbounded_Queue.h" 00038 00039 ACE_BEGIN_VERSIONED_NAMESPACE_DECL 00040 00041 class ACE_Allocator; 00042 00043 00044 /** 00045 * @class ACE_Bounded_Stack 00046 * 00047 * @brief Implement a generic LIFO abstract data type. 00048 * 00049 * This implementation of a Stack uses a bounded array 00050 * that is allocated dynamically. The Stack interface 00051 * provides the standard constant time push, pop, and top 00052 * operations. 00053 * 00054 * <b> Requirements and Performance Characteristics</b> 00055 * - Internal Structure 00056 * Dynamic array 00057 * - Duplicates allowed? 00058 * Yes 00059 * - Random access allowed? 00060 * No 00061 * - Search speed 00062 * N/A 00063 * - Insert/replace speed 00064 * N/A 00065 * - Iterator still valid after change to container? 00066 * N/A 00067 * - Frees memory for removed elements? 00068 * No 00069 * - Items inserted by 00070 * Value 00071 * - Requirements for contained type 00072 * -# Default constructor 00073 * -# Copy constructor 00074 * -# operator= 00075 * 00076 */ 00077 template <class T> 00078 class ACE_Bounded_Stack 00079 { 00080 public: 00081 // = Initialization, assignment, and termination methods. 00082 00083 /// Initialize a new empty stack with the provided size.. 00084 /** 00085 * Initialize and allocate space for a new Bounded_Stack with the provided 00086 * size. 00087 */ 00088 ACE_Bounded_Stack (size_t size); 00089 00090 /// Initialize the stack to be a copy of the stack provided. 00091 /** 00092 * Initialize the stack to be an exact copy of the Bounded_Stack provided 00093 * as a parameter. 00094 */ 00095 ACE_Bounded_Stack (const ACE_Bounded_Stack<T> &s); 00096 00097 /// Assignment operator 00098 /** 00099 * Perform a deep copy operation using the Bounded_Stack parameter. If the 00100 * capacity of the lhs isn't sufficient for the rhs, then the underlying data 00101 * structure will be reallocated to accomadate the larger number of elements. 00102 */ 00103 void operator= (const ACE_Bounded_Stack<T> &s); 00104 00105 /// Perform actions needed when stack goes out of scope. 00106 /** 00107 * Deallocate the memory used by the Bounded_Stack. 00108 */ 00109 ~ACE_Bounded_Stack (void); 00110 00111 // = Classic Stack operations. 00112 00113 ///Add an element to the top of the stack. 00114 /** 00115 * Place a new item on top of the stack. Returns -1 if the stack 00116 * is already full, 0 if the stack is not already full, and -1 if 00117 * failure occurs. 00118 */ 00119 int push (const T &new_item); 00120 00121 ///Remove an item from the top of stack. 00122 /** 00123 * Remove and return the top stack item. Returns -1 if the stack is 00124 * already empty, 0 if the stack is not already empty, and -1 if 00125 * failure occurs. 00126 */ 00127 int pop (T &item); 00128 00129 ///Examine the contents of the top of stack. 00130 /** 00131 * Return top stack item without removing it. Returns -1 if the 00132 * stack is already empty, 0 if the stack is not already empty, and 00133 * -1 if failure occurs. 00134 */ 00135 int top (T &item) const; 00136 00137 // = Check boundary conditions. 00138 00139 /// Returns 1 if the container is empty, otherwise returns 0. 00140 /** 00141 * Performs constant time check to determine if the stack is empty. 00142 */ 00143 int is_empty (void) const; 00144 00145 /// Returns 1 if the container is full, otherwise returns 0. 00146 /** 00147 * Performs constant time check to determine if the stack is at capacity. 00148 */ 00149 int is_full (void) const; 00150 00151 /// The number of items in the stack. 00152 /** 00153 * Return the number of items currently in the stack. 00154 */ 00155 size_t size (void) const; 00156 00157 /// Dump the state of an object. 00158 void dump (void) const; 00159 00160 /// Declare the dynamic allocation hooks. 00161 ACE_ALLOC_HOOK_DECLARE; 00162 00163 private: 00164 /// Size of the dynamically allocated data. 00165 size_t size_; 00166 00167 /// Keeps track of the current top of stack. 00168 size_t top_; 00169 00170 /// Holds the stack's contents. 00171 T *stack_; 00172 }; 00173 00174 //---------------------------------------- 00175 00176 00177 /** 00178 * @class ACE_Fixed_Stack 00179 * 00180 * @brief Implement a generic LIFO abstract data type. 00181 * 00182 * This implementation of a Stack uses a fixed array 00183 * with the size fixed at instantiation time. 00184 * 00185 * <b> Requirements and Performance Characteristics</b> 00186 * - Internal Structure 00187 * Fixed array 00188 * - Duplicates allowed? 00189 * Yes 00190 * - Random access allowed? 00191 * No 00192 * - Search speed 00193 * N/A 00194 * - Insert/replace speed 00195 * N/A 00196 * - Iterator still valid after change to container? 00197 * N/A 00198 * - Frees memory for removed elements? 00199 * No 00200 * - Items inserted by 00201 * Value 00202 * - Requirements for contained type 00203 * -# Default constructor 00204 * -# Copy constructor 00205 * -# operator= 00206 * 00207 */ 00208 template <class T, size_t ACE_SIZE> 00209 class ACE_Fixed_Stack 00210 { 00211 public: 00212 // = Initialization, assignment, and termination methods. 00213 /// Initialize a new stack so that it is empty. 00214 /** 00215 * Initialize an empty stack. 00216 */ 00217 ACE_Fixed_Stack (void); 00218 00219 /// The copy constructor (performs initialization). 00220 /** 00221 * Initialize the stack and copy the provided stack into the current stack. 00222 */ 00223 ACE_Fixed_Stack (const ACE_Fixed_Stack<T, ACE_SIZE> &s); 00224 00225 /// Assignment operator (performs assignment). 00226 /** 00227 * Perform a deep copy of the provided stack. 00228 */ 00229 void operator= (const ACE_Fixed_Stack<T, ACE_SIZE> &s); 00230 00231 /// Perform actions needed when stack goes out of scope. 00232 /** 00233 * Destroy the stack. 00234 */ 00235 ~ACE_Fixed_Stack (void); 00236 00237 // = Classic Stack operations. 00238 00239 ///Constant time placement of element on top of stack. 00240 /** 00241 * Place a new item on top of the stack. Returns -1 if the stack 00242 * is already full, 0 if the stack is not already full, and -1 if 00243 * failure occurs. 00244 */ 00245 int push (const T &new_item); 00246 00247 ///Constant time removal of top of stack. 00248 /** 00249 * Remove and return the top stack item. Returns -1 if the stack is 00250 * already empty, 0 if the stack is not already empty, and -1 if 00251 * failure occurs. 00252 */ 00253 int pop (T &item); 00254 00255 ///Constant time examination of top of stack. 00256 /** 00257 * Return top stack item without removing it. Returns -1 if the 00258 * stack is already empty, 0 if the stack is not already empty, and 00259 * -1 if failure occurs. 00260 */ 00261 int top (T &item) const; 00262 00263 // = Check boundary conditions. 00264 00265 /// Returns 1 if the container is empty, otherwise returns 0. 00266 /** 00267 * Performs constant time check to see if stack is empty. 00268 */ 00269 int is_empty (void) const; 00270 00271 /// Returns 1 if the container is full, otherwise returns 0. 00272 /** 00273 * Performs constant time check to see if stack is full. 00274 */ 00275 int is_full (void) const; 00276 00277 /// The number of items in the stack. 00278 /** 00279 * Constant time access to the current size of the stack. 00280 */ 00281 size_t size (void) const; 00282 00283 /// Dump the state of an object. 00284 void dump (void) const; 00285 00286 /// Declare the dynamic allocation hooks. 00287 ACE_ALLOC_HOOK_DECLARE; 00288 00289 private: 00290 /// Size of the allocated data. 00291 size_t size_; 00292 00293 /// Keeps track of the current top of stack. 00294 size_t top_; 00295 00296 /// Holds the stack's contents. 00297 T stack_[ACE_SIZE]; 00298 }; 00299 00300 //---------------------------------------- 00301 00302 template<class T> class ACE_Ordered_MultiSet; 00303 template<class T> class ACE_Ordered_MultiSet_Iterator; 00304 00305 /** 00306 * @class ACE_DNode 00307 * 00308 * @brief Implementation element in a bilinked list. 00309 */ 00310 template<class T> 00311 class ACE_DNode 00312 { 00313 friend class ACE_Ordered_MultiSet<T>; 00314 friend class ACE_Ordered_MultiSet_Iterator<T>; 00315 00316 public: 00317 00318 /// This isn't necessary, but it keeps some compilers happy. 00319 ~ACE_DNode (void); 00320 00321 private: 00322 00323 // = Initialization methods 00324 ACE_DNode (const T &i, ACE_DNode<T> *n = 0, ACE_DNode<T> *p = 0); 00325 00326 /// Pointer to next element in the list of {ACE_DNode}s. 00327 ACE_DNode<T> *next_; 00328 00329 /// Pointer to previous element in the list of {ACE_DNode}s. 00330 ACE_DNode<T> *prev_; 00331 00332 /// Current value of the item in this node. 00333 T item_; 00334 }; 00335 00336 00337 00338 /** 00339 * @class ACE_Unbounded_Stack 00340 * 00341 * @brief Implement a generic LIFO abstract data type. 00342 * 00343 * This implementation of an unbounded Stack uses a linked list. 00344 * If you use the {insert} or {remove} methods you should keep 00345 * in mind that duplicate entries aren't allowed. In general, 00346 * therefore, you should avoid the use of these methods since 00347 * they aren't really part of the ADT stack. The stack is implemented 00348 * as a doubly linked list. 00349 * 00350 * <b> Requirements and Performance Characteristics</b> 00351 * - Internal Structure 00352 * Double linked list 00353 * - Duplicates allowed? 00354 * No 00355 * - Random access allowed? 00356 * No 00357 * - Search speed 00358 * Linear 00359 * - Insert/replace speed 00360 * Linear 00361 * - Iterator still valid after change to container? 00362 * Yes 00363 * - Frees memory for removed elements? 00364 * Yes 00365 * - Items inserted by 00366 * Value 00367 * - Requirements for contained type 00368 * -# Default constructor 00369 * -# Copy constructor 00370 * -# operator= 00371 * 00372 */ 00373 template <class T> 00374 class ACE_Unbounded_Stack 00375 { 00376 public: 00377 friend class ACE_Unbounded_Stack_Iterator<T>; 00378 00379 // Trait definition. 00380 typedef ACE_Unbounded_Stack_Iterator<T> ITERATOR; 00381 00382 // = Initialization, assignment, and termination methods. 00383 /// Initialize a new stack so that it is empty. Use user defined 00384 /// allocation strategy if specified. 00385 /** 00386 * Initialize an empty stack using the user specified allocation strategy 00387 * if provided. 00388 */ 00389 ACE_Unbounded_Stack (ACE_Allocator *the_allocator = 0); 00390 00391 /// The copy constructor (performs initialization). 00392 /** 00393 * Initialize this stack to be an exact copy of {s}. 00394 */ 00395 ACE_Unbounded_Stack (const ACE_Unbounded_Stack<T> &s); 00396 00397 /// Assignment operator (performs assignment). 00398 /** 00399 * Perform a deep copy of the rhs into the lhs. 00400 */ 00401 void operator= (const ACE_Unbounded_Stack<T> &s); 00402 00403 /// Perform actions needed when stack goes out of scope. 00404 /** 00405 * Destroy the underlying list for the stack. 00406 */ 00407 ~ACE_Unbounded_Stack (void); 00408 00409 // = Classic Stack operations. 00410 00411 00412 ///Push an element onto the top of stack. 00413 /** 00414 * Place a new item on top of the stack. Returns -1 if the stack 00415 * is already full, 0 if the stack is not already full, and -1 if 00416 * failure occurs. 00417 */ 00418 int push (const T &new_item); 00419 00420 ///Pop the top element of the stack. 00421 /** 00422 * Remove and return the top stack item. Returns -1 if the stack is 00423 * already empty, 0 if the stack is not already empty, and -1 if 00424 * failure occurs. 00425 */ 00426 int pop (T &item); 00427 00428 ///Examine the top of the stack. 00429 /** 00430 * Return top stack item without removing it. Returns -1 if the 00431 * stack is already empty, 0 if the stack is not already empty, and 00432 * -1 if failure occurs. 00433 */ 00434 int top (T &item) const; 00435 00436 // = Check boundary conditions. 00437 00438 /// Returns 1 if the container is empty, otherwise returns 0. 00439 /** 00440 * Constant time check to see if the stack is empty. 00441 */ 00442 int is_empty (void) const; 00443 00444 /// Returns 1 if the container is full, otherwise returns 0. 00445 /** 00446 * Always resturns 0 since the stack is unbounded. 00447 */ 00448 int is_full (void) const; 00449 00450 // = Auxiliary methods (not strictly part of the Stack ADT). 00451 00452 ///Linear Insert of an item. 00453 /** 00454 * Insert {new_item} into the Stack at the head (but doesn't allow 00455 * duplicates). Returns -1 if failures occur, 1 if item is already 00456 * present (i.e., no duplicates are allowed), else 0. 00457 */ 00458 int insert (const T &new_item); 00459 00460 /// Remove @a item from the Stack. Returns 0 if it removes the item, 00461 /// -1 if it can't find the item, and -1 if a failure occurs. 00462 /** 00463 * Linear remove operation. 00464 */ 00465 int remove (const T &item); 00466 00467 /// Finds if @a item occurs the set. Returns 0 if finds, else -1. 00468 /** 00469 * Linear find operation. 00470 */ 00471 int find (const T &item) const; 00472 00473 /// The number of items in the stack. 00474 /** 00475 * Constant time access to the current stack size. 00476 */ 00477 size_t size (void) const; 00478 00479 /// Dump the state of an object. 00480 void dump (void) const; 00481 00482 /// Declare the dynamic allocation hooks. 00483 ACE_ALLOC_HOOK_DECLARE; 00484 00485 private: 00486 /// Delete all the nodes in the stack. 00487 void delete_all_nodes (void); 00488 00489 /// Copy all nodes from {s} to {this}. 00490 void copy_all_nodes (const ACE_Unbounded_Stack<T> &s); 00491 00492 /// Head of the linked list of Nodes. 00493 ACE_Node<T> *head_; 00494 00495 /// Current size of the stack. 00496 size_t cur_size_; 00497 00498 /// Allocation strategy of the stack. 00499 ACE_Allocator *allocator_; 00500 }; 00501 00502 /** 00503 * @class ACE_Unbounded_Stack_Iterator 00504 * 00505 * @brief Implement an iterator over an unbounded Stack. 00506 */ 00507 template <class T> 00508 class ACE_Unbounded_Stack_Iterator 00509 { 00510 public: 00511 // = Initialization method. 00512 /// Move to the first element in the {stack}. 00513 ACE_Unbounded_Stack_Iterator (ACE_Unbounded_Stack<T> &stack); 00514 00515 // = Iteration methods. 00516 00517 /// Pass back the @a next_item that hasn't been seen in the Stack. 00518 /// Returns 0 when all items have been seen, else 1. 00519 int next (T *&next_item); 00520 00521 /// Move forward by one element in the Stack. Returns 0 when all the 00522 /// items in the Stack have been seen, else 1. 00523 int advance (void); 00524 00525 /// Move to the first element in the Stack. Returns 0 if the 00526 /// Stack is empty, else 1. 00527 int first (void); 00528 00529 /// Returns 1 when all items have been seen, else 0. 00530 int done (void) const; 00531 00532 /// Dump the state of an object. 00533 void dump (void) const; 00534 00535 /// Declare the dynamic allocation hooks. 00536 ACE_ALLOC_HOOK_DECLARE; 00537 00538 private: 00539 /// Pointer to the current node in the iteration. 00540 ACE_Node<T> *current_; 00541 00542 /// Pointer to the Stack we're iterating over. 00543 ACE_Unbounded_Stack<T> &stack_; 00544 }; 00545 00546 template <class T> 00547 class ACE_Double_Linked_List; 00548 00549 /** 00550 * @class ACE_Double_Linked_List_Iterator_Base 00551 * 00552 * @brief Implements a common base class for iterators for a double 00553 * linked list ADT 00554 */ 00555 template <class T> 00556 class ACE_Double_Linked_List_Iterator_Base 00557 { 00558 public: 00559 // = Iteration methods. 00560 00561 /// Passes back the {entry} under the iterator. Returns 0 if the 00562 /// iteration has completed, otherwise 1 00563 int next (T *&) const; 00564 00565 /** 00566 * @deprecated Return the address of next (current) unvisited item in 00567 * the list. 0 if there is no more element available. 00568 */ 00569 T *next (void) const; 00570 00571 /// Returns 1 when all items have been seen, else 0. 00572 int done (void) const; 00573 00574 /// STL-like iterator dereference operator: returns a reference 00575 /// to the node underneath the iterator. 00576 T & operator* (void) const ; 00577 00578 /** 00579 * Retasks the iterator to iterate over a new 00580 * Double_Linked_List. This allows clients to reuse an iterator 00581 * without incurring the constructor overhead. If you do use this, 00582 * be aware that if there are more than one reference to this 00583 * iterator, the other "clients" may be very bothered when their 00584 * iterator changes. @@ Here be dragons. Comments? 00585 */ 00586 void reset (ACE_Double_Linked_List<T> &); 00587 00588 /// Declare the dynamic allocation hooks. 00589 ACE_ALLOC_HOOK_DECLARE; 00590 00591 protected: 00592 // = Initialization methods. 00593 00594 /// Constructor 00595 ACE_Double_Linked_List_Iterator_Base (const ACE_Double_Linked_List<T> &); 00596 00597 /// Copy constructor. 00598 ACE_Double_Linked_List_Iterator_Base (const 00599 ACE_Double_Linked_List_Iterator_Base<T> 00600 &iter); 00601 00602 // = Iteration methods. 00603 /** 00604 * Move to the first element of the list. Returns 0 if the list is 00605 * empty, else 1. 00606 * @note the head of the ACE_DLList is actually a null entry, so the 00607 * first element is actually the 2n'd entry 00608 */ 00609 int go_head (void); 00610 00611 /// Move to the last element of the list. Returns 0 if the list is 00612 /// empty, else 1. 00613 int go_tail (void); 00614 00615 /** 00616 * Check if we reach the end of the list. Can also be used to get 00617 * the *current* element in the list. Return the address of the 00618 * current item if there are still elements left , 0 if we run out 00619 * of element. 00620 */ 00621 T *not_done (void) const ; 00622 00623 /// Advance to the next element in the list. Return the address of the 00624 /// next element if there are more, 0 otherwise. 00625 T *do_advance (void); 00626 00627 /// Retreat to the previous element in the list. Return the address 00628 /// of the previous element if there are more, 0 otherwise. 00629 T *do_retreat (void); 00630 00631 /// Dump the state of an object. 00632 void dump_i (void) const; 00633 00634 /// Remember where we are. 00635 T *current_; 00636 00637 const ACE_Double_Linked_List<T> *dllist_; 00638 }; 00639 00640 /** 00641 * @class ACE_Double_Linked_List_Iterator 00642 * 00643 * @brief Implements an iterator for a double linked list ADT 00644 * 00645 * Iterate thru the double-linked list. This class provides 00646 * an interface that let users access the internal element 00647 * addresses directly. Notice {class T} must declare 00648 * ACE_Double_Linked_List<T>, 00649 * ACE_Double_Linked_List_Iterator_Base <T> and 00650 * ACE_Double_Linked_List_Iterator as friend classes and class T 00651 * should also have data members T* next_ and T* prev_. 00652 */ 00653 template <class T> 00654 class ACE_Double_Linked_List_Iterator : public ACE_Double_Linked_List_Iterator_Base <T> 00655 { 00656 public: 00657 // = Initialization method. 00658 ACE_Double_Linked_List_Iterator (const ACE_Double_Linked_List<T> &); 00659 00660 /** 00661 * Retasks the iterator to iterate over a new 00662 * Double_Linked_List. This allows clients to reuse an iterator 00663 * without incurring the constructor overhead. If you do use this, 00664 * be aware that if there are more than one reference to this 00665 * iterator, the other "clients" may be very bothered when their 00666 * iterator changes. 00667 * @@ Here be dragons. Comments? 00668 */ 00669 void reset (ACE_Double_Linked_List<T> &); 00670 00671 /// Move to the first element in the list. Returns 0 if the 00672 /// list is empty, else 1. 00673 int first (void); 00674 00675 /// Move forward by one element in the list. Returns 0 when all the 00676 /// items in the list have been seen, else 1. 00677 int advance (void); 00678 00679 /** 00680 * Advance the iterator while removing the original item from the 00681 * list. Return a pointer points to the original (removed) item. 00682 * If @a dont_remove equals false, this function behaves like {advance} 00683 * but return 0 (NULL) instead. 00684 */ 00685 T* advance_and_remove (bool dont_remove); 00686 00687 // = STL-style iteration methods 00688 00689 /// Prefix advance. 00690 ACE_Double_Linked_List_Iterator<T> & operator++ (void); 00691 00692 /// Postfix advance. 00693 ACE_Double_Linked_List_Iterator<T> operator++ (int); 00694 00695 /// Prefix reverse. 00696 ACE_Double_Linked_List_Iterator<T> & operator-- (void); 00697 00698 /// Postfix reverse. 00699 ACE_Double_Linked_List_Iterator<T> operator-- (int); 00700 00701 /// Dump the state of an object. 00702 void dump (void) const; 00703 00704 /// Declare the dynamic allocation hooks. 00705 ACE_ALLOC_HOOK_DECLARE; 00706 }; 00707 00708 /** 00709 * @class ACE_Double_Linked_List_Reverse_Iterator 00710 * 00711 * @brief Implements a reverse iterator for a double linked list ADT 00712 * 00713 * Iterate backwards over the double-linked list. This class 00714 * provide an interface that let users access the internal 00715 * element addresses directly, which seems to break the 00716 * encapsulation. Notice {class T} must declare 00717 * ACE_Double_Linked_List<T>, 00718 * ACE_Double_Linked_List_Iterator_Base <T> and 00719 * ACE_Double_Linked_List_Iterator as friend classes and class T 00720 * should also have data members T* next_ and T* prev_. 00721 */ 00722 template <class T> 00723 class ACE_Double_Linked_List_Reverse_Iterator : public ACE_Double_Linked_List_Iterator_Base <T> 00724 { 00725 public: 00726 // = Initialization method. 00727 ACE_Double_Linked_List_Reverse_Iterator (ACE_Double_Linked_List<T> &); 00728 00729 /** 00730 * Retasks the iterator to iterate over a new 00731 * Double_Linked_List. This allows clients to reuse an iterator 00732 * without incurring the constructor overhead. If you do use this, 00733 * be aware that if there are more than one reference to this 00734 * iterator, the other "clients" may be very bothered when their 00735 * iterator changes. 00736 * @@ Here be dragons. Comments? 00737 */ 00738 void reset (ACE_Double_Linked_List<T> &); 00739 00740 /// Move to the first element in the list. Returns 0 if the 00741 /// list is empty, else 1. 00742 int first (void); 00743 00744 /// Move forward by one element in the list. Returns 0 when all the 00745 /// items in the list have been seen, else 1. 00746 int advance (void); 00747 00748 /** 00749 * Advance the iterator while removing the original item from the 00750 * list. Return a pointer points to the original (removed) item. 00751 * If @a dont_remove equals false, this function behaves like {advance} 00752 * but return 0 (NULL) instead. 00753 */ 00754 T* advance_and_remove (bool dont_remove); 00755 00756 // = STL-style iteration methods 00757 00758 /// Prefix advance. 00759 ACE_Double_Linked_List_Reverse_Iterator<T> & operator++ (void); 00760 00761 /// Postfix advance. 00762 ACE_Double_Linked_List_Reverse_Iterator<T> operator++ (int); 00763 00764 /// Prefix reverse. 00765 ACE_Double_Linked_List_Reverse_Iterator<T> & operator-- (void); 00766 00767 /// Postfix reverse. 00768 ACE_Double_Linked_List_Reverse_Iterator<T> operator-- (int); 00769 00770 /// Dump the state of an object. 00771 void dump (void) const; 00772 00773 /// Declare the dynamic allocation hooks. 00774 ACE_ALLOC_HOOK_DECLARE; 00775 }; 00776 00777 00778 /** 00779 * @class ACE_Double_Linked_List 00780 * 00781 * @brief A double-linked list implementation. 00782 * 00783 * This implementation of an unbounded double-linked list uses a 00784 * circular linked list with a dummy node. It is pretty much 00785 * like the {ACE_Unbounded_Queue} except that it allows removing 00786 * of a specific element from a specific location. 00787 * Notice that this class is an implementation of a very simple 00788 * data structure. This is *NOT* a container class. You can use the 00789 * class to implement other contains classes but it is *NOT* a 00790 * general purpose container class. 00791 * The parameter class *MUST* have members T* prev and T* next 00792 * and users of this class are responsible to follow the general 00793 * rules of using double-linked lists to maintaining the list 00794 * integrity. 00795 * If you need a double linked container class, use the DLList 00796 * class which is a container but delegates to the Double_Linked_List 00797 * class. 00798 * 00799 * <b> Requirements and Performance Characteristics</b> 00800 * - Internal Structure 00801 * Double Linked List 00802 * - Duplicates allowed? 00803 * Yes 00804 * - Random access allowed? 00805 * No 00806 * - Search speed 00807 * N/A 00808 * - Insert/replace speed 00809 * Linear 00810 * - Iterator still valid after change to container? 00811 * Yes 00812 * - Frees memory for removed elements? 00813 * No 00814 * - Items inserted by 00815 * Value 00816 * - Requirements for contained type 00817 * -# Default constructor 00818 * -# Copy constructor 00819 * -# operator= 00820 * 00821 */ 00822 template <class T> 00823 class ACE_Double_Linked_List 00824 { 00825 public: 00826 friend class ACE_Double_Linked_List_Iterator_Base<T>; 00827 friend class ACE_Double_Linked_List_Iterator<T>; 00828 friend class ACE_Double_Linked_List_Reverse_Iterator<T>; 00829 00830 // Trait definition. 00831 typedef ACE_Double_Linked_List_Iterator<T> ITERATOR; 00832 typedef ACE_Double_Linked_List_Reverse_Iterator<T> REVERSE_ITERATOR; 00833 00834 // = Initialization and termination methods. 00835 /// construction. Use user specified allocation strategy 00836 /// if specified. 00837 /** 00838 * Initialize an empy list using the allocation strategy specified by the user. 00839 * If none is specified, then use default allocation strategy. 00840 */ 00841 ACE_Double_Linked_List (ACE_Allocator *the_allocator = 0); 00842 00843 /// Copy constructor. 00844 /** 00845 * Create a double linked list that is a copy of the provided 00846 * parameter. 00847 */ 00848 ACE_Double_Linked_List (const ACE_Double_Linked_List<T> &); 00849 00850 /// Assignment operator. 00851 /** 00852 * Perform a deep copy of the provided list by first deleting the nodes of the 00853 * lhs and then copying the nodes of the rhs. 00854 */ 00855 void operator= (const ACE_Double_Linked_List<T> &); 00856 00857 /// Destructor. 00858 /** 00859 * Clean up the memory allocated for the nodes of the list. 00860 */ 00861 ~ACE_Double_Linked_List (void); 00862 00863 // = Check boundary conditions. 00864 00865 /// Returns 1 if the container is empty, 0 otherwise. 00866 /** 00867 * Performs constant time check to determine if the list is empty. 00868 */ 00869 int is_empty (void) const; 00870 00871 /// The list is unbounded, so this always returns 0. 00872 /** 00873 * Since the list is unbounded, the method simply returns 0. 00874 */ 00875 int is_full (void) const; 00876 00877 // = Classic queue operations. 00878 00879 /// Adds @a new_item to the tail of the list. Returns the new item 00880 /// that was inserted. 00881 /** 00882 * Provides constant time insertion at the end of the list structure. 00883 */ 00884 T *insert_tail (T *new_item); 00885 00886 /// Adds @a new_item to the head of the list.Returns the new item that 00887 /// was inserted. 00888 /** 00889 * Provides constant time insertion at the head of the list. 00890 */ 00891 T *insert_head (T *new_item); 00892 00893 /// Removes the head of the list and returns a pointer to that item. 00894 /** 00895 * Removes and returns the first {item} in the list. Returns 00896 * internal node's address on success, 0 if the queue was empty. 00897 * This method will *not* free the internal node. 00898 */ 00899 T* delete_head (void); 00900 00901 /// Removes the tail of the list and returns a pointer to that item. 00902 /** 00903 * Removes and returns the last {item} in the list. Returns 00904 * internal nodes's address on success, 0 if the queue was 00905 * empty. This method will *not* free the internal node. 00906 */ 00907 T *delete_tail (void); 00908 00909 // = Additional utility methods. 00910 00911 ///Empty the list. 00912 /** 00913 * Reset the {ACE_Double_Linked_List} to be empty. 00914 * Notice that since no one is interested in the items within, 00915 * This operation will delete all items. 00916 */ 00917 void reset (void); 00918 00919 /// Get the {slot}th element in the set. Returns -1 if the element 00920 /// isn't in the range {0..{size} - 1}, else 0. 00921 /** 00922 * Iterates through the list to the desired index and assigns the provides pointer 00923 * with the address of the node occupying that index. 00924 */ 00925 int get (T *&item, size_t slot = 0); 00926 00927 /// The number of items in the queue. 00928 /** 00929 * Constant time call to return the current size of the list. 00930 */ 00931 size_t size (void) const; 00932 00933 /// Dump the state of an object. 00934 void dump (void) const; 00935 00936 /// Use DNode address directly. 00937 /** 00938 * Constant time removal of an item from the list using it's address. 00939 */ 00940 int remove (T *n); 00941 00942 /// Declare the dynamic allocation hooks. 00943 ACE_ALLOC_HOOK_DECLARE; 00944 00945 protected: 00946 /// Delete all the nodes in the list. 00947 /** 00948 * Removes and deallocates memory for all of the list nodes. 00949 */ 00950 void delete_nodes (void); 00951 00952 /// Copy nodes from {rhs} into this list. 00953 /** 00954 * Copy the elements of the provided list by allocated new nodes and assigning 00955 * them with the proper data. 00956 */ 00957 void copy_nodes (const ACE_Double_Linked_List<T> &rhs); 00958 00959 /// Setup header pointer. Called after we create the head node in ctor. 00960 /** 00961 * Initialize the head pointer so that the list has a dummy node. 00962 */ 00963 void init_head (void); 00964 00965 ///Constant time insert a new item into the list structure. 00966 /** 00967 * Insert a @a new_item into the list. It will be added before 00968 * or after @a old_item. Default is to insert the new item *after* 00969 * {head_}. Return 0 if succeed, -1 if error occured. 00970 */ 00971 int insert_element (T *new_item, 00972 int before = 0, 00973 T *old_item = 0); 00974 00975 ///Constant time delete an item from the list structure. 00976 /** 00977 * Remove @a item from the list. Return 0 if succeed, -1 otherwise. 00978 * Notice that this function checks if item is {head_} and either its 00979 * {next_} or {prev_} is NULL. The function resets item's {next_} and 00980 * {prev_} to 0 to prevent clobbering the double-linked list if a user 00981 * tries to remove the same node again. 00982 */ 00983 int remove_element (T *item); 00984 00985 /// Head of the circular double-linked list. 00986 T *head_; 00987 00988 /// Size of this list. 00989 size_t size_; 00990 00991 /// Allocation Strategy of the queue. 00992 ACE_Allocator *allocator_; 00993 }; 00994 00995 00996 template <class T> class ACE_DLList; 00997 template <class T> class ACE_DLList_Iterator; 00998 template <class T> class ACE_DLList_Reverse_Iterator; 00999 01000 typedef ACE_Double_Linked_List<ACE_DLList_Node> ACE_DLList_Base; 01001 01002 //typedef ACE_Double_Linked_List_Iterator <ACE_DLList_Node> 01003 // ACE_DLList_Iterator_Base; 01004 //typedef ACE_Double_Linked_List_Reverse_Iterator <ACE_DLList_Node> 01005 // ACE_DLList_Reverse_Iterator_Base; 01006 //@@ These two typedefs (inherited from James Hu's original design) 01007 // have been removed because Sun CC 4.2 had problems with it. I guess 01008 // having the DLList_Iterators inheriting from a class which is 01009 // actually a typedef leads to problems. #define'ing rather than 01010 // typedef'ing worked, but as per Carlos's reccomendation, I'm just 01011 // replacing all references to the base classes with their actual 01012 // type. Matt Braun (6/15/99) 01013 01014 /** 01015 * @class ACE_DLList 01016 * 01017 * @brief A double-linked list container class. 01018 * 01019 * ACE_DLList is a simple, unbounded container implemented using a 01020 * double-linked list. It is critical to remember that ACE_DLList inherits 01021 * from ACE_Double_Linked_List, wrapping each T pointer in a ACE_DLList_Node 01022 * object which satisfies the next/prev pointer requirements imposed by 01023 * ACE_Double_Linked_List. 01024 * 01025 * Each item inserted to an ACE_DLList is a pointer to a T object. The 01026 * caller is responsible for lifetime of the T object. ACE_DLList takes no 01027 * action on the T object; it is not copied on insertion and it is not 01028 * deleted on removal from the ACE_DLList. 01029 */ 01030 template <class T> 01031 class ACE_DLList : public ACE_DLList_Base 01032 { 01033 friend class ACE_DLList_Node; 01034 friend class ACE_Double_Linked_List_Iterator<T>; 01035 friend class ACE_DLList_Iterator<T>; 01036 friend class ACE_DLList_Reverse_Iterator<T>; 01037 01038 public: 01039 01040 /// Delegates to ACE_Double_Linked_List. 01041 void operator= (const ACE_DLList<T> &l); 01042 01043 /** 01044 * @name Queue-like insert and delete methods 01045 */ 01046 //@{ 01047 01048 /** 01049 * Insert pointer for a new item at the tail of the list. 01050 * 01051 * @return Pointer to item inserted; 0 on error. 01052 */ 01053 T *insert_tail (T *new_item); 01054 01055 /** 01056 * Insert pointer for a new item at the head of the list. 01057 * 01058 * @return Pointer to item inserted; 0 on error. 01059 */ 01060 T *insert_head (T *new_item); 01061 01062 /** 01063 * Removes the item at the head of the list and returns its pointer. 01064 * 01065 * @return Pointer to previously inserted item; 0 if the list is empty, 01066 * an error occurred, or the original pointer inserted was 0. 01067 */ 01068 T *delete_head (void); 01069 01070 /** 01071 * Removes the item at the tail of the list and returns its pointer. 01072 * 01073 * @return Pointer to previously inserted item; 0 if the list is empty, 01074 * an error occurred, or the original pointer inserted was 0. 01075 */ 01076 T *delete_tail (void); 01077 //@} 01078 01079 /** 01080 * Provide random access to any item in the list. 01081 * 01082 * @param item Receives a pointer to the T object pointer held at the 01083 * specified position in the list. 01084 * @param slot Position in the list to access. The first position is 0. 01085 * 01086 * @retval 0 Success; T pointer returned in item. 01087 * @retval -1 Error, most likely slot is outside the range of the list. 01088 */ 01089 int get (T *&item, size_t slot = 0); 01090 01091 /// Delegates to ACE_Double_Linked_List. 01092 void dump (void) const; 01093 01094 /// Delegates to ACE_Double_Linked_List. 01095 int remove (ACE_DLList_Node *n); 01096 01097 /** 01098 * Constructor. 01099 * 01100 * @param the_allocator Allocator to use for allocating ACE_DLList_Node 01101 * objects that wrap T objects for inclusion in the 01102 * list. If 0, ACE_Allocator::instance() is used. 01103 */ 01104 ACE_DLList (ACE_Allocator *the_allocator = 0); 01105 01106 /// Delegates to ACE_Double_Linked_List. 01107 ACE_DLList (const ACE_DLList<T> &l); 01108 01109 /** 01110 * Deletes all ACE_DLList_Node objects in the list starting from the head. 01111 * No T objects referred to by the deleted ACE_DLList_Node objects are 01112 * modified or freed. If you desire all of the T objects in the list to 01113 * be deleted as well, code such as this should be used prior to destroying 01114 * the ACE_DLList: 01115 * @code 01116 ACE_DLList<Item> list; 01117 ... // insert dynamically allocated Items... 01118 Item *p; 01119 while ((p = list.delete_head()) != 0) 01120 delete *p; 01121 @endcode 01122 */ 01123 ~ACE_DLList (void); 01124 }; 01125 01126 /** 01127 * @class ACE_DLList_Iterator 01128 * 01129 * @brief A double-linked list container class iterator. 01130 * 01131 * This implementation uses ACE_Double_Linked_List_Iterator to 01132 * perform the logic behind this container class. It delegates 01133 * all of its calls to ACE_Double_Linked_List_Iterator. 01134 */ 01135 template <class T> 01136 class ACE_DLList_Iterator : public ACE_Double_Linked_List_Iterator <ACE_DLList_Node> 01137 { 01138 01139 friend class ACE_DLList<T>; 01140 friend class ACE_DLList_Node; 01141 01142 public: 01143 01144 // = Initialization method. 01145 ACE_DLList_Iterator (ACE_DLList<T> &l); 01146 01147 /** 01148 * Retasks the iterator to iterate over a new 01149 * Double_Linked_List. This allows clients to reuse an iterator 01150 * without incurring the constructor overhead. If you do use this, 01151 * be aware that if there are more than one reference to this 01152 * iterator, the other "clients" may be very bothered when their 01153 * iterator changes. 01154 * @@ Here be dragons. Comments? 01155 */ 01156 void reset (ACE_DLList<T> &l); 01157 01158 // = Iteration methods. 01159 /// Move forward by one element in the list. Returns 0 when all the 01160 /// items in the list have been seen, else 1. 01161 int advance (void); 01162 01163 /// Pass back the {next_item} that hasn't been seen in the list. 01164 /// Returns 0 when all items have been seen, else 1. 01165 int next (T *&); 01166 01167 /** 01168 * @deprecated Delegates to ACE_Double_Linked_List_Iterator, except that 01169 * whereas the Double_Linked_List version of next returns the node, this next 01170 * returns the contents of the node 01171 */ 01172 T *next (void) const; 01173 01174 /** 01175 * Removes the current item (i.e., {next}) from the list. 01176 * Note that DLList iterators do not support {advance_and_remove} 01177 * directly (defined in its base class) and you will need to 01178 * release the element returned by it. 01179 */ 01180 int remove (void); 01181 01182 /// Delegates to ACE_Double_Linked_List_Iterator. 01183 void dump (void) const; 01184 01185 private: 01186 ACE_DLList<T> *list_; 01187 }; 01188 01189 /** 01190 * @class ACE_DLList_Reverse_Iterator 01191 * 01192 * @brief A double-linked list container class iterator. 01193 * 01194 * This implementation uses ACE_Double_Linked_List_Iterator to 01195 * perform the logic behind this container class. It delegates 01196 * all of its calls to ACE_Double_Linked_List_Iterator. 01197 */ 01198 template <class T> 01199 class ACE_DLList_Reverse_Iterator : public ACE_Double_Linked_List_Reverse_Iterator <ACE_DLList_Node> 01200 { 01201 01202 friend class ACE_DLList<T>; 01203 friend class ACE_DLList_Node; 01204 01205 public: 01206 01207 // = Initialization method. 01208 ACE_DLList_Reverse_Iterator (ACE_DLList<T> &l); 01209 01210 /** 01211 * Retasks the iterator to iterate over a new 01212 * Double_Linked_List. This allows clients to reuse an iterator 01213 * without incurring the constructor overhead. If you do use this, 01214 * be aware that if there are more than one reference to this 01215 * iterator, the other "clients" may be very bothered when their 01216 * iterator changes. 01217 * @@ Here be dragons. Comments? 01218 */ 01219 void reset (ACE_DLList<T> &l); 01220 01221 // = Iteration methods. 01222 /// Move forward by one element in the list. Returns 0 when all the 01223 /// items in the list have been seen, else 1. 01224 int advance (void); 01225 01226 /// Pass back the {next_item} that hasn't been seen in the list. 01227 /// Returns 0 when all items have been seen, else 1. 01228 int next (T *&); 01229 01230 /// @deprecated Delegates to ACE_Double_Linked_List_Iterator. 01231 T *next (void) const; 01232 01233 /// Removes the current item (i.e., {next}) from the list. 01234 /// Note that DLList iterators do not support {advance_and_remove} 01235 /// directly (defined in its base class) and you will need to 01236 /// release the element returned by it. 01237 int remove (void); 01238 01239 /// Delegates to ACE_Double_Linked_List_Iterator. 01240 void dump (void) const; 01241 01242 private: 01243 ACE_DLList<T> *list_; 01244 }; 01245 01246 // Forward declaration. 01247 template <class T, size_t ACE_SIZE> 01248 class ACE_Fixed_Set; 01249 01250 /** 01251 * @class ACE_Fixed_Set_Iterator_Base 01252 * 01253 * @brief Implements a common base class for iterators for a unordered set. 01254 */ 01255 template <class T, size_t ACE_SIZE> 01256 class ACE_Fixed_Set_Iterator_Base 01257 { 01258 public: 01259 // = Iteration methods. 01260 01261 /// Pass back the {next_item} that hasn't been seen in the Set. 01262 /// Returns 0 when all items have been seen, else 1. 01263 int next (T *&next_item); 01264 01265 /// Move forward by one element in the set. Returns 0 when all the 01266 /// items in the set have been seen, else 1. 01267 int advance (void); 01268 01269 /// Move to the first element in the set. Returns 0 if the 01270 /// set is empty, else 1. 01271 int first (void); 01272 01273 /// Returns 1 when all items have been seen, else 0. 01274 int done (void) const; 01275 01276 /// Declare the dynamic allocation hooks. 01277 ACE_ALLOC_HOOK_DECLARE; 01278 01279 protected: 01280 // = Initialization method. 01281 ACE_Fixed_Set_Iterator_Base (ACE_Fixed_Set<T, ACE_SIZE> &s); 01282 01283 /// Set we are iterating over. 01284 ACE_Fixed_Set<T, ACE_SIZE> &s_; 01285 01286 /// How far we've advanced over the set. 01287 ssize_t next_; 01288 01289 /// The number of non free items that the iterator had pointed at. 01290 size_t iterated_items_; 01291 01292 /// Dump the state of an object. 01293 void dump_i (void) const; 01294 01295 /// Pass back the {next_item} that hasn't been seen in the Set. 01296 /// Returns 0 when all items have been seen, else 1. 01297 int next_i (T *&next_item); 01298 }; 01299 01300 /** 01301 * @class ACE_Fixed_Set_Iterator 01302 * 01303 * @brief Iterates through an unordered set. 01304 * 01305 * This implementation of an unordered set uses a fixed array. 01306 * Allows deletions while iteration is occurring. 01307 */ 01308 template <class T, size_t ACE_SIZE> 01309 class ACE_Fixed_Set_Iterator : public ACE_Fixed_Set_Iterator_Base <T, ACE_SIZE> 01310 { 01311 public: 01312 // = Initialization method. 01313 ACE_Fixed_Set_Iterator (ACE_Fixed_Set<T, ACE_SIZE> &s); 01314 01315 // = Iteration methods. 01316 01317 /// Pass back the {next_item} that hasn't been seen in the Set. 01318 /// Returns 0 when all items have been seen, else 1. 01319 int next (T *&next_item); 01320 01321 /// Dump the state of an object. 01322 void dump (void) const; 01323 01324 /// Remove the item where the itearetor is located at. 01325 /// Returns 1 if it removes a item, else 0. 01326 /// Pass back the removed {item}. 01327 int remove (T *&item); 01328 01329 /// STL-like iterator dereference operator: returns a reference 01330 /// to the node underneath the iterator. 01331 T & operator* (void); 01332 01333 /// Declare the dynamic allocation hooks. 01334 ACE_ALLOC_HOOK_DECLARE; 01335 }; 01336 01337 /** 01338 * @class ACE_Fixed_Set_Const_Iterator 01339 * 01340 * @brief Iterates through a const unordered set. 01341 * 01342 * This implementation of an unordered set uses a fixed array. 01343 */ 01344 template <class T, size_t ACE_SIZE> 01345 class ACE_Fixed_Set_Const_Iterator : public ACE_Fixed_Set_Iterator_Base <T, ACE_SIZE> 01346 { 01347 public: 01348 // = Initialization method. 01349 ACE_Fixed_Set_Const_Iterator (const ACE_Fixed_Set<T, ACE_SIZE> &s); 01350 01351 // = Iteration methods. 01352 01353 /// Pass back the {next_item} that hasn't been seen in the Set. 01354 /// Returns 0 when all items have been seen, else 1. 01355 int next (const T *&next_item); 01356 01357 /// Dump the state of an object. 01358 void dump (void) const; 01359 01360 /// STL-like iterator dereference operator: returns a reference 01361 /// to the node underneath the iterator. 01362 const T & operator* (void) const ; 01363 01364 /// Declare the dynamic allocation hooks. 01365 ACE_ALLOC_HOOK_DECLARE; 01366 }; 01367 01368 /** 01369 * @class ACE_Fixed_Set 01370 * 01371 * @brief Implement a simple unordered set of {T} with maximum {ACE_SIZE}. 01372 * 01373 * This implementation of an unordered set uses a fixed array. 01374 * It does not allow duplicate members. The set provides linear insertion/deletion 01375 * operations. 01376 * 01377 * <b> Requirements and Performance Characteristics</b> 01378 * - Internal Structure 01379 * Fixed array 01380 * - Duplicates allowed? 01381 * No 01382 * - Random access allowed? 01383 * No 01384 * - Search speed 01385 * Linear 01386 * - Insert/replace speed 01387 * Linear 01388 * - Iterator still valid after change to container? 01389 * Yes 01390 * - Frees memory for removed elements? 01391 * No 01392 * - Items inserted by 01393 * Value 01394 * - Requirements for contained type 01395 * -# Default constructor 01396 * -# Copy constructor 01397 * -# operator= 01398 * -# operator== 01399 * 01400 */ 01401 template <class T, size_t ACE_SIZE> 01402 class ACE_Fixed_Set 01403 { 01404 public: 01405 friend class ACE_Fixed_Set_Iterator_Base<T, ACE_SIZE>; 01406 friend class ACE_Fixed_Set_Iterator<T, ACE_SIZE>; 01407 friend class ACE_Fixed_Set_Const_Iterator<T, ACE_SIZE>; 01408 01409 // Trait definitions. 01410 typedef ACE_Fixed_Set_Iterator<T, ACE_SIZE> ITERATOR; 01411 typedef ACE_Fixed_Set_Const_Iterator<T, ACE_SIZE> CONST_ITERATOR; 01412 01413 // = Initialization and termination methods. 01414 /// Default Constructor. 01415 /** 01416 * Creates an empy set 01417 */ 01418 ACE_Fixed_Set (void); 01419 01420 /// Copy constructor. 01421 /** 01422 * Initializes a set to be a copy of the set parameter. 01423 */ 01424 ACE_Fixed_Set (const ACE_Fixed_Set<T, ACE_SIZE> &); 01425 01426 /// Assignment operator. 01427 /** 01428 * Deep copy of one set to another. 01429 */ 01430 void operator= (const ACE_Fixed_Set<T, ACE_SIZE> &); 01431 01432 /// Destructor. 01433 /** 01434 * Destroys a set. 01435 */ 01436 ~ACE_Fixed_Set (void); 01437 01438 // = Check boundary conditions. 01439 01440 /// Returns 1 if the container is empty, otherwise returns 0. 01441 /** 01442 * Performs constant time check to determine if a set is empty. 01443 */ 01444 int is_empty (void) const; 01445 01446 /// Returns 1 if the container is full, otherwise returns 0. 01447 /** 01448 * Performs a constant time check to see if the set is full. 01449 */ 01450 int is_full (void) const; 01451 01452 // = Classic unordered set operations. 01453 01454 ///Linear time insertion of an item unique to the set. 01455 /** 01456 * Insert @a new_item into the set (doesn't allow duplicates). 01457 * Returns -1 if failures occur, 1 if item is already present, else 01458 * 0. 01459 */ 01460 int insert (const T &new_item); 01461 01462 ///Linear time removal operation of an item. 01463 /** 01464 * Remove first occurrence of {item} from the set. Returns 0 if 01465 * it removes the item, -1 if it can't find the item, and -1 if a 01466 * failure occurs. Removal doesn't reclaim memory for the @a item. 01467 */ 01468 int remove (const T &item); 01469 01470 /// Finds if @a item occurs in the set. Returns 0 if finds, else -1. 01471 /** 01472 * Performs a linear find operation for the specified @a item. 01473 */ 01474 int find (const T &item) const; 01475 01476 /// Size of the set. 01477 /** 01478 * Returns the current size of the set. 01479 */ 01480 size_t size (void) const; 01481 01482 /// Dump the state of an object. 01483 void dump (void) const; 01484 01485 /// Declare the dynamic allocation hooks. 01486 ACE_ALLOC_HOOK_DECLARE; 01487 01488 private: 01489 /// Holds the contents of the set. 01490 struct 01491 { 01492 /// Item in the set. 01493 T item_; 01494 01495 /// Keeps track of whether this item is in use or not. 01496 int is_free_; 01497 } search_structure_[ACE_SIZE]; 01498 01499 /// Current size of the set. 01500 size_t cur_size_; 01501 01502 /// Maximum size of the set. 01503 size_t max_size_; 01504 }; 01505 01506 // Forward declaration. 01507 template <class T> 01508 class ACE_Bounded_Set; 01509 01510 /** 01511 * @class ACE_Bounded_Set_Iterator 01512 * 01513 * @brief Iterates through an unordered set. 01514 * 01515 * This implementation of an unordered set uses a Bounded array. 01516 * Allows deletions while iteration is occurring. 01517 */ 01518 template <class T> 01519 class ACE_Bounded_Set_Iterator 01520 { 01521 public: 01522 // = Initialization method. 01523 ACE_Bounded_Set_Iterator (ACE_Bounded_Set<T> &s); 01524 01525 // = Iteration methods. 01526 01527 /// Pass back the {next_item} that hasn't been seen in the Set. 01528 /// Returns 0 when all items have been seen, else 1. 01529 int next (T *&next_item); 01530 01531 /// Move forward by one element in the set. Returns 0 when all the 01532 /// items in the set have been seen, else 1. 01533 int advance (void); 01534 01535 /// Move to the first element in the set. Returns 0 if the 01536 /// set is empty, else 1. 01537 int first (void); 01538 01539 /// Returns 1 when all items have been seen, else 0. 01540 int done (void) const; 01541 01542 /// Dump the state of an object. 01543 void dump (void) const; 01544 01545 /// Declare the dynamic allocation hooks. 01546 ACE_ALLOC_HOOK_DECLARE; 01547 01548 private: 01549 /// Set we are iterating over. 01550 ACE_Bounded_Set<T> &s_; 01551 01552 /// How far we've advanced over the set. 01553 ssize_t next_; 01554 }; 01555 01556 01557 /** 01558 * @class ACE_Bounded_Set 01559 * 01560 * @brief Implement a simple unordered set of {T} with maximum 01561 * set at creation time. 01562 * 01563 * This implementation of an unordered set uses a Bounded array. 01564 * This implementation does not allow duplicates. It provides 01565 * linear insert/remove/find operations. Insertion/removal does not 01566 * invalidate iterators, but caution should be taken to ensure 01567 * expected behavior. Once initialized, the object has a maximum size 01568 * which can only be increased by the assignment of another larger Bounded_Set. 01569 * 01570 * <b> Requirements and Performance Characteristics</b> 01571 * - Internal Structure 01572 * Bounded array which can grow via assignment 01573 * - Duplicates allowed? 01574 * No 01575 * - Random access allowed? 01576 * No 01577 * - Search speed 01578 * Linear 01579 * - Insert/replace speed 01580 * Linear 01581 * - Iterator still valid after change to container? 01582 * Yes 01583 * - Frees memory for removed elements? 01584 * No 01585 * - Items inserted by 01586 * Value 01587 * - Requirements for contained type 01588 * -# Default constructor 01589 * -# Copy constructor 01590 * -# operator= 01591 * -# operator== 01592 * 01593 */ 01594 template <class T> 01595 class ACE_Bounded_Set 01596 { 01597 public: 01598 friend class ACE_Bounded_Set_Iterator<T>; 01599 01600 // Trait definition. 01601 typedef ACE_Bounded_Set_Iterator<T> ITERATOR; 01602 01603 enum 01604 { 01605 DEFAULT_SIZE = 10 01606 }; 01607 01608 // = Initialization and termination methods. 01609 /// Construct a Bounded_Set using the default size. 01610 /** 01611 * The default constructor initializes the Bounded_Set to a maximum size 01612 * specified by the DEFAULT_SIZE. 01613 */ 01614 ACE_Bounded_Set (void); 01615 01616 /// Construct a Bounded_Set with the provided sizeB. 01617 /** 01618 * Initialize the Bounded_Set to have a maximum size equal to the size 01619 * parameter specified. 01620 */ 01621 ACE_Bounded_Set (size_t size); 01622 01623 /// Construct a Bounded_Set that is a copy of the provides Bounded_Set. 01624 /** 01625 * Initialize the Bounded_Set to be a copy of the Bounded_Set parameter. 01626 */ 01627 ACE_Bounded_Set (const ACE_Bounded_Set<T> &); 01628 01629 /// Assignment operator. 01630 /** 01631 * The assignment will make a deep copy of the Bounded_Set provided. If the 01632 * rhs has more elements than the capacity of the lhs, then the lhs will be 01633 * deleted and reallocated to accomadate the larger number of elements. 01634 */ 01635 void operator= (const ACE_Bounded_Set<T> &); 01636 01637 /// Destructor 01638 /** 01639 * Clean up the underlying dynamically allocated memory that is used by 01640 * the Bounded_Set. 01641 */ 01642 ~ACE_Bounded_Set (void); 01643 01644 // = Check boundary conditions. 01645 01646 /// Returns 1 if the container is empty, otherwise returns 0. 01647 /** 01648 * A constant time check is performed to determine if the Bounded_Set is 01649 * empty. 01650 */ 01651 int is_empty (void) const; 01652 01653 /// Returns 1 if the container is full, otherwise returns 0. 01654 /** 01655 * Performs a constant time check to determine if the Bounded_Set is at 01656 * capacity. 01657 */ 01658 int is_full (void) const; 01659 01660 // = Classic unordered set operations. 01661 01662 ///Inserts a new element unique to the set. 01663 /** 01664 * Insert @a new_item into the set (doesn't allow duplicates) in linear 01665 * time. 01666 * Returns -1 if failures occur, 1 if item is already present, else 01667 * 0. 01668 */ 01669 int insert (const T &new_item); 01670 01671 ///Finds the specified element and removes it from the set. 01672 /** 01673 * Remove first occurrence of @a item from the set. Returns 0 if it 01674 * removes the item, -1 if it can't find the item, and -1 if a 01675 * failure occurs. The linear remove operation does not reclaim the 01676 * memory associated with the removed item. 01677 */ 01678 int remove (const T &item); 01679 01680 /// Finds if @a item occurs in the set. Returns 0 if finds, else -1. 01681 /** 01682 * find preforms a linear search for {item} and returns 0 on successful 01683 * find and -1 otherwise. 01684 */ 01685 int find (const T &item) const; 01686 01687 /// Size of the set. 01688 /** 01689 * Returns a size_t representing the current size of the set. 01690 */ 01691 size_t size (void) const; 01692 01693 /// Dump the state of an object. 01694 void dump (void) const; 01695 01696 /// Declare the dynamic allocation hooks. 01697 ACE_ALLOC_HOOK_DECLARE; 01698 01699 private: 01700 struct Search_Structure 01701 { 01702 /// Item in the set. 01703 T item_; 01704 01705 /// Keeps track of whether this item is in use or not. 01706 int is_free_; 01707 }; 01708 01709 /// Holds the contents of the set. 01710 Search_Structure *search_structure_; 01711 01712 /// Current size of the set. 01713 size_t cur_size_; 01714 01715 /// Maximum size of the set. 01716 size_t max_size_; 01717 }; 01718 01719 /** 01720 * @class ACE_Ordered_MultiSet_Iterator 01721 * 01722 * @brief Implement a bidirectional iterator over an ordered multiset. 01723 * This class template requires that < operator semantics be 01724 * defined for the parameterized type {T}, but does not impose 01725 * any restriction on how that ordering operator is implemented. 01726 */ 01727 template <class T> 01728 class ACE_Ordered_MultiSet_Iterator 01729 { 01730 public: 01731 friend class ACE_Ordered_MultiSet<T>; 01732 01733 // = Initialization method. 01734 ACE_Ordered_MultiSet_Iterator (ACE_Ordered_MultiSet<T> &s); 01735 01736 // = Iteration methods. 01737 01738 /// Pass back the {next_item} that hasn't been seen in the ordered multiset. 01739 /// Returns 0 when all items have been seen, else 1. 01740 int next (T *&next_item) const; 01741 01742 /// Repositions the iterator at the first item in the ordered multiset 01743 /// Returns 0 if the list is empty else 1. 01744 int first (void); 01745 01746 /// Repositions the iterator at the last item in the ordered multiset 01747 /// Returns 0 if the list is empty else 1. 01748 int last (void); 01749 01750 /// Move forward by one element in the set. Returns 0 when all the 01751 /// items in the set have been seen, else 1. 01752 int advance (void); 01753 01754 /// Move backward by one element in the set. Returns 0 when all the 01755 /// items in the set have been seen, else 1. 01756 int retreat (void); 01757 01758 /// Returns 1 when all items have been seen, else 0. 01759 int done (void) const; 01760 01761 /// Dump the state of an object. 01762 void dump (void) const; 01763 01764 /// Returns a reference to the internal element {this} is pointing to. 01765 T& operator* (void); 01766 01767 /// Declare the dynamic allocation hooks. 01768 ACE_ALLOC_HOOK_DECLARE; 01769 01770 private: 01771 01772 /// Pointer to the current node in the iteration. 01773 ACE_DNode<T> *current_; 01774 01775 /// Pointer to the set we're iterating over. 01776 ACE_Ordered_MultiSet<T> &set_; 01777 }; 01778 01779 01780 /** 01781 * @class ACE_Ordered_MultiSet 01782 * 01783 * @brief Implement a simple ordered multiset of {T} of unbounded size 01784 * that allows duplicates. This class template requires that < 01785 * operator semantics be defined for the parameterized type {T}, but 01786 * does not impose any restriction on how that ordering operator is 01787 * implemented. The set is implemented as a linked list. 01788 * 01789 * 01790 * <b> Requirements and Performance Characteristics</b> 01791 * - Internal Structure 01792 * Double linked list 01793 * - Duplicates allowed? 01794 * Yes 01795 * - Random access allowed? 01796 * No 01797 * - Search speed 01798 * Linear 01799 * - Insert/replace speed 01800 * Linear 01801 * - Iterator still valid after change to container? 01802 * Yes 01803 * - Frees memory for removed elements? 01804 * Yes 01805 * - Items inserted by 01806 * Value 01807 * - Requirements for contained type 01808 * -# Default constructor 01809 * -# Copy constructor 01810 * -# operator= 01811 * -# operator== 01812 * -# operator< 01813 * 01814 * 01815 */ 01816 template <class T> 01817 class ACE_Ordered_MultiSet 01818 { 01819 public: 01820 friend class ACE_Ordered_MultiSet_Iterator<T>; 01821 01822 // Trait definition. 01823 typedef ACE_Ordered_MultiSet_Iterator<T> ITERATOR; 01824 01825 // = Initialization and termination methods. 01826 /// Constructor. Use user specified allocation strategy 01827 /// if specified. 01828 /** 01829 * Initialize the set using the allocation strategy specified. If none, use the 01830 * default strategy. 01831 */ 01832 ACE_Ordered_MultiSet (ACE_Allocator *the_allocator = 0); 01833 01834 /// Copy constructor. 01835 /** 01836 * Initialize the set to be a copy of the provided set. 01837 */ 01838 ACE_Ordered_MultiSet (const ACE_Ordered_MultiSet<T> &); 01839 01840 /// Destructor. 01841 /** 01842 * Delete the nodes of the set. 01843 */ 01844 ~ACE_Ordered_MultiSet (void); 01845 01846 /// Assignment operator. 01847 /** 01848 * Delete the nodes in lhs, and copy the nodes from the rhs. 01849 */ 01850 void operator= (const ACE_Ordered_MultiSet<T> &); 01851 01852 // = Check boundary conditions. 01853 01854 /// Returns 1 if the container is empty, otherwise returns 0. 01855 /** 01856 * Constant time check to determine if the set is empty. 01857 */ 01858 int is_empty (void) const; 01859 01860 /// Size of the set. 01861 /** 01862 * Constant time check to determine the size of the set. 01863 */ 01864 size_t size (void) const; 01865 01866 // = Classic unordered set operations. 01867 01868 /// Insert @a new_item into the ordered multiset. 01869 /// Returns -1 if failures occur, else 0. 01870 /** 01871 * Linear time, order preserving insert into the set beginning at the head. 01872 */ 01873 int insert (const T &new_item); 01874 01875 ///Linear time insert beginning at the point specified by the provided iterator. 01876 /** 01877 * Insert @a new_item into the ordered multiset, starting its search at 01878 * the node pointed to by the iterator, and if insertion was successful, 01879 * updates the iterator to point to the newly inserted node. 01880 * Returns -1 if failures occur, else 0. 01881 */ 01882 int insert (const T &new_item, ITERATOR &iter); 01883 01884 /// Remove first occurrence of @a item from the set. Returns 0 if 01885 /// it removes the item, -1 if it can't find the item. 01886 /** 01887 * Linear time search operation which removes the item from the set if found . 01888 */ 01889 int remove (const T &item); 01890 01891 ///Linear find operation. 01892 /** 01893 * Finds first occurrence of @a item in the multiset, using the iterator's 01894 * current position as a hint to improve performance. If find succeeds, 01895 * it positions the iterator at that node and returns 0, or if it cannot 01896 * locate the node, it leaves the iterator alone and just returns -1. 01897 */ 01898 int find (const T &item, ITERATOR &iter) const; 01899 01900 /// Reset the ACE_Ordered_MultiSet to be empty. 01901 /** 01902 * Delete the nodes inside the set. 01903 */ 01904 void reset (void); 01905 01906 /// Dump the state of an object. 01907 void dump (void) const; 01908 01909 /// Declare the dynamic allocation hooks. 01910 ACE_ALLOC_HOOK_DECLARE; 01911 01912 private: 01913 01914 /** 01915 * Insert @a item, starting its search at the position given, 01916 * and if successful updates the passed pointer to point to 01917 * the newly inserted item's node. 01918 */ 01919 int insert_from (const T &item, ACE_DNode<T> *start_position, 01920 ACE_DNode<T> **new_position); 01921 01922 /** 01923 * Looks for first occurance of @a item in the ordered set, using the 01924 * passed starting position as a hint: if there is such an instance, it 01925 * updates the new_position pointer to point to this node and returns 0; 01926 * if there is no such node, then if there is a node before where the 01927 * item would have been, it updates the new_position pointer to point 01928 * to this node and returns -1; if there is no such node, then if there 01929 * is a node after where the item would have been, it updates the 01930 * new_position pointer to point to this node (or 0 if there is no such 01931 * node) and returns 1; 01932 */ 01933 int locate (const T &item, ACE_DNode<T> *start_position, 01934 ACE_DNode<T> *&new_position) const; 01935 01936 /// Delete all the nodes in the Set. 01937 void delete_nodes (void); 01938 01939 /// Copy nodes into this set. 01940 void copy_nodes (const ACE_Ordered_MultiSet<T> &); 01941 01942 /// Head of the bilinked list of Nodes. 01943 ACE_DNode<T> *head_; 01944 01945 /// Head of the bilinked list of Nodes. 01946 ACE_DNode<T> *tail_; 01947 01948 /// Current size of the set. 01949 size_t cur_size_; 01950 01951 /// Allocation strategy of the set. 01952 ACE_Allocator *allocator_; 01953 }; 01954 01955 // **************************************************************** 01956 01957 /** 01958 * @class ACE_Array 01959 * 01960 * @brief A dynamic array class. 01961 * 01962 * This class extends ACE_Array_Base, adding comparison operators. 01963 * 01964 * <b> Requirements and Performance Characteristics</b> 01965 * - Internal Structure 01966 * Dynamic array 01967 * - Duplicates allowed? 01968 * Yes 01969 * - Random access allowed? 01970 * Yes 01971 * - Search speed 01972 * N/A 01973 * - Insert/replace speed 01974 * O(1) 01975 * - Iterator still valid after change to container? 01976 * - In general, yes. 01977 * - If array size is changed during iteration, no. 01978 * - Frees memory for removed elements? 01979 * No 01980 * - Items inserted by 01981 * Value 01982 * - Requirements for contained type 01983 * -# Default constructor 01984 * -# Copy constructor 01985 * -# operator= 01986 * -# operator!= 01987 * 01988 * @sa ACE_Array_Base. This class inherits its operations and requirements. 01989 */ 01990 template <class T> 01991 class ACE_Array : public ACE_Array_Base<T> 01992 { 01993 public: 01994 // Define a "trait" 01995 typedef T TYPE; 01996 typedef ACE_Array_Iterator<T> ITERATOR; 01997 01998 /// Dynamically create an uninitialized array. 01999 /** 02000 * Initialize an empty array of the specified size using the provided 02001 * allocation strategy. 02002 */ 02003 ACE_Array (size_t size = 0, 02004 ACE_Allocator* alloc = 0); 02005 02006 /// Dynamically initialize the entire array to the {default_value}. 02007 /** 02008 * Initialize an array the given size placing the default_value in each index. 02009 */ 02010 ACE_Array (size_t size, 02011 const T &default_value, 02012 ACE_Allocator* alloc = 0); 02013 02014 ///Copy constructor. 02015 /** 02016 * The copy constructor performs initialization by making an exact 02017 * copy of the contents of parameter {s}, i.e., *this == s will 02018 * return true. 02019 */ 02020 ACE_Array (const ACE_Array<T> &s); 02021 02022 ///Assignment operator 02023 /** 02024 * Assignment operator performs an assignment by making an exact 02025 * copy of the contents of parameter {s}, i.e., *this == s will 02026 * return true. Note that if the {max_size_} of {array_} is >= than 02027 * {s.max_size_} we can copy it without reallocating. However, if 02028 * {max_size_} is < {s.max_size_} we must delete the {array_}, 02029 * reallocate a new {array_}, and then copy the contents of {s}. 02030 */ 02031 void operator= (const ACE_Array<T> &s); 02032 02033 // = Compare operators 02034 02035 ///Equality comparison operator. 02036 /** 02037 * Compare this array with {s} for equality. Two arrays are equal 02038 * if their {size}'s are equal and all the elements from 0 .. {size} 02039 * are equal. 02040 */ 02041 bool operator== (const ACE_Array<T> &s) const; 02042 02043 ///Inequality comparison operator. 02044 /** 02045 * Compare this array with {s} for inequality such that {*this} != 02046 * {s} is always the complement of the boolean return value of 02047 * {*this} == {s}. 02048 */ 02049 bool operator!= (const ACE_Array<T> &s) const; 02050 }; 02051 02052 ACE_END_VERSIONED_NAMESPACE_DECL 02053 02054 #if defined (__ACE_INLINE__) 02055 #include "ace/Containers_T.inl" 02056 #endif /* __ACE_INLINE__ */ 02057 02058 #if defined (ACE_TEMPLATES_REQUIRE_SOURCE) 02059 #include "ace/Containers_T.cpp" 02060 #endif /* ACE_TEMPLATES_REQUIRE_SOURCE */ 02061 02062 #if defined (ACE_TEMPLATES_REQUIRE_PRAGMA) 02063 #pragma implementation ("Containers_T.cpp") 02064 #endif /* ACE_TEMPLATES_REQUIRE_PRAGMA */ 02065 02066 #include /**/ "ace/post.h" 02067 02068 #endif /* ACE_CONTAINERS_T_H */