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

Subversion Repositories openrisc

Compare Revisions

  • This comparison shows the changes necessary to convert path 
    /openrisc/tags/gnu-src/gcc-4.5.1/gcc-4.5.1-or32-1.0rc4/libstdc++-v3/include/ext/pb_ds/detail/thin_heap_
    from Rev 424 to Rev 519
    ↔ Reverse comparison
  •

Rev 424 → Rev 519

/trace_fn_imps.hpp
0,0 → 1,55
// -*- C++ -*-
 
// Copyright (C) 2005, 2006, 2009 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library. This library is free
// software; you can redistribute it and/or modify it under the terms
// of the GNU General Public License as published by the Free Software
// Foundation; either version 3, or (at your option) any later
// version.
 
// This library is distributed in the hope that it will be useful, but
// WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
// General Public License for more details.
 
// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.
 
// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
// <http://www.gnu.org/licenses/>.
 
// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
 
// Permission to use, copy, modify, sell, and distribute this software
// is hereby granted without fee, provided that the above copyright
// notice appears in all copies, and that both that copyright notice
// and this permission notice appear in supporting documentation. None
// of the above authors, nor IBM Haifa Research Laboratories, make any
// representation about the suitability of this software for any
// purpose. It is provided "as is" without express or implied
// warranty.
 
/**
* @file trace_fn_imps.hpp
* Contains an implementation class for left_child_next_sibling_heap_.
*/
 
#ifdef PB_DS_THIN_HEAP_TRACE_
 
PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
trace() const
{
std::cerr << std::endl;
 
std::cerr << "m_p_max " << m_p_max << std::endl;
 
base_type::trace();
}
 
#endif // #ifdef PB_DS_THIN_HEAP_TRACE_
/erase_fn_imps.hpp
0,0 → 1,296
// -*- C++ -*-
 
// Copyright (C) 2005, 2006, 2009 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library. This library is free
// software; you can redistribute it and/or modify it under the terms
// of the GNU General Public License as published by the Free Software
// Foundation; either version 3, or (at your option) any later
// version.
 
// This library is distributed in the hope that it will be useful, but
// WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
// General Public License for more details.
 
// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.
 
// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
// <http://www.gnu.org/licenses/>.
 
// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
 
// Permission to use, copy, modify, sell, and distribute this software
// is hereby granted without fee, provided that the above copyright
// notice appears in all copies, and that both that copyright notice
// and this permission notice appear in supporting documentation. None
// of the above authors, nor IBM Haifa Research Laboratories, make any
// representation about the suitability of this software for any
// purpose. It is provided "as is" without express or implied
// warranty.
 
/**
* @file erase_fn_imps.hpp
* Contains an implementation for thin_heap_.
*/
 
PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
pop()
{
_GLIBCXX_DEBUG_ONLY(assert_valid();)
_GLIBCXX_DEBUG_ASSERT(!base_type::empty());
 
_GLIBCXX_DEBUG_ASSERT(m_p_max != NULL);
 
node_pointer p_nd = m_p_max;
 
remove_max_node();
 
base_type::actual_erase_node(p_nd);
 
_GLIBCXX_DEBUG_ONLY(assert_valid();)
}
 
PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
remove_max_node()
{
to_aux_except_max();
 
make_from_aux();
}
 
PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
to_aux_except_max()
{
node_pointer p_add = base_type::m_p_root;
 
while (p_add != m_p_max)
{
node_pointer p_next_add = p_add->m_p_next_sibling;
 
add_to_aux(p_add);
 
p_add = p_next_add;
}
 
p_add = m_p_max->m_p_l_child;
 
while (p_add != NULL)
{
node_pointer p_next_add = p_add->m_p_next_sibling;
 
p_add->m_metadata = p_add->m_p_l_child == NULL?
0 :
p_add->m_p_l_child->m_metadata + 1;
 
add_to_aux(p_add);
 
p_add = p_next_add;
}
 
p_add = m_p_max->m_p_next_sibling;
 
while (p_add != NULL)
{
node_pointer p_next_add = p_add->m_p_next_sibling;
 
add_to_aux(p_add);
 
p_add = p_next_add;
}
}
 
PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
add_to_aux(node_pointer p_nd)
{
size_type r = p_nd->m_metadata;
 
while (m_a_aux[r] != NULL)
{
_GLIBCXX_DEBUG_ASSERT(p_nd->m_metadata < rank_bound());
 
if (Cmp_Fn::operator()(m_a_aux[r]->m_value, p_nd->m_value))
make_child_of(m_a_aux[r], p_nd);
else
{
make_child_of(p_nd, m_a_aux[r]);
 
p_nd = m_a_aux[r];
}
 
m_a_aux[r] = NULL;
 
++r;
}
 
_GLIBCXX_DEBUG_ASSERT(p_nd->m_metadata < rank_bound());
 
m_a_aux[r] = p_nd;
}
 
PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
make_child_of(node_pointer p_nd, node_pointer p_new_parent)
{
_GLIBCXX_DEBUG_ASSERT(p_nd->m_metadata == p_new_parent->m_metadata);
_GLIBCXX_DEBUG_ASSERT(m_a_aux[p_nd->m_metadata] == p_nd ||
m_a_aux[p_nd->m_metadata] == p_new_parent);
 
++p_new_parent->m_metadata;
 
base_type::make_child_of(p_nd, p_new_parent);
}
 
PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
make_from_aux()
{
base_type::m_p_root = m_p_max = NULL;
 
const size_type rnk_bnd = rank_bound();
 
size_type i = 0;
 
while (i < rnk_bnd)
{
if (m_a_aux[i] != NULL)
{
make_root_and_link(m_a_aux[i]);
 
m_a_aux[i] = NULL;
}
 
++i;
}
 
_GLIBCXX_DEBUG_ONLY(assert_aux_null();)
}
 
PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
remove_node(node_pointer p_nd)
{
node_pointer p_parent = p_nd;
while (base_type::parent(p_parent) != NULL)
p_parent = base_type::parent(p_parent);
 
base_type::bubble_to_top(p_nd);
 
m_p_max = p_nd;
 
node_pointer p_fix = base_type::m_p_root;
while (p_fix != NULL&& p_fix->m_p_next_sibling != p_parent)
p_fix = p_fix->m_p_next_sibling;
 
if (p_fix != NULL)
p_fix->m_p_next_sibling = p_nd;
 
remove_max_node();
}
 
PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
clear()
{
base_type::clear();
 
m_p_max = NULL;
}
 
PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
erase(point_iterator it)
{
_GLIBCXX_DEBUG_ONLY(assert_valid();)
_GLIBCXX_DEBUG_ASSERT(!base_type::empty());
 
node_pointer p_nd = it.m_p_nd;
 
remove_node(p_nd);
 
base_type::actual_erase_node(p_nd);
 
_GLIBCXX_DEBUG_ONLY(assert_valid();)
}
 
PB_DS_CLASS_T_DEC
template<typename Pred>
typename PB_DS_CLASS_C_DEC::size_type
PB_DS_CLASS_C_DEC::
erase_if(Pred pred)
{
_GLIBCXX_DEBUG_ONLY(assert_valid();)
 
if (base_type::empty())
{
_GLIBCXX_DEBUG_ONLY(assert_valid();)
 
return 0;
}
 
base_type::to_linked_list();
 
node_pointer p_out = base_type::prune(pred);
 
size_type ersd = 0;
 
while (p_out != NULL)
{
++ersd;
 
node_pointer p_next = p_out->m_p_next_sibling;
 
base_type::actual_erase_node(p_out);
 
p_out = p_next;
}
 
node_pointer p_cur = base_type::m_p_root;
 
m_p_max = base_type::m_p_root = NULL;
 
while (p_cur != NULL)
{
node_pointer p_next = p_cur->m_p_next_sibling;
 
make_root_and_link(p_cur);
 
p_cur = p_next;
}
 
_GLIBCXX_DEBUG_ONLY(assert_valid();)
 
return ersd;
}
 
PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::size_type
PB_DS_CLASS_C_DEC::
rank_bound()
{
const std::size_t* const p_upper =
std::upper_bound( g_a_rank_bounds, g_a_rank_bounds + num_distinct_rank_bounds, base_type::m_size);
 
if (p_upper == g_a_rank_bounds + num_distinct_rank_bounds)
return max_rank;
 
return (p_upper - g_a_rank_bounds);
}
 
/find_fn_imps.hpp
0,0 → 1,51
// -*- C++ -*-
 
// Copyright (C) 2005, 2006, 2009 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library. This library is free
// software; you can redistribute it and/or modify it under the terms
// of the GNU General Public License as published by the Free Software
// Foundation; either version 3, or (at your option) any later
// version.
 
// This library is distributed in the hope that it will be useful, but
// WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
// General Public License for more details.
 
// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.
 
// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
// <http://www.gnu.org/licenses/>.
 
// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
 
// Permission to use, copy, modify, sell, and distribute this software
// is hereby granted without fee, provided that the above copyright
// notice appears in all copies, and that both that copyright notice
// and this permission notice appear in supporting documentation. None
// of the above authors, nor IBM Haifa Research Laboratories, make any
// representation about the suitability of this software for any
// purpose. It is provided "as is" without express or implied
// warranty.
 
/**
* @file find_fn_imps.hpp
* Contains an implementation for thin_heap_.
*/
 
PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::const_reference
PB_DS_CLASS_C_DEC::
top() const
{
_GLIBCXX_DEBUG_ONLY(assert_valid();)
_GLIBCXX_DEBUG_ASSERT(!base_type::empty());
 
_GLIBCXX_DEBUG_ASSERT(m_p_max != NULL);
return m_p_max->m_value;
}
/thin_heap_.hpp
0,0 → 1,351
// -*- C++ -*-
 
// Copyright (C) 2005, 2006, 2009 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library. This library is free
// software; you can redistribute it and/or modify it under the terms
// of the GNU General Public License as published by the Free Software
// Foundation; either version 3, or (at your option) any later
// version.
 
// This library is distributed in the hope that it will be useful, but
// WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
// General Public License for more details.
 
// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.
 
// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
// <http://www.gnu.org/licenses/>.
 
// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
 
// Permission to use, copy, modify, sell, and distribute this software
// is hereby granted without fee, provided that the above copyright
// notice appears in all copies, and that both that copyright notice
// and this permission notice appear in supporting documentation. None
// of the above authors, nor IBM Haifa Research Laboratories, make any
// representation about the suitability of this software for any
// purpose. It is provided "as is" without express or implied
// warranty.
 
/**
* @file thin_heap_.hpp
* Contains an implementation class for a thin heap.
*/
 
#ifndef PB_DS_THIN_HEAP_HPP
#define PB_DS_THIN_HEAP_HPP
 
/*
* Thin heaps.
* Tarjan and Kaplan.
*/
 
#include <algorithm>
#include <ext/pb_ds/detail/cond_dealtor.hpp>
#include <ext/pb_ds/detail/type_utils.hpp>
#include <ext/pb_ds/detail/left_child_next_sibling_heap_/left_child_next_sibling_heap_.hpp>
#include <ext/pb_ds/detail/left_child_next_sibling_heap_/null_metadata.hpp>
#include <debug/debug.h>
 
