libstdc++
resize_policy.hpp
Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 // Copyright (C) 2005, 2006, 2009, 2011 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 binary_heap_/resize_policy.hpp
00038  * Contains an implementation class for a binary_heap.
00039  */
00040 
00041 #ifndef PB_DS_BINARY_HEAP_RESIZE_POLICY_HPP
00042 #define PB_DS_BINARY_HEAP_RESIZE_POLICY_HPP
00043 
00044 #include <debug/debug.h>
00045 
00046 namespace __gnu_pbds
00047 {
00048   namespace detail
00049   {
00050     /// Resize policy for binary heap.
00051     template<typename _Tp>
00052     class resize_policy
00053     {
00054     private:
00055       enum
00056     {
00057       ratio = 8,
00058       factor = 2
00059     };
00060 
00061       /// Next shrink size.
00062       _Tp       m_shrink_size;
00063 
00064       /// Next grow size.
00065       _Tp       m_grow_size;
00066 
00067     public:
00068       typedef _Tp   size_type;
00069 
00070       static const _Tp  min_size = 16;
00071 
00072       resize_policy() : m_shrink_size(0), m_grow_size(min_size)
00073       { PB_DS_ASSERT_VALID((*this)) }
00074 
00075       resize_policy(const resize_policy& other)
00076       : m_shrink_size(other.m_shrink_size), m_grow_size(other.m_grow_size)
00077       { PB_DS_ASSERT_VALID((*this)) }
00078 
00079       inline void
00080       swap(resize_policy<_Tp>&);
00081 
00082       inline bool
00083       resize_needed_for_grow(size_type) const;
00084 
00085       inline bool
00086       resize_needed_for_shrink(size_type) const;
00087 
00088       inline bool
00089       grow_needed(size_type) const;
00090 
00091       inline bool
00092       shrink_needed(size_type) const;
00093 
00094       inline size_type
00095       get_new_size_for_grow() const;
00096 
00097       inline size_type
00098       get_new_size_for_shrink() const;
00099 
00100       inline size_type
00101       get_new_size_for_arbitrary(size_type) const;
00102 
00103       inline void
00104       notify_grow_resize();
00105 
00106       inline void
00107       notify_shrink_resize();
00108 
00109       void
00110       notify_arbitrary(size_type);
00111 
00112 #ifdef _GLIBCXX_DEBUG
00113       void
00114       assert_valid(const char*, int) const;
00115 #endif
00116 
00117 #ifdef PB_DS_BINARY_HEAP_TRACE_
00118       void
00119       trace() const;
00120 #endif
00121     };
00122 
00123     template<typename _Tp>
00124       const _Tp resize_policy<_Tp>::min_size;
00125 
00126     template<typename _Tp>
00127     inline void
00128     resize_policy<_Tp>::
00129     swap(resize_policy<_Tp>& other)
00130     {
00131       std::swap(m_shrink_size, other.m_shrink_size);
00132       std::swap(m_grow_size, other.m_grow_size);
00133     }
00134 
00135     template<typename _Tp>
00136     inline bool
00137     resize_policy<_Tp>::
00138     resize_needed_for_grow(size_type size) const
00139     {
00140       _GLIBCXX_DEBUG_ASSERT(size <= m_grow_size);
00141       return size == m_grow_size;
00142     }
00143 
00144     template<typename _Tp>
00145     inline bool
00146     resize_policy<_Tp>::
00147     resize_needed_for_shrink(size_type size) const
00148     {
00149       _GLIBCXX_DEBUG_ASSERT(size <= m_grow_size);
00150       return size == m_shrink_size;
00151     }
00152 
00153     template<typename _Tp>
00154     inline typename resize_policy<_Tp>::size_type
00155     resize_policy<_Tp>::
00156     get_new_size_for_grow() const
00157     { return m_grow_size * factor; }
00158 
00159     template<typename _Tp>
00160     inline typename resize_policy<_Tp>::size_type
00161     resize_policy<_Tp>::
00162     get_new_size_for_shrink() const
00163     {
00164       const size_type half_size = m_grow_size / factor;
00165       return std::max(min_size, half_size);
00166     }
00167 
00168     template<typename _Tp>
00169     inline typename resize_policy<_Tp>::size_type
00170     resize_policy<_Tp>::
00171     get_new_size_for_arbitrary(size_type size) const
00172     {
00173       size_type ret = min_size;
00174       while (ret < size)
00175     ret *= factor;
00176       return ret;
00177     }
00178 
00179     template<typename _Tp>
00180     inline void
00181     resize_policy<_Tp>::
00182     notify_grow_resize()
00183     {
00184       PB_DS_ASSERT_VALID((*this))
00185       _GLIBCXX_DEBUG_ASSERT(m_grow_size >= min_size);
00186       m_grow_size *= factor;
00187       m_shrink_size = m_grow_size / ratio;
00188       PB_DS_ASSERT_VALID((*this))
00189     }
00190 
00191     template<typename _Tp>
00192     inline void
00193     resize_policy<_Tp>::
00194     notify_shrink_resize()
00195     {
00196       PB_DS_ASSERT_VALID((*this))
00197       m_shrink_size /= factor;
00198       if (m_shrink_size == 1)
00199     m_shrink_size = 0;
00200       m_grow_size = std::max(m_grow_size / factor, min_size);
00201       PB_DS_ASSERT_VALID((*this))
00202     }
00203 
00204     template<typename _Tp>
00205     inline void
00206     resize_policy<_Tp>::
00207     notify_arbitrary(size_type actual_size)
00208     {
00209       m_grow_size = actual_size;
00210       m_shrink_size = m_grow_size / ratio;
00211       PB_DS_ASSERT_VALID((*this))
00212     }
00213 
00214 #ifdef _GLIBCXX_DEBUG
00215     template<typename _Tp>
00216     void
00217     resize_policy<_Tp>::
00218     assert_valid(const char* __file, int __line) const
00219     {
00220       PB_DS_DEBUG_VERIFY(m_shrink_size == 0
00221              || m_shrink_size * ratio == m_grow_size);
00222       PB_DS_DEBUG_VERIFY(m_grow_size >= min_size);
00223     }
00224 #endif
00225 
00226 #ifdef PB_DS_BINARY_HEAP_TRACE_
00227     template<typename _Tp>
00228     void
00229     resize_policy<_Tp>::
00230     trace() const
00231     {
00232       std::cerr << "shrink = " << m_shrink_size
00233         << " grow = " << m_grow_size << std::endl;
00234     }
00235 #endif
00236 
00237 } // namespace detail
00238 } // namespace __gnu_pbds
00239 
00240 #endif