boost/asio/detail/hash_map.hpp

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