diff options
author | Martin Liska <mliska@suse.cz> | 2014-11-24 11:25:06 +0100 |
---|---|---|
committer | Martin Liska <marxin@gcc.gnu.org> | 2014-11-24 10:25:06 +0000 |
commit | a3dc1a4518793aa75cd60e41cf7f75d234a55031 (patch) | |
tree | 63b196c61b62633c876f3299249b61d50acf905c /gcc/fibonacci_heap.h | |
parent | aa098165777d11e3c8bb39936339e9a54d7d6f12 (diff) | |
download | gcc-a3dc1a4518793aa75cd60e41cf7f75d234a55031.tar.gz |
re PR lto/63968 (175.vpr from cpu2000 fails to build with LTO)
PR lto/63968
* bb-reorder.c (find_traces_1_round): decreate_key is replaced
with replace_key method.
* fibonacci_heap.h (fibonacci_heap::insert): New argument.
(fibonacci_heap::replace_key_data): Likewise.
(fibonacci_heap::replace_key): New method that can even increment key,
this operation costs O(log N).
(fibonacci_heap::extract_min): New argument.
(fibonacci_heap::delete_node): Likewise.
From-SVN: r218006
Diffstat (limited to 'gcc/fibonacci_heap.h')
-rw-r--r-- | gcc/fibonacci_heap.h | 60 |
1 files changed, 43 insertions, 17 deletions
diff --git a/gcc/fibonacci_heap.h b/gcc/fibonacci_heap.h index ecb92f8b01f..3fce3701737 100644 --- a/gcc/fibonacci_heap.h +++ b/gcc/fibonacci_heap.h @@ -183,20 +183,27 @@ public: } /* For given NODE, set new KEY value. */ - K decrease_key (fibonacci_node_t *node, K key) + K replace_key (fibonacci_node_t *node, K key) { K okey = node->m_key; - gcc_assert (key <= okey); replace_key_data (node, key, node->m_data); return okey; } + /* For given NODE, decrease value to new KEY. */ + K decrease_key (fibonacci_node_t *node, K key) + { + gcc_assert (key <= node->m_key); + return replace_key (node, key); + } + /* For given NODE, set new KEY and DATA value. */ V *replace_key_data (fibonacci_node_t *node, K key, V *data); - /* Extract minimum node in the heap. */ - V *extract_min (); + /* Extract minimum node in the heap. If RELEASE is specified, + memory is released. */ + V *extract_min (bool release = true); /* Return value associated with minimum node in the heap. */ V *min () @@ -214,12 +221,15 @@ public: } /* Delete NODE in the heap. */ - V *delete_node (fibonacci_node_t *node); + V *delete_node (fibonacci_node_t *node, bool release = true); /* Union the heap with HEAPB. */ fibonacci_heap *union_with (fibonacci_heap *heapb); private: + /* Insert new NODE given by KEY and DATA associated with the key. */ + fibonacci_node_t *insert (fibonacci_node_t *node, K key, V *data); + /* Insert it into the root list. */ void insert_root (fibonacci_node_t *node); @@ -322,6 +332,15 @@ fibonacci_heap<K,V>::insert (K key, V *data) /* Create the new node. */ fibonacci_node<K,V> *node = new fibonacci_node_t (); + return insert (node, key, data); +} + +/* Insert new NODE given by KEY and DATA associated with the key. */ + +template<class K, class V> +fibonacci_node<K,V>* +fibonacci_heap<K,V>::insert (fibonacci_node_t *node, K key, V *data) +{ /* Set the node's data. */ node->m_data = data; node->m_key = key; @@ -345,17 +364,22 @@ V* fibonacci_heap<K,V>::replace_key_data (fibonacci_node<K,V> *node, K key, V *data) { - V *odata; K okey; fibonacci_node<K,V> *y; + V *odata = node->m_data; - /* If we wanted to, we could actually do a real increase by redeleting and - inserting. However, this would require O (log n) time. So just bail out - for now. */ + /* If we wanted to, we do a real increase by redeleting and + inserting. */ if (node->compare_data (key) > 0) - return NULL; + { + delete_node (node, false); + + node = new (node) fibonacci_node_t (); + insert (node, key, data); + + return odata; + } - odata = node->m_data; okey = node->m_key; node->m_data = data; node->m_key = key; @@ -385,7 +409,7 @@ fibonacci_heap<K,V>::replace_key_data (fibonacci_node<K,V> *node, K key, /* Extract minimum node in the heap. */ template<class K, class V> V* -fibonacci_heap<K,V>::extract_min () +fibonacci_heap<K,V>::extract_min (bool release) { fibonacci_node<K,V> *z; V *ret = NULL; @@ -397,28 +421,30 @@ fibonacci_heap<K,V>::extract_min () node's data. */ z = extract_minimum_node (); ret = z->m_data; - delete (z); + + if (release) + delete (z); } return ret; } -/* Delete NODE in the heap. */ +/* Delete NODE in the heap, if RELEASE is specified memory is released. */ template<class K, class V> V* -fibonacci_heap<K,V>::delete_node (fibonacci_node<K,V> *node) +fibonacci_heap<K,V>::delete_node (fibonacci_node<K,V> *node, bool release) { V *ret = node->m_data; /* To perform delete, we just make it the min key, and extract. */ - decrease_key (node, m_global_min_key); + replace_key (node, m_global_min_key); if (node != m_min) { fprintf (stderr, "Can't force minimum on fibheap.\n"); abort (); } - extract_min (); + extract_min (release); return ret; } |