Main Page   Class Hierarchy   Alphabetical List   Compound List   File List   Compound Members   File Members   Related Pages  

ACE_Fixed_Set Class Template Reference

Implement a simple unordered set of <T> with maximum <ACE_SIZE>. More...

#include <Containers_T.h>

Inheritance diagram for ACE_Fixed_Set:

Inheritance graph
[legend]
Collaboration diagram for ACE_Fixed_Set:

Collaboration graph
[legend]
List of all members.

Public Types

typedef ACE_Fixed_Set_Iterator<
T, ACE_SIZE > 		ITERATOR
typedef ACE_Fixed_Set_Iterator<
T, ACE_SIZE > 		CONST_ITERATOR

Public Methods

 ACE_Fixed_Set (void)
 Default Constructor. More...

 ACE_Fixed_Set (const ACE_Fixed_Set< T, ACE_SIZE > &)
 Copy constructor. More...

void operator= (const ACE_Fixed_Set< T, ACE_SIZE > &)
 Assignment operator. More...

 ~ACE_Fixed_Set (void)
 Destructor. More...

int is_empty (void) const
 Returns 1 if the container is empty, otherwise returns 0. More...

int is_full (void) const
 Returns 1 if the container is full, otherwise returns 0. More...

int insert (const T &new_item)
 Linear time insertion of an item unique to the set. More...

int remove (const T &item)
 Linear time removal operation of an item. More...

int find (const T &item) const
 Finds if item occurs in the set. Returns 0 if finds, else -1. More...

size_t size (void) const
 Size of the set. More...

void dump (void) const
 Dump the state of an object. More...


Public Attributes

 ACE_ALLOC_HOOK_DECLARE
 Declare the dynamic allocation hooks. More...


Private Attributes

struct {
   T   item_
   int   is_free_
} search_structure_ [ACE_SIZE]
 Holds the contents of the set. More...

size_t cur_size_
 Current size of the set. More...

size_t max_size_
 Maximum size of the set. More...


Friends

class ACE_Fixed_Set_Iterator< T, ACE_SIZE >
class ACE_Fixed_Set_Const_Iterator< T, ACE_SIZE >

Detailed Description

template<class T, size_t ACE_SIZE>
class ACE_Fixed_Set< T, ACE_SIZE >

Implement a simple unordered set of <T> with maximum <ACE_SIZE>.

This implementation of an unordered set uses a fixed array. It does not allow duplicate members. The set provides linear insertion/deletion operations.

Requirements and Performance Characteristics

Definition at line 1327 of file Containers_T.h.

Member Typedef Documentation

template<class T, size_t ACE_SIZE>
typedef ACE_Fixed_Set_Iterator<T, ACE_SIZE> ACE_Fixed_Set::CONST_ITERATOR
 

Definition at line 1335 of file Containers_T.h.

template<class T, size_t ACE_SIZE>
typedef ACE_Fixed_Set_Iterator<T, ACE_SIZE> ACE_Fixed_Set::ITERATOR
 

Definition at line 1334 of file Containers_T.h.

Constructor & Destructor Documentation

template<class T, size_t ACE_SIZE>
ACE_Fixed_Set< T, ACE_SIZE >::ACE_Fixed_Set (  void    ) 
 

Default Constructor.

Creates an empy set

Definition at line 951 of file Containers_T.cpp.

References ACE_TRACE, max_size_, and search_structure_. 

00952   : cur_size_ (0),
00953     max_size_ (ACE_SIZE)
00954 {
00955   ACE_TRACE ("ACE_Fixed_Set<T, ACE_SIZE>::ACE_Fixed_Set");
00956   for (size_t i = 0; i < this->max_size_; i++)
00957     this->search_structure_[i].is_free_ = 1;
00958 }

template<class T, size_t ACE_SIZE>
ACE_Fixed_Set< T, ACE_SIZE >::ACE_Fixed_Set (  const ACE_Fixed_Set< T, ACE_SIZE > &    ) 
 

Copy constructor.

Initializes a set to be a copy of the set parameter.

Definition at line 927 of file Containers_T.cpp.

References ACE_TRACE, cur_size_, and search_structure_. 

00928   : cur_size_ (fs.cur_size_)
00929 {
00930   ACE_TRACE ("ACE_Fixed_Set<T>::ACE_Fixed_Set");
00931 
00932   for (size_t i = 0; i < this->cur_size_; i++)
00933     this->search_structure_[i] = fs.search_structure_[i];
00934 }

