ceph/src/boost/boost/asio/detail/hash_map.hpp

   1 //
   2 // detail/hash_map.hpp
   3 // ~~~~~~~~~~~~~~~~~~~
   4 //
   5 // Copyright (c) 2003-2017 Christopher M. Kohlhoff (chris at kohlhoff dot com)
   6 //
   7 // Distributed under the Boost Software License, Version 1.0. (See accompanying
   8 // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
   9 //
  10
  11 #ifndef BOOST_ASIO_DETAIL_HASH_MAP_HPP
  12 #define BOOST_ASIO_DETAIL_HASH_MAP_HPP
  13
  14 #if defined(_MSC_VER) && (_MSC_VER >= 1200)
  15 # pragma once
  16 #endif // defined(_MSC_VER) && (_MSC_VER >= 1200)
  17
  18 #include <boost/asio/detail/config.hpp>
  19 #include <list>
  20 #include <utility>
  21 #include <boost/asio/detail/assert.hpp>
  22 #include <boost/asio/detail/noncopyable.hpp>
  23
  24 #if defined(BOOST_ASIO_WINDOWS) || defined(__CYGWIN__)
  25 # include <boost/asio/detail/socket_types.hpp>
  26 #endif // defined(BOOST_ASIO_WINDOWS) || defined(__CYGWIN__)
  27
  28 #include <boost/asio/detail/push_options.hpp>
  29
  30 namespace boost {
  31 namespace asio {
  32 namespace detail {
  33
  34 inline std::size_t calculate_hash_value(int i)
  35 {
  36   return static_cast<std::size_t>(i);
  37 }
  38
  39 inline std::size_t calculate_hash_value(void* p)
  40 {
  41   return reinterpret_cast<std::size_t>(p)
  42     + (reinterpret_cast<std::size_t>(p) >> 3);
  43 }
  44
  45 #if defined(BOOST_ASIO_WINDOWS) || defined(__CYGWIN__)
  46 inline std::size_t calculate_hash_value(SOCKET s)
  47 {
  48   return static_cast<std::size_t>(s);
  49 }
  50 #endif // defined(BOOST_ASIO_WINDOWS) || defined(__CYGWIN__)
  51
  52 // Note: assumes K and V are POD types.
  53 template <typename K, typename V>
  54 class hash_map
  55   : private noncopyable
  56 {
  57 public:
  58   // The type of a value in the map.
  59   typedef std::pair<K, V> value_type;
  60
  61   // The type of a non-const iterator over the hash map.
  62   typedef typename std::list<value_type>::iterator iterator;
  63
  64   // The type of a const iterator over the hash map.
  65   typedef typename std::list<value_type>::const_iterator const_iterator;
  66
  67   // Constructor.
  68   hash_map()
  69     : size_(0),
  70       buckets_(0),
  71       num_buckets_(0)
  72   {
  73   }
  74
  75   // Destructor.
  76   ~hash_map()
  77   {
  78     delete[] buckets_;
  79   }
  80
  81   // Get an iterator for the beginning of the map.
  82   iterator begin()
  83   {
  84     return values_.begin();
  85   }
  86
  87   // Get an iterator for the beginning of the map.
  88   const_iterator begin() const
  89   {
  90     return values_.begin();
  91   }
  92
  93   // Get an iterator for the end of the map.
  94   iterator end()
  95   {
  96     return values_.end();
  97   }
  98
  99   // Get an iterator for the end of the map.
 100   const_iterator end() const
 101   {
 102     return values_.end();
 103   }
 104
 105   // Check whether the map is empty.
 106   bool empty() const
 107   {
 108     return values_.empty();
 109   }
 110
 111   // Find an entry in the map.
 112   iterator find(const K& k)
 113   {
 114     if (num_buckets_)
 115     {
 116       size_t bucket = calculate_hash_value(k) % num_buckets_;
 117       iterator it = buckets_[bucket].first;
 118       if (it == values_.end())
 119         return values_.end();
 120       iterator end_it = buckets_[bucket].last;
 121       ++end_it;
 122       while (it != end_it)
 123       {
 124         if (it->first == k)
 125           return it;
 126         ++it;
 127       }
 128     }
 129     return values_.end();
 130   }
 131
 132   // Find an entry in the map.
 133   const_iterator find(const K& k) const
 134   {
 135     if (num_buckets_)
 136     {
 137       size_t bucket = calculate_hash_value(k) % num_buckets_;
 138       const_iterator it = buckets_[bucket].first;
 139       if (it == values_.end())
 140         return it;
 141       const_iterator end_it = buckets_[bucket].last;
 142       ++end_it;
 143       while (it != end_it)
 144       {
 145         if (it->first == k)
 146           return it;
 147         ++it;
 148       }
 149     }
 150     return values_.end();
 151   }
 152
 153   // Insert a new entry into the map.
 154   std::pair<iterator, bool> insert(const value_type& v)
 155   {
 156     if (size_ + 1 >= num_buckets_)
 157       rehash(hash_size(size_ + 1));
 158     size_t bucket = calculate_hash_value(v.first) % num_buckets_;
 159     iterator it = buckets_[bucket].first;
 160     if (it == values_.end())
 161     {
 162       buckets_[bucket].first = buckets_[bucket].last =
 163         values_insert(values_.end(), v);
 164       ++size_;
 165       return std::pair<iterator, bool>(buckets_[bucket].last, true);
 166     }
 167     iterator end_it = buckets_[bucket].last;
 168     ++end_it;
 169     while (it != end_it)
 170     {
 171       if (it->first == v.first)
 172         return std::pair<iterator, bool>(it, false);
 173       ++it;
 174     }
 175     buckets_[bucket].last = values_insert(end_it, v);
 176     ++size_;
 177     return std::pair<iterator, bool>(buckets_[bucket].last, true);
 178   }
 179
 180   // Erase an entry from the map.
 181   void erase(iterator it)
 182   {
 183     BOOST_ASIO_ASSERT(it != values_.end());
 184     BOOST_ASIO_ASSERT(num_buckets_ != 0);
 185
 186     size_t bucket = calculate_hash_value(it->first) % num_buckets_;
 187     bool is_first = (it == buckets_[bucket].first);
 188     bool is_last = (it == buckets_[bucket].last);
 189     if (is_first && is_last)
 190       buckets_[bucket].first = buckets_[bucket].last = values_.end();
 191     else if (is_first)
 192       ++buckets_[bucket].first;
 193     else if (is_last)
 194       --buckets_[bucket].last;
 195
 196     values_erase(it);
 197     --size_;
 198   }
 199
 200   // Erase a key from the map.
 201   void erase(const K& k)
 202   {
 203     iterator it = find(k);
 204     if (it != values_.end())
 205       erase(it);
 206   }
 207
 208   // Remove all entries from the map.
 209   void clear()
 210   {
 211     // Clear the values.
 212     values_.clear();
 213     size_ = 0;
 214
 215     // Initialise all buckets to empty.
 216     iterator end_it = values_.end();
 217     for (size_t i = 0; i < num_buckets_; ++i)
 218       buckets_[i].first = buckets_[i].last = end_it;
 219   }
 220
 221 private:
 222   // Calculate the hash size for the specified number of elements.
 223   static std::size_t hash_size(std::size_t num_elems)
 224   {
 225     static std::size_t sizes[] =
 226     {
 227 #if defined(BOOST_ASIO_HASH_MAP_BUCKETS)
 228       BOOST_ASIO_HASH_MAP_BUCKETS
 229 #else // BOOST_ASIO_HASH_MAP_BUCKETS
 230       3, 13, 23, 53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593,
 231       49157, 98317, 196613, 393241, 786433, 1572869, 3145739, 6291469,
 232       12582917, 25165843
 233 #endif // BOOST_ASIO_HASH_MAP_BUCKETS
 234     };
 235     const std::size_t nth_size = sizeof(sizes) / sizeof(std::size_t) - 1;
 236     for (std::size_t i = 0; i < nth_size; ++i)
 237       if (num_elems < sizes[i])
 238         return sizes[i];
 239     return sizes[nth_size];
 240   }
 241
 242   // Re-initialise the hash from the values already contained in the list.
 243   void rehash(std::size_t num_buckets)
 244   {
 245     if (num_buckets == num_buckets_)
 246       return;
 247     BOOST_ASIO_ASSERT(num_buckets != 0);
 248
 249     iterator end_iter = values_.end();
 250
 251     // Update number of buckets and initialise all buckets to empty.
 252     bucket_type* tmp = new bucket_type[num_buckets];
 253     delete[] buckets_;
 254     buckets_ = tmp;
 255     num_buckets_ = num_buckets;
 256     for (std::size_t i = 0; i < num_buckets_; ++i)
 257       buckets_[i].first = buckets_[i].last = end_iter;
 258
 259     // Put all values back into the hash.
 260     iterator iter = values_.begin();
 261     while (iter != end_iter)
 262     {
 263       std::size_t bucket = calculate_hash_value(iter->first) % num_buckets_;
 264       if (buckets_[bucket].last == end_iter)
 265       {
 266         buckets_[bucket].first = buckets_[bucket].last = iter++;
 267       }
 268       else if (++buckets_[bucket].last == iter)
 269       {
 270         ++iter;
 271       }
 272       else
 273       {
 274         values_.splice(buckets_[bucket].last, values_, iter++);
 275         --buckets_[bucket].last;
 276       }
 277     }
 278   }
 279
 280   // Insert an element into the values list by splicing from the spares list,
 281   // if a spare is available, and otherwise by inserting a new element.
 282   iterator values_insert(iterator it, const value_type& v)
 283   {
 284     if (spares_.empty())
 285     {
 286       return values_.insert(it, v);
 287     }
 288     else
 289     {
 290       spares_.front() = v;
 291       values_.splice(it, spares_, spares_.begin());
 292       return --it;
 293     }
 294   }
 295
 296   // Erase an element from the values list by splicing it to the spares list.
 297   void values_erase(iterator it)
 298   {
 299     *it = value_type();
 300     spares_.splice(spares_.begin(), values_, it);
 301   }
 302
 303   // The number of elements in the hash.
 304   std::size_t size_;
 305
 306   // The list of all values in the hash map.
 307   std::list<value_type> values_;
 308
 309   // The list of spare nodes waiting to be recycled. Assumes that POD types only
 310   // are stored in the hash map.
 311   std::list<value_type> spares_;
 312
 313   // The type for a bucket in the hash table.
 314   struct bucket_type
 315   {
 316     iterator first;
 317     iterator last;
 318   };
 319
 320   // The buckets in the hash.
 321   bucket_type* buckets_;
 322
 323   // The number of buckets in the hash.
 324   std::size_t num_buckets_;
 325 };
 326
 327 } // namespace detail
 328 } // namespace asio
 329 } // namespace boost
 330
 331 #include <boost/asio/detail/pop_options.hpp>
 332
 333 #endif // BOOST_ASIO_DETAIL_HASH_MAP_HPP