Import stripped Arm GNU Toolchain 13.2.Rel1HEADumineko

https://developer.arm.com/downloads/-/arm-gnu-toolchain-downloads

Change-Id: I7303388733328cd98ab9aa3c30236db67f2e9e9c

1 files changed, 491 insertions, 0 deletions

diff --git a/lib/gcc/aarch64-none-linux-gnu/13.2.1/plugin/include/splay-tree-utils.h b/lib/gcc/aarch64-none-linux-gnu/13.2.1/plugin/include/splay-tree-utils.h
new file mode 100644
index 0000000..f0f795a
--- /dev/null
+++ b/lib/gcc/aarch64-none-linux-gnu/13.2.1/plugin/include/splay-tree-utils.h
@@ -0,0 +1,491 @@
+// Splay tree utilities                                             -*- C++ -*-
+// Copyright (C) 2020-2023 Free Software Foundation, Inc.
+//
+// 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/>.
+
+// Implement splay tree node accessors for a class that stores its
+// two child nodes in a member variable of the form:
+//
+//    Node m_children[2];
+template<typename Node>
+class default_splay_tree_accessors
+{
+public:
+  using node_type = Node;
+
+  static auto
+  child (node_type node, unsigned int index)
+    -> decltype (node->m_children[index]) &
+  {
+    return node->m_children[index];
+  }
+};
+
+// Implement splay tree node accessors for a class that stores its
+// two child nodes in a member variable of the form:
+//
+//    Node m_children[2];
+//
+// and also stores its parent node in a member variable of the form:
+//
+//    Node m_parent;
+template<typename Node>
+class default_splay_tree_accessors_with_parent
+  : public default_splay_tree_accessors<Node>
+{
+public:
+  using node_type = Node;
+
+  static auto
+  parent (node_type node) -> decltype (node->m_parent) &
+  {
+    return node->m_parent;
+  }
+};
+
+// Base is a splay tree accessor class for nodes that have no parent field.
+// Base therefore provides a Base::child method but does not provide a
+// Base::parent method.  Extend Base with dummy routines for setting the
+// parent, which is a no-op when the parent is not stored.
+template<typename Base>
+class splay_tree_accessors_without_parent : public Base
+{
+public:
+  using typename Base::node_type;
+
+  static void set_parent (node_type, node_type) {}
+};
+
+// Base is splay tree accessor class for nodes that have a parent field.
+// Base therefore provides both Base::child and Base::parent methods.
+// Extend Base with routines for setting the parent.
+template<typename Base>
+class splay_tree_accessors_with_parent : public Base
+{
+public:
+  using typename Base::node_type;
+
+  // Record that NODE's parent is now NEW_PARENT.
+  static void
+  set_parent (node_type node, node_type new_parent)
+  {
+    Base::parent (node) = new_parent;
+  }
+};
+
+// A base class that provides some splay tree operations that are common
+// to both rooted_splay_tree and rootless_splay_tree.
+//
+// Nodes in the splay tree have type Accessors::node_type; this is
+// usually a pointer type.  The Accessors class provides the following
+// static member functions for accessing nodes:
+//
+// - Accessors::child (NODE, INDEX)
+//     INDEX is guaranteed to be 0 or 1.  If INDEX is 0, return a reference
+//     to where NODE's left child is stored, otherwise return a reference
+//     to where NODE's right child is stored.
+//
+// - Accessors::set_parent (NODE, PARENT)
+//     Record that NODE's parent node is now PARENT.
+template<typename Accessors>
+class base_splay_tree : protected Accessors
+{
+public:
+  using typename Accessors::node_type;
+
+  // INDEX is either 0 or 1.  If INDEX is 0, insert CHILD immediately
+  // before NODE, otherwise insert CHILD immediately after NODE.
+  //
+  // Complexity: O(1).
+  static void insert_child (node_type node, unsigned int index,
+			    node_type child);
+
+  // Print NODE and its child nodes to PP for debugging purposes,
+  // using PRINTER (PP, N) to print the data for node N.
+  template<typename Printer>
+  static void print (pretty_printer *pp, node_type node, Printer printer);
+
+protected:
+  using Accessors::set_parent;
+
+  static node_type get_child (node_type, unsigned int);
+  static void set_child (node_type, unsigned int, node_type);
+  static node_type promote_child (node_type, unsigned int);
+  static void promote_child (node_type, unsigned int, node_type);
+
+  template<unsigned int N>
+  static node_type splay_limit (node_type);
+
+  static node_type remove_node_internal (node_type);
+
+  template<typename Printer>
+  static void print (pretty_printer *pp, node_type node, Printer printer,
+		     char, vec<char> &);
+};
+
+// This class provides splay tree routines for cases in which the root
+// of the splay tree is known.  It works with both nodes that store
+// their parent node and nodes that don't.
+//
+// The class is lightweight: it only contains a single root node.
+template<typename Accessors>
+class rooted_splay_tree : public base_splay_tree<Accessors>
+{
+  using parent = base_splay_tree<Accessors>;
+
+public:
+  using typename Accessors::node_type;
+
+protected:
+  // The root of the splay tree, or node_type () if the tree is empty.
+  node_type m_root;
+
+public:
+  rooted_splay_tree () : m_root () {}
+
+  // Construct a tree with the specified root node.
+  rooted_splay_tree (node_type root) : m_root (root) {}
+
+  // Return the root of the tree.
+  node_type root () const { return m_root; }
+
+  // Return true if the tree contains any nodes.
+  explicit operator bool () const { return m_root; }
+
+  // Dereference the root node.
+  node_type operator-> () { return m_root; }
+
+  // Insert NEW_NODE into the splay tree, if no equivalent node already
+  // exists.  For a given node N, COMPARE (N) should return:
+  //
+  // - a negative value if NEW_NODE should come before N
+  // - zero if NEW_NODE and N are the same
+  // - a positive value if NEW_NODE should come after N
+  //
+  // Return true if NEW_NODE was inserted.
+  //
+  // On return, NEW_NODE or its equivalent is the root of the tree.
+  //
+  // Complexity: amortized O(C log N), worst-cast O(C N), where C is
+  // the complexity of the comparison.
+  template<typename Comparator>
+  bool insert (node_type new_node, Comparator compare);
+
+  // Insert NEW_NODE into the splay tree, given that NEW_NODE is the
+  // maximum node of the new tree.  On return, NEW_NODE is also the
+  // root of the tree.
+  //
+  // Complexity: O(1).
+  void insert_max_node (node_type new_node);
+
+  // Splice NEXT_TREE onto this one, given that all nodes in NEXT_TREE
+  // are greater than the maximum node in this tree.  NEXT_TREE should
+  // not be used afterwards.
+  //
+  // Complexity: O(1) if the root of the splay tree is already the maximum
+  // node.  Otherwise amortized O(log N), worst-cast O(N).
+  void splice_next_tree (rooted_splay_tree next_tree);
+
+  // The root of the tree is currently the maximum node.  Replace it
+  // with NEW_NODE.
+  //
+  // Complexity: O(1).
+  void replace_max_node_at_root (node_type new_node);
+
+  // Remove the root node of the splay tree.
+  //
+  // Complexity: O(1) if removing the maximum or minimum node.
+  // Otherwise amortized O(log N), worst-cast O(N).
+  void remove_root ();
+
+  // Split the left child of the current root out into a separate tree
+  // and return the new tree.
+  rooted_splay_tree split_before_root ();
+
+  // Split the right child of the current root out into a separate tree
+  // and return the new tree.
+  rooted_splay_tree split_after_root ();
+
+  // If the root is not the minimum node of the splay tree, bring the previous
+  // node to the root and return true, otherwise return false.
+  //
+  // Complexity: amortized O(log N), worst-cast O(N).
+  bool splay_prev_node ();
+
+  // If the root is not the maximum node of the splay tree, bring the next
+  // node to the root and return true, otherwise return false.
+  //
+  // Complexity: amortized O(log N), worst-cast O(N).
+  bool splay_next_node ();
+
+  // Bring the minimum node of the splay tree to the root.
+  //
+  // Complexity: amortized O(log N), worst-cast O(N).
+  void splay_min_node ();
+
+  // Bring the maximum node of the splay tree to the root.
+  //
+  // Complexity: amortized O(log N), worst-cast O(N).
+  void splay_max_node ();
+
+  // Return the minimum node of the splay tree, or node_type () if the
+  // tree is empty.  On return, the minimum node (if any) is also the
+  // root of the tree.
+  //
+  // Complexity: amortized O(log N), worst-cast O(N).
+  node_type min_node ();
+
+  // Return the maximum node of the splay tree, or node_type () if the
+  // tree is empty.  On return, the maximum node (if any) is also the
+  // root of the tree.
+  //
+  // Complexity: amortized O(log N), worst-cast O(N).
+  node_type max_node ();
+
+  // Search the splay tree.  For a given node N, COMPARE (N) should return:
+  //
+  // - a negative value if N is bigger than the node being searched for
+  // - zero if N is the node being searched for
+  // - a positive value if N is smaller than the node being searched for
+  //
+  // If the node that COMPARE is looking for exists, install it as the root
+  // node of the splay tree.  Otherwise, arbitrarily pick either:
+  //
+  // - the maximum node that is smaller than the node being searched for or
+  // - the minimum node that is bigger than the node being searched for
+  //
+  // and install that node as the root instead.
+  //
+  // Return the result of COMPARE for the new root.
+  //
+  // This form of lookup is intended for cases in which both the following
+  // are true:
+  //
+  // (a) The work that COMPARE needs to do to detect if a node is too big
+  //     is the same as the work that COMPARE needs to do to detect if a
+  //     node is too small.  (This is not true of range comparisons,
+  //     for example.)
+  //
+  // (b) COMPARE is (or might be) relatively complex.
+  //
+  // This form of lookup is also useful if the items being compared naturally
+  // provide a <=>-style comparison result, without the result having to be
+  // forced by the equivalent of a ?: expression.
+  //
+  // The implementation only invokes COMPARE once per node.
+  //
+  // Complexity: amortized O(C log N), worst-cast O(C N), where C is
+  // the complexity of the comparison.
+  template<typename Comparator>
+  auto lookup (Comparator compare) -> decltype (compare (m_root));
+
+  // Search the splay tree.  For a given node N, WANT_SOMETHING_SMALLER (N)
+  // is true if N is too big and WANT_SOMETHING_BIGGER (N) is true if N
+  // is too small.  Both functions return false if N is the node being
+  // searched for.
+  //
+  // If the node that is being searched for exists, install it as the root
+  // node of the splay tree and return 0.  Otherwise, arbitrarily choose
+  // between these two options:
+  //
+  // - Install the maximum node that is smaller than the node being
+  //   searched for as the root of the splay tree and return 1.
+  //
+  // - Install the minimum node that is bigger than the node being
+  //   searched for and return -1.
+  //
+  // This form of lookup is intended for cases in which either of the
+  // following are true:
+  //
+  // (a) WANT_SOMETHING_SMALLER and WANT_SOMETHING_BIGGER test different
+  //     parts of the node's data.  For example, when comparing ranges,
+  //     WANT_SOMETHING_SMALLER would test the lower limit of the given
+  //     node's range while WANT_SOMETHING_BIGGER would test the upper
+  //     limit of the given node's range.
+  //
+  // (b) There is no significant overhead to calling both
+  //     WANT_SOMETHING_SMALLER and WANT_SOMETHING_BIGGER for the same node.
+  //
+  // Complexity: amortized O(C log N), worst-cast O(C N), where C is
+  // the complexity of the comparisons.
+  template<typename LeftPredicate, typename RightPredicate>
+  int lookup (LeftPredicate want_something_smaller,
+	      RightPredicate want_something_bigger);
+
+  // Keep the ability to print subtrees.
+  using parent::print;
+
+  // Print the tree to PP for debugging purposes, using PRINTER (PP, N)
+  // to print the data for node N.
+  template<typename Printer>
+  void print (pretty_printer *pp, Printer printer) const;
+
+protected:
+  using parent::get_child;
+  using parent::set_child;
+  using parent::promote_child;
+
+  using parent::set_parent;
+
+  template<unsigned int N>
+  bool splay_neighbor ();
+};
+
+// Provide splay tree routines for nodes of type Accessors::node_type,
+// which doesn't have a parent field.  Use Accessors::child to access
+// the children of a node.
+template<typename Accessors>
+using splay_tree_without_parent
+  = rooted_splay_tree<splay_tree_accessors_without_parent<Accessors>>;
+
+// A splay tree for nodes of type Node, which is usually a pointer type.
+// The child nodes are stored in a member variable:
+//
+//    Node m_children[2];
+//
+// Node does not have a parent field.
+template<typename Node>
+using default_splay_tree
+  = splay_tree_without_parent<default_splay_tree_accessors<Node>>;
+
+// A simple splay tree node that stores a value of type T.
+template<typename T>
+class splay_tree_node
+{
+  friend class default_splay_tree_accessors<splay_tree_node *>;
+
+public:
+  splay_tree_node () = default;
+  splay_tree_node (T value) : m_value (value), m_children () {}
+
+  T &value () { return m_value; }
+  const T &value () const { return m_value; }
+
+private:
+  T m_value;
+  splay_tree_node *m_children[2];
+};
+
+// A splay tree whose nodes hold values of type T.
+template<typename T>
+using splay_tree = default_splay_tree<splay_tree_node<T> *>;
+
+// Provide splay tree routines for cases in which the root of the tree
+// is not explicitly stored.
+//
+// The nodes of the tree have type Accessors::node_type, which is usually
+// a pointer type.  The nodes have a link back to their parent.
+//
+// The Accessors class provides the following static member functions:
+//
+// - Accessors::child (NODE, INDEX)
+//     INDEX is guaranteed to be 0 or 1.  If INDEX is 0, return a reference
+//     to where NODE's left child is stored, otherwise return a reference
+//     to where NODE's right child is stored.
+//
+// - Accessors::parent (NODE)
+//     Return a reference to where NODE's parent is stored.
+template<typename Accessors>
+class rootless_splay_tree
+  : public base_splay_tree<splay_tree_accessors_with_parent<Accessors>>
+{
+  using full_accessors = splay_tree_accessors_with_parent<Accessors>;
+  using parent = base_splay_tree<full_accessors>;
+
+public:
+  using rooted = rooted_splay_tree<full_accessors>;
+
+  using typename Accessors::node_type;
+
+  // Remove NODE from the splay tree.  Return the node that replaces it,
+  // or null if NODE had no children.
+  //
+  // Complexity: O(1) if removing the maximum or minimum node.
+  // Otherwise amortized O(log N), worst-cast O(N).
+  static node_type remove_node (node_type node);
+
+  // Splay NODE so that it becomes the root of the splay tree.
+  //
+  // Complexity: amortized O(log N), worst-cast O(N).
+  static void splay (node_type node);
+
+  // Like splay, but take advantage of the fact that NODE is known to be
+  // the minimum node in the tree.
+  //
+  // Complexity: amortized O(log N), worst-cast O(N).
+  static void splay_known_min_node (node_type node);
+
+  // Like splay, but take advantage of the fact that NODE is known to be
+  // the maximum node in the tree.
+  //
+  // Complexity: amortized O(log N), worst-cast O(N).
+  static void splay_known_max_node (node_type node);
+
+  // Splay NODE while looking for an ancestor node N for which PREDICATE (N)
+  // is true.  If such an ancestor node exists, stop the splay operation
+  // early and return PREDICATE (N).  Otherwise, complete the splay operation
+  // and return DEFAULT_RESULT.  In the latter case, NODE is now the root of
+  // the splay tree.
+  //
+  // Note that this routine only examines nodes that happen to be ancestors
+  // of NODE.  It does not search the full tree.
+  //
+  // Complexity: amortized O(P log N), worst-cast O(P N), where P is the
+  // complexity of the predicate.
+  template<typename DefaultResult, typename Predicate>
+  static auto splay_and_search (node_type node, DefaultResult default_result,
+				Predicate predicate)
+    -> decltype (predicate (node, 0));
+
+  // NODE1 and NODE2 are known to belong to the same splay tree.  Return:
+  //
+  // -1 if NODE1 < NODE2
+  // 0 if NODE1 == NODE2
+  // 1 if NODE1 > NODE2
+  //
+  // Complexity: amortized O(log N), worst-cast O(N).
+  static int compare_nodes (node_type node1, node_type node2);
+
+protected:
+  using parent::get_child;
+  using parent::set_child;
+  using parent::promote_child;
+
+  static node_type get_parent (node_type);
+  using parent::set_parent;
+
+  static unsigned int child_index (node_type, node_type);
+
+  static int compare_nodes_one_way (node_type, node_type);
+
+  template<unsigned int N>
+  static void splay_known_limit (node_type);
+};
+
+// Provide rootless splay tree routines for nodes of type Node.
+// The child nodes are stored in a member variable:
+//
+//    Node m_children[2];
+//
+// and the parent node is stored in a member variable:
+//
+//    Node m_parent;
+template<typename Node>
+using default_rootless_splay_tree
+  = rootless_splay_tree<default_splay_tree_accessors_with_parent<Node>>;
+
+#include "splay-tree-utils.tcc"