merge from gcc
[external/binutils.git] / libiberty / fibheap.c
1 /* A Fibonacci heap datatype.
2    Copyright 1998, 1999, 2000, 2001 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, 59 Temple Place - Suite 330,
20 Boston, MA 02111-1307, 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 PARAMS ((fibheap_t, fibnode_t));
41 static void fibheap_rem_root PARAMS ((fibheap_t, fibnode_t));
42 static void fibheap_consolidate PARAMS ((fibheap_t));
43 static void fibheap_link PARAMS ((fibheap_t, fibnode_t, fibnode_t));
44 static void fibheap_cut PARAMS ((fibheap_t, fibnode_t, fibnode_t));
45 static void fibheap_cascading_cut PARAMS ((fibheap_t, fibnode_t));
46 static fibnode_t fibheap_extr_min_node PARAMS ((fibheap_t));
47 static int fibheap_compare PARAMS ((fibheap_t, fibnode_t, fibnode_t));
48 static int fibheap_comp_data PARAMS ((fibheap_t, fibheapkey_t, void *,
49                                       fibnode_t));
50 static fibnode_t fibnode_new PARAMS ((void));
51 static void fibnode_insert_after PARAMS ((fibnode_t, fibnode_t));
52 #define fibnode_insert_before(a, b) fibnode_insert_after (a->left, b)
53 static fibnode_t fibnode_remove PARAMS ((fibnode_t));
54
55 \f
56 /* Create a new fibonacci heap.  */
57 fibheap_t
58 fibheap_new ()
59 {
60   return (fibheap_t) xcalloc (1, sizeof (struct fibheap));
61 }
62
63 /* Create a new fibonacci heap node.  */
64 static fibnode_t
65 fibnode_new ()
66 {
67   fibnode_t node;
68
69   node = (fibnode_t) xcalloc (1, sizeof *node);
70   node->left = node;
71   node->right = node;
72
73   return node;
74 }
75
76 static inline int
77 fibheap_compare (heap, a, b)
78      fibheap_t heap ATTRIBUTE_UNUSED;
79      fibnode_t a;
80      fibnode_t b;
81 {
82   if (a->key < b->key)
83     return -1;
84   if (a->key > b->key)
85     return 1;
86   return 0;
87 }
88
89 static inline int
90 fibheap_comp_data (heap, key, data, b)
91      fibheap_t heap;
92      fibheapkey_t key;
93      void *data;
94      fibnode_t b;
95 {
96   struct fibnode a;
97
98   a.key = key;
99   a.data = data;
100
101   return fibheap_compare (heap, &a, b);
102 }
103
104 /* Insert DATA, with priority KEY, into HEAP.  */
105 fibnode_t
106 fibheap_insert (heap, key, data)
107      fibheap_t heap;
108      fibheapkey_t key;
109      void *data;
110 {
111   fibnode_t node;
112
113   /* Create the new node.  */
114   node = fibnode_new ();
115
116   /* Set the node's data.  */
117   node->data = data;
118   node->key = key;
119
120   /* Insert it into the root list.  */
121   fibheap_ins_root (heap, node);
122
123   /* If their was no minimum, or this key is less than the min,
124      it's the new min.  */
125   if (heap->min == NULL || node->key < heap->min->key)
126     heap->min = node;
127
128   heap->nodes++;
129
130   return node;
131 }
132
133 /* Return the data of the minimum node (if we know it).  */
134 void *
135 fibheap_min (heap)
136      fibheap_t heap;
137 {
138   /* If there is no min, we can't easily return it.  */
139   if (heap->min == NULL)
140     return NULL;
141   return heap->min->data;
142 }
143
144 /* Return the key of the minimum node (if we know it).  */
145 fibheapkey_t
146 fibheap_min_key (heap)
147      fibheap_t heap;
148 {
149   /* If there is no min, we can't easily return it.  */
150   if (heap->min == NULL)
151     return 0;
152   return heap->min->key;
153 }
154
155 /* Union HEAPA and HEAPB into a new heap.  */
156 fibheap_t
157 fibheap_union (heapa, heapb)
158      fibheap_t heapa;
159      fibheap_t heapb;
160 {
161   fibnode_t a_root, b_root, temp;
162
163   /* If one of the heaps is empty, the union is just the other heap.  */
164   if ((a_root = heapa->root) == NULL)
165     {
166       free (heapa);
167       return heapb;
168     }
169   if ((b_root = heapb->root) == NULL)
170     {
171       free (heapb);
172       return heapa;
173     }
174
175   /* Merge them to the next nodes on the opposite chain.  */
176   a_root->left->right = b_root;
177   b_root->left->right = a_root;
178   temp = a_root->left;
179   a_root->left = b_root->left;
180   b_root->left = temp;
181   heapa->nodes += heapb->nodes;
182
183   /* And set the new minimum, if it's changed.  */
184   if (fibheap_compare (heapa, heapb->min, heapa->min) < 0)
185     heapa->min = heapb->min;
186
187   free (heapb);
188   return heapa;
189 }
190
191 /* Extract the data of the minimum node from HEAP.  */
192 void *
193 fibheap_extract_min (heap)
194      fibheap_t heap;
195 {
196   fibnode_t z;
197   void *ret = NULL;
198
199   /* If we don't have a min set, it means we have no nodes.  */
200   if (heap->min != NULL)
201     {
202       /* Otherwise, extract the min node, free the node, and return the
203          node's data.  */
204       z = fibheap_extr_min_node (heap);
205       ret = z->data;
206       free (z);
207     }
208
209   return ret;
210 }
211
212 /* Replace both the KEY and the DATA associated with NODE.  */
213 void *
214 fibheap_replace_key_data (heap, node, key, data)
215      fibheap_t heap;
216      fibnode_t node;
217      fibheapkey_t key;
218      void *data;
219 {
220   void *odata;
221   fibheapkey_t okey;
222   fibnode_t y;
223
224   /* If we wanted to, we could actually do a real increase by redeleting and
225      inserting. However, this would require O (log n) time. So just bail out
226      for now.  */
227   if (fibheap_comp_data (heap, key, data, node) > 0)
228     return NULL;
229
230   odata = node->data;
231   okey = node->key;
232   node->data = data;
233   node->key = key;
234   y = node->parent;
235
236   if (okey == key)
237     return odata;
238
239   /* These two compares are specifically <= 0 to make sure that in the case
240      of equality, a node we replaced the data on, becomes the new min.  This
241      is needed so that delete's call to extractmin gets the right node.  */
242   if (y != NULL && fibheap_compare (heap, node, y) <= 0)
243     {
244       fibheap_cut (heap, node, y);
245       fibheap_cascading_cut (heap, y);
246     }
247
248   if (fibheap_compare (heap, node, heap->min) <= 0)
249     heap->min = node;
250
251   return odata;
252 }
253
254 /* Replace the DATA associated with NODE.  */
255 void *
256 fibheap_replace_data (heap, node, data)
257      fibheap_t heap;
258      fibnode_t node;
259      void *data;
260 {
261   return fibheap_replace_key_data (heap, node, node->key, data);
262 }
263
264 /* Replace the KEY associated with NODE.  */
265 fibheapkey_t
266 fibheap_replace_key (heap, node, key)
267      fibheap_t heap;
268      fibnode_t node;
269      fibheapkey_t key;
270 {
271   int okey = node->key;
272   fibheap_replace_key_data (heap, node, key, node->data);
273   return okey;
274 }
275
276 /* Delete NODE from HEAP.  */
277 void *
278 fibheap_delete_node (heap, node)
279      fibheap_t heap;
280      fibnode_t node;
281 {
282   void *ret = node->data;
283
284   /* To perform delete, we just make it the min key, and extract.  */
285   fibheap_replace_key (heap, node, FIBHEAPKEY_MIN);
286   fibheap_extract_min (heap);
287
288   return ret;
289 }
290
291 /* Delete HEAP.  */
292 void
293 fibheap_delete (heap)
294      fibheap_t heap;
295 {
296   while (heap->min != NULL)
297     free (fibheap_extr_min_node (heap));
298
299   free (heap);
300 }
301
302 /* Determine if HEAP is empty.  */
303 int
304 fibheap_empty (heap)
305      fibheap_t heap;
306 {
307   return heap->nodes == 0;
308 }
309
310 /* Extract the minimum node of the heap.  */
311 static fibnode_t
312 fibheap_extr_min_node (heap)
313      fibheap_t heap;
314 {
315   fibnode_t ret = heap->min;
316   fibnode_t x, y, orig;
317
318   /* Attach the child list of the minimum node to the root list of the heap.
319      If there is no child list, we don't do squat.  */
320   for (x = ret->child, orig = NULL; x != orig && x != NULL; x = y)
321     {
322       if (orig == NULL)
323         orig = x;
324       y = x->right;
325       x->parent = NULL;
326       fibheap_ins_root (heap, x);
327     }
328
329   /* Remove the old root.  */
330   fibheap_rem_root (heap, ret);
331   heap->nodes--;
332
333   /* If we are left with no nodes, then the min is NULL.  */
334   if (heap->nodes == 0)
335     heap->min = NULL;
336   else
337     {
338       /* Otherwise, consolidate to find new minimum, as well as do the reorg
339          work that needs to be done.  */
340       heap->min = ret->right;
341       fibheap_consolidate (heap);
342     }
343
344   return ret;
345 }
346
347 /* Insert NODE into the root list of HEAP.  */
348 static void
349 fibheap_ins_root (heap, node)
350      fibheap_t heap;
351      fibnode_t node;
352 {
353   /* If the heap is currently empty, the new node becomes the singleton
354      circular root list.  */
355   if (heap->root == NULL)
356     {
357       heap->root = node;
358       node->left = node;
359       node->right = node;
360       return;
361     }
362
363   /* Otherwise, insert it in the circular root list between the root
364      and it's right node.  */
365   fibnode_insert_after (heap->root, node);
366 }
367
368 /* Remove NODE from the rootlist of HEAP.  */
369 static void
370 fibheap_rem_root (heap, node)
371      fibheap_t heap;
372      fibnode_t node;
373 {
374   if (node->left == node)
375     heap->root = NULL;
376   else
377     heap->root = fibnode_remove (node);
378 }
379
380 /* Consolidate the heap.  */
381 static void
382 fibheap_consolidate (heap)
383      fibheap_t heap;
384 {
385   fibnode_t a[1 + 8 * sizeof (long)];
386   fibnode_t w;
387   fibnode_t y;
388   fibnode_t x;
389   int i;
390   int d;
391   int D;
392
393   D = 1 + 8 * sizeof (long);
394
395   memset (a, 0, sizeof (fibnode_t) * D);
396
397   while ((w = heap->root) != NULL)
398     {
399       x = w;
400       fibheap_rem_root (heap, w);
401       d = x->degree;
402       while (a[d] != NULL)
403         {
404           y = a[d];
405           if (fibheap_compare (heap, x, y) > 0)
406             {
407               fibnode_t temp;
408               temp = x;
409               x = y;
410               y = temp;
411             }
412           fibheap_link (heap, y, x);
413           a[d] = NULL;
414           d++;
415         }
416       a[d] = x;
417     }
418   heap->min = NULL;
419   for (i = 0; i < D; i++)
420     if (a[i] != NULL)
421       {
422         fibheap_ins_root (heap, a[i]);
423         if (heap->min == NULL || fibheap_compare (heap, a[i], heap->min) < 0)
424           heap->min = a[i];
425       }
426 }
427
428 /* Make NODE a child of PARENT.  */
429 static void
430 fibheap_link (heap, node, parent)
431      fibheap_t heap ATTRIBUTE_UNUSED;
432      fibnode_t node;
433      fibnode_t parent;
434 {
435   if (parent->child == NULL)
436     parent->child = node;
437   else
438     fibnode_insert_before (parent->child, node);
439   node->parent = parent;
440   parent->degree++;
441   node->mark = 0;
442 }
443
444 /* Remove NODE from PARENT's child list.  */
445 static void
446 fibheap_cut (heap, node, parent)
447      fibheap_t heap;
448      fibnode_t node;
449      fibnode_t parent;
450 {
451   fibnode_remove (node);
452   parent->degree--;
453   fibheap_ins_root (heap, node);
454   node->parent = NULL;
455   node->mark = 0;
456 }
457
458 static void
459 fibheap_cascading_cut (heap, y)
460      fibheap_t heap;
461      fibnode_t y;
462 {
463   fibnode_t z;
464
465   while ((z = y->parent) != NULL)
466     {
467       if (y->mark == 0)
468         {
469           y->mark = 1;
470           return;
471         }
472       else
473         {
474           fibheap_cut (heap, y, z);
475           y = z;
476         }
477     }
478 }
479
480 static void
481 fibnode_insert_after (a, b)
482      fibnode_t a;
483      fibnode_t b;
484 {
485   if (a == a->right)
486     {
487       a->right = b;
488       a->left = b;
489       b->right = a;
490       b->left = a;
491     }
492   else
493     {
494       b->right = a->right;
495       a->right->left = b;
496       a->right = b;
497       b->left = a;
498     }
499 }
500
501 static fibnode_t
502 fibnode_remove (node)
503      fibnode_t node;
504 {
505   fibnode_t ret;
506
507   if (node == node->left)
508     ret = NULL;
509   else
510     ret = node->left;
511
512   if (node->parent != NULL && node->parent->child == node)
513     node->parent->child = ret;
514
515   node->right->left = node->left;
516   node->left->right = node->right;
517
518   node->parent = NULL;
519   node->left = node;
520   node->right = node;
521
522   return ret;
523 }