#include <Containers_T.h>
Collaboration diagram for ACE_Bounded_Set< T >:
Public Types | |
typedef ACE_Bounded_Set_Iterator< T > | ITERATOR |
enum | { DEFAULT_SIZE = 10 } |
Public Member Functions | |
ACE_Bounded_Set (void) | |
Construct a Bounded_Set using the default size. | |
ACE_Bounded_Set (size_t size) | |
Construct a Bounded_Set with the provided sizeB. | |
ACE_Bounded_Set (const ACE_Bounded_Set< T > &) | |
Construct a Bounded_Set that is a copy of the provides Bounded_Set. | |
void | operator= (const ACE_Bounded_Set< T > &) |
Assignment operator. | |
~ACE_Bounded_Set (void) | |
Destructor. | |
int | is_empty (void) const |
Returns 1 if the container is empty, otherwise returns 0. | |
int | is_full (void) const |
Returns 1 if the container is full, otherwise returns 0. | |
int | insert (const T &new_item) |
Inserts a new element unique to the set. | |
int | remove (const T &item) |
Finds the specified element and removes it from the set. | |
int | find (const T &item) const |
Finds if item occurs in the set. Returns 0 if finds, else -1. | |
size_t | size (void) const |
Size of the set. | |
void | dump (void) const |
Dump the state of an object. | |
Public Attributes | |
ACE_ALLOC_HOOK_DECLARE | |
Declare the dynamic allocation hooks. | |
Private Attributes | |
Search_Structure * | search_structure_ |
Holds the contents of the set. | |
size_t | cur_size_ |
Current size of the set. | |
size_t | max_size_ |
Maximum size of the set. | |
Friends | |
class | ACE_Bounded_Set_Iterator< T > |
This implementation of an unordered set uses a Bounded array. This implementation does not allow duplicates. It provides linear insert/remove/find operations. Insertion/removal does not invalidate iterators, but caution should be taken to ensure expected behavior. Once initialized, the object has a maximum size which can only be increased by the assignment of another larger Bounded_Set.
Requirements and Performance Characteristics
Definition at line 1546 of file Containers_T.h.
|
Definition at line 1552 of file Containers_T.h. |
|
Definition at line 1554 of file Containers_T.h.
01555 { 01556 DEFAULT_SIZE = 10 01557 }; |
|
Construct a Bounded_Set using the default size. The default constructor initializes the Bounded_Set to a maximum size specified by the DEFAULT_SIZE. Definition at line 1235 of file Containers_T.cpp. References ACE_NEW, ACE_TRACE, and ACE_Bounded_Set< T >::Search_Structure::is_free_.
01236 : cur_size_ (0), 01237 max_size_ (static_cast<size_t> (ACE_Bounded_Set<T>::DEFAULT_SIZE)) 01238 { 01239 ACE_TRACE ("ACE_Bounded_Set<T>::ACE_Bounded_Set"); 01240 01241 ACE_NEW (this->search_structure_, 01242 typename ACE_Bounded_Set<T>::Search_Structure[this->max_size_]); 01243 01244 for (size_t i = 0; i < this->max_size_; ++i) 01245 this->search_structure_[i].is_free_ = 1; 01246 } |
|
Construct a Bounded_Set with the provided sizeB. Initialize the Bounded_Set to have a maximum size equal to the size parameter specified. Definition at line 1292 of file Containers_T.cpp. References ACE_NEW, ACE_TRACE, and ACE_Bounded_Set< T >::Search_Structure::is_free_.
01293 : cur_size_ (0), 01294 max_size_ (size) 01295 { 01296 ACE_TRACE ("ACE_Bounded_Set<T>::ACE_Bounded_Set"); 01297 ACE_NEW (this->search_structure_, 01298 typename ACE_Bounded_Set<T>::Search_Structure[size]); 01299 01300 for (size_t i = 0; i < this->max_size_; i++) 01301 this->search_structure_[i].is_free_ = 1; 01302 } |
|
Construct a Bounded_Set that is a copy of the provides Bounded_Set. Initialize the Bounded_Set to be a copy of the Bounded_Set parameter. Definition at line 1256 of file Containers_T.cpp. References ACE_NEW, ACE_TRACE, and ACE_Bounded_Set< T >::search_structure_.
01257 : cur_size_ (bs.cur_size_), 01258 max_size_ (bs.max_size_) 01259 { 01260 ACE_TRACE ("ACE_Bounded_Set<T>::ACE_Bounded_Set"); 01261 01262 ACE_NEW (this->search_structure_, 01263 typename ACE_Bounded_Set<T>::Search_Structure[this->max_size_]); 01264 01265 for (size_t i = 0; i < this->cur_size_; i++) 01266 this->search_structure_[i] = bs.search_structure_[i]; 01267 } |
|
Destructor. Clean up the underlying dynamically allocated memory that is used by the Bounded_Set. Definition at line 1228 of file Containers_T.cpp. References ACE_TRACE.
01229 { 01230 ACE_TRACE ("ACE_Bounded_Set<T>::~ACE_Bounded_Set"); 01231 delete [] this->search_structure_; 01232 } |
|
Dump the state of an object.
Definition at line 1220 of file Containers_T.cpp. References ACE_TRACE.
01221 { 01222 #if defined (ACE_HAS_DUMP) 01223 ACE_TRACE ("ACE_Bounded_Set<T>::dump"); 01224 #endif /* ACE_HAS_DUMP */ 01225 } |
|
Finds if item occurs in the set. Returns 0 if finds, else -1. find preforms a linear search for {item} and returns 0 on successful find and -1 otherwise. Definition at line 1305 of file Containers_T.cpp. References ACE_TRACE, ACE_Bounded_Set< T >::Search_Structure::is_free_, and ACE_Bounded_Set< T >::Search_Structure::item_.
01306 { 01307 ACE_TRACE ("ACE_Bounded_Set<T>::find"); 01308 01309 for (size_t i = 0; i < this->cur_size_; i++) 01310 if (this->search_structure_[i].item_ == item 01311 && this->search_structure_[i].is_free_ == 0) 01312 return 0; 01313 01314 return -1; 01315 } |
|
Inserts a new element unique to the set. Insert new_item into the set (doesn't allow duplicates) in linear time. Returns -1 if failures occur, 1 if item is already present, else 0. Definition at line 1318 of file Containers_T.cpp. References ACE_TRACE, ACE_Bounded_Set< T >::Search_Structure::is_free_, and ACE_Bounded_Set< T >::Search_Structure::item_.
01319 { 01320 ACE_TRACE ("ACE_Bounded_Set<T>::insert"); 01321 int first_free = -1; // Keep track of first free slot. 01322 size_t i; 01323 01324 for (i = 0; i < this->cur_size_; i++) 01325 // First, make sure we don't allow duplicates. 01326 01327 if (this->search_structure_[i].item_ == item 01328 && this->search_structure_[i].is_free_ == 0) 01329 return 1; 01330 else if (this->search_structure_[i].is_free_ && first_free == -1) 01331 first_free = static_cast<int> (i); 01332 01333 if (first_free > -1) // If we found a free spot let's reuse it. 01334 { 01335 this->search_structure_[first_free].item_ = item; 01336 this->search_structure_[first_free].is_free_ = 0; 01337 return 0; 01338 } 01339 else if (i < this->max_size_) // Insert at the end of the active portion. 01340 { 01341 this->search_structure_[i].item_ = item; 01342 this->search_structure_[i].is_free_ = 0; 01343 this->cur_size_++; 01344 return 0; 01345 } 01346 else /* No more room! */ 01347 { 01348 errno = ENOMEM; 01349 return -1; 01350 } 01351 } |
|
Returns 1 if the container is empty, otherwise returns 0. A constant time check is performed to determine if the Bounded_Set is empty. Definition at line 182 of file Containers_T.inl. References ACE_TRACE.
|
|
Returns 1 if the container is full, otherwise returns 0. Performs a constant time check to determine if the Bounded_Set is at capacity. Definition at line 189 of file Containers_T.inl. References ACE_TRACE.
|
|
Assignment operator. The assignment will make a deep copy of the Bounded_Set provided. If the rhs has more elements than the capacity of the lhs, then the lhs will be deleted and reallocated to accomadate the larger number of elements. Definition at line 1270 of file Containers_T.cpp. References ACE_NEW, ACE_TRACE, ACE_Bounded_Set< T >::cur_size_, and ACE_Bounded_Set< T >::search_structure_.
01271 { 01272 ACE_TRACE ("ACE_Bounded_Set<T>::operator="); 01273 01274 if (this != &bs) 01275 { 01276 if (this->max_size_ < bs.cur_size_) 01277 { 01278 delete [] this->search_structure_; 01279 ACE_NEW (this->search_structure_, 01280 typename ACE_Bounded_Set<T>::Search_Structure[bs.cur_size_]); 01281 this->max_size_ = bs.cur_size_; 01282 } 01283 01284 this->cur_size_ = bs.cur_size_; 01285 01286 for (size_t i = 0; i < this->cur_size_; i++) 01287 this->search_structure_[i] = bs.search_structure_[i]; 01288 } 01289 } |
|
Finds the specified element and removes it from the set. 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. The linear remove operation does not reclaim the memory associated with the removed item. Definition at line 1354 of file Containers_T.cpp. References ACE_TRACE, ACE_Bounded_Set< T >::Search_Structure::is_free_, and ACE_Bounded_Set< T >::Search_Structure::item_.
01355 { 01356 ACE_TRACE ("ACE_Bounded_Set<T>::remove"); 01357 for (size_t i = 0; i < this->cur_size_; i++) 01358 if (this->search_structure_[i].item_ == item) 01359 { 01360 // Mark this entry as being free. 01361 this->search_structure_[i].is_free_ = 1; 01362 01363 // If we just unbound the highest entry, then we need to 01364 // figure out where the next highest active entry is. 01365 if (i + 1 == this->cur_size_) 01366 { 01367 while (i > 0 && this->search_structure_[--i].is_free_) 01368 continue; 01369 01370 if (i == 0 && this->search_structure_[i].is_free_) 01371 this->cur_size_ = 0; 01372 else 01373 this->cur_size_ = i + 1; 01374 } 01375 return 0; 01376 } 01377 01378 return -1; 01379 } |
|
Size of the set. Returns a size_t representing the current size of the set. Definition at line 1249 of file Containers_T.cpp. References ACE_TRACE.
|
|
Definition at line 1549 of file Containers_T.h. |
|
Declare the dynamic allocation hooks.
Definition at line 1648 of file Containers_T.h. |
|
Current size of the set.
Definition at line 1664 of file Containers_T.h. Referenced by ACE_Bounded_Set< T >::operator=(). |
|
Maximum size of the set.
Definition at line 1667 of file Containers_T.h. |
|
Holds the contents of the set.
Definition at line 1661 of file Containers_T.h. Referenced by ACE_Bounded_Set< T >::ACE_Bounded_Set(), and ACE_Bounded_Set< T >::operator=(). |