namespace __gnu_pbds
{
namespace detail
{
 
#define PB_DS_CLASS_T_DEC \
template<typename Value_Type, class Cmp_Fn, class Allocator>
 
#define PB_DS_CLASS_C_DEC \
thin_heap_<Value_Type, Cmp_Fn, Allocator>
 
#ifdef _GLIBCXX_DEBUG
#define PB_DS_BASE_C_DEC \
left_child_next_sibling_heap_<Value_Type, Cmp_Fn, \
typename Allocator::size_type, Allocator, true>
#else
#define PB_DS_BASE_C_DEC \
left_child_next_sibling_heap_<Value_Type, Cmp_Fn, \
typename Allocator::size_type, Allocator>
#endif
 
/**
* class description = "t|-|i|\| h34p">
**/
template<typename Value_Type, class Cmp_Fn, class Allocator>
class thin_heap_ : public PB_DS_BASE_C_DEC
{
 
private:
typedef PB_DS_BASE_C_DEC base_type;
 
protected:
typedef typename base_type::node node;
 
typedef typename base_type::node_pointer node_pointer;
 
typedef typename base_type::const_node_pointer const_node_pointer;
 
public:
 
typedef typename Allocator::size_type size_type;
 
typedef typename Allocator::difference_type difference_type;
 
typedef Value_Type value_type;
 
typedef
typename Allocator::template rebind<
value_type>::other::pointer
pointer;
 
typedef
typename Allocator::template rebind<
value_type>::other::const_pointer
const_pointer;
 
typedef
typename Allocator::template rebind<
value_type>::other::reference
reference;
 
typedef
typename Allocator::template rebind<
value_type>::other::const_reference
const_reference;
 
typedef
typename PB_DS_BASE_C_DEC::const_point_iterator
const_point_iterator;
 
typedef typename PB_DS_BASE_C_DEC::point_iterator point_iterator;
 
typedef typename PB_DS_BASE_C_DEC::const_iterator const_iterator;
 
typedef typename PB_DS_BASE_C_DEC::iterator iterator;
 
typedef Cmp_Fn cmp_fn;
 
typedef Allocator allocator_type;
 
public:
 
inline point_iterator
push(const_reference r_val);
 
void
modify(point_iterator it, const_reference r_new_val);
 
inline const_reference
top() const;
 
void
pop();
 
void
erase(point_iterator it);
 
inline void
clear();
 
template<typename Pred>
size_type
erase_if(Pred pred);
 
template<typename Pred>
void
split(Pred pred, PB_DS_CLASS_C_DEC& other);
 
void
join(PB_DS_CLASS_C_DEC& other);
 
protected:
 
thin_heap_();
 
thin_heap_(const Cmp_Fn& r_cmp_fn);
 
thin_heap_(const PB_DS_CLASS_C_DEC& other);
 
void
swap(PB_DS_CLASS_C_DEC& other);
 
~thin_heap_();
 
template<typename It>
void
copy_from_range(It first_it, It last_it);
 
#ifdef _GLIBCXX_DEBUG
void
assert_valid() const;
 
void
assert_max() const;
#endif
 
#ifdef PB_DS_THIN_HEAP_TRACE_
void
trace() const;
#endif
 
private:
enum
{
max_rank = (sizeof(size_type) << 4) + 2
};
 
private:
 
void
initialize();
 
inline void
update_max(node_pointer p_nd);
 
inline void
fix(node_pointer p_nd);
 
inline void
fix_root(node_pointer p_y);
 
inline void
fix_sibling_rank_1_unmarked(node_pointer p_y);
 
inline void
fix_sibling_rank_1_marked(node_pointer p_y);
 
inline void
fix_sibling_general_unmarked(node_pointer p_y);
 
inline void
fix_sibling_general_marked(node_pointer p_y);
 
inline void
fix_child(node_pointer p_y);
 
inline static void
make_root(node_pointer p_nd);
 
inline void
make_root_and_link(node_pointer p_nd);
 
inline void
remove_max_node();
 
void
to_aux_except_max();
 
inline void
add_to_aux(node_pointer p_nd);
 
inline void
make_from_aux();
 
inline size_type
rank_bound();
 
inline void
make_child_of(node_pointer p_nd, node_pointer p_new_parent);
 
inline void
remove_node(node_pointer p_nd);
 
inline node_pointer
join(node_pointer p_lhs, node_pointer p_rhs) const;
 
#ifdef _GLIBCXX_DEBUG
void
assert_node_consistent(const_node_pointer p_nd, bool root) const;
 
void
assert_aux_null() const;
#endif
 
private:
node_pointer m_p_max;
 
node_pointer m_a_aux[max_rank];
};
 
enum
{
num_distinct_rank_bounds = 48
};
 
// Taken from the SGI implementation; acknowledged in the docs.
static const std::size_t g_a_rank_bounds[num_distinct_rank_bounds] =
{
/* Dealing cards... */
/* 0 */ 0ul,
/* 1 */ 1ul,
/* 2 */ 1ul,
/* 3 */ 2ul,
/* 4 */ 4ul,
/* 5 */ 6ul,
/* 6 */ 11ul,
/* 7 */ 17ul,
/* 8 */ 29ul,
/* 9 */ 46ul,
/* 10 */ 76ul,
/* 11 */ 122ul,
/* 12 */ 199ul,
/* 13 */ 321ul,
/* 14 */ 521ul,
/* 15 */ 842ul,
/* 16 */ 1364ul,
/* 17 */ 2206ul,
/* 18 */ 3571ul,
/* 19 */ 5777ul,
/* 20 */ 9349ul,
/* 21 */ 15126ul,
/* 22 */ 24476ul,
/* 23 */ 39602ul,
/* 24 */ 64079ul,
/* 25 */ 103681ul,
/* 26 */ 167761ul,
/* 27 */ 271442ul,
/* 28 */ 439204ul,
/* 29 */ 710646ul,
/* 30 */ 1149851ul,
/* 31 */ 1860497ul,
/* 32 */ 3010349ul,
/* 33 */ 4870846ul,
/* 34 */ 7881196ul,
/* 35 */ 12752042ul,
/* 36 */ 20633239ul,
/* 37 */ 33385282ul,
/* 38 */ 54018521ul,
/* 39 */ 87403803ul,
/* 40 */ 141422324ul,
/* 41 */ 228826127ul,
/* 42 */ 370248451ul,
/* 43 */ 599074578ul,
/* 44 */ 969323029ul,
/* 45 */ 1568397607ul,
/* 46 */ 2537720636ul,
/* 47 */ 4106118243ul
/* Pot's good, let's play */
};
 
#include <ext/pb_ds/detail/thin_heap_/constructors_destructor_fn_imps.hpp>
#include <ext/pb_ds/detail/thin_heap_/debug_fn_imps.hpp>
#include <ext/pb_ds/detail/thin_heap_/trace_fn_imps.hpp>
#include <ext/pb_ds/detail/thin_heap_/find_fn_imps.hpp>
#include <ext/pb_ds/detail/thin_heap_/insert_fn_imps.hpp>
#include <ext/pb_ds/detail/thin_heap_/erase_fn_imps.hpp>
#include <ext/pb_ds/detail/thin_heap_/split_join_fn_imps.hpp>
 
#undef PB_DS_CLASS_C_DEC
#undef PB_DS_CLASS_T_DEC
#undef PB_DS_BASE_C_DEC
 
} // namespace detail
} // namespace __gnu_pbds
 
