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/] [rc_binomial_heap_/] [rc.hpp] - Blame information for rev 424

Go to most recent revision | 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 rc.hpp
38 
 * Contains a redundant (binary counter).
39 
 */
40 
 
41 
#ifndef PB_DS_RC_HPP
42 
#define PB_DS_RC_HPP
43 
 
44 
namespace __gnu_pbds
45 
{
46 
  namespace detail
47 
  {
48 
 
49 
#define PB_DS_CLASS_T_DEC \
50 
    template<typename Node, class Allocator>
51 
 
52 
#define PB_DS_CLASS_C_DEC \
53 
    rc<Node, Allocator>
54 
 
55 
    template<typename Node, class Allocator>
56 
    class rc
57 
    {
58 
    private:
59 
      typedef Allocator allocator_type;
60 
 
61 
      typedef typename allocator_type::size_type size_type;
62 
 
63 
      typedef Node node;
64 
 
65 
      typedef
66 
      typename allocator_type::template rebind<
67 
        node>::other::pointer
68 
      node_pointer;
69 
 
70 
      typedef
71 
      typename allocator_type::template rebind<
72 
        node_pointer>::other::pointer
73 
      entry_pointer;
74 
 
75 
      typedef
76 
      typename allocator_type::template rebind<
77 
        node_pointer>::other::const_pointer
78 
      const_entry_pointer;
79 
 
80 
      enum
81 
        {
82 
          max_entries = sizeof(size_type) << 3
83 
        };
84 
 
85 
    public:
86 
      typedef node_pointer entry;
87 
 
88 
      typedef const_entry_pointer const_iterator;
89 
 
90 
    public:
91 
      rc();
92 
 
93 
      rc(const PB_DS_CLASS_C_DEC& other);
94 
 
95 
      inline void
96 
      swap(PB_DS_CLASS_C_DEC& other);
97 
 
98 
      inline void
99 
      push(entry p_nd);
100 
 
101 
      inline node_pointer
102 
      top() const;
103 
 
104 
      inline void
105 
      pop();
106 
 
107 
      inline bool
108 
      empty() const;
109 
 
110 
      inline size_type
111 
      size() const;
112 
 
113 
      void
114 
      clear();
115 
 
116 
      const const_iterator
117 
      begin() const;
118 
 
119 
      const const_iterator
120 
      end() const;
121 
 
122 
#ifdef _GLIBCXX_DEBUG
123 
      void
124 
      assert_valid() const;
125 
#endif
126 
 
127 
#ifdef PB_DS_RC_BINOMIAL_HEAP_TRACE_
128 
      void
129 
      trace() const;
130 
#endif
131 
 
132 
    private:
133 
      node_pointer m_a_entries[max_entries];
134 
 
135 
      size_type m_over_top;
136 
    };
137 
 
138 
    PB_DS_CLASS_T_DEC
139 
    PB_DS_CLASS_C_DEC::
140 
    rc() : m_over_top(0)
141 
    { _GLIBCXX_DEBUG_ONLY(assert_valid();) }
142 
 
143 
    PB_DS_CLASS_T_DEC
144 
    PB_DS_CLASS_C_DEC::
145 
    rc(const PB_DS_CLASS_C_DEC& other) : m_over_top(0)
146 
    { _GLIBCXX_DEBUG_ONLY(assert_valid();) }
147 
 
148 
    PB_DS_CLASS_T_DEC
149 
    inline void
150 
    PB_DS_CLASS_C_DEC::
151 
    swap(PB_DS_CLASS_C_DEC& other)
152 
    {
153 
      _GLIBCXX_DEBUG_ONLY(assert_valid();)
154 
      _GLIBCXX_DEBUG_ONLY(other.assert_valid();)
155 
 
156 
      const size_type over_top = std::max(m_over_top, other.m_over_top);
157 
 
158 
      for (size_type i = 0; i < over_top; ++i)
159 
        std::swap(m_a_entries[i], other.m_a_entries[i]);
160 
 
161 
      std::swap(m_over_top, other.m_over_top);
162 
      _GLIBCXX_DEBUG_ONLY(assert_valid();)
163 
      _GLIBCXX_DEBUG_ONLY(other.assert_valid();)
164 
     }
165 
 
166 
    PB_DS_CLASS_T_DEC
167 
    inline void
168 
    PB_DS_CLASS_C_DEC::
169 
    push(entry p_nd)
170 
    {
171 
      _GLIBCXX_DEBUG_ONLY(assert_valid();)
172 
      _GLIBCXX_DEBUG_ASSERT(m_over_top < max_entries);
173 
      m_a_entries[m_over_top++] = p_nd;
174 
      _GLIBCXX_DEBUG_ONLY(assert_valid();)
175 
    }
176 
 
177 
    PB_DS_CLASS_T_DEC
178 
    inline void
179 
    PB_DS_CLASS_C_DEC::
180 
    pop()
181 
    {
182 
      _GLIBCXX_DEBUG_ONLY(assert_valid();)
183 
      _GLIBCXX_DEBUG_ASSERT(!empty());
184 
      --m_over_top;
185 
      _GLIBCXX_DEBUG_ONLY(assert_valid();)
186 
    }
187 
 
188 
    PB_DS_CLASS_T_DEC
189 
    inline typename PB_DS_CLASS_C_DEC::node_pointer
190 
    PB_DS_CLASS_C_DEC::
191 
    top() const
192 
    {
193 
      _GLIBCXX_DEBUG_ONLY(assert_valid();)
194 
      _GLIBCXX_DEBUG_ASSERT(!empty());
195 
      return *(m_a_entries + m_over_top - 1);
196 
    }
197 
 
198 
    PB_DS_CLASS_T_DEC
199 
    inline bool
200 
    PB_DS_CLASS_C_DEC::
201 
    empty() const
202 
    {
203 
      _GLIBCXX_DEBUG_ONLY(assert_valid();)
204 
      return m_over_top == 0;
205 
    }
206 
 
207 
    PB_DS_CLASS_T_DEC
208 
    inline typename PB_DS_CLASS_C_DEC::size_type
209 
    PB_DS_CLASS_C_DEC::
210 
    size() const
211 
    { return m_over_top; }
212 
 
213 
    PB_DS_CLASS_T_DEC
214 
    void
215 
    PB_DS_CLASS_C_DEC::
216 
    clear()
217 
    {
218 
      _GLIBCXX_DEBUG_ONLY(assert_valid();)
219 
      m_over_top = 0;
220 
      _GLIBCXX_DEBUG_ONLY(assert_valid();)
221 
    }
222 
 
223 
    PB_DS_CLASS_T_DEC
224 
    const typename PB_DS_CLASS_C_DEC::const_iterator
225 
    PB_DS_CLASS_C_DEC::
226 
    begin() const
227 
    { return& m_a_entries[0]; }
228 
 
229 
    PB_DS_CLASS_T_DEC
230 
    const typename PB_DS_CLASS_C_DEC::const_iterator
231 
    PB_DS_CLASS_C_DEC::
232 
    end() const
233 
    { return& m_a_entries[m_over_top]; }
234 
 
235 
#ifdef _GLIBCXX_DEBUG
236 
    PB_DS_CLASS_T_DEC
237 
    void
238 
    PB_DS_CLASS_C_DEC::
239 
    assert_valid() const
240 
    { _GLIBCXX_DEBUG_ASSERT(m_over_top < max_entries); }
241 
#endif
242 
 
243 
#ifdef PB_DS_RC_BINOMIAL_HEAP_TRACE_
244 
    PB_DS_CLASS_T_DEC
245 
    void
246 
    PB_DS_CLASS_C_DEC::
247 
    trace() const
248 
    {
249 
      std::cout << "rc" << std::endl;
250 
      for (size_type i = 0; i < m_over_top; ++i)
251 
        std::cerr << m_a_entries[i] << std::endl;
252 
      std::cout << std::endl;
253 
    }
254 
#endif
255 
 
256 
#undef PB_DS_CLASS_T_DEC
257 
#undef PB_DS_CLASS_C_DEC
258 
 
259 
} // namespace detail
260 
} // namespace __gnu_pbds
261 
 
262 
#endif

powered by: WebSVN 2.1.0

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