daily update
[binutils.git] / libiberty / fibheap.c
blobc032149c0c24fc9639d9c56725691e9d4035aed8
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)
10 any later version.
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, 51 Franklin Street - Fifth Floor,
20 Boston, MA 02110-1301, USA. */
22 #ifdef HAVE_CONFIG_H
23 #include "config.h"
24 #endif
25 #ifdef HAVE_LIMITS_H
26 #include <limits.h>
27 #endif
28 #ifdef HAVE_STDLIB_H
29 #include <stdlib.h>
30 #endif
31 #ifdef HAVE_STRING_H
32 #include <string.h>
33 #endif
34 #include "libiberty.h"
35 #include "fibheap.h"
38 #define FIBHEAPKEY_MIN LONG_MIN
40 static void fibheap_ins_root (fibheap_t, fibnode_t);
41 static void fibheap_rem_root (fibheap_t, fibnode_t);
42 static void fibheap_consolidate (fibheap_t);
43 static void fibheap_link (fibheap_t, fibnode_t, fibnode_t);
44 static void fibheap_cut (fibheap_t, fibnode_t, fibnode_t);
45 static void fibheap_cascading_cut (fibheap_t, fibnode_t);
46 static fibnode_t fibheap_extr_min_node (fibheap_t);
47 static int fibheap_compare (fibheap_t, fibnode_t, fibnode_t);
48 static int fibheap_comp_data (fibheap_t, fibheapkey_t, void *, fibnode_t);
49 static fibnode_t fibnode_new (void);
50 static void fibnode_insert_after (fibnode_t, fibnode_t);
51 #define fibnode_insert_before(a, b) fibnode_insert_after (a->left, b)
52 static fibnode_t fibnode_remove (fibnode_t);
55 /* Create a new fibonacci heap. */
56 fibheap_t
57 fibheap_new (void)
59 return (fibheap_t) xcalloc (1, sizeof (struct fibheap));
62 /* Create a new fibonacci heap node. */
63 static fibnode_t
64 fibnode_new (void)
66 fibnode_t node;
68 node = (fibnode_t) xcalloc (1, sizeof *node);
69 node->left = node;
70 node->right = node;
72 return node;
75 static inline int
76 fibheap_compare (fibheap_t heap ATTRIBUTE_UNUSED, fibnode_t a, fibnode_t b)
78 if (a->key < b->key)
79 return -1;
80 if (a->key > b->key)
81 return 1;
82 return 0;
85 static inline int
86 fibheap_comp_data (fibheap_t heap, fibheapkey_t key, void *data, fibnode_t b)
88 struct fibnode a;
90 a.key = key;
91 a.data = data;
93 return fibheap_compare (heap, &a, b);
96 /* Insert DATA, with priority KEY, into HEAP. */
97 fibnode_t
98 fibheap_insert (fibheap_t heap, fibheapkey_t key, void *data)
100 fibnode_t node;
102 /* Create the new node. */
103 node = fibnode_new ();
105 /* Set the node's data. */
106 node->data = data;
107 node->key = key;
109 /* Insert it into the root list. */
110 fibheap_ins_root (heap, node);
112 /* If their was no minimum, or this key is less than the min,
113 it's the new min. */
114 if (heap->min == NULL || node->key < heap->min->key)
115 heap->min = node;
117 heap->nodes++;
119 return node;
122 /* Return the data of the minimum node (if we know it). */
123 void *
124 fibheap_min (fibheap_t heap)
126 /* If there is no min, we can't easily return it. */
127 if (heap->min == NULL)
128 return NULL;
129 return heap->min->data;
132 /* Return the key of the minimum node (if we know it). */
133 fibheapkey_t
134 fibheap_min_key (fibheap_t heap)
136 /* If there is no min, we can't easily return it. */
137 if (heap->min == NULL)
138 return 0;
139 return heap->min->key;
142 /* Union HEAPA and HEAPB into a new heap. */
143 fibheap_t
144 fibheap_union (fibheap_t heapa, fibheap_t heapb)
146 fibnode_t a_root, b_root, temp;
148 /* If one of the heaps is empty, the union is just the other heap. */
149 if ((a_root = heapa->root) == NULL)
151 free (heapa);
152 return heapb;
154 if ((b_root = heapb->root) == NULL)
156 free (heapb);
157 return heapa;
160 /* Merge them to the next nodes on the opposite chain. */
161 a_root->left->right = b_root;
162 b_root->left->right = a_root;
163 temp = a_root->left;
164 a_root->left = b_root->left;
165 b_root->left = temp;
166 heapa->nodes += heapb->nodes;
168 /* And set the new minimum, if it's changed. */
169 if (fibheap_compare (heapa, heapb->min, heapa->min) < 0)
170 heapa->min = heapb->min;
172 free (heapb);
173 return heapa;
176 /* Extract the data of the minimum node from HEAP. */
177 void *
178 fibheap_extract_min (fibheap_t heap)
180 fibnode_t z;
181 void *ret = NULL;
183 /* If we don't have a min set, it means we have no nodes. */
184 if (heap->min != NULL)
186 /* Otherwise, extract the min node, free the node, and return the
187 node's data. */
188 z = fibheap_extr_min_node (heap);
189 ret = z->data;
190 free (z);
193 return ret;
196 /* Replace both the KEY and the DATA associated with NODE. */
197 void *
198 fibheap_replace_key_data (fibheap_t heap, fibnode_t node,
199 fibheapkey_t key, void *data)
201 void *odata;
202 fibheapkey_t okey;
203 fibnode_t y;
205 /* If we wanted to, we could actually do a real increase by redeleting and
206 inserting. However, this would require O (log n) time. So just bail out
207 for now. */
208 if (fibheap_comp_data (heap, key, data, node) > 0)
209 return NULL;
211 odata = node->data;
212 okey = node->key;
213 node->data = data;
214 node->key = key;
215 y = node->parent;
217 if (okey == key)
218 return odata;
220 /* These two compares are specifically <= 0 to make sure that in the case
221 of equality, a node we replaced the data on, becomes the new min. This
222 is needed so that delete's call to extractmin gets the right node. */
223 if (y != NULL && fibheap_compare (heap, node, y) <= 0)
225 fibheap_cut (heap, node, y);
226 fibheap_cascading_cut (heap, y);
229 if (fibheap_compare (heap, node, heap->min) <= 0)
230 heap->min = node;
232 return odata;
235 /* Replace the DATA associated with NODE. */
236 void *
237 fibheap_replace_data (fibheap_t heap, fibnode_t node, void *data)
239 return fibheap_replace_key_data (heap, node, node->key, data);
242 /* Replace the KEY associated with NODE. */
243 fibheapkey_t
244 fibheap_replace_key (fibheap_t heap, fibnode_t node, fibheapkey_t key)
246 int okey = node->key;
247 fibheap_replace_key_data (heap, node, key, node->data);
248 return okey;
251 /* Delete NODE from HEAP. */
252 void *
253 fibheap_delete_node (fibheap_t heap, fibnode_t node)
255 void *ret = node->data;
257 /* To perform delete, we just make it the min key, and extract. */
258 fibheap_replace_key (heap, node, FIBHEAPKEY_MIN);
259 fibheap_extract_min (heap);
261 return ret;
264 /* Delete HEAP. */
265 void
266 fibheap_delete (fibheap_t heap)
268 while (heap->min != NULL)
269 free (fibheap_extr_min_node (heap));
271 free (heap);
274 /* Determine if HEAP is empty. */
276 fibheap_empty (fibheap_t heap)
278 return heap->nodes == 0;
281 /* Extract the minimum node of the heap. */
282 static fibnode_t
283 fibheap_extr_min_node (fibheap_t heap)
285 fibnode_t ret = heap->min;
286 fibnode_t x, y, orig;
288 /* Attach the child list of the minimum node to the root list of the heap.
289 If there is no child list, we don't do squat. */
290 for (x = ret->child, orig = NULL; x != orig && x != NULL; x = y)
292 if (orig == NULL)
293 orig = x;
294 y = x->right;
295 x->parent = NULL;
296 fibheap_ins_root (heap, x);
299 /* Remove the old root. */
300 fibheap_rem_root (heap, ret);
301 heap->nodes--;
303 /* If we are left with no nodes, then the min is NULL. */
304 if (heap->nodes == 0)
305 heap->min = NULL;
306 else
308 /* Otherwise, consolidate to find new minimum, as well as do the reorg
309 work that needs to be done. */
310 heap->min = ret->right;
311 fibheap_consolidate (heap);
314 return ret;
317 /* Insert NODE into the root list of HEAP. */
318 static void
319 fibheap_ins_root (fibheap_t heap, fibnode_t node)
321 /* If the heap is currently empty, the new node becomes the singleton
322 circular root list. */
323 if (heap->root == NULL)
325 heap->root = node;
326 node->left = node;
327 node->right = node;
328 return;
331 /* Otherwise, insert it in the circular root list between the root
332 and it's right node. */
333 fibnode_insert_after (heap->root, node);
336 /* Remove NODE from the rootlist of HEAP. */
337 static void
338 fibheap_rem_root (fibheap_t heap, fibnode_t node)
340 if (node->left == node)
341 heap->root = NULL;
342 else
343 heap->root = fibnode_remove (node);
346 /* Consolidate the heap. */
347 static void
348 fibheap_consolidate (fibheap_t heap)
350 fibnode_t a[1 + 8 * sizeof (long)];
351 fibnode_t w;
352 fibnode_t y;
353 fibnode_t x;
354 int i;
355 int d;
356 int D;
358 D = 1 + 8 * sizeof (long);
360 memset (a, 0, sizeof (fibnode_t) * D);
362 while ((w = heap->root) != NULL)
364 x = w;
365 fibheap_rem_root (heap, w);
366 d = x->degree;
367 while (a[d] != NULL)
369 y = a[d];
370 if (fibheap_compare (heap, x, y) > 0)
372 fibnode_t temp;
373 temp = x;
374 x = y;
375 y = temp;
377 fibheap_link (heap, y, x);
378 a[d] = NULL;
379 d++;
381 a[d] = x;
383 heap->min = NULL;
384 for (i = 0; i < D; i++)
385 if (a[i] != NULL)
387 fibheap_ins_root (heap, a[i]);
388 if (heap->min == NULL || fibheap_compare (heap, a[i], heap->min) < 0)
389 heap->min = a[i];
393 /* Make NODE a child of PARENT. */
394 static void
395 fibheap_link (fibheap_t heap ATTRIBUTE_UNUSED,
396 fibnode_t node, fibnode_t parent)
398 if (parent->child == NULL)
399 parent->child = node;
400 else
401 fibnode_insert_before (parent->child, node);
402 node->parent = parent;
403 parent->degree++;
404 node->mark = 0;
407 /* Remove NODE from PARENT's child list. */
408 static void
409 fibheap_cut (fibheap_t heap, fibnode_t node, fibnode_t parent)
411 fibnode_remove (node);
412 parent->degree--;
413 fibheap_ins_root (heap, node);
414 node->parent = NULL;
415 node->mark = 0;
418 static void
419 fibheap_cascading_cut (fibheap_t heap, fibnode_t y)
421 fibnode_t z;
423 while ((z = y->parent) != NULL)
425 if (y->mark == 0)
427 y->mark = 1;
428 return;
430 else
432 fibheap_cut (heap, y, z);
433 y = z;
438 static void
439 fibnode_insert_after (fibnode_t a, fibnode_t b)
441 if (a == a->right)
443 a->right = b;
444 a->left = b;
445 b->right = a;
446 b->left = a;
448 else
450 b->right = a->right;
451 a->right->left = b;
452 a->right = b;
453 b->left = a;
457 static fibnode_t
458 fibnode_remove (fibnode_t node)
460 fibnode_t ret;
462 if (node == node->left)
463 ret = NULL;
464 else
465 ret = node->left;
467 if (node->parent != NULL && node->parent->child == node)
468 node->parent->child = ret;
470 node->right->left = node->left;
471 node->left->right = node->right;
473 node->parent = NULL;
474 node->left = node;
475 node->right = node;
477 return ret;