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