libstdc++
hash_load_check_resize_trigger_imp.hpp
Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 // Copyright (C) 2005-2013 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the terms
00007 // of the GNU General Public License as published by the Free Software
00008 // Foundation; either version 3, or (at your option) any later
00009 // version.
00010 
00011 // This library is distributed in the hope that it will be useful, but
00012 // WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00014 // General Public License for more details.
00015 
00016 // Under Section 7 of GPL version 3, you are granted additional
00017 // permissions described in the GCC Runtime Library Exception, version
00018 // 3.1, as published by the Free Software Foundation.
00019 
00020 // You should have received a copy of the GNU General Public License and
00021 // a copy of the GCC Runtime Library Exception along with this program;
00022 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00023 // <http://www.gnu.org/licenses/>.
00024 
00025 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
00026 
00027 // Permission to use, copy, modify, sell, and distribute this software
00028 // is hereby granted without fee, provided that the above copyright
00029 // notice appears in all copies, and that both that copyright notice
00030 // and this permission notice appear in supporting documentation. None
00031 // of the above authors, nor IBM Haifa Research Laboratories, make any
00032 // representation about the suitability of this software for any
00033 // purpose. It is provided "as is" without express or implied
00034 // warranty.
00035 
00036 /**
00037  * @file hash_load_check_resize_trigger_imp.hpp
00038  * Contains a resize trigger implementation.
00039  */
00040 
00041 #define PB_DS_ASSERT_VALID(X)                       \
00042   _GLIBCXX_DEBUG_ONLY(X.assert_valid(__FILE__, __LINE__);)
00043 
00044 PB_DS_CLASS_T_DEC
00045 PB_DS_CLASS_C_DEC::
00046 hash_load_check_resize_trigger(float load_min, float load_max)
00047 : m_load_min(load_min), m_load_max(load_max), m_next_shrink_size(0),
00048   m_next_grow_size(0), m_resize_needed(false)
00049 { PB_DS_ASSERT_VALID((*this)) }
00050 
00051 PB_DS_CLASS_T_DEC
00052 inline void
00053 PB_DS_CLASS_C_DEC::
00054 notify_find_search_start()
00055 { PB_DS_ASSERT_VALID((*this)) }
00056 
00057 PB_DS_CLASS_T_DEC
00058 inline void
00059 PB_DS_CLASS_C_DEC::
00060 notify_find_search_collision()
00061 { PB_DS_ASSERT_VALID((*this)) }
00062 
00063 PB_DS_CLASS_T_DEC
00064 inline void
00065 PB_DS_CLASS_C_DEC::
00066 notify_find_search_end()
00067 { PB_DS_ASSERT_VALID((*this)) }
00068 
00069 PB_DS_CLASS_T_DEC
00070 inline void
00071 PB_DS_CLASS_C_DEC::
00072 notify_insert_search_start()
00073 { PB_DS_ASSERT_VALID((*this)) }
00074 
00075 PB_DS_CLASS_T_DEC
00076 inline void
00077 PB_DS_CLASS_C_DEC::
00078 notify_insert_search_collision()
00079 { PB_DS_ASSERT_VALID((*this)) }
00080 
00081 PB_DS_CLASS_T_DEC
00082 inline void
00083 PB_DS_CLASS_C_DEC::
00084 notify_insert_search_end()
00085 { PB_DS_ASSERT_VALID((*this)) }
00086 
00087 PB_DS_CLASS_T_DEC
00088 inline void
00089 PB_DS_CLASS_C_DEC::
00090 notify_erase_search_start()
00091 { PB_DS_ASSERT_VALID((*this)) }
00092 
00093 PB_DS_CLASS_T_DEC
00094 inline void
00095 PB_DS_CLASS_C_DEC::
00096 notify_erase_search_collision()
00097 { PB_DS_ASSERT_VALID((*this)) }
00098 
00099 PB_DS_CLASS_T_DEC
00100 inline void
00101 PB_DS_CLASS_C_DEC::
00102 notify_erase_search_end()
00103 { PB_DS_ASSERT_VALID((*this)) }
00104 
00105 PB_DS_CLASS_T_DEC
00106 inline void
00107 PB_DS_CLASS_C_DEC::
00108 notify_inserted(size_type num_entries)
00109 {
00110   m_resize_needed = (num_entries >= m_next_grow_size);
00111   size_base::set_size(num_entries);
00112   PB_DS_ASSERT_VALID((*this))
00113 }
00114 
00115 PB_DS_CLASS_T_DEC
00116 inline void
00117 PB_DS_CLASS_C_DEC::
00118 notify_erased(size_type num_entries)
00119 {
00120   size_base::set_size(num_entries);
00121   m_resize_needed = num_entries <= m_next_shrink_size;
00122   PB_DS_ASSERT_VALID((*this))
00123 }
00124 
00125 PB_DS_CLASS_T_DEC
00126 inline bool
00127 PB_DS_CLASS_C_DEC::
00128 is_resize_needed() const
00129 {
00130   PB_DS_ASSERT_VALID((*this))
00131   return m_resize_needed;
00132 }
00133 
00134 PB_DS_CLASS_T_DEC
00135 inline bool
00136 PB_DS_CLASS_C_DEC::
00137 is_grow_needed(size_type /*size*/, size_type num_entries) const
00138 {
00139   _GLIBCXX_DEBUG_ASSERT(m_resize_needed);
00140   return num_entries >= m_next_grow_size;
00141 }
00142 
00143 PB_DS_CLASS_T_DEC
00144 PB_DS_CLASS_C_DEC::
00145 ~hash_load_check_resize_trigger() { }
00146 
00147 PB_DS_CLASS_T_DEC
00148 void
00149 PB_DS_CLASS_C_DEC::
00150 notify_resized(size_type new_size)
00151 {
00152   m_resize_needed = false;
00153   m_next_grow_size = size_type(m_load_max * new_size - 1);
00154   m_next_shrink_size = size_type(m_load_min * new_size);
00155 
00156 #ifdef PB_DS_HT_MAP_RESIZE_TRACE_
00157   std::cerr << "hlcrt::notify_resized "  << std::endl
00158         << "1 " << new_size << std::endl
00159         << "2 " << m_load_min << std::endl
00160         << "3 " << m_load_max << std::endl
00161         << "4 " << m_next_shrink_size << std::endl
00162         << "5 " << m_next_grow_size << std::endl;
00163 #endif
00164 
00165   PB_DS_ASSERT_VALID((*this))
00166 }
00167 
00168 PB_DS_CLASS_T_DEC
00169 void
00170 PB_DS_CLASS_C_DEC::
00171 notify_externally_resized(size_type new_size)
00172 {
00173   m_resize_needed = false;
00174   size_type new_grow_size = size_type(m_load_max * new_size - 1);
00175   size_type new_shrink_size = size_type(m_load_min * new_size);
00176 
00177 #ifdef PB_DS_HT_MAP_RESIZE_TRACE_
00178   std::cerr << "hlcrt::notify_externally_resized "  << std::endl
00179         << "1 " << new_size << std::endl
00180         << "2 " << m_load_min << std::endl
00181         << "3 " << m_load_max << std::endl
00182         << "4 " << m_next_shrink_size << std::endl
00183         << "5 " << m_next_grow_size << std::endl
00184         << "6 " << new_shrink_size << std::endl
00185         << "7 " << new_grow_size << std::endl;
00186 #endif
00187 
00188   if (new_grow_size >= m_next_grow_size)
00189     {
00190       _GLIBCXX_DEBUG_ASSERT(new_shrink_size >= m_next_shrink_size);
00191       m_next_grow_size = new_grow_size;
00192     }
00193   else
00194     {
00195       _GLIBCXX_DEBUG_ASSERT(new_shrink_size <= m_next_shrink_size);
00196       m_next_shrink_size = new_shrink_size;
00197     }
00198 
00199   PB_DS_ASSERT_VALID((*this))
00200 }
00201 
00202 PB_DS_CLASS_T_DEC
00203 void
00204 PB_DS_CLASS_C_DEC::
00205 notify_cleared()
00206 {
00207   PB_DS_ASSERT_VALID((*this))
00208   size_base::set_size(0);
00209   m_resize_needed = (0 < m_next_shrink_size);
00210   PB_DS_ASSERT_VALID((*this))
00211 }
00212 
00213 PB_DS_CLASS_T_DEC
00214 void
00215 PB_DS_CLASS_C_DEC::
00216 swap(PB_DS_CLASS_C_DEC& other)
00217 {
00218   PB_DS_ASSERT_VALID((*this))
00219   PB_DS_ASSERT_VALID(other)
00220 
00221   size_base::swap(other);
00222   std::swap(m_load_min, other.m_load_min);
00223   std::swap(m_load_max, other.m_load_max);
00224   std::swap(m_resize_needed, other.m_resize_needed);
00225   std::swap(m_next_grow_size, other.m_next_grow_size);
00226   std::swap(m_next_shrink_size, other.m_next_shrink_size);
00227 
00228   PB_DS_ASSERT_VALID((*this))
00229   PB_DS_ASSERT_VALID(other)
00230 }
00231 
00232 PB_DS_CLASS_T_DEC
00233 inline std::pair<float, float>
00234 PB_DS_CLASS_C_DEC::
00235 get_loads() const
00236 {
00237   PB_DS_STATIC_ASSERT(access, external_load_access);
00238   return std::make_pair(m_load_min, m_load_max);
00239 }
00240 
00241 PB_DS_CLASS_T_DEC
00242 void
00243 PB_DS_CLASS_C_DEC::
00244 set_loads(std::pair<float, float> load_pair)
00245 {
00246   PB_DS_STATIC_ASSERT(access, external_load_access);
00247   const float old_load_min = m_load_min;
00248   const float old_load_max = m_load_max;
00249   const size_type old_next_shrink_size = m_next_shrink_size;
00250   const size_type old_next_grow_size = m_next_grow_size;
00251   const bool old_resize_needed = m_resize_needed;
00252 
00253   __try
00254     {
00255       m_load_min = load_pair.first;
00256       m_load_max = load_pair.second;
00257       do_resize(static_cast<size_type>(size_base::get_size() / ((m_load_min + m_load_max) / 2)));
00258     }
00259   __catch(...)
00260     {
00261       m_load_min = old_load_min;
00262       m_load_max = old_load_max;
00263       m_next_shrink_size = old_next_shrink_size;
00264       m_next_grow_size = old_next_grow_size;
00265       m_resize_needed = old_resize_needed;
00266       __throw_exception_again;
00267     }
00268 }
00269 
00270 PB_DS_CLASS_T_DEC
00271 void
00272 PB_DS_CLASS_C_DEC::
00273 do_resize(size_type)
00274 { std::abort(); }
00275 
00276 #ifdef _GLIBCXX_DEBUG
00277 # define PB_DS_DEBUG_VERIFY(_Cond)                  \
00278   _GLIBCXX_DEBUG_VERIFY_AT(_Cond,                   \
00279                _M_message(#_Cond" assertion from %1;:%2;")  \
00280                ._M_string(__FILE__)._M_integer(__LINE__)    \
00281                ,__file,__line)
00282 
00283 PB_DS_CLASS_T_DEC
00284 void
00285 PB_DS_CLASS_C_DEC::
00286 assert_valid(const char* __file, int __line) const
00287 {
00288   PB_DS_DEBUG_VERIFY(m_load_max > m_load_min);
00289   PB_DS_DEBUG_VERIFY(m_next_grow_size >= m_next_shrink_size);
00290 }
00291 # undef PB_DS_DEBUG_VERIFY
00292 #endif
00293 #undef PB_DS_ASSERT_VALID