diff options
| -rw-r--r-- | gcc/ChangeLog | 12 | ||||
| -rw-r--r-- | gcc/bb-reorder.c | 4 | ||||
| -rw-r--r-- | gcc/fibonacci_heap.h | 60 |
3 files changed, 57 insertions, 19 deletions
diff --git a/gcc/ChangeLog b/gcc/ChangeLog index d950750..8f42d09 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,15 @@ +2014-11-24 Martin Liska <mliska@suse.cz> + + 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. + 2014-11-24 Richard Biener <rguenther@suse.de> PR tree-optimization/55334 diff --git a/gcc/bb-reorder.c b/gcc/bb-reorder.c index 689d7b6..b568114 100644 --- a/gcc/bb-reorder.c +++ b/gcc/bb-reorder.c @@ -644,7 +644,7 @@ find_traces_1_round (int branch_th, int exec_th, gcov_type count_th, (long) bbd[e->dest->index].node->get_key (), key); } - bbd[e->dest->index].heap->decrease_key + bbd[e->dest->index].heap->replace_key (bbd[e->dest->index].node, key); } } @@ -812,7 +812,7 @@ find_traces_1_round (int branch_th, int exec_th, gcov_type count_th, e->dest->index, (long) bbd[e->dest->index].node->get_key (), key); } - bbd[e->dest->index].heap->decrease_key + bbd[e->dest->index].heap->replace_key (bbd[e->dest->index].node, key); } } diff --git a/gcc/fibonacci_heap.h b/gcc/fibonacci_heap.h index ecb92f8..3fce370 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; } |