New template fibonacci_heap class introduced.

	* fibonacci_heap.h: New file.
	(fibonacci_heap::insert): Created from fibheap_insert.
	(fibonacci_heap::empty): Created from fibheap_empty.
	(fibonacci_heap::nodes): Created from fibheap_nodes.
	(fibonacci_heap::min_key): Created from fibheap_min_key.
	(fibonacci_heap::decrease_key): Created from fibheap_replace_key.
	(fibonacci_heap::replace_key_data): Created from fibheap_replace_key_data.
	(fibonacci_heap::extract_min): Created from fibheap_extract_min.
	(fibonacci_heap::min): Created from fibheap_min.
	(fibonacci_heap::replace_data): Created from fibheap_replace_data.
	(fibonacci_heap::delete_node): Created from fibheap_delete_node.
	(fibonacci_heap::union_with): Created from fibheap_union.
	* ipa-inline.c (update_edge_key): New heap API is used.
	(update_caller_keys): Likewise.
	(update_callee_keys): Likewise.
	(lookup_recursive_calls): Likewise.
	(recursive_inlining): Likewise.
	(add_new_edges_to_heap): Likewise.
	(heap_edge_removal_hook): Likewise.
	(inline_small_functions): Likewise.


git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@217720 138bc75d-0d04-0410-961f-82ee72b054a4

1 files changed, 608 insertions, 0 deletions

