Mercurial > hg > CbC > CbC_gcc

comparison gcc/fibonacci_heap.h @ 145:1830386684a0

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
gcc-9.2.0
author anatofuz
date Thu, 13 Feb 2020 11:34:05 +0900
parents 84e7813d76e9
children
comparison
equal deleted inserted replaced
131:84e7813d76e9 145:1830386684a0
1 /* Fibonacci heap for GNU compiler. 1 /* Fibonacci heap for GNU compiler.
2 Copyright (C) 1998-2018 Free Software Foundation, Inc. 2 Copyright (C) 1998-2020 Free Software Foundation, Inc.
3 Contributed by Daniel Berlin (dan@cgsoftware.com). 3 Contributed by Daniel Berlin (dan@cgsoftware.com).
4 Re-implemented in C++ by Martin Liska <mliska@suse.cz> 4 Re-implemented in C++ by Martin Liska <mliska@suse.cz>
5 5
6 This file is part of GCC. 6 This file is part of GCC.
7 7
54 friend class fibonacci_heap<K,V>; 54 friend class fibonacci_heap<K,V>;
55 55
56 public: 56 public:
57 /* Default constructor. */ 57 /* Default constructor. */
58 fibonacci_node (): m_parent (NULL), m_child (NULL), m_left (this), 58 fibonacci_node (): m_parent (NULL), m_child (NULL), m_left (this),
59 m_right (this), m_degree (0), m_mark (0) 59 m_right (this), m_data (NULL), m_degree (0), m_mark (0)
60 { 60 {
61 } 61 }
62 62
63 /* Constructor for a node with given KEY. */ 63 /* Constructor for a node with given KEY. */
64 fibonacci_node (K key, V *data = NULL): m_parent (NULL), m_child (NULL), 64 fibonacci_node (K key, V *data = NULL): m_parent (NULL), m_child (NULL),
143 { 143 {
144 typedef fibonacci_node<K,V> fibonacci_node_t; 144 typedef fibonacci_node<K,V> fibonacci_node_t;
145 friend class fibonacci_node<K,V>; 145 friend class fibonacci_node<K,V>;
146 146
147 public: 147 public:
148 /* Default constructor. */ 148 /* Default constructor. ALLOCATOR is optional and is primarily useful
149 fibonacci_heap (K global_min_key): m_nodes (0), m_min (NULL), m_root (NULL), 149 when heaps are going to be merged (in that case they need to be allocated
150 m_global_min_key (global_min_key) 150 in same alloc pool). */
151 { 151 fibonacci_heap (K global_min_key, pool_allocator *allocator = NULL):
152 m_nodes (0), m_min (NULL), m_root (NULL),
153 m_global_min_key (global_min_key),
154 m_allocator (allocator), m_own_allocator (false)
155 {
156 if (!m_allocator)
157 {
158 m_allocator = new pool_allocator ("Fibonacci heap",
159 sizeof (fibonacci_node_t));
160 m_own_allocator = true;
161 }
152 } 162 }
153 163
154 /* Destructor. */ 164 /* Destructor. */
155 ~fibonacci_heap () 165 ~fibonacci_heap ()
156 { 166 {
157 while (m_min != NULL) 167 /* Actual memory will be released by the destructor of m_allocator. */
158 delete (extract_minimum_node ()); 168 if (need_finalization_p<fibonacci_node_t> () || !m_own_allocator)
169 while (m_min != NULL)
170 {
171 fibonacci_node_t *n = extract_minimum_node ();
172 n->~fibonacci_node_t ();
173 if (!m_own_allocator)
174 m_allocator->remove (n);
175 }
176 if (m_own_allocator)
177 delete m_allocator;
159 } 178 }
160 179
161 /* Insert new node given by KEY and DATA associated with the key. */ 180 /* Insert new node given by KEY and DATA associated with the key. */
162 fibonacci_node_t *insert (K key, V *data); 181 fibonacci_node_t *insert (K key, V *data);
163 182
164 /* Return true if no entry is present. */ 183 /* Return true if no entry is present. */
165 bool empty () 184 bool empty () const
166 { 185 {
167 return m_nodes == 0; 186 return m_nodes == 0;
168 } 187 }
169 188
170 /* Return the number of nodes. */ 189 /* Return the number of nodes. */
171 size_t nodes () 190 size_t nodes () const
172 { 191 {
173 return m_nodes; 192 return m_nodes;
174 } 193 }
175 194
176 /* Return minimal key presented in the heap. */ 195 /* Return minimal key presented in the heap. */
177 K min_key () 196 K min_key () const
178 { 197 {
179 if (m_min == NULL) 198 if (m_min == NULL)
180 gcc_unreachable (); 199 gcc_unreachable ();
181 200
182 return m_min->m_key; 201 return m_min->m_key;
204 /* Extract minimum node in the heap. If RELEASE is specified, 223 /* Extract minimum node in the heap. If RELEASE is specified,
205 memory is released. */ 224 memory is released. */
206 V *extract_min (bool release = true); 225 V *extract_min (bool release = true);
207 226
208 /* Return value associated with minimum node in the heap. */ 227 /* Return value associated with minimum node in the heap. */
209 V *min () 228 V *min () const
210 { 229 {
211 if (m_min == NULL) 230 if (m_min == NULL)
212 return NULL; 231 return NULL;
213 232
214 return m_min->m_data; 233 return m_min->m_data;
257 fibonacci_node_t *m_min; 276 fibonacci_node_t *m_min;
258 /* Root node of the heap. */ 277 /* Root node of the heap. */
259 fibonacci_node_t *m_root; 278 fibonacci_node_t *m_root;
260 /* Global minimum given in the heap construction. */ 279 /* Global minimum given in the heap construction. */
261 K m_global_min_key; 280 K m_global_min_key;
281
282 /* Allocator used to hold nodes. */
283 pool_allocator *m_allocator;
284 /* True if alocator is owned by the current heap only. */
285 bool m_own_allocator;
262 }; 286 };
263 287
264 /* Remove fibonacci heap node. */ 288 /* Remove fibonacci heap node. */
265 289
266 template<class K, class V> 290 template<class K, class V>
331 template<class K, class V> 355 template<class K, class V>
332 fibonacci_node<K,V>* 356 fibonacci_node<K,V>*
333 fibonacci_heap<K,V>::insert (K key, V *data) 357 fibonacci_heap<K,V>::insert (K key, V *data)
334 { 358 {
335 /* Create the new node. */ 359 /* Create the new node. */
336 fibonacci_node<K,V> *node = new fibonacci_node_t (key, data); 360 fibonacci_node<K,V> *node = new (m_allocator->allocate ())
361 fibonacci_node_t (key, data);
337 362
338 return insert_node (node); 363 return insert_node (node);
339 } 364 }
340 365
341 /* Insert new NODE given by DATA associated with the key. */ 366 /* Insert new NODE given by DATA associated with the key. */
436 node's data. */ 461 node's data. */
437 z = extract_minimum_node (); 462 z = extract_minimum_node ();
438 ret = z->m_data; 463 ret = z->m_data;
439 464
440 if (release) 465 if (release)
441 delete (z); 466 {
467 z->~fibonacci_node_t ();
468 m_allocator->remove (z);
469 }
442 } 470 }
443 471
444 return ret; 472 return ret;
445 } 473 }
446 474
471 fibonacci_heap<K,V>::union_with (fibonacci_heap<K,V> *heapb) 499 fibonacci_heap<K,V>::union_with (fibonacci_heap<K,V> *heapb)
472 { 500 {
473 fibonacci_heap<K,V> *heapa = this; 501 fibonacci_heap<K,V> *heapa = this;
474 502
475 fibonacci_node<K,V> *a_root, *b_root; 503 fibonacci_node<K,V> *a_root, *b_root;
504
505 /* Both heaps must share allocator. */
506 gcc_checking_assert (m_allocator == heapb->m_allocator);
476 507
477 /* If one of the heaps is empty, the union is just the other heap. */ 508 /* If one of the heaps is empty, the union is just the other heap. */
478 if ((a_root = heapa->m_root) == NULL) 509 if ((a_root = heapa->m_root) == NULL)
479 { 510 {
480 delete (heapa); 511 delete (heapa);
614 /* Consolidate heap. */ 645 /* Consolidate heap. */
615 646
616 template<class K, class V> 647 template<class K, class V>
617 void fibonacci_heap<K,V>::consolidate () 648 void fibonacci_heap<K,V>::consolidate ()
618 { 649 {
619 int D = 1 + 8 * sizeof (long); 650 const int D = 1 + 8 * sizeof (long);
620 auto_vec<fibonacci_node<K,V> *> a (D); 651 fibonacci_node<K,V> *a[D];
621 a.safe_grow_cleared (D);
622 fibonacci_node<K,V> *w, *x, *y; 652 fibonacci_node<K,V> *w, *x, *y;
623 int i, d; 653 int i, d;
654
655 memset (a, 0, sizeof (a));
624 656
625 while ((w = m_root) != NULL) 657 while ((w = m_root) != NULL)
626 { 658 {
627 x = w; 659 x = w;
628 remove_root (w); 660 remove_root (w);
629 d = x->m_degree; 661 d = x->m_degree;
662 gcc_checking_assert (d < D);
630 while (a[d] != NULL) 663 while (a[d] != NULL)
631 { 664 {
632 y = a[d]; 665 y = a[d];
633 if (x->compare (y) > 0) 666 if (x->compare (y) > 0)
634 std::swap (x, y); 667 std::swap (x, y);