OpenCores
URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [tags/] [gnu-src/] [gcc-4.5.1/] [gcc-4.5.1-or32-1.0rc4/] [libstdc++-v3/] [include/] [ext/] [pb_ds/] [detail/] [binary_heap_/] [resize_policy.hpp] - Blame information for rev 519

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 424 jeremybenn 
// -*- 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

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.