diff --git a/gcc/fibonacci_heap.h b/gcc/fibonacci_heap.h
new file mode 100644
index 00000000000..ecb92f8b01f
--- /dev/null
+++ b/gcc/fibonacci_heap.h
@@ -0,0 +1,608 @@
+/* Vector API for GNU compiler.
+   Copyright (C) 1998-2014 Free Software Foundation, Inc.
+   Contributed by Daniel Berlin (dan@cgsoftware.com).
+   Re-implemented in C++ by Martin Liska <mliska@suse.cz>
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free
+Software Foundation; either version 3, or (at your option) any later
+version.
+
+GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */
+
+/* Fibonacci heaps are somewhat complex, but, there's an article in
+   DDJ that explains them pretty well:
+
+   http://www.ddj.com/articles/1997/9701/9701o/9701o.htm?topic=algoritms
+
+   Introduction to algorithms by Corman and Rivest also goes over them.
+
+   The original paper that introduced them is "Fibonacci heaps and their
+   uses in improved network optimization algorithms" by Tarjan and
+   Fredman (JACM 34(3), July 1987).
+
+   Amortized and real worst case time for operations:
+
+   ExtractMin: O(lg n) amortized. O(n) worst case.
+   DecreaseKey: O(1) amortized.  O(lg n) worst case.
+   Insert: O(1) amortized.
+   Union: O(1) amortized.  */
+
+#ifndef GCC_FIBONACCI_HEAP_H
+#define GCC_FIBONACCI_HEAP_H
+
+/* Forward definition.  */
+
+template<class K, class V>
+class fibonacci_heap;
+
+/* Fibonacci heap node class.  */
+
+template<class K, class V>
+class fibonacci_node
+{
+  typedef fibonacci_node<K,V> fibonacci_node_t;
+  friend class fibonacci_heap<K,V>;
+
+public:
+  /* Default constructor.  */
+  fibonacci_node (): m_parent (NULL), m_child (NULL), m_left (this),
+    m_right (this), m_degree (0), m_mark (0)
+  {
+  }
+
+  /* Constructor for a node with given KEY.  */
+  fibonacci_node (K key): m_parent (NULL), m_child (NULL), m_left (this),
+    m_right (this), m_key (key),
+    m_degree (0), m_mark (0)
+  {
+  }
+
+  /* Compare fibonacci node with OTHER node.  */
+  int compare (fibonacci_node_t *other)
+  {
+    if (m_key < other->m_key)
+      return -1;
+    if (m_key > other->m_key)
+      return 1;
+    return 0;
+  }
+
+  /* Compare the node with a given KEY.  */
+  int compare_data (K key)
+  {
+    return fibonacci_node_t (key).compare (this);
+  }
+
+  /* Remove fibonacci heap node.  */
+  fibonacci_node_t *remove ();
+
+  /* Link the node with PARENT.  */
+  void link (fibonacci_node_t *parent);
+
+  /* Return key associated with the node.  */
+  K get_key ()
+  {
+    return m_key;
+  }
+
+  /* Return data associated with the node.  */
+  V *get_data ()
+  {
+    return m_data;
+  }
+
+private:
+  /* Put node B after this node.  */
+  void insert_after (fibonacci_node_t *b);
+
+  /* Insert fibonacci node B after this node.  */
+  void insert_before (fibonacci_node_t *b)
+  {
+    m_left->insert_after (b);
+  }
+
+  /* Parent node.  */
+  fibonacci_node *m_parent;
+  /* Child node.  */
+  fibonacci_node *m_child;
+  /* Left sibling.  */
+  fibonacci_node *m_left;
+  /* Right node.  */
+  fibonacci_node *m_right;
+  /* Key associated with node.  */
+  K m_key;
+  /* Data associated with node.  */
+  V *m_data;
+
+#if defined (__GNUC__) && (!defined (SIZEOF_INT) || SIZEOF_INT < 4)
+  /* Degree of the node.  */
+  __extension__ unsigned long int m_degree : 31;
+  /* Mark of the node.  */
+  __extension__ unsigned long int m_mark : 1;
+#else
+  /* Degree of the node.  */
+  unsigned int m_degree : 31;
+  /* Mark of the node.  */
+  unsigned int m_mark : 1;
+#endif
+};
+
+/* Fibonacci heap class. */
+template<class K, class V>
+class fibonacci_heap
+{
+  typedef fibonacci_node<K,V> fibonacci_node_t;
+  friend class fibonacci_node<K,V>;
+
+public:
+  /* Default constructor.  */
+  fibonacci_heap (K global_min_key): m_nodes (0), m_min (NULL), m_root (NULL),
+    m_global_min_key (global_min_key)
+  {
+  }
+
+  /* Destructor.  */
+  ~fibonacci_heap ()
+  {
+    while (m_min != NULL)
+      delete (extract_minimum_node ());
+  }
+
+  /* Insert new node given by KEY and DATA associated with the key.  */
+  fibonacci_node_t *insert (K key, V *data);
+
+  /* Return true if no entry is present.  */
+  bool empty ()
+  {
+    return m_nodes == 0;
+  }
+
+  /* Return the number of nodes.  */
+  size_t nodes ()
+  {
+    return m_nodes;
+  }
+
+  /* Return minimal key presented in the heap.  */
+  K min_key ()
+  {
+    if (m_min == NULL)
+      gcc_unreachable ();
+
+    return m_min->m_key;
+  }
+
+  /* For given NODE, set new KEY value.  */
+  K decrease_key (fibonacci_node_t *node, K key)
+  {
+    K okey = node->m_key;
+    gcc_assert (key <= okey);
+
+    replace_key_data (node, key, node->m_data);
+    return okey;
+  }
+
+  /* For given NODE, set new KEY and DATA value.  */
+  V *replace_key_data (fibonacci_node_t *node, K key, V *data);
+
+  /* Extract minimum node in the heap. */
+  V *extract_min ();
+
+  /* Return value associated with minimum node in the heap.  */
+  V *min ()
+  {
+    if (m_min == NULL)
+      return NULL;
+
+    return m_min->data;
+  }
+
+  /* Replace data associated with NODE and replace it with DATA.  */
+  V *replace_data (fibonacci_node_t *node, V *data)
+  {
+    return replace_key_data (node, node->m_key, data);
+  }
+
+  /* Delete NODE in the heap.  */
+  V *delete_node (fibonacci_node_t *node);
+
+  /* Union the heap with HEAPB.  */
+  fibonacci_heap *union_with (fibonacci_heap *heapb);
+
+private:
+  /* Insert it into the root list.  */
+  void insert_root (fibonacci_node_t *node);
+
+  /* Remove NODE from PARENT's child list.  */
+  void cut (fibonacci_node_t *node, fibonacci_node_t *parent);
+
+  /* Process cut of node Y and do it recursivelly.  */
+  void cascading_cut (fibonacci_node_t *y);
+
+  /* Extract minimum node from the heap.  */
+  fibonacci_node_t * extract_minimum_node ();
+
+  /* Remove root NODE from the heap.  */
+  void remove_root (fibonacci_node_t *node);
+
+  /* Consolidate heap.  */
+  void consolidate ();
+
+  /* Number of nodes.  */
+  size_t m_nodes;
+  /* Minimum node of the heap.  */
+  fibonacci_node_t *m_min;
+  /* Root node of the heap.  */
+  fibonacci_node_t *m_root;
+  /* Global minimum given in the heap construction.  */
+  K m_global_min_key;
+};
+
+/* Remove fibonacci heap node.  */
+
+template<class K, class V>
+fibonacci_node<K,V> *
+fibonacci_node<K,V>::remove ()
+{
+  fibonacci_node<K,V> *ret;
+
+  if (this == m_left)
+    ret = NULL;
+  else
+    ret = m_left;
+
+  if (m_parent != NULL && m_parent->m_child == this)
+    m_parent->m_child = ret;
+
+  m_right->m_left = m_left;
+  m_left->m_right = m_right;
+
+  m_parent = NULL;
+  m_left = this;
+  m_right = this;
+
+  return ret;
+}
+
+/* Link the node with PARENT.  */
+
+template<class K, class V>
+void
+fibonacci_node<K,V>::link (fibonacci_node<K,V> *parent)
+{
+  if (parent->m_child == NULL)
+    parent->m_child = this;
+  else
+    parent->m_child->insert_before (this);
+  m_parent = parent;
+  parent->m_degree++;
+  m_mark = 0;
+}
+
+/* Put node B after this node.  */
+
+template<class K, class V>
+void
+fibonacci_node<K,V>::insert_after (fibonacci_node<K,V> *b)
+{
+  fibonacci_node<K,V> *a = this;
+
+  if (a == a->m_right)
+    {
+      a->m_right = b;
+      a->m_left = b;
+      b->m_right = a;
+      b->m_left = a;
+    }
+  else
+    {
+      b->m_right = a->m_right;
+      a->m_right->m_left = b;
+      a->m_right = b;
+      b->m_left = a;
+    }
+}
+
+/* Insert new node given by KEY and DATA associated with the key.  */
+
+template<class K, class V>
+fibonacci_node<K,V>*
+fibonacci_heap<K,V>::insert (K key, V *data)
+{
+  /* Create the new node.  */
+  fibonacci_node<K,V> *node = new fibonacci_node_t ();
+
+  /* Set the node's data.  */
+  node->m_data = data;
+  node->m_key = key;
+
+  /* Insert it into the root list.  */
+  insert_root (node);
+
+  /* If their was no minimum, or this key is less than the min,
+     it's the new min.  */
+  if (m_min == NULL || node->m_key < m_min->m_key)
+    m_min = node;
+
+  m_nodes++;
+
+  return node;
+}
+
+/* For given NODE, set new KEY and DATA value.  */
+template<class K, class V>
+V*
+fibonacci_heap<K,V>::replace_key_data (fibonacci_node<K,V> *node, K key,
+				       V *data)
+{
+  V *odata;
+  K okey;
+  fibonacci_node<K,V> *y;
+
+  /* If we wanted to, we could actually do a real increase by redeleting and
+     inserting. However, this would require O (log n) time. So just bail out
+     for now.  */
+  if (node->compare_data (key) > 0)
+    return NULL;
+
+  odata = node->m_data;
+  okey = node->m_key;
+  node->m_data = data;
+  node->m_key = key;
+  y = node->m_parent;
+
+  /* Short-circuit if the key is the same, as we then don't have to
+     do anything.  Except if we're trying to force the new node to
+     be the new minimum for delete.  */
+  if (okey == key && okey != m_global_min_key)
+    return odata;
+
+  /* These two compares are specifically <= 0 to make sure that in the case
+     of equality, a node we replaced the data on, becomes the new min.  This
+     is needed so that delete's call to extractmin gets the right node.  */
+  if (y != NULL && node->compare (y) <= 0)
+    {
+      cut (node, y);
+      cascading_cut (y);
+    }
+
+  if (node->compare (m_min) <= 0)
+    m_min = node;
+
+  return odata;
+}
+
+/* Extract minimum node in the heap.  */
+template<class K, class V>
+V*
+fibonacci_heap<K,V>::extract_min ()
+{
+  fibonacci_node<K,V> *z;
+  V *ret = NULL;
+
+  /* If we don't have a min set, it means we have no nodes.  */
+  if (m_min != NULL)
+    {
+      /* Otherwise, extract the min node, free the node, and return the
+       node's data.  */
+      z = extract_minimum_node ();
+      ret = z->m_data;
+      delete (z);
+    }
+
+  return ret;
+}
+
+/* Delete NODE in the heap.  */
+
+template<class K, class V>
+V*
+fibonacci_heap<K,V>::delete_node (fibonacci_node<K,V> *node)
+{
+  V *ret = node->m_data;
+
+  /* To perform delete, we just make it the min key, and extract.  */
+  decrease_key (node, m_global_min_key);
+  if (node != m_min)
+    {
+      fprintf (stderr, "Can't force minimum on fibheap.\n");
+      abort ();
+    }
+  extract_min ();
+
+  return ret;
+}
+
+/* Union the heap with HEAPB.  */
+
+template<class K, class V>
+fibonacci_heap<K,V>*
+fibonacci_heap<K,V>::union_with (fibonacci_heap<K,V> *heapb)
+{
+  fibonacci_heap<K,V> *heapa = this;
+
+  fibonacci_node<K,V> *a_root, *b_root, *temp;
+
+  /* If one of the heaps is empty, the union is just the other heap.  */
+  if ((a_root = heapa->m_root) == NULL)
+    {
+      delete (heapa);
+      return heapb;
+    }
+  if ((b_root = heapb->m_root) == NULL)
+    {
+      delete (heapb);
+      return heapa;
+    }
+
+  /* Merge them to the next nodes on the opposite chain.  */
+  a_root->m_left->m_right = b_root;
+  b_root->m_left->m_right = a_root;
+  temp = a_root->m_left;
+  a_root->m_left = b_root->m_left;
+  b_root->m_left = temp;
+  heapa->m_nodes += heapb->m_nodes;
+
+  /* And set the new minimum, if it's changed.  */
+  if (heapb->min->compare (heapa->min) < 0)
+    heapa->m_min = heapb->m_min;
+
+  delete (heapb);
+  return heapa;
+}
+
+/* Insert it into the root list.  */
+
+template<class K, class V>
+void
+fibonacci_heap<K,V>::insert_root (fibonacci_node_t *node)
+{
+  /* If the heap is currently empty, the new node becomes the singleton
+     circular root list.  */
+  if (m_root == NULL)
+    {
+      m_root = node;
+      node->m_left = node;
+      node->m_right = node;
+      return;
+    }
+
+  /* Otherwise, insert it in the circular root list between the root
+     and it's right node.  */
+  m_root->insert_after (node);
+}
+
+/* Remove NODE from PARENT's child list.  */
+
+template<class K, class V>
+void
+fibonacci_heap<K,V>::cut (fibonacci_node<K,V> *node,
+			  fibonacci_node<K,V> *parent)
+{
+  node->remove ();
+  parent->m_degree--;
+  insert_root (node);
+  node->m_parent = NULL;
+  node->m_mark = 0;
+}
+
+/* Process cut of node Y and do it recursivelly.  */
+
+template<class K, class V>
+void
+fibonacci_heap<K,V>::cascading_cut (fibonacci_node<K,V> *y)
+{
+  fibonacci_node<K,V> *z;
+
+  while ((z = y->m_parent) != NULL)
+    {
+      if (y->m_mark == 0)
+	{
+	  y->m_mark = 1;
+	  return;
+	}
+      else
+	{
+	  cut (y, z);
+	  y = z;
+	}
+    }
+}
+
+/* Extract minimum node from the heap.  */
+template<class K, class V>
+fibonacci_node<K,V>*
+fibonacci_heap<K,V>::extract_minimum_node ()
+{
+  fibonacci_node<K,V> *ret = m_min;
+  fibonacci_node<K,V> *x, *y, *orig;
+
+  /* Attach the child list of the minimum node to the root list of the heap.
+     If there is no child list, we don't do squat.  */
+  for (x = ret->m_child, orig = NULL; x != orig && x != NULL; x = y)
+    {
+      if (orig == NULL)
+	orig = x;
+      y = x->m_right;
+      x->m_parent = NULL;
+      insert_root (x);
+    }
+
+  /* Remove the old root.  */
+  remove_root (ret);
+  m_nodes--;
+
+  /* If we are left with no nodes, then the min is NULL.  */
+  if (m_nodes == 0)
+    m_min = NULL;
+  else
+    {
+      /* Otherwise, consolidate to find new minimum, as well as do the reorg
+       work that needs to be done.  */
+      m_min = ret->m_right;
+      consolidate ();
+    }
+
+  return ret;
+}
+
+/* Remove root NODE from the heap.  */
+
+template<class K, class V>
+void
+fibonacci_heap<K,V>::remove_root (fibonacci_node<K,V> *node)
+{
+  if (node->m_left == node)
+    m_root = NULL;
+  else
+    m_root = node->remove ();
+}
+
+/* Consolidate heap.  */
+
+template<class K, class V>
+void fibonacci_heap<K,V>::consolidate ()
+{
+  int D = 1 + 8 * sizeof (long);
+  auto_vec<fibonacci_node<K,V> *> a (D);
+  a.safe_grow_cleared (D);
+  fibonacci_node<K,V> *w, *x, *y;
+  int i, d;
+
+  while ((w = m_root) != NULL)
+    {
+      x = w;
+      remove_root (w);
+      d = x->m_degree;
+      while (a[d] != NULL)
+	{
+	  y = a[d];
+	  if (x->compare (y) > 0)
+	    std::swap (x, y);
+	  y->link (x);
+	  a[d] = NULL;
+	  d++;
+	}
+      a[d] = x;
+    }
+  m_min = NULL;
+  for (i = 0; i < D; i++)
+    if (a[i] != NULL)
+      {
+	insert_root (a[i]);
+	if (m_min == NULL || a[i]->compare (m_min) < 0)
+	  m_min = a[i];
+      }
+}
+
+#endif  // GCC_FIBONACCI_HEAP_H