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 PB_DS_CLASS_T_DEC
     43 PB_DS_CLASS_C_DEC::
     44 hash_load_check_resize_trigger(float load_min, float load_max)
     45 : m_load_min(load_min), m_load_max(load_max), m_next_shrink_size(0),
     46   m_next_grow_size(0), m_resize_needed(false)
     47 { _GLIBCXX_DEBUG_ONLY(assert_valid();) }
     48 
     49 PB_DS_CLASS_T_DEC
     50 inline void
     51 PB_DS_CLASS_C_DEC::
     52 notify_find_search_start()
     53 { _GLIBCXX_DEBUG_ONLY(assert_valid();) }
     54 
     55 PB_DS_CLASS_T_DEC
     56 inline void
     57 PB_DS_CLASS_C_DEC::
     58 notify_find_search_collision()
     59 { _GLIBCXX_DEBUG_ONLY(assert_valid();) }
     60 
     61 PB_DS_CLASS_T_DEC
     62 inline void
     63 PB_DS_CLASS_C_DEC::
     64 notify_find_search_end()
     65 { _GLIBCXX_DEBUG_ONLY(assert_valid();) }
     66 
     67 PB_DS_CLASS_T_DEC
     68 inline void
     69 PB_DS_CLASS_C_DEC::
     70 notify_insert_search_start()
     71 { _GLIBCXX_DEBUG_ONLY(assert_valid();) }
     72 
     73 PB_DS_CLASS_T_DEC
     74 inline void
     75 PB_DS_CLASS_C_DEC::
     76 notify_insert_search_collision()
     77 { _GLIBCXX_DEBUG_ONLY(assert_valid();) }
     78 
     79 PB_DS_CLASS_T_DEC
     80 inline void
     81 PB_DS_CLASS_C_DEC::
     82 notify_insert_search_end()
     83 { _GLIBCXX_DEBUG_ONLY(assert_valid();) }
     84 
     85 PB_DS_CLASS_T_DEC
     86 inline void
     87 PB_DS_CLASS_C_DEC::
     88 notify_erase_search_start()
     89 { _GLIBCXX_DEBUG_ONLY(assert_valid();) }
     90 
     91 PB_DS_CLASS_T_DEC
     92 inline void
     93 PB_DS_CLASS_C_DEC::
     94 notify_erase_search_collision()
     95 { _GLIBCXX_DEBUG_ONLY(assert_valid();) }
     96 
     97 PB_DS_CLASS_T_DEC
     98 inline void
     99 PB_DS_CLASS_C_DEC::
    100 notify_erase_search_end()
    101 { _GLIBCXX_DEBUG_ONLY(assert_valid();) }
    102 
    103 PB_DS_CLASS_T_DEC
    104 inline void
    105 PB_DS_CLASS_C_DEC::
    106 notify_inserted(size_type num_entries)
    107 {
    108   m_resize_needed = (num_entries >= m_next_grow_size);
    109   size_base::set_size(num_entries);
    110   _GLIBCXX_DEBUG_ONLY(assert_valid();)
    111 }
    112 
    113 PB_DS_CLASS_T_DEC
    114 inline void
    115 PB_DS_CLASS_C_DEC::
    116 notify_erased(size_type num_entries)
    117 {
    118   size_base::set_size(num_entries);
    119   m_resize_needed = num_entries <= m_next_shrink_size;
    120   _GLIBCXX_DEBUG_ONLY(assert_valid();)
    121 }
    122 
    123 PB_DS_CLASS_T_DEC
    124 inline bool
    125 PB_DS_CLASS_C_DEC::
    126 is_resize_needed() const
    127 {
    128   _GLIBCXX_DEBUG_ONLY(assert_valid();)
    129   return m_resize_needed;
    130 }
    131 
    132 PB_DS_CLASS_T_DEC
    133 inline bool
    134 PB_DS_CLASS_C_DEC::
    135 is_grow_needed(size_type /*size*/, size_type num_entries) const
    136 {
    137   _GLIBCXX_DEBUG_ASSERT(m_resize_needed);
    138   return num_entries >= m_next_grow_size;
    139 }
    140 
    141 PB_DS_CLASS_T_DEC
    142 PB_DS_CLASS_C_DEC::
    143 ~hash_load_check_resize_trigger() { }
    144 
    145 PB_DS_CLASS_T_DEC
    146 void
    147 PB_DS_CLASS_C_DEC::
    148 notify_resized(size_type new_size)
    149 {
    150   m_resize_needed = false;
    151   m_next_grow_size = size_type(m_load_max * new_size - 1);
    152   m_next_shrink_size = size_type(m_load_min * new_size);
    153 
    154 #ifdef PB_DS_HT_MAP_RESIZE_TRACE_
    155   std::cerr << "hlcrt::notify_resized "  << std::endl
    156 	    << "1 " << new_size << std::endl
    157 	    << "2 " << m_load_min << std::endl
    158 	    << "3 " << m_load_max << std::endl
    159 	    << "4 " << m_next_shrink_size << std::endl
    160 	    << "5 " << m_next_grow_size << std::endl;
    161 #endif
    162 
    163   _GLIBCXX_DEBUG_ONLY(assert_valid();)
    164 }
    165 
    166 PB_DS_CLASS_T_DEC
    167 void
    168 PB_DS_CLASS_C_DEC::
    169 notify_externally_resized(size_type new_size)
    170 {
    171   m_resize_needed = false;
    172   size_type new_grow_size = size_type(m_load_max * new_size - 1);
    173   size_type new_shrink_size = size_type(m_load_min * new_size);
    174 
    175 #ifdef PB_DS_HT_MAP_RESIZE_TRACE_
    176   std::cerr << "hlcrt::notify_externally_resized "  << std::endl
    177 	    << "1 " << new_size << std::endl
    178 	    << "2 " << m_load_min << std::endl
    179 	    << "3 " << m_load_max << std::endl
    180 	    << "4 " << m_next_shrink_size << std::endl
    181 	    << "5 " << m_next_grow_size << std::endl
    182 	    << "6 " << new_shrink_size << std::endl
    183 	    << "7 " << new_grow_size << std::endl;
    184 #endif
    185 
    186   if (new_grow_size >= m_next_grow_size)
    187     {
    188       _GLIBCXX_DEBUG_ASSERT(new_shrink_size >= m_next_shrink_size);
    189       m_next_grow_size = new_grow_size;
    190     }
    191   else
    192     {
    193       _GLIBCXX_DEBUG_ASSERT(new_shrink_size <= m_next_shrink_size);
    194       m_next_shrink_size = new_shrink_size;
    195     }
    196 
    197   _GLIBCXX_DEBUG_ONLY(assert_valid();)
    198 }
    199 
    200 PB_DS_CLASS_T_DEC
    201 void
    202 PB_DS_CLASS_C_DEC::
    203 notify_cleared()
    204 {
    205   _GLIBCXX_DEBUG_ONLY(assert_valid();)
    206   size_base::set_size(0);
    207   m_resize_needed = (0 < m_next_shrink_size);
    208   _GLIBCXX_DEBUG_ONLY(assert_valid();)
    209 }
    210 
    211 PB_DS_CLASS_T_DEC
    212 void
    213 PB_DS_CLASS_C_DEC::
    214 swap(PB_DS_CLASS_C_DEC& other)
    215 {
    216   _GLIBCXX_DEBUG_ONLY(assert_valid();)
    217   _GLIBCXX_DEBUG_ONLY(other.assert_valid();)
    218 
    219   size_base::swap(other);
    220   std::swap(m_load_min, other.m_load_min);
    221   std::swap(m_load_max, other.m_load_max);
    222   std::swap(m_resize_needed, other.m_resize_needed);
    223   std::swap(m_next_grow_size, other.m_next_grow_size);
    224   std::swap(m_next_shrink_size, other.m_next_shrink_size);
    225 
    226   _GLIBCXX_DEBUG_ONLY(assert_valid();)
    227   _GLIBCXX_DEBUG_ONLY(other.assert_valid();)
    228 }
    229 
    230 PB_DS_CLASS_T_DEC
    231 inline std::pair<float, float>
    232 PB_DS_CLASS_C_DEC::
    233 get_loads() const
    234 {
    235   PB_DS_STATIC_ASSERT(access, external_load_access);
    236   return std::make_pair(m_load_min, m_load_max);
    237 }
    238 
    239 PB_DS_CLASS_T_DEC
    240 void
    241 PB_DS_CLASS_C_DEC::
    242 set_loads(std::pair<float, float> load_pair)
    243 {
    244   PB_DS_STATIC_ASSERT(access, external_load_access);
    245   const float old_load_min = m_load_min;
    246   const float old_load_max = m_load_max;
    247   const size_type old_next_shrink_size = m_next_shrink_size;
    248   const size_type old_next_grow_size = m_next_grow_size;
    249   const bool old_resize_needed = m_resize_needed;
    250 
    251   __try
    252     {
    253       m_load_min = load_pair.first;
    254       m_load_max = load_pair.second;
    255       do_resize(static_cast<size_type>(size_base::get_size() / ((m_load_min + m_load_max) / 2)));
    256     }
    257   __catch(...)
    258     {
    259       m_load_min = old_load_min;
    260       m_load_max = old_load_max;
    261       m_next_shrink_size = old_next_shrink_size;
    262       m_next_grow_size = old_next_grow_size;
    263       m_resize_needed = old_resize_needed;
    264       __throw_exception_again;
    265     }
    266 }
    267 
    268 PB_DS_CLASS_T_DEC
    269 void
    270 PB_DS_CLASS_C_DEC::
    271 do_resize(size_type)
    272 { std::abort(); }
    273 
    274 #ifdef _GLIBCXX_DEBUG
    275 PB_DS_CLASS_T_DEC
    276 void
    277 PB_DS_CLASS_C_DEC::
    278 assert_valid() const
    279 {
    280   _GLIBCXX_DEBUG_ASSERT(m_load_max > m_load_min);
    281   _GLIBCXX_DEBUG_ASSERT(m_next_grow_size >= m_next_shrink_size);
    282 }
    283 #endif
    284