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 (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 \f
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   if (okey == key)
218     return odata;
219
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)
224     {
225       fibheap_cut (heap, node, y);
226       fibheap_cascading_cut (heap, y);
227     }
228
229   if (fibheap_compare (heap, node, heap->min) <= 0)
230     heap->min = node;
231
232   return odata;
233 }
234
235 /* Replace the DATA associated with NODE.  */
236 void *
237 fibheap_replace_data (fibheap_t heap, fibnode_t node, void *data)
238 {
239   return fibheap_replace_key_data (heap, node, node->key, data);
240 }
241
242 /* Replace the KEY associated with NODE.  */
243 fibheapkey_t
244 fibheap_replace_key (fibheap_t heap, fibnode_t node, fibheapkey_t key)
245 {
246   int okey = node->key;
247   fibheap_replace_key_data (heap, node, key, node->data);
248   return okey;
249 }
250
251 /* Delete NODE from HEAP.  */
252 void *
253 fibheap_delete_node (fibheap_t heap, fibnode_t node)
254 {
255   void *ret = node->data;
256
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);
260
261   return ret;
262 }
263
264 /* Delete HEAP.  */
265 void
266 fibheap_delete (fibheap_t heap)
267 {
268   while (heap->min != NULL)
269     free (fibheap_extr_min_node (heap));
270
271   free (heap);
272 }
273
274 /* Determine if HEAP is empty.  */
275 int
276 fibheap_empty (fibheap_t heap)
277 {
278   return heap->nodes == 0;
279 }
280
281 /* Extract the minimum node of the heap.  */
282 static fibnode_t
283 fibheap_extr_min_node (fibheap_t heap)
284 {
285   fibnode_t ret = heap->min;
286   fibnode_t x, y, orig;
287
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)
291     {
292       if (orig == NULL)
293         orig = x;
294       y = x->right;
295       x->parent = NULL;
296       fibheap_ins_root (heap, x);
297     }
298
299   /* Remove the old root.  */
300   fibheap_rem_root (heap, ret);
301   heap->nodes--;
302
303   /* If we are left with no nodes, then the min is NULL.  */
304   if (heap->nodes == 0)
305     heap->min = NULL;
306   else
307     {
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);
312     }
313
314   return ret;
315 }
316
317 /* Insert NODE into the root list of HEAP.  */
318 static void
319 fibheap_ins_root (fibheap_t heap, fibnode_t node)
320 {
321   /* If the heap is currently empty, the new node becomes the singleton
322      circular root list.  */
323   if (heap->root == NULL)
324     {
325       heap->root = node;
326       node->left = node;
327       node->right = node;
328       return;
329     }
330
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);
334 }
335
336 /* Remove NODE from the rootlist of HEAP.  */
337 static void
338 fibheap_rem_root (fibheap_t heap, fibnode_t node)
339 {
340   if (node->left == node)
341     heap->root = NULL;
342   else
343     heap->root = fibnode_remove (node);
344 }
345
346 /* Consolidate the heap.  */
347 static void
348 fibheap_consolidate (fibheap_t heap)
349 {
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;
357
358   D = 1 + 8 * sizeof (long);
359
360   memset (a, 0, sizeof (fibnode_t) * D);
361
362   while ((w = heap->root) != NULL)
363     {
364       x = w;
365       fibheap_rem_root (heap, w);
366       d = x->degree;
367       while (a[d] != NULL)
368         {
369           y = a[d];
370           if (fibheap_compare (heap, x, y) > 0)
371             {
372               fibnode_t temp;
373               temp = x;
374               x = y;
375               y = temp;
376             }
377           fibheap_link (heap, y, x);
378           a[d] = NULL;
379           d++;
380         }
381       a[d] = x;
382     }
383   heap->min = NULL;
384   for (i = 0; i < D; i++)
385     if (a[i] != NULL)
386       {
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];
390       }
391 }
392
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)
397 {
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;
405 }
406
407 /* Remove NODE from PARENT's child list.  */
408 static void
409 fibheap_cut (fibheap_t heap, fibnode_t node, fibnode_t parent)
410 {
411   fibnode_remove (node);
412   parent->degree--;
413   fibheap_ins_root (heap, node);
414   node->parent = NULL;
415   node->mark = 0;
416 }
417
418 static void
419 fibheap_cascading_cut (fibheap_t heap, fibnode_t y)
420 {
421   fibnode_t z;
422
423   while ((z = y->parent) != NULL)
424     {
425       if (y->mark == 0)
426         {
427           y->mark = 1;
428           return;
429         }
430       else
431         {
432           fibheap_cut (heap, y, z);
433           y = z;
434         }
435     }
436 }
437
438 static void
439 fibnode_insert_after (fibnode_t a, fibnode_t b)
440 {
441   if (a == a->right)
442     {
443       a->right = b;
444       a->left = b;
445       b->right = a;
446       b->left = a;
447     }
448   else
449     {
450       b->right = a->right;
451       a->right->left = b;
452       a->right = b;
453       b->left = a;
454     }
455 }
456
457 static fibnode_t
458 fibnode_remove (fibnode_t node)
459 {
460   fibnode_t ret;
461
462   if (node == node->left)
463     ret = NULL;
464   else
465     ret = node->left;
466
467   if (node->parent != NULL && node->parent->child == node)
468     node->parent->child = ret;
469
470   node->right->left = node->left;
471   node->left->right = node->right;
472
473   node->parent = NULL;
474   node->left = node;
475   node->right = node;
476
477   return ret;
478 }