1/* A Fibonacci heap datatype.
2   Copyright 1998, 1999, 2000, 2001 Free Software Foundation, Inc.
3   Contributed by Daniel Berlin (dan@cgsoftware.com).
4
5This file is part of GNU CC.
6
7GNU CC is free software; you can redistribute it and/or modify it
8under the terms of the GNU General Public License as published by
9the Free Software Foundation; either version 2, or (at your option)
10any later version.
11
12GNU CC is distributed in the hope that it will be useful, but
13WITHOUT ANY WARRANTY; without even the implied warranty of
14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
15General Public License for more details.
16
17You should have received a copy of the GNU General Public License
18along with GNU CC; see the file COPYING.  If not, write to
19the Free Software Foundation, 51 Franklin Street - Fifth Floor,
20Boston, 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
40static void fibheap_ins_root (fibheap_t, fibnode_t);
41static void fibheap_rem_root (fibheap_t, fibnode_t);
42static void fibheap_consolidate (fibheap_t);
43static void fibheap_link (fibheap_t, fibnode_t, fibnode_t);
44static void fibheap_cut (fibheap_t, fibnode_t, fibnode_t);
45static void fibheap_cascading_cut (fibheap_t, fibnode_t);
46static fibnode_t fibheap_extr_min_node (fibheap_t);
47static int fibheap_compare (fibheap_t, fibnode_t, fibnode_t);
48static int fibheap_comp_data (fibheap_t, fibheapkey_t, void *, fibnode_t);
49static fibnode_t fibnode_new (void);
50static void fibnode_insert_after (fibnode_t, fibnode_t);
51#define fibnode_insert_before(a, b) fibnode_insert_after (a->left, b)
52static fibnode_t fibnode_remove (fibnode_t);
53
54
55/* Create a new fibonacci heap.  */
56fibheap_t
57fibheap_new (void)
58{
59  return (fibheap_t) xcalloc (1, sizeof (struct fibheap));
60}
61
62/* Create a new fibonacci heap node.  */
63static fibnode_t
64fibnode_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
75static inline int
76fibheap_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
85static inline int
86fibheap_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.  */
97fibnode_t
98fibheap_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).  */
123void *
124fibheap_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).  */
133fibheapkey_t
134fibheap_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.  */
143fibheap_t
144fibheap_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.  */
177void *
178fibheap_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.  */
197void *
198fibheap_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.  */
236void *
237fibheap_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.  */
243fibheapkey_t
244fibheap_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.  */
252void *
253fibheap_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.  */
265void
266fibheap_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.  */
275int
276fibheap_empty (fibheap_t heap)
277{
278  return heap->nodes == 0;
279}
280
281/* Extract the minimum node of the heap.  */
282static fibnode_t
283fibheap_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.  */
318static void
319fibheap_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.  */
337static void
338fibheap_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.  */
347static void
348fibheap_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.  */
394static void
395fibheap_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.  */
408static void
409fibheap_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
418static void
419fibheap_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
438static void
439fibnode_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
457static fibnode_t
458fibnode_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}
479