-/* Vector API for GNU compiler.
- Copyright (C) 1998-2015 Free Software Foundation, Inc.
+/* Fibonacci heap for GNU compiler.
+ Copyright (C) 1998-2024 Free Software Foundation, Inc.
Contributed by Daniel Berlin (dan@cgsoftware.com).
Re-implemented in C++ by Martin Liska <mliska@suse.cz>
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)
{
}
/* Constructor for a node with given KEY. */
- fibonacci_node (K key): m_parent (NULL), m_child (NULL), m_left (this),
- m_right (this), m_key (key),
+ fibonacci_node (K key, V *data = NULL): m_parent (NULL), m_child (NULL),
+ m_left (this), m_right (this), m_key (key), m_data (data),
m_degree (0), m_mark (0)
{
}
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 ();
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;
/* 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 new NODE that has already filled key and value. */
+ fibonacci_node_t *insert_node (fibonacci_node_t *node);
+
/* Insert it into the root list. */
void insert_root (fibonacci_node_t *node);
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. */
fibonacci_heap<K,V>::insert (K key, V *data)
{
/* Create the new node. */
- fibonacci_node<K,V> *node = new fibonacci_node_t ();
+ fibonacci_node<K,V> *node = new (m_allocator->allocate ())
+ fibonacci_node_t (key, data);
- return insert (node, key, data);
+ return insert_node (node);
}
-/* Insert new NODE given by KEY and DATA associated with the key. */
+/* Insert new NODE given by DATA associated with the key. */
template<class K, class V>
fibonacci_node<K,V>*
node->m_data = data;
node->m_key = key;
+ return insert_node (node);
+}
+
+/* Insert new NODE that has already filled key and value. */
+
+template<class K, class V>
+fibonacci_node<K,V>*
+fibonacci_heap<K,V>::insert_node (fibonacci_node_t *node)
+{
/* Insert it into the root list. */
insert_root (node);
}
/* For given NODE, set new KEY and DATA value. */
+
template<class K, class V>
V*
fibonacci_heap<K,V>::replace_key_data (fibonacci_node<K,V> *node, K key,
return odata;
}
-/* Extract minimum node in the heap. */
+/* Extract minimum node in the heap. Delete fibonacci node if RELEASE
+ is true. */
+
template<class K, class V>
V*
fibonacci_heap<K,V>::extract_min (bool release)
ret = z->m_data;
if (release)
- delete (z);
+ {
+ z->~fibonacci_node_t ();
+ m_allocator->remove (z);
+ }
}
return ret;
return ret;
}
-/* Union the heap with HEAPB. */
+/* Union the heap with HEAPB. One of the heaps is going to be deleted. */
template<class K, class V>
fibonacci_heap<K,V>*
{
fibonacci_heap<K,V> *heapa = this;
- fibonacci_node<K,V> *a_root, *b_root, *temp;
+ 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)
/* Merge them to the next nodes on the opposite chain. */
a_root->m_left->m_right = b_root;
b_root->m_left->m_right = a_root;
- temp = a_root->m_left;
- a_root->m_left = b_root->m_left;
- b_root->m_left = temp;
+ std::swap (a_root->m_left, b_root->m_left);
heapa->m_nodes += heapb->m_nodes;
/* And set the new minimum, if it's changed. */
- if (heapb->min->compare (heapa->min) < 0)
+ if (heapb->m_min->compare (heapa->m_min) < 0)
heapa->m_min = heapb->m_min;
+ /* Set m_min to NULL to not to delete live fibonacci nodes. */
+ heapb->m_min = NULL;
delete (heapb);
+
return heapa;
}
}
/* Extract minimum node from the heap. */
+
template<class K, class V>
fibonacci_node<K,V>*
fibonacci_heap<K,V>::extract_minimum_node ()
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];
projects / thirdparty / gcc.git / blobdiff