ACE_Unbounded_Set_Ex< T, C > Class Template Reference

Implement a simple unordered set of <T> of unbounded size. More...

#include <Unbounded_Set_Ex.h>

Collaboration diagram for ACE_Unbounded_Set_Ex< T, C >:

Collaboration graph
[legend]
List of all members.

Public Types

typedef ACE_Unbounded_Set_Ex_Iterator<
T, C > 		ITERATOR
typedef ACE_Unbounded_Set_Ex_Iterator<
T, C > 		iterator
typedef ACE_Unbounded_Set_Ex_Const_Iterator<
T, C > 		CONST_ITERATOR
typedef ACE_Unbounded_Set_Ex_Const_Iterator<
T, C > 		const_iterator
typedef C COMP
typedef ACE_Node< T, C > NODE

Public Member Functions

 ACE_Unbounded_Set_Ex (ACE_Allocator *alloc=0)
 ACE_Unbounded_Set_Ex (const C &comparator, ACE_Allocator *alloc=0)
 ACE_Unbounded_Set_Ex (const ACE_Unbounded_Set_Ex< T, C > &)
 Copy constructor.
ACE_Unbounded_Set_Ex< T, C > & operator= (const ACE_Unbounded_Set_Ex< T, C > &)
 Assignment operator.
 ~ACE_Unbounded_Set_Ex (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_Ex 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_Ex< T, C > &)
 Copy nodes into this set.

Private Attributes

NODE * 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.
COMP comp_
 Comparator to be used.

Friends

class ACE_Unbounded_Set_Ex_Iterator< T, C >
class ACE_Unbounded_Set_Ex_Const_Iterator< T, C >

Detailed Description

template<class T, class C>
class ACE_Unbounded_Set_Ex< T, C >

Implement a simple unordered set of <T> of unbounded size.

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.

This implementation may also be parameterized with a comparator functor, which must implement bool operator () (const T&, const T&) const, returning true if the given items are equivalent. The default comparator is sufficient for objects reliably compared with operator==.

Requirements and Performance Characteristics

Definition at line 195 of file Unbounded_Set_Ex.h.

Member Typedef Documentation

template<class T, class C>
typedef C ACE_Unbounded_Set_Ex< T, C >::COMP

Definition at line 206 of file Unbounded_Set_Ex.h.

template<class T, class C>
typedef ACE_Unbounded_Set_Ex_Const_Iterator<T, C> ACE_Unbounded_Set_Ex< T, C >::const_iterator

Definition at line 205 of file Unbounded_Set_Ex.h.

template<class T, class C>
typedef ACE_Unbounded_Set_Ex_Const_Iterator<T, C> ACE_Unbounded_Set_Ex< T, C >::CONST_ITERATOR

Definition at line 204 of file Unbounded_Set_Ex.h.

template<class T, class C>
typedef ACE_Unbounded_Set_Ex_Iterator<T, C> ACE_Unbounded_Set_Ex< T, C >::iterator

Definition at line 203 of file Unbounded_Set_Ex.h.

template<class T, class C>
typedef ACE_Unbounded_Set_Ex_Iterator<T, C> ACE_Unbounded_Set_Ex< T, C >::ITERATOR

Definition at line 202 of file Unbounded_Set_Ex.h.

template<class T, class C>
typedef ACE_Node<T, C> ACE_Unbounded_Set_Ex< T, C >::NODE

Definition at line 207 of file Unbounded_Set_Ex.h.

Constructor & Destructor Documentation

template<class T, class C>
ACE_Unbounded_Set_Ex< T, C >::ACE_Unbounded_Set_Ex ( ACE_Allocator *  alloc = 0  ) 

Initialize an empty set using the allocation strategy of the user if provided.

Definition at line 134 of file Unbounded_Set_Ex.cpp.

References ACE_NEW_MALLOC, ACE_Unbounded_Set_Ex< T, C >::allocator_, ACE_Unbounded_Set_Ex< T, C >::head_, ACE_Allocator::instance(), and ACE_Node< T, C >::next_.

00135   : head_ (0),
00136     cur_size_ (0),
00137     allocator_ (alloc)
00138 {
00139   // ACE_TRACE ("ACE_Unbounded_Set_Ex<T, C>::ACE_Unbounded_Set_Ex");
00140 
00141   if (this->allocator_ == 0)
00142     this->allocator_ = ACE_Allocator::instance ();
00143 
00144   ACE_NEW_MALLOC (this->head_,
00145                   (NODE*) this->allocator_->malloc (sizeof (NODE)),
00146                   NODE);
00147   // Make the list circular by pointing it back to itself.
00148   this->head_->next_ = this->head_;
00149 }

