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 pb_ds
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::
resize_policy()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::
swap(PB_DS_CLASS_C_DEC & other)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::
resize_needed_for_grow(size_type size) const151     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::
resize_needed_for_shrink(size_type size) const160     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::
get_new_size_for_grow() const169     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::
get_new_size_for_shrink() const175     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::
get_new_size_for_arbitrary(size_type size) const184     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::
notify_grow_resize()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::
notify_shrink_resize()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::
notify_arbitrary(size_type actual_size)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::
assert_valid() const233     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::
trace() const246     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 pb_ds
258 
259 #endif
260