libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/resize_policy.hpp

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005, 2006, 2009, 2011 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the terms
   7 // of the GNU General Public License as published by the Free Software
   8 // Foundation; either version 3, or (at your option) any later
   9 // version.
  10
  11 // This library is distributed in the hope that it will be useful, but
  12 // WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14 // General Public License for more details.
  15
  16 // Under Section 7 of GPL version 3, you are granted additional
  17 // permissions described in the GCC Runtime Library Exception, version
  18 // 3.1, as published by the Free Software Foundation.
  19
  20 // You should have received a copy of the GNU General Public License and
  21 // a copy of the GCC Runtime Library Exception along with this program;
  22 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  23 // <http://www.gnu.org/licenses/>.
  24
  25 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
  26
  27 // Permission to use, copy, modify, sell, and distribute this software
  28 // is hereby granted without fee, provided that the above copyright
  29 // notice appears in all copies, and that both that copyright notice
  30 // and this permission notice appear in supporting documentation. None
  31 // of the above authors, nor IBM Haifa Research Laboratories, make any
  32 // representation about the suitability of this software for any
  33 // purpose. It is provided "as is" without express or implied
  34 // warranty.
  35
  36 /**
  37  * @file resize_policy.hpp
  38  * Contains an implementation class for a binary_heap.
  39  */
  40
  41 #ifndef PB_DS_BINARY_HEAP_RESIZE_POLICY_HPP
  42 #define PB_DS_BINARY_HEAP_RESIZE_POLICY_HPP
  43
  44 #include <debug/debug.h>
  45
  46 namespace __gnu_pbds
  47 {
  48   namespace detail
  49   {
  50
  51 #define PB_DS_CLASS_T_DEC template<typename Size_Type>
  52
  53 #define PB_DS_CLASS_C_DEC resize_policy<Size_Type>
  54
  55 #define PB_DS_ASSERT_VALID(X)\
  56   _GLIBCXX_DEBUG_ONLY(X.assert_valid(__FILE__, __LINE__);)
  57
  58 #define PB_DS_DEBUG_VERIFY(_Cond)                                       \
  59   _GLIBCXX_DEBUG_VERIFY_AT(_Cond,                                       \
  60                            _M_message(#_Cond" assertion from %1;:%2;")  \
  61                            ._M_string(__FILE__)._M_integer(__LINE__)    \
  62                            ,__file,__line)
  63
  64     template<typename Size_Type>
  65     class resize_policy
  66     {
  67     public:
  68       typedef Size_Type size_type;
  69
  70       enum
  71         {
  72           min_size = 16
  73         };
  74
  75     public:
  76       inline
  77       resize_policy();
  78
  79       inline void
  80       swap(PB_DS_CLASS_C_DEC& other);
  81
  82       inline bool
  83       resize_needed_for_grow(size_type size) const;
  84
  85       inline bool
  86       resize_needed_for_shrink(size_type size) const;
  87
  88       inline bool
  89       grow_needed(size_type size) const;
  90
  91       inline bool
  92       shrink_needed(size_type size) const;
  93
  94       inline size_type
  95       get_new_size_for_grow() const;
  96
  97       inline size_type
  98       get_new_size_for_shrink() const;
  99
 100       size_type
 101       get_new_size_for_arbitrary(size_type size) const;
 102
 103       inline void
 104       notify_grow_resize();
 105
 106       inline void
 107       notify_shrink_resize();
 108
 109       void
 110       notify_arbitrary(size_type actual_size);
 111
 112 #ifdef _GLIBCXX_DEBUG
 113       void
 114       assert_valid(const char* file, int line) const;
 115 #endif
 116
 117 #ifdef PB_DS_BINARY_HEAP_TRACE_
 118       void
 119       trace() const;
 120 #endif
 121
 122     private:
 123       enum
 124         {
 125           ratio = 8,
 126           factor = 2
 127         };
 128
 129     private:
 130       size_type m_next_shrink_size;
 131       size_type m_next_grow_size;
 132     };
 133
 134     PB_DS_CLASS_T_DEC
 135     inline
 136     PB_DS_CLASS_C_DEC::
 137     resize_policy() :
 138       m_next_shrink_size(0),
 139       m_next_grow_size(min_size)
 140     { PB_DS_ASSERT_VALID((*this)) }
 141
 142     PB_DS_CLASS_T_DEC
 143     inline void
 144     PB_DS_CLASS_C_DEC::
 145     swap(PB_DS_CLASS_C_DEC& other)
 146     {
 147       std::swap(m_next_shrink_size, other.m_next_shrink_size);
 148       std::swap(m_next_grow_size, other.m_next_grow_size);
 149     }
 150
 151     PB_DS_CLASS_T_DEC
 152     inline bool
 153     PB_DS_CLASS_C_DEC::
 154     resize_needed_for_grow(size_type size) const
 155     {
 156       _GLIBCXX_DEBUG_ASSERT(size <= m_next_grow_size);
 157       return size == m_next_grow_size;
 158     }
 159
 160     PB_DS_CLASS_T_DEC
 161     inline bool
 162     PB_DS_CLASS_C_DEC::
 163     resize_needed_for_shrink(size_type size) const
 164     {
 165       _GLIBCXX_DEBUG_ASSERT(size <= m_next_grow_size);
 166       return size == m_next_shrink_size;
 167     }
 168
 169     PB_DS_CLASS_T_DEC
 170     inline typename PB_DS_CLASS_C_DEC::size_type
 171     PB_DS_CLASS_C_DEC::
 172     get_new_size_for_grow() const
 173     { return m_next_grow_size*  factor; }
 174
 175     PB_DS_CLASS_T_DEC
 176     inline typename PB_DS_CLASS_C_DEC::size_type
 177     PB_DS_CLASS_C_DEC::
 178     get_new_size_for_shrink() const
 179     {
 180       const size_type half_size = m_next_grow_size / factor;
 181       return std::max(static_cast<size_type>(min_size), half_size);
 182     }
 183
 184     PB_DS_CLASS_T_DEC
 185     inline typename PB_DS_CLASS_C_DEC::size_type
 186     PB_DS_CLASS_C_DEC::
 187     get_new_size_for_arbitrary(size_type size) const
 188     {
 189       size_type ret = min_size;
 190       while (ret < size)
 191         ret *= factor;
 192       return ret;
 193     }
 194
 195     PB_DS_CLASS_T_DEC
 196     inline void
 197     PB_DS_CLASS_C_DEC::
 198     notify_grow_resize()
 199     {
 200       PB_DS_ASSERT_VALID((*this))
 201       _GLIBCXX_DEBUG_ASSERT(m_next_grow_size >= min_size);
 202       m_next_grow_size *= factor;
 203       m_next_shrink_size = m_next_grow_size / ratio;
 204       PB_DS_ASSERT_VALID((*this))
 205     }
 206
 207     PB_DS_CLASS_T_DEC
 208     inline void
 209     PB_DS_CLASS_C_DEC::
 210     notify_shrink_resize()
 211     {
 212       PB_DS_ASSERT_VALID((*this))
 213       m_next_shrink_size /= factor;
 214       if (m_next_shrink_size == 1)
 215         m_next_shrink_size = 0;
 216
 217       m_next_grow_size =
 218         std::max(m_next_grow_size / factor, static_cast<size_type>(min_size));
 219       PB_DS_ASSERT_VALID((*this))
 220     }
 221
 222     PB_DS_CLASS_T_DEC
 223     inline void
 224     PB_DS_CLASS_C_DEC::
 225     notify_arbitrary(size_type actual_size)
 226     {
 227       m_next_grow_size = actual_size;
 228       m_next_shrink_size = m_next_grow_size / ratio;
 229       PB_DS_ASSERT_VALID((*this))
 230     }
 231
 232 #ifdef _GLIBCXX_DEBUG
 233     PB_DS_CLASS_T_DEC
 234     void
 235     PB_DS_CLASS_C_DEC::
 236     assert_valid(const char* __file, int __line) const
 237     {
 238       PB_DS_DEBUG_VERIFY(m_next_shrink_size == 0 ||
 239                        m_next_shrink_size*  ratio == m_next_grow_size);
 240
 241       PB_DS_DEBUG_VERIFY(m_next_grow_size >= min_size);
 242     }
 243 #endif
 244
 245 #ifdef PB_DS_BINARY_HEAP_TRACE_
 246     PB_DS_CLASS_T_DEC
 247     void
 248     PB_DS_CLASS_C_DEC::
 249     trace() const
 250     {
 251       std::cerr << "shrink = " << m_next_shrink_size <<
 252         " grow = " << m_next_grow_size << std::endl;
 253     }
 254 #endif
 255
 256 #undef PB_DS_DEBUG_VERIFY
 257 #undef PB_DS_ASSERT_VALID
 258 #undef PB_DS_CLASS_T_DEC
 259 #undef PB_DS_CLASS_C_DEC
 260
 261 } // namespace detail
 262 } // namespace __gnu_pbds
 263
 264 #endif