template<class T, class C>
ACE_Unbounded_Set_Ex< T, C >::ACE_Unbounded_Set_Ex ( const C &  comparator,
ACE_Allocator *  alloc = 0 
)

Initialize an empty set using the allocation strategy of the user if provided, and a given comparator functor.

Definition at line 152 of file Unbounded_Set_Ex.cpp.

References ACE_NEW_MALLOC, ACE_Unbounded_Set_Ex< T, C >::allocator_, ACE_Unbounded_Set_Ex< T, C >::head_, ACE_Allocator::instance(), and ACE_Node< T, C >::next_.

00154   : head_ (0),
00155     cur_size_ (0),
00156     allocator_ (alloc),
00157     comp_ (comp)
00158 {
00159   // ACE_TRACE ("ACE_Unbounded_Set_Ex<T, C>::ACE_Unbounded_Set_Ex");
00160 
00161   if (this->allocator_ == 0)
00162     this->allocator_ = ACE_Allocator::instance ();
00163 
00164   ACE_NEW_MALLOC (this->head_,
00165                   (NODE*) this->allocator_->malloc (sizeof (NODE)),
00166                   NODE);
00167   // Make the list circular by pointing it back to itself.
00168   this->head_->next_ = this->head_;
00169 }

template<class T, class C>
ACE_Unbounded_Set_Ex< T, C >::ACE_Unbounded_Set_Ex ( const ACE_Unbounded_Set_Ex< T, C > &   ) 

Copy constructor.

Initialize this set to be an exact copy of the set provided.

Definition at line 172 of file Unbounded_Set_Ex.cpp.

References ACE_NEW_MALLOC, ACE_TRACE, ACE_Unbounded_Set_Ex< T, C >::allocator_, ACE_Unbounded_Set_Ex< T, C >::copy_nodes(), ACE_Unbounded_Set_Ex< T, C >::head_, ACE_Allocator::instance(), and ACE_Node< T, C >::next_.

00173   : head_ (0),
00174     cur_size_ (0),
00175     allocator_ (us.allocator_),
00176     comp_ (us.comp_)
00177 {
00178   ACE_TRACE ("ACE_Unbounded_Set_Ex<T, C>::ACE_Unbounded_Set_Ex");
00179 
00180   if (this->allocator_ == 0)
00181     this->allocator_ = ACE_Allocator::instance ();
00182 
00183   ACE_NEW_MALLOC (this->head_,
00184                   (NODE*) this->allocator_->malloc (sizeof (NODE)),
00185                   NODE);
00186   this->head_->next_ = this->head_;
00187   this->copy_nodes (us);
00188 }

template<class T, class C>
ACE_Unbounded_Set_Ex< T, C >::~ACE_Unbounded_Set_Ex ( void   ) 

Destructor.

Destroy the nodes of the set.

Definition at line 119 of file Unbounded_Set_Ex.cpp.

References ACE_DES_FREE_TEMPLATE2, ACE_Unbounded_Set_Ex< T, C >::delete_nodes(), and ACE_Unbounded_Set_Ex< T, C >::head_.

00120 {
00121   // ACE_TRACE ("ACE_Unbounded_Set_Ex<T, C>::~ACE_Unbounded_Set_Ex");
00122 
00123   this->delete_nodes ();
00124 
00125   // Delete the dummy node.
00126   ACE_DES_FREE_TEMPLATE2 (head_,
00127                          this->allocator_->free,
00128                          ACE_Node,
00129                          T, C);
00130   this->head_ = 0;
00131 }

Member Function Documentation

template<class T, class C>
ACE_Unbounded_Set_Ex< T, C >::const_iterator ACE_Unbounded_Set_Ex< T, C >::begin ( void   )  const

Definition at line 270 of file Unbounded_Set_Ex.cpp.

00271 {
00272   // ACE_TRACE ("ACE_Unbounded_Set_Ex<T, C>::begin");
00273   return const_iterator (*this);
00274 }

template<class T, class C>
ACE_Unbounded_Set_Ex< T, C >::iterator ACE_Unbounded_Set_Ex< T, C >::begin ( void   ) 

Definition at line 256 of file Unbounded_Set_Ex.cpp.

00257 {
00258   // ACE_TRACE ("ACE_Unbounded_Set_Ex<T, C>::begin");
00259   return iterator (*this);
00260 }

