#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 1548 of file Containers_T.h.
|
Definition at line 1554 of file Containers_T.h. |
|
Definition at line 1556 of file Containers_T.h.
01557 { 01558 DEFAULT_SIZE = 10 01559 }; |
|
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 1239 of file Containers_T.cpp. References ACE_NEW, ACE_TRACE, and ACE_Bounded_Set< T >::Search_Structure::is_free_.
01240 : cur_size_ (0), 01241 max_size_ (static_cast<size_t> (ACE_Bounded_Set<T>::DEFAULT_SIZE)) 01242 { 01243 ACE_TRACE ("ACE_Bounded_Set<T>::ACE_Bounded_Set"); 01244 01245 ACE_NEW (this->search_structure_, 01246 ACE_TYPENAME ACE_Bounded_Set<T>::Search_Structure[this->max_size_]); 01247 01248 for (size_t i = 0; i < this->max_size_; ++i) 01249 this->search_structure_[i].is_free_ = 1; 01250 } |
|
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 1296 of file Containers_T.cpp. References ACE_NEW, ACE_TRACE, and ACE_Bounded_Set< T >::Search_Structure::is_free_.
01297 : cur_size_ (0), 01298 max_size_ (size) 01299 { 01300 ACE_TRACE ("ACE_Bounded_Set<T>::ACE_Bounded_Set"); 01301 ACE_NEW (this->search_structure_, 01302 ACE_TYPENAME ACE_Bounded_Set<T>::Search_Structure[size]); 01303 01304 for (size_t i = 0; i < this->max_size_; i++) 01305 this->search_structure_[i].is_free_ = 1; 01306 } |
|
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 1260 of file Containers_T.cpp. References ACE_NEW, ACE_TRACE, and ACE_Bounded_Set< T >::search_structure_.
01261 : cur_size_ (bs.cur_size_), 01262 max_size_ (bs.max_size_) 01263 { 01264 ACE_TRACE ("ACE_Bounded_Set<T>::ACE_Bounded_Set"); 01265 01266 ACE_NEW (this->search_structure_, 01267 ACE_TYPENAME ACE_Bounded_Set<T>::Search_Structure[this->max_size_]); 01268 01269 for (size_t i = 0; i < this->cur_size_; i++) 01270 this->search_structure_[i] = bs.search_structure_[i]; 01271 } |
|
Destructor. Clean up the underlying dynamically allocated memory that is used by the Bounded_Set. Definition at line 1232 of file Containers_T.cpp. References ACE_TRACE.
01233 { 01234 ACE_TRACE ("ACE_Bounded_Set<T>::~ACE_Bounded_Set"); 01235 delete [] this->search_structure_; 01236 } |
|
Dump the state of an object.
Definition at line 1224 of file Containers_T.cpp. References ACE_TRACE.
01225 { 01226 #if defined (ACE_HAS_DUMP) 01227 ACE_TRACE ("ACE_Bounded_Set<T>::dump"); 01228 #endif /* ACE_HAS_DUMP */ 01229 } |
|
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 1309 of file Containers_T.cpp. References ACE_TRACE, ACE_Bounded_Set< T >::Search_Structure::is_free_, and ACE_Bounded_Set< T >::Search_Structure::item_.
01310 { 01311 ACE_TRACE ("ACE_Bounded_Set<T>::find"); 01312 01313 for (size_t i = 0; i < this->cur_size_; i++) 01314 if (this->search_structure_[i].item_ == item 01315 && this->search_structure_[i].is_free_ == 0) 01316 return 0; 01317 01318 return -1; 01319 } |
|
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 1322 of file Containers_T.cpp. References ACE_TRACE, ACE_Bounded_Set< T >::Search_Structure::is_free_, and ACE_Bounded_Set< T >::Search_Structure::item_.
01323 { 01324 ACE_TRACE ("ACE_Bounded_Set<T>::insert"); 01325 int first_free = -1; // Keep track of first free slot. 01326 size_t i; 01327 01328 for (i = 0; i < this->cur_size_; i++) 01329 // First, make sure we don't allow duplicates. 01330 01331 if (this->search_structure_[i].item_ == item 01332 && this->search_structure_[i].is_free_ == 0) 01333 return 1; 01334 else if (this->search_structure_[i].is_free_ && first_free == -1) 01335 first_free = static_cast<int> (i); 01336 01337 if (first_free > -1) // If we found a free spot let's reuse it. 01338 { 01339 this->search_structure_[first_free].item_ = item; 01340 this->search_structure_[first_free].is_free_ = 0; 01341 return 0; 01342 } 01343 else if (i < this->max_size_) // Insert at the end of the active portion. 01344 { 01345 this->search_structure_[i].item_ = item; 01346 this->search_structure_[i].is_free_ = 0; 01347 this->cur_size_++; 01348 return 0; 01349 } 01350 else /* No more room! */ 01351 { 01352 errno = ENOMEM; 01353 return -1; 01354 } 01355 } |
|
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 1274 of file Containers_T.cpp. References ACE_NEW, ACE_TRACE, ACE_Bounded_Set< T >::cur_size_, and ACE_Bounded_Set< T >::search_structure_.
01275 { 01276 ACE_TRACE ("ACE_Bounded_Set<T>::operator="); 01277 01278 if (this != &bs) 01279 { 01280 if (this->max_size_ < bs.cur_size_) 01281 { 01282 delete [] this->search_structure_; 01283 ACE_NEW (this->search_structure_, 01284 ACE_TYPENAME ACE_Bounded_Set<T>::Search_Structure[bs.cur_size_]); 01285 this->max_size_ = bs.cur_size_; 01286 } 01287 01288 this->cur_size_ = bs.cur_size_; 01289 01290 for (size_t i = 0; i < this->cur_size_; i++) 01291 this->search_structure_[i] = bs.search_structure_[i]; 01292 } 01293 } |
|
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 1358 of file Containers_T.cpp. References ACE_TRACE, ACE_Bounded_Set< T >::Search_Structure::is_free_, and ACE_Bounded_Set< T >::Search_Structure::item_.
01359 { 01360 ACE_TRACE ("ACE_Bounded_Set<T>::remove"); 01361 for (size_t i = 0; i < this->cur_size_; i++) 01362 if (this->search_structure_[i].item_ == item) 01363 { 01364 // Mark this entry as being free. 01365 this->search_structure_[i].is_free_ = 1; 01366 01367 // If we just unbound the highest entry, then we need to 01368 // figure out where the next highest active entry is. 01369 if (i + 1 == this->cur_size_) 01370 { 01371 while (i > 0 && this->search_structure_[--i].is_free_) 01372 continue; 01373 01374 if (i == 0 && this->search_structure_[i].is_free_) 01375 this->cur_size_ = 0; 01376 else 01377 this->cur_size_ = i + 1; 01378 } 01379 return 0; 01380 } 01381 01382 return -1; 01383 } |
|
Size of the set. Returns a size_t representing the current size of the set. Definition at line 1253 of file Containers_T.cpp. References ACE_TRACE.
|
|
Definition at line 1551 of file Containers_T.h. |
|
Declare the dynamic allocation hooks.
Definition at line 1650 of file Containers_T.h. |
|
Current size of the set.
Definition at line 1666 of file Containers_T.h. Referenced by ACE_Bounded_Set< T >::operator=(). |
|
Maximum size of the set.
Definition at line 1669 of file Containers_T.h. |
|
Holds the contents of the set.
Definition at line 1663 of file Containers_T.h. Referenced by ACE_Bounded_Set< T >::ACE_Bounded_Set(), and ACE_Bounded_Set< T >::operator=(). |