#include <Unbounded_Set.h>
Collaboration diagram for ACE_Unbounded_Set< T >:
Public Types | |
typedef ACE_Unbounded_Set_Iterator< T > | ITERATOR |
typedef ACE_Unbounded_Set_Iterator< T > | iterator |
typedef ACE_Unbounded_Set_Const_Iterator< T > | CONST_ITERATOR |
typedef ACE_Unbounded_Set_Const_Iterator< T > | const_iterator |
Public Member Functions | |
ACE_Unbounded_Set (ACE_Allocator *alloc=0) | |
ACE_Unbounded_Set (const ACE_Unbounded_Set< T > &) | |
Copy constructor. | |
ACE_Unbounded_Set< T > & | operator= (const ACE_Unbounded_Set< T > &) |
Assignment operator. | |
~ACE_Unbounded_Set (void) | |
Destructor. | |
bool | is_empty (void) const |
Returns true if the container is empty, otherwise returns false . | |
bool | is_full (void) const |
Returns false . | |
int | insert (const T &new_item) |
Linear insertion of an item. | |
int | insert_tail (const T &item) |
int | remove (const T &item) |
Linear remove operation. | |
int | find (const T &item) const |
size_t | size (void) const |
Size of the set. | |
void | dump (void) const |
Dump the state of an object. | |
void | reset (void) |
Reset the ACE_Unbounded_Set to be empty. | |
iterator | begin (void) |
iterator | end (void) |
const_iterator | begin (void) const |
const_iterator | end (void) const |
Public Attributes | |
ACE_ALLOC_HOOK_DECLARE | |
Declare the dynamic allocation hooks. | |
Private Member Functions | |
void | delete_nodes (void) |
Delete all the nodes in the Set. | |
void | copy_nodes (const ACE_Unbounded_Set< T > &) |
Copy nodes into this set. | |
Private Attributes | |
ACE_Node< T > * | head_ |
Head of the linked list of Nodes. | |
size_t | cur_size_ |
Current size of the set. | |
ACE_Allocator * | allocator_ |
Allocation strategy of the set. | |
Friends | |
class | ACE_Unbounded_Set_Iterator< T > |
class | ACE_Unbounded_Set_Const_Iterator< T > |
This implementation of an unordered set uses a circular linked list with a dummy node. This implementation does not allow duplicates, but it maintains FIFO ordering of insertions.
Requirements and Performance Characteristics
Definition at line 181 of file Unbounded_Set.h.
|
Definition at line 191 of file Unbounded_Set.h. Referenced by ACE_Unbounded_Set< T >::begin(), and ACE_Unbounded_Set< T >::end(). |
|
Definition at line 190 of file Unbounded_Set.h. |
|
Definition at line 189 of file Unbounded_Set.h. Referenced by ACE_Unbounded_Set< T >::begin(), and ACE_Unbounded_Set< T >::end(). |
|
Definition at line 188 of file Unbounded_Set.h. |
|
Initialize an empty set using the allocation strategy of the user if provided. Definition at line 134 of file Unbounded_Set.cpp. References ACE_NEW_MALLOC, and ACE_Allocator::instance().
00135 : head_ (0), 00136 cur_size_ (0), 00137 allocator_ (alloc) 00138 { 00139 // ACE_TRACE ("ACE_Unbounded_Set<T>::ACE_Unbounded_Set"); 00140 00141 if (this->allocator_ == 0) 00142 this->allocator_ = ACE_Allocator::instance (); 00143 00144 ACE_NEW_MALLOC (this->head_, 00145 (ACE_Node<T>*) this->allocator_->malloc (sizeof (ACE_Node<T>)), 00146 ACE_Node<T>); 00147 // Make the list circular by pointing it back to itself. 00148 this->head_->next_ = this->head_; 00149 } |
|
Copy constructor. Initialize this set to be an exact copy of the set provided. Definition at line 152 of file Unbounded_Set.cpp. References ACE_NEW_MALLOC, ACE_TRACE, ACE_Unbounded_Set< T >::copy_nodes(), and ACE_Allocator::instance().
00153 : head_ (0), 00154 cur_size_ (0), 00155 allocator_ (us.allocator_) 00156 { 00157 ACE_TRACE ("ACE_Unbounded_Set<T>::ACE_Unbounded_Set"); 00158 00159 if (this->allocator_ == 0) 00160 this->allocator_ = ACE_Allocator::instance (); 00161 00162 ACE_NEW_MALLOC (this->head_, 00163 (ACE_Node<T>*) this->allocator_->malloc (sizeof (ACE_Node<T>)), 00164 ACE_Node<T>); 00165 this->head_->next_ = this->head_; 00166 this->copy_nodes (us); 00167 } |
|
Destructor. Destroy the nodes of the set. Definition at line 119 of file Unbounded_Set.cpp. References ACE_DES_FREE_TEMPLATE, and ACE_Unbounded_Set< T >::delete_nodes().
00120 { 00121 // ACE_TRACE ("ACE_Unbounded_Set<T>::~ACE_Unbounded_Set"); 00122 00123 this->delete_nodes (); 00124 00125 // Delete the dummy node. 00126 ACE_DES_FREE_TEMPLATE (head_, 00127 this->allocator_->free, 00128 ACE_Node, 00129 <T>); 00130 this->head_ = 0; 00131 } |
|
Definition at line 249 of file Unbounded_Set.cpp. References ACE_Unbounded_Set< T >::const_iterator.
00250 { 00251 // ACE_TRACE ("ACE_Unbounded_Set<T>::begin"); 00252 return const_iterator (*this); 00253 } |
|
Definition at line 235 of file Unbounded_Set.cpp. References ACE_Unbounded_Set< T >::iterator. Referenced by ACE_Unbounded_Set< T >::find(), and ACE_Future_Rep< T >::set().
00236 { 00237 // ACE_TRACE ("ACE_Unbounded_Set<T>::begin"); 00238 return iterator (*this); 00239 } |
|
Copy nodes into this set.
Definition at line 88 of file Unbounded_Set.cpp. References ACE_Unbounded_Set< T >::head_, ACE_Unbounded_Set< T >::insert_tail(), ACE_Node< T >::item_, and ACE_Node< T >::next_. Referenced by ACE_Unbounded_Set< T >::ACE_Unbounded_Set(), and ACE_Unbounded_Set< T >::operator=().
00089 { 00090 for (ACE_Node<T> *curr = us.head_->next_; 00091 curr != us.head_; 00092 curr = curr->next_) 00093 this->insert_tail (curr->item_); 00094 } |
|
Delete all the nodes in the Set.
Definition at line 97 of file Unbounded_Set.cpp. References ACE_DES_FREE_TEMPLATE, and ACE_Node< T >::next_. Referenced by ACE_Unbounded_Set< T >::operator=(), ACE_Unbounded_Set< T >::reset(), and ACE_Unbounded_Set< T >::~ACE_Unbounded_Set().
00098 { 00099 ACE_Node<T> *curr = this->head_->next_; 00100 00101 // Keep looking until we've hit the dummy node. 00102 00103 while (curr != this->head_) 00104 { 00105 ACE_Node<T> *temp = curr; 00106 curr = curr->next_; 00107 ACE_DES_FREE_TEMPLATE (temp, 00108 this->allocator_->free, 00109 ACE_Node, 00110 <T>); 00111 --this->cur_size_; 00112 } 00113 00114 // Reset the list to be a circular list with just a dummy node. 00115 this->head_->next_ = this->head_; 00116 } |
|
Dump the state of an object.
Definition at line 62 of file Unbounded_Set.cpp. References ACE_BEGIN_DUMP, ACE_DEBUG, ACE_END_DUMP, ACE_TEXT, ACE_TRACE, ACE_Unbounded_Set< T >::end(), and LM_DEBUG.
00063 { 00064 #if defined (ACE_HAS_DUMP) 00065 ACE_TRACE ("ACE_Unbounded_Set<T>::dump"); 00066 00067 ACE_DEBUG ((LM_DEBUG, ACE_BEGIN_DUMP, this)); 00068 ACE_DEBUG ((LM_DEBUG, ACE_TEXT ("\nhead_ = %u"), this->head_)); 00069 ACE_DEBUG ((LM_DEBUG, ACE_TEXT ("\nhead_->next_ = %u"), this->head_->next_)); 00070 ACE_DEBUG ((LM_DEBUG, ACE_TEXT ("\ncur_size_ = %d\n"), this->cur_size_)); 00071 00072 T *item = 0; 00073 #if !defined (ACE_NLOGGING) 00074 size_t count = 1; 00075 #endif /* ! ACE_NLOGGING */ 00076 00077 const_iterator const the_end = this->end (); 00078 for (const_iterator i (this->begin ()); 00079 i != end; 00080 ++i) 00081 ACE_DEBUG ((LM_DEBUG, ACE_TEXT ("count = %u\n"), count++)); 00082 00083 ACE_DEBUG ((LM_DEBUG, ACE_END_DUMP)); 00084 #endif /* ACE_HAS_DUMP */ 00085 } |
|
Definition at line 256 of file Unbounded_Set.cpp. References ACE_Unbounded_Set< T >::const_iterator.
00257 { 00258 // ACE_TRACE ("ACE_Unbounded_Set<T>::end"); 00259 return const_iterator (*this, 1); 00260 } |
|
Definition at line 242 of file Unbounded_Set.cpp. References ACE_Unbounded_Set< T >::iterator. Referenced by ACE_Unbounded_Set< T >::dump(), ACE_Unbounded_Set< T >::find(), and ACE_Future_Rep< T >::set().
00243 { 00244 // ACE_TRACE ("ACE_Unbounded_Set<T>::end"); 00245 return iterator (*this, 1); 00246 } |
|
Performs a linear find operation. Definition at line 184 of file Unbounded_Set.cpp. References ACE_Unbounded_Set< T >::begin(), and ACE_Unbounded_Set< T >::end(). Referenced by ACE_Unbounded_Set< T >::insert().
00185 { 00186 // ACE_TRACE ("ACE_Unbounded_Set<T>::find"); 00187 const_iterator const the_end = this->end (); 00188 for (const_iterator i = this->begin (); i != the_end; ++i) 00189 if ((*i) == item) 00190 return 0; 00191 00192 return -1; 00193 } |
|
|
Constant time insert at the end of the set. Definition at line 30 of file Unbounded_Set.cpp. References ACE_NEW_MALLOC_RETURN. Referenced by ACE_Unbounded_Set< T >::copy_nodes(), and ACE_Unbounded_Set< T >::insert().
00031 { 00032 // ACE_TRACE ("ACE_Unbounded_Set<T>::insert_tail"); 00033 ACE_Node<T> *temp = 0; 00034 00035 // Insert <item> into the old dummy node location. 00036 this->head_->item_ = item; 00037 00038 // Create a new dummy node. 00039 ACE_NEW_MALLOC_RETURN (temp, 00040 static_cast<ACE_Node<T>*> (this->allocator_->malloc (sizeof (ACE_Node<T>))), 00041 ACE_Node<T> (this->head_->next_), 00042 -1); 00043 // Link this pointer into the list. 00044 this->head_->next_ = temp; 00045 00046 // Point the head to the new dummy node. 00047 this->head_ = temp; 00048 00049 ++this->cur_size_; 00050 return 0; 00051 } |
|
Returns Constant time is_empty check. Definition at line 10 of file Unbounded_Set.inl. References ACE_TRACE. Referenced by ACE_Service_Gestalt::close(), and ACE_Service_Gestalt::~ACE_Service_Gestalt().
|
|
Returns
Always returns Definition at line 17 of file Unbounded_Set.inl. References ACE_TRACE.
00018 { 00019 ACE_TRACE ("ACE_Unbounded_Set<T>::is_full"); 00020 return 0; // We should implement a "node of last resort for this..." 00021 } |
|
Assignment operator. Perform a deep copy of the rhs into the lhs. Definition at line 170 of file Unbounded_Set.cpp. References ACE_TRACE, ACE_Unbounded_Set< T >::copy_nodes(), and ACE_Unbounded_Set< T >::delete_nodes().
00171 { 00172 ACE_TRACE ("ACE_Unbounded_Set<T>::operator="); 00173 00174 if (this != &us) 00175 { 00176 this->delete_nodes (); 00177 this->copy_nodes (us); 00178 } 00179 00180 return *this; 00181 } |
|
Linear remove operation. Remove first occurrence of item from the set. Returns 0 if it removes the item, -1 if it can't find the item, and -1 if a failure occurs. Definition at line 206 of file Unbounded_Set.cpp. References ACE_DES_FREE_TEMPLATE, and ACE_Node< T >::next_. Referenced by ACE_Future_Rep< T >::detach(), and ACE_Hash_Multi_Map_Manager< EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK >::unbind_i().
00207 { 00208 // ACE_TRACE ("ACE_Unbounded_Set<T>::remove"); 00209 00210 // Insert the item to be founded into the dummy node. 00211 this->head_->item_ = item; 00212 00213 ACE_Node<T> *curr = this->head_; 00214 00215 while (!(curr->next_->item_ == item)) 00216 curr = curr->next_; 00217 00218 if (curr->next_ == this->head_) 00219 return -1; // Item was not found. 00220 else 00221 { 00222 ACE_Node<T> *temp = curr->next_; 00223 // Skip over the node that we're deleting. 00224 curr->next_ = temp->next_; 00225 --this->cur_size_; 00226 ACE_DES_FREE_TEMPLATE (temp, 00227 this->allocator_->free, 00228 ACE_Node, 00229 <T>); 00230 return 0; 00231 } 00232 } |
|
Reset the ACE_Unbounded_Set to be empty. Delete the nodes of the set. Definition at line 54 of file Unbounded_Set.cpp. References ACE_TRACE, and ACE_Unbounded_Set< T >::delete_nodes().
00055 { 00056 ACE_TRACE ("reset"); 00057 00058 this->delete_nodes (); 00059 } |
|
Size of the set. Access the size of the set. Definition at line 23 of file Unbounded_Set.cpp. Referenced by ACE_Hash_Multi_Map_Manager< EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK >::unbind_i().
00024 { 00025 // ACE_TRACE ("ACE_Unbounded_Set<T>::size"); 00026 return this->cur_size_; 00027 } |
|
Definition at line 185 of file Unbounded_Set.h. |
|
Definition at line 184 of file Unbounded_Set.h. |
|
Declare the dynamic allocation hooks.
Definition at line 288 of file Unbounded_Set.h. |
|
Allocation strategy of the set.
Definition at line 304 of file Unbounded_Set.h. |
|
Current size of the set.
Definition at line 301 of file Unbounded_Set.h. |
|
Head of the linked list of Nodes.
Definition at line 298 of file Unbounded_Set.h. Referenced by ACE_Unbounded_Set< T >::copy_nodes(). |