#endif
/insert_fn_imps.hpp
0,0 → 1,326
// -*- C++ -*-
 
// Copyright (C) 2005, 2006, 2009 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library. This library is free
// software; you can redistribute it and/or modify it under the terms
// of the GNU General Public License as published by the Free Software
// Foundation; either version 3, or (at your option) any later
// version.
 
// This library is distributed in the hope that it will be useful, but
// WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
// General Public License for more details.
 
// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.
 
// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
// <http://www.gnu.org/licenses/>.
 
// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
 
// Permission to use, copy, modify, sell, and distribute this software
// is hereby granted without fee, provided that the above copyright
// notice appears in all copies, and that both that copyright notice
// and this permission notice appear in supporting documentation. None
// of the above authors, nor IBM Haifa Research Laboratories, make any
// representation about the suitability of this software for any
// purpose. It is provided "as is" without express or implied
// warranty.
 
/**
* @file insert_fn_imps.hpp
* Contains an implementation for thin_heap_.
*/
 
PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::point_iterator
PB_DS_CLASS_C_DEC::
push(const_reference r_val)
{
_GLIBCXX_DEBUG_ONLY(assert_valid();)
 
node_pointer p_nd = base_type::get_new_node_for_insert(r_val);
 
p_nd->m_metadata = 0;
 
p_nd->m_p_prev_or_parent = p_nd->m_p_l_child = NULL;
 
if (base_type::m_p_root == NULL)
{
p_nd->m_p_next_sibling = NULL;
 
m_p_max = base_type::m_p_root = p_nd;
 
_GLIBCXX_DEBUG_ONLY(assert_valid();)
 
return point_iterator(p_nd);
}
 
p_nd->m_p_next_sibling = base_type::m_p_root;
 
base_type::m_p_root->m_p_prev_or_parent = NULL;
 
base_type::m_p_root = p_nd;
 
update_max(p_nd);
 
_GLIBCXX_DEBUG_ONLY(assert_valid();)
 
return point_iterator(p_nd);
}
 
PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
make_root(node_pointer p_nd)
{
p_nd->m_metadata =
p_nd->m_p_l_child == NULL?
0 :
1 + p_nd->m_p_l_child->m_metadata;
}
 
PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
make_root_and_link(node_pointer p_nd)
{
make_root(p_nd);
 
p_nd->m_p_prev_or_parent = NULL;
 
p_nd->m_p_next_sibling = base_type::m_p_root;
 
if (base_type::m_p_root != NULL)
base_type::m_p_root->m_p_prev_or_parent = NULL;
 
base_type::m_p_root = p_nd;
 
update_max(p_nd);
}
 
PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
fix(node_pointer p_y)
{
while (true)
{
if (p_y->m_p_prev_or_parent == NULL)
{
fix_root(p_y);
 
return;
}
else if (p_y->m_metadata == 1&& p_y->m_p_next_sibling == NULL)
{
if (p_y->m_p_l_child != NULL)
{
fix_sibling_rank_1_unmarked(p_y);
 
return;
}
 
fix_sibling_rank_1_marked(p_y);
 
p_y = p_y->m_p_prev_or_parent;
}
else if (p_y->m_metadata > p_y->m_p_next_sibling->m_metadata + 1)
{
_GLIBCXX_DEBUG_ASSERT(p_y->m_p_l_child != NULL);
 
if (p_y->m_metadata != p_y->m_p_l_child->m_metadata + 2)
{
fix_sibling_general_unmarked(p_y);
 
return;
}
 
fix_sibling_general_marked(p_y);
 
p_y = p_y->m_p_prev_or_parent;
}
else if ((p_y->m_p_l_child == NULL&&
p_y->m_metadata == 2) ||(p_y->m_p_l_child != NULL&&
p_y->m_metadata == p_y->m_p_l_child->m_metadata + 3))
{
node_pointer p_z = p_y->m_p_prev_or_parent;
 
fix_child(p_y);
 
p_y = p_z;
}
else
return;
}
}
 
PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
fix_root(node_pointer p_y)
{
_GLIBCXX_DEBUG_ASSERT(p_y->m_p_prev_or_parent == NULL);
 
make_root(p_y);
 
_GLIBCXX_DEBUG_ONLY(assert_node_consistent(p_y, true);)
}
 
PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
fix_sibling_rank_1_unmarked(node_pointer p_y)
{
_GLIBCXX_DEBUG_ASSERT(p_y->m_p_prev_or_parent != NULL);
 
_GLIBCXX_DEBUG_ONLY(node_pointer p_w = p_y->m_p_l_child;)
_GLIBCXX_DEBUG_ASSERT(p_w != NULL);
_GLIBCXX_DEBUG_ASSERT(p_w->m_p_next_sibling == NULL);
_GLIBCXX_DEBUG_ASSERT(p_y->m_p_next_sibling == NULL);
 
p_y->m_p_next_sibling = p_y->m_p_l_child;
 
p_y->m_p_next_sibling->m_p_prev_or_parent = p_y;
 
p_y->m_p_l_child = NULL;
 
_GLIBCXX_DEBUG_ONLY(assert_node_consistent(p_y, false);)
}
 
PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
fix_sibling_rank_1_marked(node_pointer p_y)
{
_GLIBCXX_DEBUG_ASSERT(p_y->m_p_prev_or_parent != NULL);
_GLIBCXX_DEBUG_ASSERT(p_y->m_p_l_child == NULL);
 
p_y->m_metadata = 0;
 
_GLIBCXX_DEBUG_ONLY(assert_node_consistent(p_y, false);)
}
 
PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
fix_sibling_general_unmarked(node_pointer p_y)
{
_GLIBCXX_DEBUG_ASSERT(p_y->m_p_prev_or_parent != NULL);
 
node_pointer p_w = p_y->m_p_l_child;
_GLIBCXX_DEBUG_ASSERT(p_w != NULL);
_GLIBCXX_DEBUG_ASSERT(p_w->m_p_next_sibling != NULL);
 
p_y->m_p_l_child = p_w->m_p_next_sibling;
p_w->m_p_next_sibling->m_p_prev_or_parent = p_y;
 
p_w->m_p_next_sibling = p_y->m_p_next_sibling;
_GLIBCXX_DEBUG_ASSERT(p_w->m_p_next_sibling != NULL);
p_w->m_p_next_sibling->m_p_prev_or_parent = p_w;
 
p_y->m_p_next_sibling = p_w;
p_w->m_p_prev_or_parent = p_y;
 
_GLIBCXX_DEBUG_ONLY(assert_node_consistent(p_y, false);)
}
 
PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
fix_sibling_general_marked(node_pointer p_y)
{
_GLIBCXX_DEBUG_ASSERT(p_y->m_p_prev_or_parent != NULL);
 
--p_y->m_metadata;
 
_GLIBCXX_DEBUG_ONLY(assert_node_consistent(p_y, false);)
}
 
PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
fix_child(node_pointer p_y)
{
_GLIBCXX_DEBUG_ASSERT(p_y->m_p_prev_or_parent != NULL);
 
if (p_y->m_p_next_sibling != NULL)
p_y->m_p_next_sibling->m_p_prev_or_parent = p_y->m_p_prev_or_parent;
 
if (p_y->m_p_prev_or_parent->m_p_l_child == p_y)
p_y->m_p_prev_or_parent->m_p_l_child = p_y->m_p_next_sibling;
else
p_y->m_p_prev_or_parent->m_p_next_sibling = p_y->m_p_next_sibling;
 
make_root_and_link(p_y);
}
 
PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
modify(point_iterator it, const_reference r_new_val)
{
_GLIBCXX_DEBUG_ONLY(assert_valid();)
node_pointer p_nd = it.m_p_nd;
 
_GLIBCXX_DEBUG_ASSERT(p_nd != NULL);
 
const bool smaller = Cmp_Fn::operator()(r_new_val, p_nd->m_value);
 
p_nd->m_value = r_new_val;
 
if (smaller)
{
remove_node(p_nd);
 
p_nd->m_p_l_child = NULL;
 
make_root_and_link(p_nd);
 
_GLIBCXX_DEBUG_ONLY(assert_valid();)
 
return;
}
 
if (p_nd->m_p_prev_or_parent == NULL)
{
update_max(p_nd);
 
_GLIBCXX_DEBUG_ONLY(assert_valid();)
 
return;
}
 
node_pointer p_y = p_nd->m_p_prev_or_parent;
_GLIBCXX_DEBUG_ASSERT(p_y != NULL);
 
if (p_nd->m_p_next_sibling != NULL)
p_nd->m_p_next_sibling->m_p_prev_or_parent = p_y;
 
if (p_y->m_p_l_child == p_nd)
p_y->m_p_l_child = p_nd->m_p_next_sibling;
else
p_y->m_p_next_sibling = p_nd->m_p_next_sibling;
 
fix(p_y);
 
make_root_and_link(p_nd);
 
_GLIBCXX_DEBUG_ONLY(assert_valid();)
}
 
PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
update_max(node_pointer p_nd)
{
if (m_p_max == NULL || Cmp_Fn::operator()(m_p_max->m_value, p_nd->m_value))
m_p_max = p_nd;
}
 
/constructors_destructor_fn_imps.hpp
0,0 → 1,106
// -*- C++ -*-
 
