[PATCH] Improvements to typed_splay_tree (v2)

David Malcolm dmalcolm@redhat.com
Thu Sep 1 00:33:00 GMT 2016


On Wed, 2016-08-31 at 16:12 +0200, Bernd Schmidt wrote:
> On 08/24/2016 03:28 AM, David Malcolm wrote:
> > +/* Helper type for typed_splay_tree::foreach.  */
> > +
> > +template <typename KEY_TYPE, typename VALUE_TYPE>
> > +struct closure
> 
> Is this in the global namespace? If so, something more specific than
> "closure" might be more appropriate. Or move the struct into the
> typed_splay_tree class definition.
> 
> Looks ok otherwise.

Thanks.  Here's a revised version; I moved the "struct closure" into
the class itself.

Successfully bootstrapped&regrtested on x86_64-pc-linux-gnu.

OK for trunk?

gcc/ChangeLog:
	* Makefile.in (OBJS): Add typed-splay-tree.o.
	* selftest-run-tests.c (selftest::run_tests): Call
	typed_splay_tree_c_tests.
	* selftest.h (typed_splay_tree_c_tests): New decl.
	* typed-splay-tree.c: New file.
	* typed-splay-tree.h (typed_splay_tree::foreach_fn): New typedef.
	(typed_splay_tree::max): New method.
	(typed_splay_tree::min): New method.
	(typed_splay_tree::foreach): New method.
	(typed_splay_tree::closure): New struct.
	(typed_splay_tree::inner_foreach_fn): New function.
---
 gcc/Makefile.in          |  1 +
 gcc/selftest-run-tests.c |  1 +
 gcc/selftest.h           |  1 +
 gcc/typed-splay-tree.c   | 79 ++++++++++++++++++++++++++++++++++++++++++++++++
 gcc/typed-splay-tree.h   | 62 +++++++++++++++++++++++++++++++++++++
 5 files changed, 144 insertions(+)
 create mode 100644 gcc/typed-splay-tree.c

diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index eb5ab61..b38a0c1 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -1542,6 +1542,7 @@ OBJS = \
 	tree-vectorizer.o \
 	tree-vrp.o \
 	tree.o \
+	typed-splay-tree.o \
 	valtrack.o \
 	value-prof.o \
 	var-tracking.o \
diff --git a/gcc/selftest-run-tests.c b/gcc/selftest-run-tests.c
index 6453e31..e20bbd0 100644
--- a/gcc/selftest-run-tests.c
+++ b/gcc/selftest-run-tests.c
@@ -56,6 +56,7 @@ selftest::run_tests ()
   ggc_tests_c_tests ();
   sreal_c_tests ();
   fibonacci_heap_c_tests ();
+  typed_splay_tree_c_tests ();
 
   /* Mid-level data structures.  */
   input_c_tests ();
diff --git a/gcc/selftest.h b/gcc/selftest.h
index 47d7350..54a33f9 100644
--- a/gcc/selftest.h
+++ b/gcc/selftest.h
@@ -166,6 +166,7 @@ extern void selftest_c_tests ();
 extern void spellcheck_c_tests ();
 extern void spellcheck_tree_c_tests ();
 extern void sreal_c_tests ();
+extern void typed_splay_tree_c_tests ();
 extern void tree_c_tests ();
 extern void tree_cfg_c_tests ();
 extern void vec_c_tests ();
diff --git a/gcc/typed-splay-tree.c b/gcc/typed-splay-tree.c
new file mode 100644
index 0000000..33992c1
--- /dev/null
+++ b/gcc/typed-splay-tree.c
@@ -0,0 +1,79 @@
+/* Selftests for typed-splay-tree.h.
+   Copyright (C) 2016 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/>.  */
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "typed-splay-tree.h"
+#include "selftest.h"
+
+#if CHECKING_P
+
+namespace selftest {
+
+/* Callback for use by test_str_to_int.  */
+
+static int
+append_cb (const char *, int value, void *user_data)
+{
+  auto_vec <int> *vec = (auto_vec <int> *)user_data;
+  vec->safe_push (value);
+  return 0;
+}
+
+/* Test of typed_splay_tree <const char *, int>.  */
+
+static void
+test_str_to_int ()
+{
+  typed_splay_tree <const char *, int> t (strcmp, NULL, NULL);
+
+  t.insert ("a", 1);
+  t.insert ("b", 2);
+  t.insert ("c", 3);
+
+  ASSERT_EQ (1, t.lookup ("a"));
+  ASSERT_EQ (2, t.lookup ("b"));
+  ASSERT_EQ (3, t.lookup ("c"));
+
+  ASSERT_EQ (2, t.predecessor ("c"));
+  ASSERT_EQ (3, t.successor ("b"));
+  ASSERT_EQ (1, t.min ());
+  ASSERT_EQ (3, t.max ());
+
+  /* Test foreach by appending to a vec, and verifying the vec.  */
+  auto_vec <int> v;
+  t.foreach (append_cb, &v);
+  ASSERT_EQ (3, v.length ());
+  ASSERT_EQ (1, v[0]);
+  ASSERT_EQ (2, v[1]);
+  ASSERT_EQ (3, v[2]);
+}
+
+/* Run all of the selftests within this file.  */
+
+void
+typed_splay_tree_c_tests ()
+{
+  test_str_to_int ();
+}
+
+} // namespace selftest
+
+#endif /* #if CHECKING_P */
diff --git a/gcc/typed-splay-tree.h b/gcc/typed-splay-tree.h
index 9dd96d6..7b8afef 100644
--- a/gcc/typed-splay-tree.h
+++ b/gcc/typed-splay-tree.h
@@ -33,6 +33,7 @@ class typed_splay_tree
   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,
@@ -43,8 +44,23 @@ class typed_splay_tree
   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:
@@ -120,6 +136,52 @@ typed_splay_tree<KEY_TYPE, VALUE_TYPE>::insert (key_type 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>
-- 
1.8.5.3



More information about the Gcc-patches mailing list