From 950f6c851965c50f4460a9b5230b0425c4c77a06 Mon Sep 17 00:00:00 2001 From: David Malcolm Date: Fri, 2 Sep 2016 15:22:21 +0000 Subject: [PATCH] Improvements to typed_splay_tree This patch adds foreach, max and min methods to class typed_splay_tree, along with the start of a selftest suite. 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. From-SVN: r239958 --- gcc/ChangeLog | 14 +++++++++ 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 +++++++++++++++++++++++++++++++++++++ 6 files changed, 158 insertions(+) create mode 100644 gcc/typed-splay-tree.c diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 7e1a951..cae775f 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,17 @@ +2016-09-02 David Malcolm + + * 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. + 2016-09-02 Prathamesh Kulkarni * ipa-cp.c (ipcp_store_bits_results): Change option name from 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 +. */ + +#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 *vec = (auto_vec *)user_data; + vec->safe_push (value); + return 0; +} + +/* Test of typed_splay_tree . */ + +static void +test_str_to_int () +{ + typed_splay_tree 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 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::insert (key_type key, (splay_tree_value)value); } +/* Get the value with maximal key. */ + +template +inline VALUE_TYPE +typed_splay_tree::max () +{ + return node_to_value (splay_tree_max (m_inner)); +} + +/* Get the value with minimal key. */ + +template +inline VALUE_TYPE +typed_splay_tree::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 +inline int +typed_splay_tree::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 +int +typed_splay_tree::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 -- 2.7.4