ACE/ace/Array_Map.cpp

   1 #ifndef ACE_ARRAY_MAP_CPP
   2 #define ACE_ARRAY_MAP_CPP
   3
   4 #include "ace/Array_Map.h"
   5
   6 #ifndef __ACE_INLINE__
   7 # include "ace/Array_Map.inl"
   8 #endif  /* !__ACE_INLINE__ */
   9
  10 #include <algorithm>
  11
  12 ACE_BEGIN_VERSIONED_NAMESPACE_DECL
  13
  14 template<typename Key, typename Value, class EqualTo, class Alloc>
  15 template<typename InputIterator>
  16 ACE_Array_Map<Key, Value, EqualTo, Alloc>::ACE_Array_Map (InputIterator f,
  17                                                           InputIterator l)
  18   : size_ (l - f)
  19   , capacity_ (size_)
  20   , nodes_ (size_ == 0 ? 0 : this->alloc_.allocate (size_))
  21 {
  22   (void) std::uninitialized_copy (f,
  23                                   l,
  24                                   this->begin ());
  25 }
  26
  27 template<typename Key, typename Value, class EqualTo, class Alloc>
  28 ACE_Array_Map<Key, Value, EqualTo, Alloc>::ACE_Array_Map (
  29   ACE_Array_Map<Key, Value, EqualTo, Alloc> const & map)
  30   : size_ (map.size_)
  31   , capacity_ (map.size_)
  32   , nodes_ (size_ == 0 ? 0 : this->alloc_.allocate (size_))
  33 {
  34   (void) std::uninitialized_copy (map.begin (),
  35                                   map.end (),
  36                                   this->begin ());
  37 }
  38
  39 template<typename Key, typename Value, class EqualTo, class Alloc>
  40 ACE_Array_Map<Key, Value, EqualTo, Alloc>::~ACE_Array_Map ()
  41 {
  42   for (size_t idx = 0; idx != capacity_; ++idx)
  43   {
  44 #if defined (ACE_HAS_BCC32)
  45     using std::pair;
  46     (nodes_ + idx)->~pair<key_type, mapped_type>();
  47 #else
  48     (nodes_ + idx)->~value_type();
  49 #endif
  50
  51   }
  52
  53   alloc_.deallocate(this->nodes_, capacity_);
  54 }
  55
  56 template<typename Key, typename Value, class EqualTo, class Alloc>
  57 void
  58 ACE_Array_Map<Key, Value, EqualTo, Alloc>::swap (
  59   ACE_Array_Map<Key, Value, EqualTo, Alloc> & map)
  60 {
  61   std::swap (this->size_, map.size_);
  62   std::swap (this->capacity_, map.capacity_);
  63   std::swap (this->nodes_, map.nodes_);
  64 }
  65
  66 template<typename Key, typename Value, class EqualTo, class Alloc>
  67 std::pair<typename ACE_Array_Map<Key, Value, EqualTo, Alloc>::iterator, bool>
  68 ACE_Array_Map<Key, Value, EqualTo, Alloc>::insert (
  69   typename ACE_Array_Map<Key, Value, EqualTo, Alloc>::value_type const & x)
  70 {
  71   // Linear insertion due to linear duplicate key search.
  72
  73   bool inserted = false;
  74   iterator i = this->find (x.first);
  75
  76   if (i == this->end ())
  77     {
  78       // Add the element to the array.
  79
  80       size_type const old_size = this->size ();
  81       this->grow (1);  // Increase size by at least one.
  82
  83       i = this->begin () + old_size;
  84       *i = x;
  85
  86        ++this->size_;
  87
  88       inserted = true;
  89     }
  90
  91   return std::make_pair (i, inserted);
  92 }
  93
  94 template<typename Key, typename Value, class EqualTo, class Alloc>
  95 template<typename InputIterator>
  96 void
  97 ACE_Array_Map<Key, Value, EqualTo, Alloc>::insert (InputIterator f, InputIterator l)
  98 {
  99   this->grow (l - f);  // Preallocate storage.
 100
 101   for (InputIterator i = f; i != l; ++i)
 102     {
 103       (void) this->insert (*i);
 104     }
 105 }
 106
 107 template<typename Key, typename Value, class EqualTo, class Alloc>
 108 void
 109 ACE_Array_Map<Key, Value, EqualTo, Alloc>::erase (
 110   typename ACE_Array_Map<Key, Value, EqualTo, Alloc>::iterator pos)
 111 {
 112   iterator const first = this->begin ();
 113   iterator const last = this->end ();
 114
 115   if (pos >= first && pos < last)
 116     {
 117       if (pos != last - 1)
 118         {
 119           // Relocate the tail element to the location of the erased
 120           // element to prevent introduction of "holes" in the
 121           // underlying array.
 122           *pos = *(last - 1);
 123         }
 124
 125       // Explicitly destroy the tail element by assigning a default
 126       // constructed instance to it.  Note that this also works for
 127       // the case of a map of size 1.
 128       *(last - 1) = value_type ();
 129
 130       --this->size_;
 131     }
 132 }
 133
 134 template<typename Key, typename Value, class EqualTo, class Alloc>
 135 typename ACE_Array_Map<Key, Value, EqualTo, Alloc>::size_type
 136 ACE_Array_Map<Key, Value, EqualTo, Alloc>::erase (
 137   typename ACE_Array_Map<Key, Value, EqualTo, Alloc>::key_type const & k)
 138 {
 139   iterator pos = this->find (k);
 140
 141   size_type const old_size = this->size_;
 142
 143   this->erase (pos);
 144
 145   return old_size - this->size_;
 146 }
 147
 148 template<typename Key, typename Value, class EqualTo, class Alloc>
 149 void
 150 ACE_Array_Map<Key, Value, EqualTo, Alloc>::erase (
 151   typename ACE_Array_Map<Key, Value, EqualTo, Alloc>::iterator first,
 152   typename ACE_Array_Map<Key, Value, EqualTo, Alloc>::iterator last)
 153 {
 154   if (this->begin () <= first && first < last && last < this->end ())
 155     for (iterator i = first; i != last; ++i)
 156       this->erase (i);
 157 }
 158
 159 template<typename Key, typename Value, class EqualTo, class Alloc>
 160 void
 161 ACE_Array_Map<Key, Value, EqualTo, Alloc>::clear ()
 162 {
 163   this->size_ = 0;  // No need to deallocate array nor destroy elements.
 164 }
 165
 166 template<typename Key, typename Value, class EqualTo, class Alloc>
 167 typename ACE_Array_Map<Key, Value, EqualTo, Alloc>::iterator
 168 ACE_Array_Map<Key, Value, EqualTo, Alloc>::find (
 169   typename ACE_Array_Map<Key, Value, EqualTo, Alloc>::key_type const & k)
 170 {
 171   iterator const the_end = this->end ();
 172
 173   EqualTo eq;
 174
 175   for (iterator i = this->begin (); i != the_end; ++i)
 176     if (eq (k, i->first))
 177       return i;
 178
 179   return this->end ();
 180 }
 181
 182 template<typename Key, typename Value, class EqualTo, class Alloc>
 183 typename ACE_Array_Map<Key, Value, EqualTo, Alloc>::const_iterator
 184 ACE_Array_Map<Key, Value, EqualTo, Alloc>::find (
 185   typename ACE_Array_Map<Key, Value, EqualTo, Alloc>::key_type const & k) const
 186 {
 187   const_iterator const the_end = this->end ();
 188
 189   EqualTo eq;
 190
 191   for (const_iterator i = this->begin (); i != the_end; ++i)
 192     if (eq (k, i->first))
 193       return i;
 194
 195   return this->end ();
 196 }
 197
 198 template<typename Key, typename Value, class EqualTo, class Alloc>
 199 void
 200 ACE_Array_Map<Key, Value, EqualTo, Alloc>::grow (
 201   typename ACE_Array_Map<Key, Value, EqualTo, Alloc>::size_type s)
 202 {
 203   if (this->size () + s > this->capacity_)
 204     {
 205       // This implementation focuses more on static footprint than
 206       // speed.
 207
 208       // Strongly exception safe.
 209
 210       ACE_Array_Map<Key, Value, EqualTo, Alloc> temp (this->size () + s);
 211
 212       std::copy (this->begin (),
 213                  this->end (),
 214                  temp.begin ());
 215
 216       size_type const n = this->size ();  // Do not swap out the size
 217                                           // since we bypassed the
 218                                           // temporary map's element
 219                                           // counting code.
 220       this->swap (temp);
 221
 222       this->size_ = n;
 223     }
 224 }
 225
 226 // ---------------------------------------------------------------
 227
 228 template <typename Key, typename Value, class EqualTo, class Alloc>
 229 bool
 230 operator== (ACE_Array_Map<Key, Value, EqualTo, Alloc> const & lhs,
 231             ACE_Array_Map<Key, Value, EqualTo, Alloc> const & rhs)
 232 {
 233   // Do not include Array_Map capacity in comparison.  It isn't useful
 234   // in this case.
 235
 236   return (lhs.size () == rhs.size ()
 237           && std::equal (lhs.begin (),
 238                          lhs.end (),
 239                          rhs.begin ()));
 240 }
 241
 242 template <typename Key, typename Value, class EqualTo, class Alloc>
 243 bool
 244 operator< (ACE_Array_Map<Key, Value, EqualTo, Alloc> const & lhs,
 245            ACE_Array_Map<Key, Value, EqualTo, Alloc> const & rhs)
 246 {
 247   return std::lexicographical_compare (lhs.begin (), lhs.end (),
 248                                        rhs.begin (), rhs.end ());
 249 }
 250
 251 ACE_END_VERSIONED_NAMESPACE_DECL
 252
 253 #endif  /* ACE_ARRAY_MAP_CPP */