template<class T, class C>
void ACE_Unbounded_Set_Ex< T, C >::copy_nodes ( const ACE_Unbounded_Set_Ex< T, C > &   )  [private]

Copy nodes into this set.

Definition at line 88 of file Unbounded_Set_Ex.cpp.

References ACE_Unbounded_Set_Ex< T, C >::head_, ACE_Unbounded_Set_Ex< T, C >::insert_tail(), and ACE_Node< T, C >::next_.

Referenced by ACE_Unbounded_Set_Ex< T, C >::ACE_Unbounded_Set_Ex(), and ACE_Unbounded_Set_Ex< T, C >::operator=().

00089 {
00090   for (NODE *curr = us.head_->next_;
00091        curr != us.head_;
00092        curr = curr->next_)
00093     this->insert_tail (curr->item_);
00094 }

template<class T, class C>
void ACE_Unbounded_Set_Ex< T, C >::delete_nodes ( void   )  [private]

Delete all the nodes in the Set.

Definition at line 97 of file Unbounded_Set_Ex.cpp.

References ACE_DES_FREE_TEMPLATE2, ACE_Unbounded_Set_Ex< T, C >::cur_size_, ACE_Unbounded_Set_Ex< T, C >::head_, and ACE_Node< T, C >::next_.

Referenced by ACE_Unbounded_Set_Ex< T, C >::operator=(), ACE_Unbounded_Set_Ex< T, C >::reset(), and ACE_Unbounded_Set_Ex< T, C >::~ACE_Unbounded_Set_Ex().

