1 /* A Fibonacci heap datatype.
2 Copyright 1998, 1999, 2000, 2001 Free Software Foundation, Inc.
3 Contributed by Daniel Berlin (dan@cgsoftware.com).
5 This file is part of GNU CC.
7 GNU CC is free software; you can redistribute it and/or modify it
8 under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2, or (at your option)
12 GNU CC is distributed in the hope that it will be useful, but
13 WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GNU CC; see the file COPYING. If not, write to
19 the Free Software Foundation, 59 Temple Place - Suite 330,
20 Boston, MA 02111-1307, USA. */
34 #include "libiberty.h"
38 #define FIBHEAPKEY_MIN LONG_MIN
40 static void fibheap_init
PARAMS ((fibheap_t
));
41 static void fibheap_ins_root
PARAMS ((fibheap_t
, fibnode_t
));
42 static void fibheap_rem_root
PARAMS ((fibheap_t
, fibnode_t
));
43 static void fibheap_consolidate
PARAMS ((fibheap_t
));
44 static void fibheap_link
PARAMS ((fibheap_t
, fibnode_t
, fibnode_t
));
45 static void fibheap_cut
PARAMS ((fibheap_t
, fibnode_t
, fibnode_t
));
46 static void fibheap_cascading_cut
PARAMS ((fibheap_t
, fibnode_t
));
47 static fibnode_t fibheap_extr_min_node
PARAMS ((fibheap_t
));
48 static int fibheap_compare
PARAMS ((fibheap_t
, fibnode_t
, fibnode_t
));
49 static int fibheap_comp_data
PARAMS ((fibheap_t
, fibheapkey_t
, void *,
51 static fibnode_t fibnode_new
PARAMS ((void));
52 static void fibnode_init
PARAMS ((fibnode_t
));
53 static void fibnode_insert_after
PARAMS ((fibnode_t
, fibnode_t
));
54 #define fibnode_insert_before(a, b) fibnode_insert_after (a->left, b)
55 static fibnode_t fibnode_remove
PARAMS ((fibnode_t
));
58 /* Initialize the passed in fibonacci heap. */
68 /* Create a new fibonacci heap. */
74 if ((result
= xmalloc (sizeof (*result
))) == NULL
)
77 fibheap_init (result
);
82 /* Initialize the passed in fibonacci heap node. */
96 /* Create a new fibonacci heap node. */
97 static inline fibnode_t
102 if ((e
= xmalloc (sizeof *e
)) == NULL
)
111 fibheap_compare (heap
, a
, b
)
112 fibheap_t heap ATTRIBUTE_UNUSED
;
124 fibheap_comp_data (heap
, key
, data
, b
)
135 return fibheap_compare (heap
, &a
, b
);
138 /* Insert DATA, with priority KEY, into HEAP. */
140 fibheap_insert (heap
, key
, data
)
147 /* Create the new node, if we fail, return NULL. */
148 if ((node
= fibnode_new ()) == NULL
)
151 /* Set the node's data. */
155 /* Insert it into the root list. */
156 fibheap_ins_root (heap
, node
);
158 /* If their was no minimum, or this key is less than the min,
160 if (heap
->min
== NULL
|| node
->key
< heap
->min
->key
)
168 /* Return the data of the minimum node (if we know it). */
173 /* If there is no min, we can't easily return it. */
174 if (heap
->min
== NULL
)
176 return heap
->min
->data
;
179 /* Return the key of the minimum node (if we know it). */
181 fibheap_min_key (heap
)
184 /* If there is no min, we can't easily return it. */
185 if (heap
->min
== NULL
)
187 return heap
->min
->key
;
190 /* Union HEAPA and HEAPB into a new heap. */
192 fibheap_union (heapa
, heapb
)
196 fibnode_t a_root
, b_root
, temp
;
198 /* If one of the heaps is empty, the union is just the other heap. */
199 if ((a_root
= heapa
->root
) == NULL
)
204 if ((b_root
= heapb
->root
) == NULL
)
210 /* Merge them to the next nodes on the opposite chain. */
211 a_root
->left
->right
= b_root
;
212 b_root
->left
->right
= a_root
;
214 a_root
->left
= b_root
->left
;
216 heapa
->nodes
+= heapb
->nodes
;
218 /* And set the new minimum, if it's changed. */
219 if (fibheap_compare (heapa
, heapb
->min
, heapa
->min
) < 0)
220 heapa
->min
= heapb
->min
;
226 /* Extract the data of the minimum node from HEAP. */
228 fibheap_extract_min (heap
)
234 /* If we don't have a min set, it means we have no nodes. */
235 if (heap
->min
!= NULL
)
237 /* Otherwise, extract the min node, free the node, and return the
239 z
= fibheap_extr_min_node (heap
);
247 /* Replace both the KEY and the DATA associated with NODE. */
249 fibheap_replace_key_data (heap
, node
, key
, data
)
259 /* If we wanted to, we could actually do a real increase by redeleting and
260 inserting. However, this would require O (log n) time. So just bail out
262 if (fibheap_comp_data (heap
, key
, data
, node
) > 0)
274 /* These two compares are specifically <= 0 to make sure that in the case
275 of equality, a node we replaced the data on, becomes the new min. This
276 is needed so that delete's call to extractmin gets the right node. */
277 if (y
!= NULL
&& fibheap_compare (heap
, node
, y
) <= 0)
279 fibheap_cut (heap
, node
, y
);
280 fibheap_cascading_cut (heap
, y
);
283 if (fibheap_compare (heap
, node
, heap
->min
) <= 0)
289 /* Replace the DATA associated with NODE. */
291 fibheap_replace_data (heap
, node
, data
)
296 return fibheap_replace_key_data (heap
, node
, node
->key
, data
);
299 /* Replace the KEY associated with NODE. */
301 fibheap_replace_key (heap
, node
, key
)
306 int okey
= node
->key
;
307 fibheap_replace_key_data (heap
, node
, key
, node
->data
);
311 /* Delete NODE from HEAP. */
313 fibheap_delete_node (heap
, node
)
317 void *ret
= node
->data
;
319 /* To perform delete, we just make it the min key, and extract. */
320 fibheap_replace_key (heap
, node
, FIBHEAPKEY_MIN
);
321 fibheap_extract_min (heap
);
328 fibheap_delete (heap
)
331 while (heap
->min
!= NULL
)
332 free (fibheap_extr_min_node (heap
));
337 /* Determine if HEAP is empty. */
342 return heap
->nodes
== 0;
345 /* Extract the minimum node of the heap. */
347 fibheap_extr_min_node (heap
)
350 fibnode_t ret
= heap
->min
;
351 fibnode_t x
, y
, orig
;
353 /* Attach the child list of the minimum node to the root list of the heap.
354 If there is no child list, we don't do squat. */
355 for (x
= ret
->child
, orig
= NULL
; x
!= orig
&& x
!= NULL
; x
= y
)
361 fibheap_ins_root (heap
, x
);
364 /* Remove the old root. */
365 fibheap_rem_root (heap
, ret
);
368 /* If we are left with no nodes, then the min is NULL. */
369 if (heap
->nodes
== 0)
373 /* Otherwise, consolidate to find new minimum, as well as do the reorg
374 work that needs to be done. */
375 heap
->min
= ret
->right
;
376 fibheap_consolidate (heap
);
382 /* Insert NODE into the root list of HEAP. */
384 fibheap_ins_root (heap
, node
)
388 /* If the heap is currently empty, the new node becomes the singleton
389 circular root list. */
390 if (heap
->root
== NULL
)
398 /* Otherwise, insert it in the circular root list between the root
399 and it's right node. */
400 fibnode_insert_after (heap
->root
, node
);
403 /* Remove NODE from the rootlist of HEAP. */
405 fibheap_rem_root (heap
, node
)
409 if (node
->left
== node
)
412 heap
->root
= fibnode_remove (node
);
415 /* Consolidate the heap. */
417 fibheap_consolidate (heap
)
420 fibnode_t a
[1 + 8 * sizeof (long)];
428 D
= 1 + 8 * sizeof (long);
430 memset (a
, 0, sizeof (fibnode_t
) * D
);
432 while ((w
= heap
->root
) != NULL
)
435 fibheap_rem_root (heap
, w
);
440 if (fibheap_compare (heap
, x
, y
) > 0)
447 fibheap_link (heap
, y
, x
);
454 for (i
= 0; i
< D
; i
++)
457 fibheap_ins_root (heap
, a
[i
]);
458 if (heap
->min
== NULL
|| fibheap_compare (heap
, a
[i
], heap
->min
) < 0)
463 /* Make NODE a child of PARENT. */
465 fibheap_link (heap
, node
, parent
)
466 fibheap_t heap ATTRIBUTE_UNUSED
;
470 if (parent
->child
== NULL
)
471 parent
->child
= node
;
473 fibnode_insert_before (parent
->child
, node
);
474 node
->parent
= parent
;
479 /* Remove NODE from PARENT's child list. */
481 fibheap_cut (heap
, node
, parent
)
486 fibnode_remove (node
);
488 fibheap_ins_root (heap
, node
);
494 fibheap_cascading_cut (heap
, y
)
500 while ((z
= y
->parent
) != NULL
)
509 fibheap_cut (heap
, y
, z
);
516 fibnode_insert_after (a
, b
)
537 fibnode_remove (node
)
542 if (node
== node
->left
)
547 if (node
->parent
!= NULL
&& node
->parent
->child
== node
)
548 node
->parent
->child
= ret
;
550 node
->right
->left
= node
->left
;
551 node
->left
->right
= node
->right
;