This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[PATCH 1/2] Add gcc/typed-splay-tree.h
- From: David Malcolm <dmalcolm at redhat dot com>
- To: gcc-patches at gcc dot gnu dot org, jit at gcc dot gnu dot org
- Cc: David Malcolm <dmalcolm at redhat dot com>
- Date: Thu, 25 Jun 2015 15:13:40 -0400
- Subject: [PATCH 1/2] Add gcc/typed-splay-tree.h
- Authentication-results: sourceware.org; auth=none
- References: <558A846C dot 70003 at starynkevitch dot net>
I found when implementing switch statements for the jit that it
was much easier to work with libiberty's splay-tree.h by first
wrapping it in a C++ wrapper to add typesafety.
This patch adds such a wrapper, implementing the methods I needed.
It's unused in this patch, but is used in the followup patch (which only
touches the jit).
OK for trunk?
gcc/ChangeLog:
* typed-splay-tree.h: New file.
---
gcc/typed-splay-tree.h | 135 +++++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 135 insertions(+)
create mode 100644 gcc/typed-splay-tree.h
diff --git a/gcc/typed-splay-tree.h b/gcc/typed-splay-tree.h
new file mode 100644
index 0000000..1ec4894
--- /dev/null
+++ b/gcc/typed-splay-tree.h
@@ -0,0 +1,135 @@
+/* A typesafe wrapper around libiberty's splay-tree.h.
+ Copyright (C) 2015 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);
+
+ 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);
+ value_type insert (key_type k, value_type v);
+
+ private:
+ 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);
+}
+
+/* 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 */
--
1.8.5.3