2 /* A Fibonacci heap datatype.
3 Copyright 1998, 1999, 2000, 2001 Free Software Foundation, Inc.
4 Contributed by Daniel Berlin (dan@cgsoftware.com).
6 This file is part of GNU CC.
8 GNU CC is free software; you can redistribute it and/or modify it
9 under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 2, or (at your option)
13 GNU CC is distributed in the hope that it will be useful, but
14 WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with GNU CC; see the file COPYING. If not, write to
20 the Free Software Foundation, 59 Temple Place - Suite 330,
21 Boston, MA 02111-1307, USA. */
26 #include "libiberty.h"
30 static void fibheap_init PARAMS ((fibheap_t));
31 static void fibheap_ins_root PARAMS ((fibheap_t, fibnode_t));
32 static void fibheap_rem_root PARAMS ((fibheap_t, fibnode_t));
33 static void fibheap_consolidate PARAMS ((fibheap_t));
34 static void fibheap_link PARAMS ((fibheap_t, fibnode_t, fibnode_t));
35 static void fibheap_cut PARAMS ((fibheap_t, fibnode_t, fibnode_t));
36 static void fibheap_cascading_cut PARAMS ((fibheap_t, fibnode_t));
37 static fibnode_t fibheap_extr_min_node PARAMS ((fibheap_t));
38 static int fibheap_compare PARAMS ((fibheap_t, fibnode_t, fibnode_t));
39 static int fibheap_comp_data PARAMS ((fibheap_t, fibheapkey_t, void *, fibnode_t));
40 static fibnode_t fibnode_new PARAMS ((void));
41 static void fibnode_init PARAMS ((fibnode_t));
42 static void fibnode_insert_after PARAMS ((fibnode_t, fibnode_t));
43 #define fibnode_insert_before(a, b) fibnode_insert_after (a->left, b)
44 static fibnode_t fibnode_remove PARAMS ((fibnode_t));
46 /* Create a new fibonacci heap. */
52 if ((result = xmalloc (sizeof (*result))) == NULL)
55 fibheap_init (result);
60 /* Initialize the passed in fibonacci heap. */
70 /* Insert DATA, with priority KEY, into HEAP. */
72 fibheap_insert (heap, key, data)
78 /* Create the new node, if we fail, return NULL. */
79 if ((node = fibnode_new ()) == NULL)
81 /* Set the node's data. */
85 /* Insert it into the root list. */
86 fibheap_ins_root (heap, node);
88 /* If their was no minimum, or this key is less than the min, it's the new
90 if (heap->min == NULL || node->key < heap->min->key)
98 /* Return the data of the minimum node (if we know it). */
103 /* If there is no min, we can't easily return it. */
104 if (heap->min == NULL)
106 return heap->min->data;
109 /* Return the key of the minimum node (if we know it). */
111 fibheap_min_key (heap)
114 /* If there is no min, we can't easily return it. */
115 if (heap->min == NULL)
117 return heap->min->key;
120 /* Union HEAPA and HEAPB into a new heap. */
122 fibheap_union (heapa, heapb)
128 /* If one of the heaps is empty, the union is just the other heap. */
129 if (heapa->root == NULL || heapb->root == NULL)
131 if (heapa->root == NULL)
142 /* Merge them to the next nodes on the opposite chain. */
143 heapa->root->left->right = heapb->root;
144 heapb->root->left->right = heapa->root;
145 temp = heapa->root->left;
146 heapa->root->left = heapb->root->left;
147 heapb->root->left = temp;
148 heapa->nodes += heapb->nodes;
150 /* And set the new minimum, if it's changed. */
151 if (fibheap_compare (heapa, heapb->min, heapa->min) < 0)
152 heapa->min = heapb->min;
158 /* Extract the data of the minimum node from HEAP. */
160 fibheap_extract_min (heap)
167 /* If we don't have a min set, it means we have no nodes. */
168 if (heap->min != NULL)
170 /* Otherwise, extract the min node, free the node, and return the
172 z = fibheap_extr_min_node (heap);
180 /* Replace the DATA associated with NODE. */
182 fibheap_replace_data (heap, node, data)
187 return fibheap_replace_key_data (heap, node, node->key, data);
190 /* Replace the KEY associated with NODE. */
192 fibheap_replace_key (heap, node, key)
200 (void) fibheap_replace_key_data (heap, node, key, node->data);
205 /* Replace both the KEY and the DATA associated with NODE. */
207 fibheap_replace_key_data (heap, node, key, data)
217 /* If we wanted to, we could actually do a real increase by redeleting and
218 inserting. However, this would require O (log n) time. So just bail out
220 if (fibheap_comp_data (heap, key, data, node) > 0)
232 /* These two compares are specifically <= 0 to make sure that in the case
233 of equality, a node we replaced the data on, becomes the new min. This
234 is needed so that delete's call to extractmin gets the right node. */
235 if (y != NULL && fibheap_compare (heap, node, y) <= 0)
237 fibheap_cut (heap, node, y);
238 fibheap_cascading_cut (heap, y);
241 if (fibheap_compare (heap, node, heap->min) <= 0)
247 /* Delete NODE from HEAP. */
249 fibheap_delete_node (heap, node)
254 /* To perform delete, we just make it the min key, and extract. */
256 fibheap_replace_key (heap, node, LONG_MIN);
257 fibheap_extract_min (heap);
264 fibheap_delete (heap)
267 while (heap->min != NULL)
268 free (fibheap_extr_min_node (heap));
273 /* Determine if HEAP is empty. */
278 return heap->nodes == 0;
282 /* Extract the minimum node of the heap. */
284 fibheap_extr_min_node (heap)
288 fibnode_t x, y, orig;
293 /* Attach the child list of the minimum node to the root list of the heap.
294 If there is no child list, we don't do squat. */
295 for (x = ret->child; x != orig && x != NULL;)
301 fibheap_ins_root (heap, x);
304 /* Remove the old root. */
305 fibheap_rem_root (heap, ret);
307 /* If we are left with no nodes, then the min is NULL. */
308 if (heap->nodes == 0)
312 /* Otherwise, consolidate to find new minimum, as well as do the reorg
313 work that needs to be done. */
314 heap->min = ret->right;
315 fibheap_consolidate (heap);
321 /* Insert NODE into the root list of HEAP. */
323 fibheap_ins_root (heap, node)
327 /* If the heap is currently empty, the new node becomes the singleton
328 circular root list. */
329 if (heap->root == NULL)
336 /* Otherwise, insert it in the circular root list between the root and it's
338 fibnode_insert_after (heap->root, node);
341 /* Remove NODE from the rootlist of HEAP. */
343 fibheap_rem_root (heap, node)
347 if (node->left == node)
350 heap->root = fibnode_remove (node);
353 /* Consolidate the heap. */
355 fibheap_consolidate (heap)
358 fibnode_t a[1 + 8 * sizeof (long)];
366 D = 1 + 8 * sizeof (long);
368 memset (a, 0, sizeof (fibnode_t) * D);
370 while ((w = heap->root) != NULL)
373 fibheap_rem_root (heap, w);
378 if (fibheap_compare (heap, x, y) > 0)
385 fibheap_link (heap, y, x);
392 for (i = 0; i < D; i++)
395 fibheap_ins_root (heap, a[i]);
396 if (heap->min == NULL || fibheap_compare (heap, a[i], heap->min) < 0)
401 /* Make NODE a child of PARENT. */
403 fibheap_link (heap, node, parent)
404 fibheap_t heap ATTRIBUTE_UNUSED;
408 if (parent->child == NULL)
409 parent->child = node;
411 fibnode_insert_before (parent->child, node);
412 node->parent = parent;
417 /* Remove NODE from PARENT's child list. */
419 fibheap_cut (heap, node, parent)
424 fibnode_remove (node);
426 fibheap_ins_root (heap, node);
432 fibheap_cascading_cut (heap, y)
438 while ((z = y->parent) != NULL)
447 fibheap_cut (heap, y, z);
459 if ((e = xmalloc (sizeof *e)) == NULL)
481 fibnode_insert_after (a, b)
503 fibnode_remove (node)
508 if (node == node->left)
513 if (node->parent != NULL && node->parent->child == node)
514 node->parent->child = ret;
516 node->right->left = node->left;
517 node->left->right = node->right;
527 fibheap_compare (heap, a, b)
528 fibheap_t heap ATTRIBUTE_UNUSED;
540 fibheap_comp_data (heap, key, data, b)
551 return fibheap_compare (heap, &a, b);