Home | History | Annotate | Download | only in resize_policy 
      1 // -*- C++ -*-
      2 
      3 // Copyright (C) 2005-2013 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
    294