gcc 7.2.0

This is imported manually due to a bug in the tarball import script.

See the baserock-dev mailing list archives (November 2017) for a
more detailed explaination of the issue.

1 files changed, 0 insertions, 651 deletions

diff --git a/gcc/fibonacci_heap.h b/gcc/fibonacci_heap.h
deleted file mode 100644
index 554a142c8f..0000000000
--- a/gcc/fibonacci_heap.h
+++ /dev/null
@@ -1,651 +0,0 @@
-/* Fibonacci heap for GNU compiler.
-   Copyright (C) 1998-2017 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, V *data = NULL): m_parent (NULL), m_child (NULL),
-    m_left (this), m_right (this), m_key (key), m_data (data),
-    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 replace_key (fibonacci_node_t *node, K key)
-  {
-    K okey = node->m_key;
-
-    replace_key_data (node, key, node->m_data);
-    return okey;
-  }
-
-  /* For given NODE, decrease value to new KEY.  */
-  K decrease_key (fibonacci_node_t *node, K key)
-  {
-    gcc_assert (key <= node->m_key);
-    return replace_key (node, key);
-  }
-
-  /* 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. If RELEASE is specified,
-     memory is released.  */
-  V *extract_min (bool release = true);
-
-  /* Return value associated with minimum node in the heap.  */
-  V *min ()
-  {
-    if (m_min == NULL)
-      return NULL;
-
-    return m_min->m_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, bool release = true);
-
-  /* Union the heap with HEAPB.  */
-  fibonacci_heap *union_with (fibonacci_heap *heapb);
-
-private:
-  /* Insert new NODE given by KEY and DATA associated with the key.  */
-  fibonacci_node_t *insert (fibonacci_node_t *node, K key, V *data);
-
-  /* Insert new NODE that has already filled key and value.  */
-  fibonacci_node_t *insert_node (fibonacci_node_t *node);
-
-  /* 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 (key, data);
-
-  return insert_node (node);
-}
-
-/* Insert new NODE given by DATA associated with the key.  */
-
-template<class K, class V>
-fibonacci_node<K,V>*
-fibonacci_heap<K,V>::insert (fibonacci_node_t *node, K key, V *data)
-{
-  /* Set the node's data.  */
-  node->m_data = data;
-  node->m_key = key;
-
-  return insert_node (node);
-}
-
-/* Insert new NODE that has already filled key and value.  */
-
-template<class K, class V>
-fibonacci_node<K,V>*
-fibonacci_heap<K,V>::insert_node (fibonacci_node_t *node)
-{
-  /* 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)
-{
-  K okey;
-  fibonacci_node<K,V> *y;
-  V *odata = node->m_data;
-
-  /* If we wanted to, we do a real increase by redeleting and
-     inserting.  */
-  if (node->compare_data (key) > 0)
-    {
-      delete_node (node, false);
-
-      node = new (node) fibonacci_node_t ();
-      insert (node, key, data);
-
-      return odata;
-    }
-
-  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.  Delete fibonacci node if RELEASE
-   is true.  */
-
-template<class K, class V>
-V*
-fibonacci_heap<K,V>::extract_min (bool release)
-{
-  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;
-
-      if (release)
-        delete (z);
-    }
-
-  return ret;
-}
-
-/* Delete NODE in the heap, if RELEASE is specified memory is released.  */
-
-template<class K, class V>
-V*
-fibonacci_heap<K,V>::delete_node (fibonacci_node<K,V> *node, bool release)
-{
-  V *ret = node->m_data;
-
-  /* To perform delete, we just make it the min key, and extract.  */
-  replace_key (node, m_global_min_key);
-  if (node != m_min)
-    {
-      fprintf (stderr, "Can't force minimum on fibheap.\n");
-      abort ();
-    }
-  extract_min (release);
-
-  return ret;
-}
-
-/* Union the heap with HEAPB.  One of the heaps is going to be deleted.  */
-
-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;
-
-  /* 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;
-  std::swap (a_root->m_left, b_root->m_left);
-  heapa->m_nodes += heapb->m_nodes;
-
-  /* And set the new minimum, if it's changed.  */
-  if (heapb->m_min->compare (heapa->m_min) < 0)
-    heapa->m_min = heapb->m_min;
-
-  /* Set m_min to NULL to not to delete live fibonacci nodes.  */
-  heapb->m_min = NULL;
-  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