resize_policy.hpp revision 169692 
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
52namespace 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::
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 pb_ds
258
259#endif
260