template<class T, size_t ACE_SIZE>
ACE_Fixed_Set< T, ACE_SIZE >::~ACE_Fixed_Set (  void    ) 
 

Destructor.

Destroys a set.

Definition at line 920 of file Containers_T.cpp.

References ACE_TRACE, and cur_size_. 

00921 {
00922   ACE_TRACE ("ACE_Fixed_Set<T, ACE_SIZE>::~ACE_Fixed_Set");
00923   this->cur_size_ = 0;
00924 }

Member Function Documentation

template<class T, size_t ACE_SIZE>
void ACE_Fixed_Set< T, ACE_SIZE >::dump (  void    )  const
 

Dump the state of an object.

Definition at line 914 of file Containers_T.cpp.

References ACE_TRACE. 

00915 {
00916   ACE_TRACE ("ACE_Fixed_Set<T, ACE_SIZE>::dump");
00917 }

template<class T, size_t ACE_SIZE>
int ACE_Fixed_Set< T, ACE_SIZE >::find (  const T &    item )  const
 

Finds if item occurs in the set. Returns 0 if finds, else -1.

Performs a linear find operation for the specified item.

Definition at line 961 of file Containers_T.cpp.

References ACE_TRACE, cur_size_, and search_structure_. 

00962 {
00963   ACE_TRACE ("ACE_Fixed_Set<T, ACE_SIZE>::find");
00964 
00965   for (size_t i = 0; i < this->cur_size_; i++)
00966     if (this->search_structure_[i].item_ == item
00967         && this->search_structure_[i].is_free_ == 0)
00968       return 0;
00969 
00970   return -1;
00971 }

template<class T, size_t ACE_SIZE>
int ACE_Fixed_Set< T, ACE_SIZE >::insert (  const T &    new_item ) 
 

Linear time insertion of an item unique to the set.

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 974 of file Containers_T.cpp.

References ACE_TRACE, cur_size_, max_size_, search_structure_, and ssize_t. 

00975 {
00976   ACE_TRACE ("ACE_Fixed_Set<T, ACE_SIZE>::insert");
00977   ssize_t first_free = -1;   // Keep track of first free slot.
00978   size_t i;
00979 
00980   for (i = 0; i < this->cur_size_; i++)
00981     // First, make sure we don't allow duplicates.
00982 
00983     if (this->search_structure_[i].item_ == item
00984         && this->search_structure_[i].is_free_ == 0)
00985       return 1;
00986     else if (this->search_structure_[i].is_free_
00987              && first_free == -1)
00988       first_free = i;
00989 
00990   // If we found a free spot let's reuse it.
00991   if (first_free > -1)
00992     {
00993       this->search_structure_[first_free].item_ = item;
00994       this->search_structure_[first_free].is_free_ = 0;
00995       return 0;
00996     }
00997   // Insert at the end of the active portion.
00998   else if (i < this->max_size_)
00999     {
01000       this->search_structure_[i].item_ = item;
01001       this->search_structure_[i].is_free_ = 0;
01002       this->cur_size_++;
01003       return 0;
01004     }
01005   else /* No more room! */
01006     {
01007       errno = ENOMEM;
01008       return -1;
01009     }
01010 }

template<class T, size_t ACE_SIZE>
ACE_INLINE int ACE_Fixed_Set< T, ACE_SIZE >::is_empty (  void    )  const
 

Returns 1 if the container is empty, otherwise returns 0.

Performs constant time check to determine if a set is empty.

Definition at line 165 of file Containers_T.i.

References ACE_TRACE, and cur_size_. 

00166 {
00167   ACE_TRACE ("ACE_Fixed_Set<T>::is_empty");
00168   return this->cur_size_ == 0;
00169 }

template<class T, size_t ACE_SIZE>
ACE_INLINE int ACE_Fixed_Set< T, ACE_SIZE >::is_full (  void    )  const
 

Returns 1 if the container is full, otherwise returns 0.

Performs a constant time check to see if the set is full.

Definition at line 172 of file Containers_T.i.

References ACE_TRACE, cur_size_, and max_size_. 

00173 {
00174   ACE_TRACE ("ACE_Fixed_Set<T, ACE_SIZE>::is_full");
00175   return this->cur_size_ == this->max_size_;
00176 }

