Mercurial > hg > CbC > CbC_gcc
diff gcc/fibonacci_heap.h @ 145:1830386684a0
gcc-9.2.0
author | anatofuz |
---|---|
date | Thu, 13 Feb 2020 11:34:05 +0900 |
parents | 84e7813d76e9 |
children |
line wrap: on
line diff
--- a/gcc/fibonacci_heap.h Thu Oct 25 07:37:49 2018 +0900 +++ b/gcc/fibonacci_heap.h Thu Feb 13 11:34:05 2020 +0900 @@ -1,5 +1,5 @@ /* Fibonacci heap for GNU compiler. - Copyright (C) 1998-2018 Free Software Foundation, Inc. + Copyright (C) 1998-2020 Free Software Foundation, Inc. Contributed by Daniel Berlin (dan@cgsoftware.com). Re-implemented in C++ by Martin Liska <mliska@suse.cz> @@ -56,7 +56,7 @@ public: /* Default constructor. */ fibonacci_node (): m_parent (NULL), m_child (NULL), m_left (this), - m_right (this), m_degree (0), m_mark (0) + m_right (this), m_data (NULL), m_degree (0), m_mark (0) { } @@ -145,36 +145,55 @@ friend class fibonacci_node<K,V>; public: - /* Default constructor. */ - fibonacci_heap (K global_min_key): m_nodes (0), m_min (NULL), m_root (NULL), - m_global_min_key (global_min_key) + /* Default constructor. ALLOCATOR is optional and is primarily useful + when heaps are going to be merged (in that case they need to be allocated + in same alloc pool). */ + fibonacci_heap (K global_min_key, pool_allocator *allocator = NULL): + m_nodes (0), m_min (NULL), m_root (NULL), + m_global_min_key (global_min_key), + m_allocator (allocator), m_own_allocator (false) { + if (!m_allocator) + { + m_allocator = new pool_allocator ("Fibonacci heap", + sizeof (fibonacci_node_t)); + m_own_allocator = true; + } } /* Destructor. */ ~fibonacci_heap () { - while (m_min != NULL) - delete (extract_minimum_node ()); + /* Actual memory will be released by the destructor of m_allocator. */ + if (need_finalization_p<fibonacci_node_t> () || !m_own_allocator) + while (m_min != NULL) + { + fibonacci_node_t *n = extract_minimum_node (); + n->~fibonacci_node_t (); + if (!m_own_allocator) + m_allocator->remove (n); + } + if (m_own_allocator) + delete m_allocator; } /* Insert new node given by KEY and DATA associated with the key. */ fibonacci_node_t *insert (K key, V *data); /* Return true if no entry is present. */ - bool empty () + bool empty () const { return m_nodes == 0; } /* Return the number of nodes. */ - size_t nodes () + size_t nodes () const { return m_nodes; } /* Return minimal key presented in the heap. */ - K min_key () + K min_key () const { if (m_min == NULL) gcc_unreachable (); @@ -206,7 +225,7 @@ V *extract_min (bool release = true); /* Return value associated with minimum node in the heap. */ - V *min () + V *min () const { if (m_min == NULL) return NULL; @@ -259,6 +278,11 @@ fibonacci_node_t *m_root; /* Global minimum given in the heap construction. */ K m_global_min_key; + + /* Allocator used to hold nodes. */ + pool_allocator *m_allocator; + /* True if alocator is owned by the current heap only. */ + bool m_own_allocator; }; /* Remove fibonacci heap node. */ @@ -333,7 +357,8 @@ fibonacci_heap<K,V>::insert (K key, V *data) { /* Create the new node. */ - fibonacci_node<K,V> *node = new fibonacci_node_t (key, data); + fibonacci_node<K,V> *node = new (m_allocator->allocate ()) + fibonacci_node_t (key, data); return insert_node (node); } @@ -438,7 +463,10 @@ ret = z->m_data; if (release) - delete (z); + { + z->~fibonacci_node_t (); + m_allocator->remove (z); + } } return ret; @@ -474,6 +502,9 @@ fibonacci_node<K,V> *a_root, *b_root; + /* Both heaps must share allocator. */ + gcc_checking_assert (m_allocator == heapb->m_allocator); + /* If one of the heaps is empty, the union is just the other heap. */ if ((a_root = heapa->m_root) == NULL) { @@ -616,17 +647,19 @@ template<class K, class V> void fibonacci_heap<K,V>::consolidate () { - int D = 1 + 8 * sizeof (long); - auto_vec<fibonacci_node<K,V> *> a (D); - a.safe_grow_cleared (D); + const int D = 1 + 8 * sizeof (long); + fibonacci_node<K,V> *a[D]; fibonacci_node<K,V> *w, *x, *y; int i, d; + memset (a, 0, sizeof (a)); + while ((w = m_root) != NULL) { x = w; remove_root (w); d = x->m_degree; + gcc_checking_assert (d < D); while (a[d] != NULL) { y = a[d];