00098 {
00099   NODE *curr = this->head_->next_;
00100 
00101   // Keep looking until we've hit the dummy node.
00102 
00103   while (curr != this->head_)
00104     {
00105       NODE *temp = curr;
00106       curr = curr->next_;
00107       ACE_DES_FREE_TEMPLATE2 (temp,
00108                              this->allocator_->free,
00109                              ACE_Node,
00110                              T, C);
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 }

template<class T, class C>
void ACE_Unbounded_Set_Ex< T, C >::dump ( void   )  const

Dump the state of an object.

Definition at line 62 of file Unbounded_Set_Ex.cpp.

References ACE_BEGIN_DUMP, ACE_DEBUG, ACE_END_DUMP, ACE_TEXT, ACE_TRACE, ACE_Unbounded_Set_Ex< T, C >::end(), and LM_DEBUG.

00063 {
00064 #if defined (ACE_HAS_DUMP)
00065   ACE_TRACE ("ACE_Unbounded_Set_Ex<T, C>::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 }

template<class T, class C>
ACE_Unbounded_Set_Ex< T, C >::const_iterator ACE_Unbounded_Set_Ex< T, C >::end ( void   )  const

Definition at line 277 of file Unbounded_Set_Ex.cpp.

00278 {
00279   // ACE_TRACE ("ACE_Unbounded_Set_Ex<T, C>::end");
00280   return const_iterator (*this, 1);
00281 }

template<class T, class C>
ACE_Unbounded_Set_Ex< T, C >::iterator ACE_Unbounded_Set_Ex< T, C >::end ( void   ) 

Definition at line 263 of file Unbounded_Set_Ex.cpp.

Referenced by ACE_Unbounded_Set_Ex< T, C >::dump(), ACE_Unbounded_Set_Ex< T, C >::find(), and ACE_Local_Memory_Pool::release().

00264 {
00265   // ACE_TRACE ("ACE_Unbounded_Set_Ex<T, C>::end");
00266   return iterator (*this, 1);
00267 }

template<class T, class C>
int ACE_Unbounded_Set_Ex< T, C >::find ( const T &  item  )  const

Performs a linear find operation.

Definition at line 205 of file Unbounded_Set_Ex.cpp.

References ACE_Unbounded_Set_Ex< T, C >::end().

Referenced by ACE_Hash_Multi_Map_Manager< EXT_ID, INT_ID, HASH_KEY, COMPARE_KEYS, ACE_LOCK >::find_i().

00206 {
00207   // ACE_TRACE ("ACE_Unbounded_Set_Ex<T, C>::find");
00208   const_iterator const the_end = this->end ();
00209   for (const_iterator i = this->begin (); i != the_end; ++i)
00210     if (this->comp_(*i, item))
00211       return 0;
00212 
00213   return -1;
00214 }

template<class T, class C>
int ACE_Unbounded_Set_Ex< T, C >::insert ( const T &  new_item  ) 

Linear insertion of an item.

Insert new_item into the set (doesn't allow duplicates). Returns -1 if failures occur, 1 if item is already present, else 0.

Definition at line 217 of file Unbounded_Set_Ex.cpp.

References ACE_Unbounded_Set_Ex< T, C >::insert_tail().

Referenced by ACE_Timer_Heap_T< TYPE, FUNCTOR, ACE_LOCK >::grow_heap(), ACE_Service_Gestalt::insert(), ACE_Remote_Name_Space::list_name_entries(), ACE_Remote_Name_Space::list_names(), ACE_Local_Name_Space<, ACE_LOCK >::list_names_i(), ACE_Remote_Name_Space::list_type_entries(), ACE_Local_Name_Space<, ACE_LOCK >::list_type_entries_i(), ACE_Remote_Name_Space::list_types(), ACE_Local_Name_Space<, ACE_LOCK >::list_types_i(), ACE_Remote_Name_Space::list_value_entries(), ACE_Local_Name_Space<, ACE_LOCK >::list_value_entries_i(), ACE_Remote_Name_Space::list_values(), and ACE_Local_Name_Space<, ACE_LOCK >::list_values_i().

00218 {
00219   // ACE_TRACE ("ACE_Unbounded_Set_Ex<T, C>::insert");
00220   if (this->find (item) == 0)
00221     return 1;
00222   else
00223     return this->insert_tail (item);
00224 }

template<class T, class C>
int ACE_Unbounded_Set_Ex< T, C >::insert_tail ( const T &  item  ) 

Constant time insert at the end of the set.

Definition at line 30 of file Unbounded_Set_Ex.cpp.

References ACE_NEW_MALLOC_RETURN, ACE_Unbounded_Set_Ex< T, C >::cur_size_, ACE_Unbounded_Set_Ex< T, C >::head_, ACE_Node< T, C >::item_, and ACE_Node< T, C >::next_.

Referenced by ACE_Unbounded_Set_Ex< T, C >::copy_nodes(), and ACE_Unbounded_Set_Ex< T, C >::insert().

00031 {
00032   // ACE_TRACE ("ACE_Unbounded_Set_Ex<T, C>::insert_tail");
00033   NODE *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<NODE*> (this->allocator_->malloc (sizeof (NODE))),
00041                          NODE (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 }

template<class T, class C>
ACE_BEGIN_VERSIONED_NAMESPACE_DECL ACE_INLINE bool ACE_Unbounded_Set_Ex< T, C >::is_empty ( void   )  const

Returns true if the container is empty, otherwise returns false.

Constant time is_empty check.

Definition at line 10 of file Unbounded_Set_Ex.inl.

References ACE_TRACE, ACE_Unbounded_Set_Ex< T, C >::head_, and ACE_Node< T, C >::next_.

00011 {
00012   ACE_TRACE ("ACE_Unbounded_Set_Ex<T>::is_empty");
00013   return this->head_ == this->head_->next_;
00014 }

template<class T, class C>
ACE_INLINE bool ACE_Unbounded_Set_Ex< T, C >::is_full ( void   )  const

Returns false.

Always returns false since the set can never fill up.

Definition at line 17 of file Unbounded_Set_Ex.inl.

References ACE_TRACE.

00018 {
00019   ACE_TRACE ("ACE_Unbounded_Set_Ex<T>::is_full");
00020   return 0; // We should implement a "node of last resort for this..."
00021 }

template<class T, class C>
ACE_Unbounded_Set_Ex< T, C > & ACE_Unbounded_Set_Ex< T, C >::operator= ( const ACE_Unbounded_Set_Ex< T, C > &   ) 

Assignment operator.

Perform a deep copy of the rhs into the lhs.

Definition at line 191 of file Unbounded_Set_Ex.cpp.

References ACE_TRACE, ACE_Unbounded_Set_Ex< T, C >::copy_nodes(), and ACE_Unbounded_Set_Ex< T, C >::delete_nodes().

00192 {
00193   ACE_TRACE ("ACE_Unbounded_Set_Ex<T, C>::operator=");
00194 
00195   if (this != &us)
00196     {
00197       this->delete_nodes ();
00198       this->copy_nodes (us);
00199     }
00200 
00201   return *this;
00202 }

template<class T, class C>
int ACE_Unbounded_Set_Ex< T, C >::remove ( const T &  item  ) 

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 227 of file Unbounded_Set_Ex.cpp.

References ACE_DES_FREE_TEMPLATE2, ACE_Unbounded_Set_Ex< T, C >::cur_size_, ACE_Unbounded_Set_Ex< T, C >::head_, ACE_Node< T, C >::item_, and ACE_Node< T, C >::next_.

Referenced by ACE_Connector< SVC_HANDLER, ACE_PEER_CONNECTOR_2 >::close().

00228 {
00229   // ACE_TRACE ("ACE_Unbounded_Set_Ex<T, C>::remove");
00230 
00231   // Insert the item to be founded into the dummy node.
00232   this->head_->item_ = item;
00233 
00234   NODE *curr = this->head_;
00235 
00236   while (!(this->comp_ (curr->next_->item_, item)))
00237     curr = curr->next_;
00238 
00239   if (curr->next_ == this->head_)
00240     return -1; // Item was not found.
00241   else
00242     {
00243       NODE *temp = curr->next_;
00244       // Skip over the node that we're deleting.
00245       curr->next_ = temp->next_;
00246       --this->cur_size_;
00247       ACE_DES_FREE_TEMPLATE2 (temp,
00248                              this->allocator_->free,
00249                              ACE_Node,
00250                              T, C);
00251       return 0;
00252     }
00253 }

template<class T, class C>
void ACE_Unbounded_Set_Ex< T, C >::reset ( void   ) 

Reset the ACE_Unbounded_Set_Ex to be empty.

Delete the nodes of the set.

Definition at line 54 of file Unbounded_Set_Ex.cpp.

References ACE_TRACE, and ACE_Unbounded_Set_Ex< T, C >::delete_nodes().

Referenced by ACE_Local_Memory_Pool::release().

00055 {
00056   ACE_TRACE ("reset");
00057 
00058   this->delete_nodes ();
00059 }

template<class T, class C>
ACE_BEGIN_VERSIONED_NAMESPACE_DECL size_t ACE_Unbounded_Set_Ex< T, C >::size ( void   )  const

Size of the set.

Access the size of the set.

Definition at line 23 of file Unbounded_Set_Ex.cpp.

00024 {
00025   // ACE_TRACE ("ACE_Unbounded_Set_Ex<T, C>::size");
00026   return this->cur_size_;
00027 }

Friends And Related Function Documentation

template<class T, class C>
friend class ACE_Unbounded_Set_Ex_Const_Iterator< T, C > [friend]

Definition at line 199 of file Unbounded_Set_Ex.h.

template<class T, class C>
friend class ACE_Unbounded_Set_Ex_Iterator< T, C > [friend]

Definition at line 198 of file Unbounded_Set_Ex.h.

Member Data Documentation

template<class T, class C>
ACE_Unbounded_Set_Ex< T, C >::ACE_ALLOC_HOOK_DECLARE

Declare the dynamic allocation hooks.

Definition at line 310 of file Unbounded_Set_Ex.h.

template<class T, class C>
ACE_Allocator* ACE_Unbounded_Set_Ex< T, C >::allocator_ [private]

Allocation strategy of the set.

Definition at line 326 of file Unbounded_Set_Ex.h.

Referenced by ACE_Unbounded_Set_Ex< T, C >::ACE_Unbounded_Set_Ex().

template<class T, class C>
COMP ACE_Unbounded_Set_Ex< T, C >::comp_ [private]

Comparator to be used.

Definition at line 329 of file Unbounded_Set_Ex.h.

template<class T, class C>
size_t ACE_Unbounded_Set_Ex< T, C >::cur_size_ [private]

Current size of the set.

Definition at line 323 of file Unbounded_Set_Ex.h.

Referenced by ACE_Unbounded_Set_Ex< T, C >::delete_nodes(), ACE_Unbounded_Set_Ex< T, C >::insert_tail(), and ACE_Unbounded_Set_Ex< T, C >::remove().

template<class T, class C>
NODE* ACE_Unbounded_Set_Ex< T, C >::head_ [private]

Head of the linked list of Nodes.

Definition at line 320 of file Unbounded_Set_Ex.h.

Referenced by ACE_Unbounded_Set_Ex< T, C >::ACE_Unbounded_Set_Ex(), ACE_Unbounded_Set_Ex< T, C >::copy_nodes(), ACE_Unbounded_Set_Ex< T, C >::delete_nodes(), ACE_Unbounded_Set_Ex< T, C >::insert_tail(), ACE_Unbounded_Set_Ex< T, C >::is_empty(), ACE_Unbounded_Set_Ex< T, C >::remove(), and ACE_Unbounded_Set_Ex< T, C >::~ACE_Unbounded_Set_Ex().

The documentation for this class was generated from the following files:
Generated on Tue Feb 2 17:35:51 2010 for ACE by  doxygen 1.4.7