--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/gcc/typed-splay-tree.h	Fri Oct 27 22:46:09 2017 +0900
@@ -0,0 +1,197 @@
+/* A typesafe wrapper around libiberty's splay-tree.h.
+   Copyright (C) 2015-2017 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/>.  */
+
+#ifndef GCC_TYPED_SPLAY_TREE_H
+#define GCC_TYPED_SPLAY_TREE_H
+
+#include "splay-tree.h"
+
+/* Typesafe wrapper around libiberty's splay-tree.h.  */
+template <typename KEY_TYPE, typename VALUE_TYPE>
+class typed_splay_tree
+{
+ public:
+  typedef KEY_TYPE key_type;
+  typedef VALUE_TYPE value_type;
+
+  typedef int (*compare_fn) (key_type, key_type);
+  typedef void (*delete_key_fn) (key_type);
+  typedef void (*delete_value_fn) (value_type);
+  typedef int (*foreach_fn) (key_type, value_type, void *);
+
+  typed_splay_tree (compare_fn,
+		    delete_key_fn,
+		    delete_value_fn);
+  ~typed_splay_tree ();
+
+  value_type lookup (key_type k);
+  value_type predecessor (key_type k);
+  value_type successor (key_type k);
+  void insert (key_type k, value_type v);
+  value_type max ();
+  value_type min ();
+  int foreach (foreach_fn, void *);
+
+ private:
+  /* Helper type for typed_splay_tree::foreach.  */
+  struct closure
+  {
+    closure (foreach_fn outer_cb, void *outer_user_data)
+    : m_outer_cb (outer_cb), m_outer_user_data (outer_user_data) {}
+
+    foreach_fn m_outer_cb;
+    void *m_outer_user_data;
+  };
+
+  static int inner_foreach_fn (splay_tree_node node, void *user_data);
+
+  static value_type node_to_value (splay_tree_node node);
+
+ private:
+  ::splay_tree m_inner;
+};
+
+/* Constructor for typed_splay_tree <K, V>.  */
+
+template <typename KEY_TYPE, typename VALUE_TYPE>
+inline typed_splay_tree<KEY_TYPE, VALUE_TYPE>::
+  typed_splay_tree (compare_fn compare_fn,
+		    delete_key_fn delete_key_fn,
+		    delete_value_fn delete_value_fn)
+{
+  m_inner = splay_tree_new ((splay_tree_compare_fn)compare_fn,
+			    (splay_tree_delete_key_fn)delete_key_fn,
+			    (splay_tree_delete_value_fn)delete_value_fn);
+}
+
+/* Destructor for typed_splay_tree <K, V>.  */
+
+template <typename KEY_TYPE, typename VALUE_TYPE>
+inline typed_splay_tree<KEY_TYPE, VALUE_TYPE>::
+  ~typed_splay_tree ()
+{
+  splay_tree_delete (m_inner);
+}
+
+/* Lookup KEY, returning a value if present, and NULL
+   otherwise.  */
+
+template <typename KEY_TYPE, typename VALUE_TYPE>
+inline VALUE_TYPE
+typed_splay_tree<KEY_TYPE, VALUE_TYPE>::lookup (key_type key)
+{
+  splay_tree_node node = splay_tree_lookup (m_inner, (splay_tree_key)key);
+  return node_to_value (node);
+}
+
+/* Return the immediate predecessor of KEY, or NULL if there is no
+   predecessor.  KEY need not be present in the tree.  */
+
+template <typename KEY_TYPE, typename VALUE_TYPE>
+inline VALUE_TYPE
+typed_splay_tree<KEY_TYPE, VALUE_TYPE>::predecessor (key_type key)
+{
+  splay_tree_node node = splay_tree_predecessor (m_inner, (splay_tree_key)key);
+  return node_to_value (node);
+}
+
+/* Return the immediate successor of KEY, or NULL if there is no
+   successor.  KEY need not be present in the tree.  */
+
+template <typename KEY_TYPE, typename VALUE_TYPE>
+inline VALUE_TYPE
+typed_splay_tree<KEY_TYPE, VALUE_TYPE>::successor (key_type k)
+{
+  splay_tree_node node = splay_tree_successor (m_inner, (splay_tree_key)k);
+  return node_to_value (node);
+}
+
+/* Insert a new node (associating KEY with VALUE).  If a
+   previous node with the indicated KEY exists, its data is replaced
+   with the new value.  */
+
+template <typename KEY_TYPE, typename VALUE_TYPE>
+inline void
+typed_splay_tree<KEY_TYPE, VALUE_TYPE>::insert (key_type key,
+						value_type value)
+{
+  splay_tree_insert (m_inner,
+		     (splay_tree_key)key,
+		     (splay_tree_value)value);
+}
+
+/* Get the value with maximal key.  */
+
+template <typename KEY_TYPE, typename VALUE_TYPE>
+inline VALUE_TYPE
+typed_splay_tree<KEY_TYPE, VALUE_TYPE>::max ()
+{
+  return node_to_value (splay_tree_max (m_inner));
+}
+
+/* Get the value with minimal key.  */
+
+template <typename KEY_TYPE, typename VALUE_TYPE>
+inline VALUE_TYPE
+typed_splay_tree<KEY_TYPE, VALUE_TYPE>::min ()
+{
+  return node_to_value (splay_tree_min (m_inner));
+}
+
+/* Call OUTER_CB, passing it the OUTER_USER_DATA, for every node,
+   following an in-order traversal.  If OUTER_CB ever returns a non-zero
+   value, the iteration ceases immediately, and the value is returned.
+   Otherwise, this function returns 0.  */
+
+template <typename KEY_TYPE, typename VALUE_TYPE>
+inline int
+typed_splay_tree<KEY_TYPE, VALUE_TYPE>::foreach (foreach_fn outer_cb,
+						 void *outer_user_data)
+{
+  closure c (outer_cb, outer_user_data);
+
+  return splay_tree_foreach (m_inner, inner_foreach_fn, &c);
+}
+
+/* Helper function for typed_splay_tree::foreach.  */
+
+template <typename KEY_TYPE, typename VALUE_TYPE>
+int
+typed_splay_tree<KEY_TYPE, VALUE_TYPE>::inner_foreach_fn (splay_tree_node node,
+							  void *user_data)
+{
+  closure *c = (closure *)user_data;
+
+  return c->m_outer_cb ((KEY_TYPE)node->key, (VALUE_TYPE)node->value,
+			c->m_outer_user_data);
+}
+
+/* Internal function for converting from splay_tree_node to
+   VALUE_TYPE.  */
+template <typename KEY_TYPE, typename VALUE_TYPE>
+inline VALUE_TYPE
+typed_splay_tree<KEY_TYPE, VALUE_TYPE>::node_to_value (splay_tree_node node)
+{
+  if (node)
+    return (value_type)node->value;
+  else
+    return 0;
+}
+
+#endif  /* GCC_TYPED_SPLAY_TREE_H  */