template<class T, size_t ACE_SIZE>
void ACE_Fixed_Set< T, ACE_SIZE >::operator= (  const ACE_Fixed_Set< T, ACE_SIZE > &    ) 
 

Assignment operator.

Deep copy of one set to another.

Definition at line 937 of file Containers_T.cpp.

References ACE_TRACE, cur_size_, and search_structure_. 

00938 {
00939   ACE_TRACE ("ACE_Fixed_Set<T>::operator=");
00940 
00941   if (this != &fs)
00942     {
00943       this->cur_size_ = fs.cur_size_;
00944 
00945       for (size_t i = 0; i < this->cur_size_; i++)
00946         this->search_structure_[i] = fs.search_structure_[i];
00947     }
00948 }

template<class T, size_t ACE_SIZE>
int ACE_Fixed_Set< T, ACE_SIZE >::remove (  const T &    item ) 
 

Linear time removal operation of an item.

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. Removal doesn't reclaim memory for the item.

Definition at line 1013 of file Containers_T.cpp.

References ACE_TRACE, cur_size_, and search_structure_. 

01014 {
01015   ACE_TRACE ("ACE_Fixed_Set<T, ACE_SIZE>::remove");
01016 
01017   for (size_t i = 0; i < this->cur_size_; i++)
01018     if (this->search_structure_[i].item_ == item)
01019       {
01020         // Mark this entry as being free.
01021         this->search_structure_[i].is_free_ = 1;
01022 
01023         // If we just unbound the highest entry, then we need to
01024         // figure out where the next highest active entry is.
01025         if (i + 1 == this->cur_size_)
01026           {
01027             while (i > 0
01028                    && this->search_structure_[--i].is_free_)
01029               continue;
01030 
01031             if (i == 0
01032                 && this->search_structure_[i].is_free_)
01033               this->cur_size_ = 0;
01034             else
01035               this->cur_size_ = i + 1;
01036           }
01037         return 0;
01038       }
01039 
01040   return -1;
01041 }

template<class T, size_t ACE_SIZE>
size_t ACE_Fixed_Set< T, ACE_SIZE >::size (  void    )  const
 

Size of the set.

Returns the current size of the set.

Definition at line 901 of file Containers_T.cpp.

References cur_size_. 

00902 {
00903   return this->cur_size_;
00904 }

Friends And Related Function Documentation

template<class T, size_t ACE_SIZE>
friend class ACE_Fixed_Set_Const_Iterator< T, ACE_SIZE > [friend]
 

Definition at line 1331 of file Containers_T.h.

template<class T, size_t ACE_SIZE>
friend class ACE_Fixed_Set_Iterator< T, ACE_SIZE > [friend]
 

Definition at line 1330 of file Containers_T.h.

Member Data Documentation

template<class T, size_t ACE_SIZE>
ACE_Fixed_Set::ACE_ALLOC_HOOK_DECLARE
 

Declare the dynamic allocation hooks.

Definition at line 1410 of file Containers_T.h.

template<class T, size_t ACE_SIZE>
size_t ACE_Fixed_Set::cur_size_ [private]
 

Current size of the set.

Definition at line 1424 of file Containers_T.h.

Referenced by ACE_Fixed_Set, find, insert, is_empty, is_full, operator=, remove, size, and ~ACE_Fixed_Set.

template<class T, size_t ACE_SIZE>
int ACE_Fixed_Set::is_free_ [private]
 

Keeps track of whether this item is in use or not.

Definition at line 1420 of file Containers_T.h.

template<class T, size_t ACE_SIZE>
T ACE_Fixed_Set::item_ [private]
 

Item in the set.

Definition at line 1417 of file Containers_T.h.

template<class T, size_t ACE_SIZE>
size_t ACE_Fixed_Set::max_size_ [private]
 

Maximum size of the set.

Definition at line 1427 of file Containers_T.h.

Referenced by ACE_Fixed_Set, insert, and is_full.

struct { ... } ACE_Fixed_Set::search_structure_[ACE_SIZE] [private]
 

Holds the contents of the set.

Referenced by ACE_Fixed_Set, find, insert, operator=, and remove.

The documentation for this class was generated from the following files:
Generated on Mon Jun 16 12:47:59 2003 for ACE by doxygen1.2.14 written by Dimitri van Heesch, © 1997-2002