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  /* 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.  */
239void *
240fibheap_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.  */
246fibheapkey_t
247fibheap_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.  */
255void *
256fibheap_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.  */
273void
274fibheap_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.  */
283int
284fibheap_empty (fibheap_t heap)
285{
286  return heap->nodes == 0;
287}
288
289/* Extract the minimum node of the heap.  */
290static fibnode_t
291fibheap_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.  */
326static void
327fibheap_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.  */
345static void
346fibheap_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.  */
355static void
356fibheap_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.  */
402static void
403fibheap_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.  */
416static void
417fibheap_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
426static void
427fibheap_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
446static void
447fibnode_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
465static fibnode_t
466fibnode_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