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