1 /* A Fibonacci heap datatype.
2    Copyright (C) 1998-2018 Free Software Foundation, Inc.
3    Contributed by Daniel Berlin (dan@cgsoftware.com).
4 
5 This file is part of GNU CC.
6 
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.
11 
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.
16 
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.  */
21 
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"
36 
37 
38 #define FIBHEAPKEY_MIN	LONG_MIN
39 
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);
53 
54 
55 /* Create a new fibonacci heap.  */
56 fibheap_t
57 fibheap_new (void)
58 {
59   return (fibheap_t) xcalloc (1, sizeof (struct fibheap));
60 }
61 
62 /* Create a new fibonacci heap node.  */
63 static fibnode_t
64 fibnode_new (void)
65 {
66   fibnode_t node;
67 
68   node = (fibnode_t) xcalloc (1, sizeof *node);
69   node->left = node;
70   node->right = node;
71 
72   return node;
73 }
74 
75 static inline int
76 fibheap_compare (fibheap_t heap ATTRIBUTE_UNUSED, fibnode_t a, fibnode_t b)
77 {
78   if (a->key < b->key)
79     return -1;
80   if (a->key > b->key)
81     return 1;
82   return 0;
83 }
84 
85 static inline int
86 fibheap_comp_data (fibheap_t heap, fibheapkey_t key, void *data, fibnode_t b)
87 {
88   struct fibnode a;
89 
90   a.key = key;
91   a.data = data;
92 
93   return fibheap_compare (heap, &a, b);
94 }
95 
96 /* Insert DATA, with priority KEY, into HEAP.  */
97 fibnode_t
98 fibheap_insert (fibheap_t heap, fibheapkey_t key, void *data)
99 {
100   fibnode_t node;
101 
102   /* Create the new node.  */
103   node = fibnode_new ();
104 
105   /* Set the node's data.  */
106   node->data = data;
107   node->key = key;
108 
109   /* Insert it into the root list.  */
110   fibheap_ins_root (heap, node);
111 
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;
116 
117   heap->nodes++;
118 
119   return node;
120 }
121 
122 /* Return the data of the minimum node (if we know it).  */
123 void *
124 fibheap_min (fibheap_t heap)
125 {
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;
130 }
131 
132 /* Return the key of the minimum node (if we know it).  */
133 fibheapkey_t
134 fibheap_min_key (fibheap_t heap)
135 {
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;
140 }
141 
142 /* Union HEAPA and HEAPB into a new heap.  */
143 fibheap_t
144 fibheap_union (fibheap_t heapa, fibheap_t heapb)
145 {
146   fibnode_t a_root, b_root, temp;
147 
148   /* If one of the heaps is empty, the union is just the other heap.  */
149   if ((a_root = heapa->root) == NULL)
150     {
151       free (heapa);
152       return heapb;
153     }
154   if ((b_root = heapb->root) == NULL)
155     {
156       free (heapb);
157       return heapa;
158     }
159 
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;
167 
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;
171 
172   free (heapb);
173   return heapa;
174 }
175 
176 /* Extract the data of the minimum node from HEAP.  */
177 void *
178 fibheap_extract_min (fibheap_t heap)
179 {
180   fibnode_t z;
181   void *ret = NULL;
182 
183   /* If we don't have a min set, it means we have no nodes.  */
184   if (heap->min != NULL)
185     {
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);
191     }
192 
193   return ret;
194 }
195 
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)
200 {
201   void *odata;
202   fibheapkey_t okey;
203   fibnode_t y;
204 
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;
210 
211   odata = node->data;
212   okey = node->key;
213   node->data = data;
214   node->key = key;
215   y = node->parent;
216 
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;
222 
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)
227     {
228       fibheap_cut (heap, node, y);
229       fibheap_cascading_cut (heap, y);
230     }
231 
232   if (fibheap_compare (heap, node, heap->min) <= 0)
233     heap->min = node;
234 
235   return odata;
236 }
237 
238 /* Replace the DATA associated with NODE.  */
239 void *
240 fibheap_replace_data (fibheap_t heap, fibnode_t node, void *data)
241 {
242   return fibheap_replace_key_data (heap, node, node->key, data);
243 }
244 
245 /* Replace the KEY associated with NODE.  */
246 fibheapkey_t
247 fibheap_replace_key (fibheap_t heap, fibnode_t node, fibheapkey_t key)
248 {
249   int okey = node->key;
250   fibheap_replace_key_data (heap, node, key, node->data);
251   return okey;
252 }
253 
254 /* Delete NODE from HEAP.  */
255 void *
256 fibheap_delete_node (fibheap_t heap, fibnode_t node)
257 {
258   void *ret = node->data;
259 
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)
263     {
264       fprintf (stderr, "Can't force minimum on fibheap.\n");
265       abort ();
266     }
267   fibheap_extract_min (heap);
268 
269   return ret;
270 }
271 
272 /* Delete HEAP.  */
273 void
274 fibheap_delete (fibheap_t heap)
275 {
276   while (heap->min != NULL)
277     free (fibheap_extr_min_node (heap));
278 
279   free (heap);
280 }
281 
282 /* Determine if HEAP is empty.  */
283 int
284 fibheap_empty (fibheap_t heap)
285 {
286   return heap->nodes == 0;
287 }
288 
289 /* Extract the minimum node of the heap.  */
290 static fibnode_t
291 fibheap_extr_min_node (fibheap_t heap)
292 {
293   fibnode_t ret = heap->min;
294   fibnode_t x, y, orig;
295 
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)
299     {
300       if (orig == NULL)
301 	orig = x;
302       y = x->right;
303       x->parent = NULL;
304       fibheap_ins_root (heap, x);
305     }
306 
307   /* Remove the old root.  */
308   fibheap_rem_root (heap, ret);
309   heap->nodes--;
310 
311   /* If we are left with no nodes, then the min is NULL.  */
312   if (heap->nodes == 0)
313     heap->min = NULL;
314   else
315     {
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);
320     }
321 
322   return ret;
323 }
324 
325 /* Insert NODE into the root list of HEAP.  */
326 static void
327 fibheap_ins_root (fibheap_t heap, fibnode_t node)
328 {
329   /* If the heap is currently empty, the new node becomes the singleton
330      circular root list.  */
331   if (heap->root == NULL)
332     {
333       heap->root = node;
334       node->left = node;
335       node->right = node;
336       return;
337     }
338 
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);
342 }
343 
344 /* Remove NODE from the rootlist of HEAP.  */
345 static void
346 fibheap_rem_root (fibheap_t heap, fibnode_t node)
347 {
348   if (node->left == node)
349     heap->root = NULL;
350   else
351     heap->root = fibnode_remove (node);
352 }
353 
354 /* Consolidate the heap.  */
355 static void
356 fibheap_consolidate (fibheap_t heap)
357 {
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;
365 
366   D = 1 + 8 * sizeof (long);
367 
368   memset (a, 0, sizeof (fibnode_t) * D);
369 
370   while ((w = heap->root) != NULL)
371     {
372       x = w;
373       fibheap_rem_root (heap, w);
374       d = x->degree;
375       while (a[d] != NULL)
376 	{
377 	  y = a[d];
378 	  if (fibheap_compare (heap, x, y) > 0)
379 	    {
380 	      fibnode_t temp;
381 	      temp = x;
382 	      x = y;
383 	      y = temp;
384 	    }
385 	  fibheap_link (heap, y, x);
386 	  a[d] = NULL;
387 	  d++;
388 	}
389       a[d] = x;
390     }
391   heap->min = NULL;
392   for (i = 0; i < D; i++)
393     if (a[i] != NULL)
394       {
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];
398       }
399 }
400 
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)
405 {
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;
413 }
414 
415 /* Remove NODE from PARENT's child list.  */
416 static void
417 fibheap_cut (fibheap_t heap, fibnode_t node, fibnode_t parent)
418 {
419   fibnode_remove (node);
420   parent->degree--;
421   fibheap_ins_root (heap, node);
422   node->parent = NULL;
423   node->mark = 0;
424 }
425 
426 static void
427 fibheap_cascading_cut (fibheap_t heap, fibnode_t y)
428 {
429   fibnode_t z;
430 
431   while ((z = y->parent) != NULL)
432     {
433       if (y->mark == 0)
434 	{
435 	  y->mark = 1;
436 	  return;
437 	}
438       else
439 	{
440 	  fibheap_cut (heap, y, z);
441 	  y = z;
442 	}
443     }
444 }
445 
446 static void
447 fibnode_insert_after (fibnode_t a, fibnode_t b)
448 {
449   if (a == a->right)
450     {
451       a->right = b;
452       a->left = b;
453       b->right = a;
454       b->left = a;
455     }
456   else
457     {
458       b->right = a->right;
459       a->right->left = b;
460       a->right = b;
461       b->left = a;
462     }
463 }
464 
465 static fibnode_t
466 fibnode_remove (fibnode_t node)
467 {
468   fibnode_t ret;
469 
470   if (node == node->left)
471     ret = NULL;
472   else
473     ret = node->left;
474 
475   if (node->parent != NULL && node->parent->child == node)
476     node->parent->child = ret;
477 
478   node->right->left = node->left;
479   node->left->right = node->right;
480 
481   node->parent = NULL;
482   node->left = node;
483   node->right = node;
484 
485   return ret;
486 }
487