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

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005, 2006 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 2, 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 // You should have received a copy of the GNU General Public License
  17 // along with this library; see the file COPYING.  If not, write to
  18 // the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
  19 // MA 02111-1307, USA.
  20
  21 // As a special exception, you may use this file as part of a free
  22 // software library without restriction.  Specifically, if other files
  23 // instantiate templates or use macros or inline functions from this
  24 // file, or you compile this file and link it with other files to
  25 // produce an executable, this file does not by itself cause the
  26 // resulting executable to be covered by the GNU General Public
  27 // License.  This exception does not however invalidate any other
  28 // reasons why the executable file might be covered by the GNU General
  29 // Public License.
  30
  31 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
  32
  33 // Permission to use, copy, modify, sell, and distribute this software
  34 // is hereby granted without fee, provided that the above copyright
  35 // notice appears in all copies, and that both that copyright notice
  36 // and this permission notice appear in supporting documentation. None
  37 // of the above authors, nor IBM Haifa Research Laboratories, make any
  38 // representation about the suitability of this software for any
  39 // purpose. It is provided "as is" without express or implied
  40 // warranty.
  41
  42 /**
  43  * @file resize_policy.hpp
  44  * Contains an implementation class for a binary_heap.
  45  */
  46
  47 #ifndef PB_DS_BINARY_HEAP_RESIZE_POLICY_HPP
  48 #define PB_DS_BINARY_HEAP_RESIZE_POLICY_HPP
  49
  50 #include <debug/debug.h>
  51
  52 namespace __gnu_pbds
  53 {
  54   namespace detail
  55   {
  56
  57 #define PB_DS_CLASS_T_DEC template<typename Size_Type>
  58
  59 #define PB_DS_CLASS_C_DEC resize_policy<Size_Type>
  60
  61     template<typename Size_Type>
  62     class resize_policy
  63     {
  64     public:
  65       typedef Size_Type size_type;
  66
  67       enum
  68         {
  69           min_size = 16
  70         };
  71
  72     public:
  73       inline
  74       resize_policy();
  75
  76       inline void
  77       swap(PB_DS_CLASS_C_DEC& other);
  78
  79       inline bool
  80       resize_needed_for_grow(size_type size) const;
  81
  82       inline bool
  83       resize_needed_for_shrink(size_type size) const;
  84
  85       inline bool
  86       grow_needed(size_type size) const;
  87
  88       inline bool
  89       shrink_needed(size_type size) const;
  90
  91       inline size_type
  92       get_new_size_for_grow() const;
  93
  94       inline size_type
  95       get_new_size_for_shrink() const;
  96
  97       size_type
  98       get_new_size_for_arbitrary(size_type size) const;
  99
 100       inline void
 101       notify_grow_resize();
 102
 103       inline void
 104       notify_shrink_resize();
 105
 106       void
 107       notify_arbitrary(size_type actual_size);
 108
 109 #ifdef _GLIBCXX_DEBUG
 110       void
 111       assert_valid() const;
 112 #endif
 113
 114 #ifdef PB_DS_BINARY_HEAP_TRACE_
 115       void
 116       trace() const;
 117 #endif
 118
 119     private:
 120       enum
 121         {
 122           ratio = 8,
 123           factor = 2
 124         };
 125
 126     private:
 127       size_type m_next_shrink_size;
 128       size_type m_next_grow_size;
 129     };
 130
 131     PB_DS_CLASS_T_DEC
 132     inline
 133     PB_DS_CLASS_C_DEC::
 134     resize_policy() :
 135       m_next_shrink_size(0),
 136       m_next_grow_size(min_size)
 137     { _GLIBCXX_DEBUG_ONLY(assert_valid();) }
 138
 139     PB_DS_CLASS_T_DEC
 140     inline void
 141     PB_DS_CLASS_C_DEC::
 142     swap(PB_DS_CLASS_C_DEC& other)
 143     {
 144       std::swap(m_next_shrink_size, other.m_next_shrink_size);
 145       std::swap(m_next_grow_size, other.m_next_grow_size);
 146     }
 147
 148     PB_DS_CLASS_T_DEC
 149     inline bool
 150     PB_DS_CLASS_C_DEC::
 151     resize_needed_for_grow(size_type size) const
 152     {
 153       _GLIBCXX_DEBUG_ASSERT(size <= m_next_grow_size);
 154       return size == m_next_grow_size;
 155     }
 156
 157     PB_DS_CLASS_T_DEC
 158     inline bool
 159     PB_DS_CLASS_C_DEC::
 160     resize_needed_for_shrink(size_type size) const
 161     {
 162       _GLIBCXX_DEBUG_ASSERT(size <= m_next_grow_size);
 163       return size == m_next_shrink_size;
 164     }
 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_grow() const
 170     { return m_next_grow_size*  factor; }
 171
 172     PB_DS_CLASS_T_DEC
 173     inline typename PB_DS_CLASS_C_DEC::size_type
 174     PB_DS_CLASS_C_DEC::
 175     get_new_size_for_shrink() const
 176     {
 177       const size_type half_size = m_next_grow_size / factor;
 178       return std::max(static_cast<size_type>(min_size), half_size);
 179     }
 180
 181     PB_DS_CLASS_T_DEC
 182     inline typename PB_DS_CLASS_C_DEC::size_type
 183     PB_DS_CLASS_C_DEC::
 184     get_new_size_for_arbitrary(size_type size) const
 185     {
 186       size_type ret = min_size;
 187       while (ret < size)
 188         ret *= factor;
 189       return ret;
 190     }
 191
 192     PB_DS_CLASS_T_DEC
 193     inline void
 194     PB_DS_CLASS_C_DEC::
 195     notify_grow_resize()
 196     {
 197       _GLIBCXX_DEBUG_ONLY(assert_valid();)
 198       _GLIBCXX_DEBUG_ASSERT(m_next_grow_size >= min_size);
 199       m_next_grow_size *= factor;
 200       m_next_shrink_size = m_next_grow_size / ratio;
 201       _GLIBCXX_DEBUG_ONLY(assert_valid();)
 202     }
 203
 204     PB_DS_CLASS_T_DEC
 205     inline void
 206     PB_DS_CLASS_C_DEC::
 207     notify_shrink_resize()
 208     {
 209       _GLIBCXX_DEBUG_ONLY(assert_valid();)
 210       m_next_shrink_size /= factor;
 211       if (m_next_shrink_size == 1)
 212         m_next_shrink_size = 0;
 213
 214       m_next_grow_size =
 215         std::max(m_next_grow_size / factor, static_cast<size_type>(min_size));
 216       _GLIBCXX_DEBUG_ONLY(assert_valid();)
 217     }
 218
 219     PB_DS_CLASS_T_DEC
 220     inline void
 221     PB_DS_CLASS_C_DEC::
 222     notify_arbitrary(size_type actual_size)
 223     {
 224       m_next_grow_size = actual_size;
 225       m_next_shrink_size = m_next_grow_size / ratio;
 226       _GLIBCXX_DEBUG_ONLY(assert_valid();)
 227     }
 228
 229 #ifdef _GLIBCXX_DEBUG
 230     PB_DS_CLASS_T_DEC
 231     void
 232     PB_DS_CLASS_C_DEC::
 233     assert_valid() const
 234     {
 235       _GLIBCXX_DEBUG_ASSERT(m_next_shrink_size == 0 ||
 236                        m_next_shrink_size*  ratio == m_next_grow_size);
 237
 238       _GLIBCXX_DEBUG_ASSERT(m_next_grow_size >= min_size);
 239     }
 240 #endif
 241
 242 #ifdef PB_DS_BINARY_HEAP_TRACE_
 243     PB_DS_CLASS_T_DEC
 244     void
 245     PB_DS_CLASS_C_DEC::
 246     trace() const
 247     {
 248       std::cerr << "shrink = " << m_next_shrink_size <<
 249         " grow = " << m_next_grow_size << std::endl;
 250     }
 251 #endif
 252
 253 #undef PB_DS_CLASS_T_DEC
 254 #undef PB_DS_CLASS_C_DEC
 255
 256 } // namespace detail
 257 } // namespace __gnu_pbds
 258
 259 #endif