contrib/gcc-8.0/libstdc++-v3/include/ext/pb_ds/detail/resize_policy/hash_load_check_resize_trigger_imp.hpp

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005-2018 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the terms
   7 // of the GNU General Public License as published by the Free Software
   8 // Foundation; either version 3, or (at your option) any later
   9 // version.
  10
  11 // This library is distributed in the hope that it will be useful, but
  12 // WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14 // General Public License for more details.
  15
  16 // Under Section 7 of GPL version 3, you are granted additional
  17 // permissions described in the GCC Runtime Library Exception, version
  18 // 3.1, as published by the Free Software Foundation.
  19
  20 // You should have received a copy of the GNU General Public License and
  21 // a copy of the GCC Runtime Library Exception along with this program;
  22 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  23 // <http://www.gnu.org/licenses/>.
  24
  25 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
  26
  27 // Permission to use, copy, modify, sell, and distribute this software
  28 // is hereby granted without fee, provided that the above copyright
  29 // notice appears in all copies, and that both that copyright notice
  30 // and this permission notice appear in supporting documentation. None
  31 // of the above authors, nor IBM Haifa Research Laboratories, make any
  32 // representation about the suitability of this software for any
  33 // purpose. It is provided "as is" without express or implied
  34 // warranty.
  35
  36 /**
  37  * @file hash_load_check_resize_trigger_imp.hpp
  38  * Contains a resize trigger implementation.
  39  */
  40
  41 #define PB_DS_ASSERT_VALID(X)                                           \
  42   _GLIBCXX_DEBUG_ONLY(X.assert_valid(__FILE__, __LINE__);)
  43
  44 PB_DS_CLASS_T_DEC
  45 PB_DS_CLASS_C_DEC::
  46 hash_load_check_resize_trigger(float load_min, float load_max)
  47 : m_load_min(load_min), m_load_max(load_max), m_next_shrink_size(0),
  48   m_next_grow_size(0), m_resize_needed(false)
  49 { PB_DS_ASSERT_VALID((*this)) }
  50
  51 PB_DS_CLASS_T_DEC
  52 inline void
  53 PB_DS_CLASS_C_DEC::
  54 notify_find_search_start()
  55 { PB_DS_ASSERT_VALID((*this)) }
  56
  57 PB_DS_CLASS_T_DEC
  58 inline void
  59 PB_DS_CLASS_C_DEC::
  60 notify_find_search_collision()
  61 { PB_DS_ASSERT_VALID((*this)) }
  62
  63 PB_DS_CLASS_T_DEC
  64 inline void
  65 PB_DS_CLASS_C_DEC::
  66 notify_find_search_end()
  67 { PB_DS_ASSERT_VALID((*this)) }
  68
  69 PB_DS_CLASS_T_DEC
  70 inline void
  71 PB_DS_CLASS_C_DEC::
  72 notify_insert_search_start()
  73 { PB_DS_ASSERT_VALID((*this)) }
  74
  75 PB_DS_CLASS_T_DEC
  76 inline void
  77 PB_DS_CLASS_C_DEC::
  78 notify_insert_search_collision()
  79 { PB_DS_ASSERT_VALID((*this)) }
  80
  81 PB_DS_CLASS_T_DEC
  82 inline void
  83 PB_DS_CLASS_C_DEC::
  84 notify_insert_search_end()
  85 { PB_DS_ASSERT_VALID((*this)) }
  86
  87 PB_DS_CLASS_T_DEC
  88 inline void
  89 PB_DS_CLASS_C_DEC::
  90 notify_erase_search_start()
  91 { PB_DS_ASSERT_VALID((*this)) }
  92
  93 PB_DS_CLASS_T_DEC
  94 inline void
  95 PB_DS_CLASS_C_DEC::
  96 notify_erase_search_collision()
  97 { PB_DS_ASSERT_VALID((*this)) }
  98
  99 PB_DS_CLASS_T_DEC
 100 inline void
 101 PB_DS_CLASS_C_DEC::
 102 notify_erase_search_end()
 103 { PB_DS_ASSERT_VALID((*this)) }
 104
 105 PB_DS_CLASS_T_DEC
 106 inline void
 107 PB_DS_CLASS_C_DEC::
 108 notify_inserted(size_type num_entries)
 109 {
 110   m_resize_needed = (num_entries >= m_next_grow_size);
 111   size_base::set_size(num_entries);
 112   PB_DS_ASSERT_VALID((*this))
 113 }
 114
 115 PB_DS_CLASS_T_DEC
 116 inline void
 117 PB_DS_CLASS_C_DEC::
 118 notify_erased(size_type num_entries)
 119 {
 120   size_base::set_size(num_entries);
 121   m_resize_needed = num_entries <= m_next_shrink_size;
 122   PB_DS_ASSERT_VALID((*this))
 123 }
 124
 125 PB_DS_CLASS_T_DEC
 126 inline bool
 127 PB_DS_CLASS_C_DEC::
 128 is_resize_needed() const
 129 {
 130   PB_DS_ASSERT_VALID((*this))
 131   return m_resize_needed;
 132 }
 133
 134 PB_DS_CLASS_T_DEC
 135 inline bool
 136 PB_DS_CLASS_C_DEC::
 137 is_grow_needed(size_type /*size*/, size_type num_entries) const
 138 {
 139   _GLIBCXX_DEBUG_ASSERT(m_resize_needed);
 140   return num_entries >= m_next_grow_size;
 141 }
 142
 143 PB_DS_CLASS_T_DEC
 144 PB_DS_CLASS_C_DEC::
 145 ~hash_load_check_resize_trigger() { }
 146
 147 PB_DS_CLASS_T_DEC
 148 void
 149 PB_DS_CLASS_C_DEC::
 150 notify_resized(size_type new_size)
 151 {
 152   m_resize_needed = false;
 153   m_next_grow_size = size_type(m_load_max * new_size - 1);
 154   m_next_shrink_size = size_type(m_load_min * new_size);
 155
 156 #ifdef PB_DS_HT_MAP_RESIZE_TRACE_
 157   std::cerr << "hlcrt::notify_resized "  << std::endl
 158             << "1 " << new_size << std::endl
 159             << "2 " << m_load_min << std::endl
 160             << "3 " << m_load_max << std::endl
 161             << "4 " << m_next_shrink_size << std::endl
 162             << "5 " << m_next_grow_size << std::endl;
 163 #endif
 164
 165   PB_DS_ASSERT_VALID((*this))
 166 }
 167
 168 PB_DS_CLASS_T_DEC
 169 void
 170 PB_DS_CLASS_C_DEC::
 171 notify_externally_resized(size_type new_size)
 172 {
 173   m_resize_needed = false;
 174   size_type new_grow_size = size_type(m_load_max * new_size - 1);
 175   size_type new_shrink_size = size_type(m_load_min * new_size);
 176
 177 #ifdef PB_DS_HT_MAP_RESIZE_TRACE_
 178   std::cerr << "hlcrt::notify_externally_resized "  << std::endl
 179             << "1 " << new_size << std::endl
 180             << "2 " << m_load_min << std::endl
 181             << "3 " << m_load_max << std::endl
 182             << "4 " << m_next_shrink_size << std::endl
 183             << "5 " << m_next_grow_size << std::endl
 184             << "6 " << new_shrink_size << std::endl
 185             << "7 " << new_grow_size << std::endl;
 186 #endif
 187
 188   if (new_grow_size >= m_next_grow_size)
 189     {
 190       _GLIBCXX_DEBUG_ASSERT(new_shrink_size >= m_next_shrink_size);
 191       m_next_grow_size = new_grow_size;
 192     }
 193   else
 194     {
 195       _GLIBCXX_DEBUG_ASSERT(new_shrink_size <= m_next_shrink_size);
 196       m_next_shrink_size = new_shrink_size;
 197     }
 198
 199   PB_DS_ASSERT_VALID((*this))
 200 }
 201
 202 PB_DS_CLASS_T_DEC
 203 void
 204 PB_DS_CLASS_C_DEC::
 205 notify_cleared()
 206 {
 207   PB_DS_ASSERT_VALID((*this))
 208   size_base::set_size(0);
 209   m_resize_needed = (0 < m_next_shrink_size);
 210   PB_DS_ASSERT_VALID((*this))
 211 }
 212
 213 PB_DS_CLASS_T_DEC
 214 void
 215 PB_DS_CLASS_C_DEC::
 216 swap(PB_DS_CLASS_C_DEC& other)
 217 {
 218   PB_DS_ASSERT_VALID((*this))
 219   PB_DS_ASSERT_VALID(other)
 220
 221   size_base::swap(other);
 222   std::swap(m_load_min, other.m_load_min);
 223   std::swap(m_load_max, other.m_load_max);
 224   std::swap(m_resize_needed, other.m_resize_needed);
 225   std::swap(m_next_grow_size, other.m_next_grow_size);
 226   std::swap(m_next_shrink_size, other.m_next_shrink_size);
 227
 228   PB_DS_ASSERT_VALID((*this))
 229   PB_DS_ASSERT_VALID(other)
 230 }
 231
 232 PB_DS_CLASS_T_DEC
 233 inline std::pair<float, float>
 234 PB_DS_CLASS_C_DEC::
 235 get_loads() const
 236 {
 237   PB_DS_STATIC_ASSERT(access, external_load_access);
 238   return std::make_pair(m_load_min, m_load_max);
 239 }
 240
 241 PB_DS_CLASS_T_DEC
 242 void
 243 PB_DS_CLASS_C_DEC::
 244 set_loads(std::pair<float, float> load_pair)
 245 {
 246   PB_DS_STATIC_ASSERT(access, external_load_access);
 247   const float old_load_min = m_load_min;
 248   const float old_load_max = m_load_max;
 249   const size_type old_next_shrink_size = m_next_shrink_size;
 250   const size_type old_next_grow_size = m_next_grow_size;
 251   const bool old_resize_needed = m_resize_needed;
 252
 253   __try
 254     {
 255       m_load_min = load_pair.first;
 256       m_load_max = load_pair.second;
 257       do_resize(static_cast<size_type>(size_base::get_size() / ((m_load_min + m_load_max) / 2)));
 258     }
 259   __catch(...)
 260     {
 261       m_load_min = old_load_min;
 262       m_load_max = old_load_max;
 263       m_next_shrink_size = old_next_shrink_size;
 264       m_next_grow_size = old_next_grow_size;
 265       m_resize_needed = old_resize_needed;
 266       __throw_exception_again;
 267     }
 268 }
 269
 270 PB_DS_CLASS_T_DEC
 271 void
 272 PB_DS_CLASS_C_DEC::
 273 do_resize(size_type)
 274 { std::abort(); }
 275
 276 #ifdef _GLIBCXX_DEBUG
 277 # define PB_DS_DEBUG_VERIFY(_Cond)                                      \
 278   _GLIBCXX_DEBUG_VERIFY_AT(_Cond,                                       \
 279                            _M_message(#_Cond" assertion from %1;:%2;")  \
 280                            ._M_string(__FILE__)._M_integer(__LINE__)    \
 281                            ,__file,__line)
 282
 283 PB_DS_CLASS_T_DEC
 284 void
 285 PB_DS_CLASS_C_DEC::
 286 assert_valid(const char* __file, int __line) const
 287 {
 288   PB_DS_DEBUG_VERIFY(m_load_max > m_load_min);
 289   PB_DS_DEBUG_VERIFY(m_next_grow_size >= m_next_shrink_size);
 290 }
 291 # undef PB_DS_DEBUG_VERIFY
 292 #endif
 293 #undef PB_DS_ASSERT_VALID