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