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

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005, 2006, 2009 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     template<typename Size_Type>
  56     class resize_policy
  57     {
  58     public:
  59       typedef Size_Type size_type;
  60
  61       enum
  62         {
  63           min_size = 16
  64         };
  65
  66     public:
  67       inline
  68       resize_policy();
  69
  70       inline void
  71       swap(PB_DS_CLASS_C_DEC& other);
  72
  73       inline bool
  74       resize_needed_for_grow(size_type size) const;
  75
  76       inline bool
  77       resize_needed_for_shrink(size_type size) const;
  78
  79       inline bool
  80       grow_needed(size_type size) const;
  81
  82       inline bool
  83       shrink_needed(size_type size) const;
  84
  85       inline size_type
  86       get_new_size_for_grow() const;
  87
  88       inline size_type
  89       get_new_size_for_shrink() const;
  90
  91       size_type
  92       get_new_size_for_arbitrary(size_type size) const;
  93
  94       inline void
  95       notify_grow_resize();
  96
  97       inline void
  98       notify_shrink_resize();
  99
 100       void
 101       notify_arbitrary(size_type actual_size);
 102
 103 #ifdef _GLIBCXX_DEBUG
 104       void
 105       assert_valid() const;
 106 #endif
 107
 108 #ifdef PB_DS_BINARY_HEAP_TRACE_
 109       void
 110       trace() const;
 111 #endif
 112
 113     private:
 114       enum
 115         {
 116           ratio = 8,
 117           factor = 2
 118         };
 119
 120     private:
 121       size_type m_next_shrink_size;
 122       size_type m_next_grow_size;
 123     };
 124
 125     PB_DS_CLASS_T_DEC
 126     inline
 127     PB_DS_CLASS_C_DEC::
 128     resize_policy() :
 129       m_next_shrink_size(0),
 130       m_next_grow_size(min_size)
 131     { _GLIBCXX_DEBUG_ONLY(assert_valid();) }
 132
 133     PB_DS_CLASS_T_DEC
 134     inline void
 135     PB_DS_CLASS_C_DEC::
 136     swap(PB_DS_CLASS_C_DEC& other)
 137     {
 138       std::swap(m_next_shrink_size, other.m_next_shrink_size);
 139       std::swap(m_next_grow_size, other.m_next_grow_size);
 140     }
 141
 142     PB_DS_CLASS_T_DEC
 143     inline bool
 144     PB_DS_CLASS_C_DEC::
 145     resize_needed_for_grow(size_type size) const
 146     {
 147       _GLIBCXX_DEBUG_ASSERT(size <= m_next_grow_size);
 148       return size == 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_shrink(size_type size) const
 155     {
 156       _GLIBCXX_DEBUG_ASSERT(size <= m_next_grow_size);
 157       return size == m_next_shrink_size;
 158     }
 159
 160     PB_DS_CLASS_T_DEC
 161     inline typename PB_DS_CLASS_C_DEC::size_type
 162     PB_DS_CLASS_C_DEC::
 163     get_new_size_for_grow() const
 164     { return m_next_grow_size*  factor; }
 165
 166     PB_DS_CLASS_T_DEC
 167     inline typename PB_DS_CLASS_C_DEC::size_type
 168     PB_DS_CLASS_C_DEC::
 169     get_new_size_for_shrink() const
 170     {
 171       const size_type half_size = m_next_grow_size / factor;
 172       return std::max(static_cast<size_type>(min_size), half_size);
 173     }
 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_arbitrary(size_type size) const
 179     {
 180       size_type ret = min_size;
 181       while (ret < size)
 182         ret *= factor;
 183       return ret;
 184     }
 185
 186     PB_DS_CLASS_T_DEC
 187     inline void
 188     PB_DS_CLASS_C_DEC::
 189     notify_grow_resize()
 190     {
 191       _GLIBCXX_DEBUG_ONLY(assert_valid();)
 192       _GLIBCXX_DEBUG_ASSERT(m_next_grow_size >= min_size);
 193       m_next_grow_size *= factor;
 194       m_next_shrink_size = m_next_grow_size / ratio;
 195       _GLIBCXX_DEBUG_ONLY(assert_valid();)
 196     }
 197
 198     PB_DS_CLASS_T_DEC
 199     inline void
 200     PB_DS_CLASS_C_DEC::
 201     notify_shrink_resize()
 202     {
 203       _GLIBCXX_DEBUG_ONLY(assert_valid();)
 204       m_next_shrink_size /= factor;
 205       if (m_next_shrink_size == 1)
 206         m_next_shrink_size = 0;
 207
 208       m_next_grow_size =
 209         std::max(m_next_grow_size / factor, static_cast<size_type>(min_size));
 210       _GLIBCXX_DEBUG_ONLY(assert_valid();)
 211     }
 212
 213     PB_DS_CLASS_T_DEC
 214     inline void
 215     PB_DS_CLASS_C_DEC::
 216     notify_arbitrary(size_type actual_size)
 217     {
 218       m_next_grow_size = actual_size;
 219       m_next_shrink_size = m_next_grow_size / ratio;
 220       _GLIBCXX_DEBUG_ONLY(assert_valid();)
 221     }
 222
 223 #ifdef _GLIBCXX_DEBUG
 224     PB_DS_CLASS_T_DEC
 225     void
 226     PB_DS_CLASS_C_DEC::
 227     assert_valid() const
 228     {
 229       _GLIBCXX_DEBUG_ASSERT(m_next_shrink_size == 0 ||
 230                        m_next_shrink_size*  ratio == m_next_grow_size);
 231
 232       _GLIBCXX_DEBUG_ASSERT(m_next_grow_size >= min_size);
 233     }
 234 #endif
 235
 236 #ifdef PB_DS_BINARY_HEAP_TRACE_
 237     PB_DS_CLASS_T_DEC
 238     void
 239     PB_DS_CLASS_C_DEC::
 240     trace() const
 241     {
 242       std::cerr << "shrink = " << m_next_shrink_size <<
 243         " grow = " << m_next_grow_size << std::endl;
 244     }
 245 #endif
 246
 247 #undef PB_DS_CLASS_T_DEC
 248 #undef PB_DS_CLASS_C_DEC
 249
 250 } // namespace detail
 251 } // namespace __gnu_pbds
 252
 253 #endif