Automatic date update in version.in
[binutils-gdb.git] / libiberty / fibheap.c
blob24e0e9929e167870db14b4305bae1c85992e35da
1 /* A Fibonacci heap datatype.
2 Copyright (C) 1998-2024 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 /* Short-circuit if the key is the same, as we then don't have to
218 do anything. Except if we're trying to force the new node to
219 be the new minimum for delete. */
220 if (okey == key && okey != FIBHEAPKEY_MIN)
221 return odata;
223 /* These two compares are specifically <= 0 to make sure that in the case
224 of equality, a node we replaced the data on, becomes the new min. This
225 is needed so that delete's call to extractmin gets the right node. */
226 if (y != NULL && fibheap_compare (heap, node, y) <= 0)
228 fibheap_cut (heap, node, y);
229 fibheap_cascading_cut (heap, y);
232 if (fibheap_compare (heap, node, heap->min) <= 0)
233 heap->min = node;
235 return odata;
238 /* Replace the DATA associated with NODE. */
239 void *
240 fibheap_replace_data (fibheap_t heap, fibnode_t node, void *data)
242 return fibheap_replace_key_data (heap, node, node->key, data);
245 /* Replace the KEY associated with NODE. */
246 fibheapkey_t
247 fibheap_replace_key (fibheap_t heap, fibnode_t node, fibheapkey_t key)
249 int okey = node->key;
250 fibheap_replace_key_data (heap, node, key, node->data);
251 return okey;
254 /* Delete NODE from HEAP. */
255 void *
256 fibheap_delete_node (fibheap_t heap, fibnode_t node)
258 void *ret = node->data;
260 /* To perform delete, we just make it the min key, and extract. */
261 fibheap_replace_key (heap, node, FIBHEAPKEY_MIN);
262 if (node != heap->min)
264 fprintf (stderr, "Can't force minimum on fibheap.\n");
265 abort ();
267 fibheap_extract_min (heap);
269 return ret;
272 /* Delete HEAP. */
273 void
274 fibheap_delete (fibheap_t heap)
276 while (heap->min != NULL)
277 free (fibheap_extr_min_node (heap));
279 free (heap);
282 /* Determine if HEAP is empty. */
284 fibheap_empty (fibheap_t heap)
286 return heap->nodes == 0;
289 /* Extract the minimum node of the heap. */
290 static fibnode_t
291 fibheap_extr_min_node (fibheap_t heap)
293 fibnode_t ret = heap->min;
294 fibnode_t x, y, orig;
296 /* Attach the child list of the minimum node to the root list of the heap.
297 If there is no child list, we don't do squat. */
298 for (x = ret->child, orig = NULL; x != orig && x != NULL; x = y)
300 if (orig == NULL)
301 orig = x;
302 y = x->right;
303 x->parent = NULL;
304 fibheap_ins_root (heap, x);
307 /* Remove the old root. */
308 fibheap_rem_root (heap, ret);
309 heap->nodes--;
311 /* If we are left with no nodes, then the min is NULL. */
312 if (heap->nodes == 0)
313 heap->min = NULL;
314 else
316 /* Otherwise, consolidate to find new minimum, as well as do the reorg
317 work that needs to be done. */
318 heap->min = ret->right;
319 fibheap_consolidate (heap);
322 return ret;
325 /* Insert NODE into the root list of HEAP. */
326 static void
327 fibheap_ins_root (fibheap_t heap, fibnode_t node)
329 /* If the heap is currently empty, the new node becomes the singleton
330 circular root list. */
331 if (heap->root == NULL)
333 heap->root = node;
334 node->left = node;
335 node->right = node;
336 return;
339 /* Otherwise, insert it in the circular root list between the root
340 and it's right node. */
341 fibnode_insert_after (heap->root, node);
344 /* Remove NODE from the rootlist of HEAP. */
345 static void
346 fibheap_rem_root (fibheap_t heap, fibnode_t node)
348 if (node->left == node)
349 heap->root = NULL;
350 else
351 heap->root = fibnode_remove (node);
354 /* Consolidate the heap. */
355 static void
356 fibheap_consolidate (fibheap_t heap)
358 fibnode_t a[1 + 8 * sizeof (long)];
359 fibnode_t w;
360 fibnode_t y;
361 fibnode_t x;
362 int i;
363 int d;
364 int D;
366 D = 1 + 8 * sizeof (long);
368 memset (a, 0, sizeof (fibnode_t) * D);
370 while ((w = heap->root) != NULL)
372 x = w;
373 fibheap_rem_root (heap, w);
374 d = x->degree;
375 while (a[d] != NULL)
377 y = a[d];
378 if (fibheap_compare (heap, x, y) > 0)
380 fibnode_t temp;
381 temp = x;
382 x = y;
383 y = temp;
385 fibheap_link (heap, y, x);
386 a[d] = NULL;
387 d++;
389 a[d] = x;
391 heap->min = NULL;
392 for (i = 0; i < D; i++)
393 if (a[i] != NULL)
395 fibheap_ins_root (heap, a[i]);
396 if (heap->min == NULL || fibheap_compare (heap, a[i], heap->min) < 0)
397 heap->min = a[i];
401 /* Make NODE a child of PARENT. */
402 static void
403 fibheap_link (fibheap_t heap ATTRIBUTE_UNUSED,
404 fibnode_t node, fibnode_t parent)
406 if (parent->child == NULL)
407 parent->child = node;
408 else
409 fibnode_insert_before (parent->child, node);
410 node->parent = parent;
411 parent->degree++;
412 node->mark = 0;
415 /* Remove NODE from PARENT's child list. */
416 static void
417 fibheap_cut (fibheap_t heap, fibnode_t node, fibnode_t parent)
419 fibnode_remove (node);
420 parent->degree--;
421 fibheap_ins_root (heap, node);
422 node->parent = NULL;
423 node->mark = 0;
426 static void
427 fibheap_cascading_cut (fibheap_t heap, fibnode_t y)
429 fibnode_t z;
431 while ((z = y->parent) != NULL)
433 if (y->mark == 0)
435 y->mark = 1;
436 return;
438 else
440 fibheap_cut (heap, y, z);
441 y = z;
446 static void
447 fibnode_insert_after (fibnode_t a, fibnode_t b)
449 if (a == a->right)
451 a->right = b;
452 a->left = b;
453 b->right = a;
454 b->left = a;
456 else
458 b->right = a->right;
459 a->right->left = b;
460 a->right = b;
461 b->left = a;
465 static fibnode_t
466 fibnode_remove (fibnode_t node)
468 fibnode_t ret;
470 if (node == node->left)
471 ret = NULL;
472 else
473 ret = node->left;
475 if (node->parent != NULL && node->parent->child == node)
476 node->parent->child = ret;
478 node->right->left = node->left;
479 node->left->right = node->right;
481 node->parent = NULL;
482 node->left = node;
483 node->right = node;
485 return ret;