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