// Copyright (C) 2005, 2006, 2009 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library. This library is free
// software; you can redistribute it and/or modify it under the terms
// of the GNU General Public License as published by the Free Software
// Foundation; either version 3, or (at your option) any later
// version.
 
// This library is distributed in the hope that it will be useful, but
// WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
// General Public License for more details.
 
// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.
 
// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
// <http://www.gnu.org/licenses/>.
 
// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
 
// Permission to use, copy, modify, sell, and distribute this software
// is hereby granted without fee, provided that the above copyright
// notice appears in all copies, and that both that copyright notice
// and this permission notice appear in supporting documentation. None
// of the above authors, nor IBM Haifa Research Laboratories, make any
// representation about the suitability of this software for any
// purpose. It is provided "as is" without express or implied
// warranty.
 
/**
* @file constructors_destructor_fn_imps.hpp
* Contains an implementation for thin_heap_.
*/
 
PB_DS_CLASS_T_DEC
template<typename It>
void
PB_DS_CLASS_C_DEC::
copy_from_range(It first_it, It last_it)
{
while (first_it != last_it)
push(*(first_it++));
_GLIBCXX_DEBUG_ONLY(assert_valid();)
}
 
PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
thin_heap_() :
m_p_max(NULL)
{
initialize();
_GLIBCXX_DEBUG_ONLY(assert_valid();)
}
 
PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
thin_heap_(const Cmp_Fn& r_cmp_fn) :
PB_DS_BASE_C_DEC(r_cmp_fn),
m_p_max(NULL)
{
initialize();
_GLIBCXX_DEBUG_ONLY(assert_valid();)
}
 
PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
thin_heap_(const PB_DS_CLASS_C_DEC& other) :
PB_DS_BASE_C_DEC(other)
{
initialize();
m_p_max = base_type::m_p_root;
for (node_pointer p_nd = base_type::m_p_root; p_nd != NULL; p_nd = p_nd->m_p_next_sibling)
if (Cmp_Fn::operator()(m_p_max->m_value, p_nd->m_value))
m_p_max = p_nd;
 
_GLIBCXX_DEBUG_ONLY(assert_valid();)
}
 
PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
swap(PB_DS_CLASS_C_DEC& other)
{
_GLIBCXX_DEBUG_ONLY(assert_valid();)
base_type::swap(other);
std::swap(m_p_max, other.m_p_max);
_GLIBCXX_DEBUG_ONLY(assert_valid();)
}
 
PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
~thin_heap_()
{ }
 
PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
initialize()
{ std::fill(m_a_aux, m_a_aux + max_rank, static_cast<node_pointer>(NULL)); }
 
/debug_fn_imps.hpp
0,0 → 1,112
// -*- C++ -*-
 
// Copyright (C) 2005, 2006, 2009 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library. This library is free
// software; you can redistribute it and/or modify it under the terms
// of the GNU General Public License as published by the Free Software
// Foundation; either version 3, or (at your option) any later
// version.
 
// This library is distributed in the hope that it will be useful, but
// WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
// General Public License for more details.
 
// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.
 
// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
// <http://www.gnu.org/licenses/>.
 
// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
 
// Permission to use, copy, modify, sell, and distribute this software
// is hereby granted without fee, provided that the above copyright
// notice appears in all copies, and that both that copyright notice
// and this permission notice appear in supporting documentation. None
// of the above authors, nor IBM Haifa Research Laboratories, make any
// representation about the suitability of this software for any
// purpose. It is provided "as is" without express or implied
// warranty.
 
/**
* @file debug_fn_imps.hpp
* Contains an implementation for thin_heap_.
*/
 
#ifdef _GLIBCXX_DEBUG
 
PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
assert_valid() const
{
base_type::assert_valid();
assert_node_consistent(base_type::m_p_root, true);
assert_max();
assert_aux_null();
}
 
PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
assert_aux_null() const
{
for (size_type i = 0; i < max_rank; ++i)
_GLIBCXX_DEBUG_ASSERT(m_a_aux[i] == NULL);
}
 
PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
assert_max() const
{
if (m_p_max == NULL)
{
_GLIBCXX_DEBUG_ASSERT(base_type::empty());
return;
}
 
_GLIBCXX_DEBUG_ASSERT(!base_type::empty());
_GLIBCXX_DEBUG_ASSERT(base_type::parent(m_p_max) == NULL);
_GLIBCXX_DEBUG_ASSERT(m_p_max->m_p_prev_or_parent == NULL);
for (const_iterator it = base_type::begin(); it != base_type::end(); ++it)
_GLIBCXX_DEBUG_ASSERT(!Cmp_Fn::operator()(m_p_max->m_value, it.m_p_nd->m_value));
}
 
PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
assert_node_consistent(const_node_pointer p_nd, bool root) const
{
base_type::assert_node_consistent(p_nd, root);
if (p_nd == NULL)
return;
 
assert_node_consistent(p_nd->m_p_next_sibling, root);
assert_node_consistent(p_nd->m_p_l_child, false);
if (!root)
{
if (p_nd->m_metadata == 0)
_GLIBCXX_DEBUG_ASSERT(p_nd->m_p_next_sibling == NULL);
else
_GLIBCXX_DEBUG_ASSERT(p_nd->m_metadata == p_nd->m_p_next_sibling->m_metadata + 1);
}
 
if (p_nd->m_p_l_child != NULL)
_GLIBCXX_DEBUG_ASSERT(p_nd->m_p_l_child->m_metadata + 1 == base_type::degree(p_nd));
 
const bool unmarked_valid =(p_nd->m_p_l_child == NULL&& p_nd->m_metadata == 0) ||(p_nd->m_p_l_child != NULL&& p_nd->m_metadata == p_nd->m_p_l_child->m_metadata + 1);
 
const bool marked_valid =(p_nd->m_p_l_child == NULL&& p_nd->m_metadata == 1) ||(p_nd->m_p_l_child != NULL&& p_nd->m_metadata == p_nd->m_p_l_child->m_metadata + 2);
 
_GLIBCXX_DEBUG_ASSERT(unmarked_valid || marked_valid);
if (root)
_GLIBCXX_DEBUG_ASSERT(unmarked_valid);
}
 
#endif
/split_join_fn_imps.hpp
0,0 → 1,126
// -*- C++ -*-
 
// Copyright (C) 2005, 2006, 2009 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library. This library is free
// software; you can redistribute it and/or modify it under the terms
// of the GNU General Public License as published by the Free Software
// Foundation; either version 3, or (at your option) any later
// version.
 
// This library is distributed in the hope that it will be useful, but
// WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
// General Public License for more details.
 
// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.
 
// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
// <http://www.gnu.org/licenses/>.
 
// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
 
// Permission to use, copy, modify, sell, and distribute this software
// is hereby granted without fee, provided that the above copyright
// notice appears in all copies, and that both that copyright notice
// and this permission notice appear in supporting documentation. None
// of the above authors, nor IBM Haifa Research Laboratories, make any
// representation about the suitability of this software for any
// purpose. It is provided "as is" without express or implied
// warranty.
 
/**
* @file split_join_fn_imps.hpp
* Contains an implementation for thin_heap_.
*/
 
PB_DS_CLASS_T_DEC
template<typename Pred>
void
PB_DS_CLASS_C_DEC::
split(Pred pred, PB_DS_CLASS_C_DEC& other)
{
_GLIBCXX_DEBUG_ONLY(assert_valid();)
_GLIBCXX_DEBUG_ONLY(other.assert_valid();)
 
other.clear();
 
if (base_type::empty())
{
_GLIBCXX_DEBUG_ONLY(assert_valid();)
_GLIBCXX_DEBUG_ONLY(other.assert_valid();)
 
return;
}
 
base_type::to_linked_list();
 
node_pointer p_out = base_type::prune(pred);
 
while (p_out != NULL)
{
_GLIBCXX_DEBUG_ASSERT(base_type::m_size > 0);
--base_type::m_size;
 
++other.m_size;
 
node_pointer p_next = p_out->m_p_next_sibling;
 
other.make_root_and_link(p_out);
 
p_out = p_next;
}
 
_GLIBCXX_DEBUG_ONLY(other.assert_valid();)
 
node_pointer p_cur = base_type::m_p_root;
 
m_p_max = NULL;
 
base_type::m_p_root = NULL;
 
while (p_cur != NULL)
{
node_pointer p_next = p_cur->m_p_next_sibling;
 
make_root_and_link(p_cur);
 
p_cur = p_next;
}
 
_GLIBCXX_DEBUG_ONLY(assert_valid();)
_GLIBCXX_DEBUG_ONLY(other.assert_valid();)
}
 
PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
join(PB_DS_CLASS_C_DEC& other)
{
_GLIBCXX_DEBUG_ONLY(assert_valid();)
_GLIBCXX_DEBUG_ONLY(other.assert_valid();)
 
node_pointer p_other = other.m_p_root;
 
while (p_other != NULL)
{
node_pointer p_next = p_other->m_p_next_sibling;
 
make_root_and_link(p_other);
 
p_other = p_next;
}
 
base_type::m_size += other.m_size;
 
other.m_p_root = NULL;
other.m_size = 0;
other.m_p_max = NULL;
 
_GLIBCXX_DEBUG_ONLY(assert_valid();)
_GLIBCXX_DEBUG_ONLY(other.assert_valid();)
}

powered by: WebSVN 2.1.0

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