libstdc++
resize_policy.hpp
Go to the documentation of this file.
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 binary_heap_/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  /// Resize policy for binary heap.
51  template<typename _Tp>
53  {
54  private:
55  enum
56  {
57  ratio = 8,
58  factor = 2
59  };
60 
61  /// Next shrink size.
62  _Tp m_shrink_size;
63 
64  /// Next grow size.
65  _Tp m_grow_size;
66 
67  public:
68  typedef _Tp size_type;
69 
70  static const _Tp min_size = 16;
71 
72  resize_policy() : m_shrink_size(0), m_grow_size(min_size)
73  { PB_DS_ASSERT_VALID((*this)) }
74 
75  resize_policy(const resize_policy& other)
76  : m_shrink_size(other.m_shrink_size), m_grow_size(other.m_grow_size)
77  { PB_DS_ASSERT_VALID((*this)) }
78 
79  inline void
80  swap(resize_policy<_Tp>&);
81 
82  inline bool
83  resize_needed_for_grow(size_type) const;
84 
85  inline bool
86  resize_needed_for_shrink(size_type) const;
87 
88  inline bool
89  grow_needed(size_type) const;
90 
91  inline bool
92  shrink_needed(size_type) 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  inline size_type
101  get_new_size_for_arbitrary(size_type) 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);
111 
112 #ifdef _GLIBCXX_DEBUG
113  void
114  assert_valid(const char*, int) const;
115 #endif
116 
117 #ifdef PB_DS_BINARY_HEAP_TRACE_
118  void
119  trace() const;
120 #endif
121  };
122 
123  template<typename _Tp>
125 
126  template<typename _Tp>
127  inline void
130  {
131  std::swap(m_shrink_size, other.m_shrink_size);
132  std::swap(m_grow_size, other.m_grow_size);
133  }
134 
135  template<typename _Tp>
136  inline bool
137  resize_policy<_Tp>::
138  resize_needed_for_grow(size_type size) const
139  {
140  _GLIBCXX_DEBUG_ASSERT(size <= m_grow_size);
141  return size == m_grow_size;
142  }
143 
144  template<typename _Tp>
145  inline bool
146  resize_policy<_Tp>::
147  resize_needed_for_shrink(size_type size) const
148  {
149  _GLIBCXX_DEBUG_ASSERT(size <= m_grow_size);
150  return size == m_shrink_size;
151  }
152 
153  template<typename _Tp>
154  inline typename resize_policy<_Tp>::size_type
155  resize_policy<_Tp>::
156  get_new_size_for_grow() const
157  { return m_grow_size * factor; }
158 
159  template<typename _Tp>
160  inline typename resize_policy<_Tp>::size_type
161  resize_policy<_Tp>::
162  get_new_size_for_shrink() const
163  {
164  const size_type half_size = m_grow_size / factor;
165  return std::max(min_size, half_size);
166  }
167 
168  template<typename _Tp>
169  inline typename resize_policy<_Tp>::size_type
170  resize_policy<_Tp>::
171  get_new_size_for_arbitrary(size_type size) const
172  {
173  size_type ret = min_size;
174  while (ret < size)
175  ret *= factor;
176  return ret;
177  }
178 
179  template<typename _Tp>
180  inline void
181  resize_policy<_Tp>::
182  notify_grow_resize()
183  {
184  PB_DS_ASSERT_VALID((*this))
185  _GLIBCXX_DEBUG_ASSERT(m_grow_size >= min_size);
186  m_grow_size *= factor;
187  m_shrink_size = m_grow_size / ratio;
188  PB_DS_ASSERT_VALID((*this))
189  }
190 
191  template<typename _Tp>
192  inline void
193  resize_policy<_Tp>::
194  notify_shrink_resize()
195  {
196  PB_DS_ASSERT_VALID((*this))
197  m_shrink_size /= factor;
198  if (m_shrink_size == 1)
199  m_shrink_size = 0;
200  m_grow_size = std::max(m_grow_size / factor, min_size);
201  PB_DS_ASSERT_VALID((*this))
202  }
203 
204  template<typename _Tp>
205  inline void
206  resize_policy<_Tp>::
207  notify_arbitrary(size_type actual_size)
208  {
209  m_grow_size = actual_size;
210  m_shrink_size = m_grow_size / ratio;
211  PB_DS_ASSERT_VALID((*this))
212  }
213 
214 #ifdef _GLIBCXX_DEBUG
215  template<typename _Tp>
216  void
217  resize_policy<_Tp>::
218  assert_valid(const char* __file, int __line) const
219  {
220  PB_DS_DEBUG_VERIFY(m_shrink_size == 0
221  || m_shrink_size * ratio == m_grow_size);
222  PB_DS_DEBUG_VERIFY(m_grow_size >= min_size);
223  }
224 #endif
225 
226 #ifdef PB_DS_BINARY_HEAP_TRACE_
227  template<typename _Tp>
228  void
229  resize_policy<_Tp>::
230  trace() const
231  {
232  std::cerr << "shrink = " << m_shrink_size
233  << " grow = " << m_grow_size << std::endl;
234  }
235 #endif
236 
237 } // namespace detail
238 } // namespace __gnu_pbds
239 
240 #endif