40#ifndef GCC_FIBONACCI_HEAP_H
41#define GCC_FIBONACCI_HEAP_H
45template<
class K,
class V>
50template<
class K,
class V>
127#if defined (__GNUC__) && (!defined (SIZEOF_INT) || SIZEOF_INT < 4)
129 __extension__
unsigned long int m_degree : 31;
131 __extension__
unsigned long int m_mark : 1;
141template<
class K,
class V>
172 n->~fibonacci_node_t ();
207 K okey = node->
m_key;
290template<
class K,
class V>
316template<
class K,
class V>
331template<
class K,
class V>
346 b->m_right =
a->m_right;
347 a->m_right->m_left =
b;
355template<
class K,
class V>
363 return insert_node (node);
368template<
class K,
class V>
376 return insert_node (node);
381template<
class K,
class V>
390 if (m_min ==
NULL || node->
m_key < m_min->m_key)
400template<
class K,
class V>
413 delete_node (node,
false);
429 if (okey == key && okey != m_global_min_key)
441 if (node->
compare (m_min) <= 0)
450template<
class K,
class V>
462 z = extract_minimum_node ();
467 z->~fibonacci_node_t ();
477template<
class K,
class V>
484 replace_key (node, m_global_min_key);
487 fprintf (stderr,
"Can't force minimum on fibheap.\n");
490 extract_min (release);
497template<
class K,
class V>
539template<
class K,
class V>
555 m_root->insert_after (node);
560template<
class K,
class V>
574template<
class K,
class V>
597template<
class K,
class V>
635template<
class K,
class V>
647template<
class K,
class V>
650 const int D = 1 + 8 *
sizeof (long);
655 memset (
a, 0,
sizeof (
a));
657 while ((w = m_root) !=
NULL)
675 for (
i = 0;
i < D;
i++)
base_pool_allocator< memory_block_pool > pool_allocator
Definition alloc-pool.h:477
void remove(void *object)
Definition alloc-pool.h:430
Definition genoutput.cc:150
Definition fibonacci_heap.h:143
size_t nodes() const
Definition fibonacci_heap.h:190
size_t m_nodes
Definition fibonacci_heap.h:274
fibonacci_heap * union_with(fibonacci_heap *heapb)
Definition fibonacci_heap.h:499
void insert_root(fibonacci_node_t *node)
Definition fibonacci_heap.h:541
void cut(fibonacci_node_t *node, fibonacci_node_t *parent)
Definition fibonacci_heap.h:562
void remove_root(fibonacci_node_t *node)
Definition fibonacci_heap.h:637
V * min() const
Definition fibonacci_heap.h:228
fibonacci_node< K, V > fibonacci_node_t
Definition fibonacci_heap.h:144
V * replace_data(fibonacci_node_t *node, V *data)
Definition fibonacci_heap.h:237
V * delete_node(fibonacci_node_t *node, bool release=true)
Definition fibonacci_heap.h:479
fibonacci_node_t * m_root
Definition fibonacci_heap.h:278
fibonacci_node_t * insert_node(fibonacci_node_t *node)
Definition fibonacci_heap.h:383
~fibonacci_heap()
Definition fibonacci_heap.h:165
void consolidate()
Definition fibonacci_heap.h:648
pool_allocator * m_allocator
Definition fibonacci_heap.h:283
fibonacci_node_t * insert(fibonacci_node_t *node, K key, V *data)
Definition fibonacci_heap.h:370
V * extract_min(bool release=true)
Definition fibonacci_heap.h:452
K decrease_key(fibonacci_node_t *node, K key)
Definition fibonacci_heap.h:214
bool empty() const
Definition fibonacci_heap.h:184
fibonacci_node_t * m_min
Definition fibonacci_heap.h:276
V * replace_key_data(fibonacci_node_t *node, K key, V *data)
Definition fibonacci_heap.h:402
K m_global_min_key
Definition fibonacci_heap.h:280
bool m_own_allocator
Definition fibonacci_heap.h:285
K min_key() const
Definition fibonacci_heap.h:196
void cascading_cut(fibonacci_node_t *y)
Definition fibonacci_heap.h:576
fibonacci_node_t * extract_minimum_node()
Definition fibonacci_heap.h:599
fibonacci_heap(K global_min_key, pool_allocator *allocator=NULL)
Definition fibonacci_heap.h:151
fibonacci_node_t * insert(K key, V *data)
Definition fibonacci_heap.h:357
K replace_key(fibonacci_node_t *node, K key)
Definition fibonacci_heap.h:205
Definition fibonacci_heap.h:52
fibonacci_node * m_parent
Definition fibonacci_heap.h:115
fibonacci_node * m_left
Definition fibonacci_heap.h:119
fibonacci_node * m_child
Definition fibonacci_heap.h:117
fibonacci_node(K key, V *data=NULL)
Definition fibonacci_heap.h:64
fibonacci_node * m_right
Definition fibonacci_heap.h:121
fibonacci_node()
Definition fibonacci_heap.h:58
void link(fibonacci_node_t *parent)
Definition fibonacci_heap.h:318
K get_key()
Definition fibonacci_heap.h:93
int compare_data(K key)
Definition fibonacci_heap.h:81
V * m_data
Definition fibonacci_heap.h:125
void insert_before(fibonacci_node_t *b)
Definition fibonacci_heap.h:109
unsigned int m_mark
Definition fibonacci_heap.h:136
unsigned int m_degree
Definition fibonacci_heap.h:134
V * get_data()
Definition fibonacci_heap.h:99
fibonacci_node_t * remove()
Definition fibonacci_heap.h:292
K m_key
Definition fibonacci_heap.h:123
void insert_after(fibonacci_node_t *b)
Definition fibonacci_heap.h:333
int compare(fibonacci_node_t *other)
Definition fibonacci_heap.h:71
fibonacci_node< K, V > fibonacci_node_t
Definition fibonacci_heap.h:53
static struct operand_data * odata
Definition genoutput.cc:136
bool need_finalization_p()
Definition ggc.h:173
i
Definition poly-int.h:776
Ca const poly_int< N, Cb > & b
Definition poly-int.h:771
Ca & a
Definition poly-int.h:770
#define NULL
Definition system.h:50
#define gcc_assert(EXPR)
Definition system.h:821
#define gcc_unreachable()
Definition system.h:848
#define false
Definition system.h:895
#define abort()
Definition system.h:810
#define gcc_checking_assert(EXPR)
Definition system.h:828
static void insert(void)
Definition tree-ssa-pre.cc:3804
const T2 & y
Definition wide-int.h:3870