1/* A typesafe wrapper around libiberty's splay-tree.h.
2   Copyright (C) 2015 Free Software Foundation, Inc.
3
4This file is part of GCC.
5
6GCC is free software; you can redistribute it and/or modify it under
7the terms of the GNU General Public License as published by the Free
8Software Foundation; either version 3, or (at your option) any later
9version.
10
11GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12WARRANTY; without even the implied warranty of MERCHANTABILITY or
13FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
14for more details.
15
16You should have received a copy of the GNU General Public License
17along with GCC; see the file COPYING3.  If not see
18<http://www.gnu.org/licenses/>.  */
19
20#ifndef GCC_TYPED_SPLAY_TREE_H
21#define GCC_TYPED_SPLAY_TREE_H
22
23#include "splay-tree.h"
24
25/* Typesafe wrapper around libiberty's splay-tree.h.  */
26template <typename KEY_TYPE, typename VALUE_TYPE>
27class typed_splay_tree
28{
29 public:
30  typedef KEY_TYPE key_type;
31  typedef VALUE_TYPE value_type;
32
33  typedef int (*compare_fn) (key_type, key_type);
34  typedef void (*delete_key_fn) (key_type);
35  typedef void (*delete_value_fn) (value_type);
36
37  typed_splay_tree (compare_fn,
38		    delete_key_fn,
39		    delete_value_fn);
40  ~typed_splay_tree ();
41
42  value_type lookup (key_type k);
43  value_type predecessor (key_type k);
44  value_type successor (key_type k);
45  void insert (key_type k, value_type v);
46
47 private:
48  static value_type node_to_value (splay_tree_node node);
49
50 private:
51  ::splay_tree m_inner;
52};
53
54/* Constructor for typed_splay_tree <K, V>.  */
55
56template <typename KEY_TYPE, typename VALUE_TYPE>
57inline typed_splay_tree<KEY_TYPE, VALUE_TYPE>::
58  typed_splay_tree (compare_fn compare_fn,
59		    delete_key_fn delete_key_fn,
60		    delete_value_fn delete_value_fn)
61{
62  m_inner = splay_tree_new ((splay_tree_compare_fn)compare_fn,
63			    (splay_tree_delete_key_fn)delete_key_fn,
64			    (splay_tree_delete_value_fn)delete_value_fn);
65}
66
67/* Destructor for typed_splay_tree <K, V>.  */
68
69template <typename KEY_TYPE, typename VALUE_TYPE>
70inline typed_splay_tree<KEY_TYPE, VALUE_TYPE>::
71  ~typed_splay_tree ()
72{
73  splay_tree_delete (m_inner);
74}
75
76/* Lookup KEY, returning a value if present, and NULL
77   otherwise.  */
78
79template <typename KEY_TYPE, typename VALUE_TYPE>
80inline VALUE_TYPE
81typed_splay_tree<KEY_TYPE, VALUE_TYPE>::lookup (key_type key)
82{
83  splay_tree_node node = splay_tree_lookup (m_inner, (splay_tree_key)key);
84  return node_to_value (node);
85}
86
87/* Return the immediate predecessor of KEY, or NULL if there is no
88   predecessor.  KEY need not be present in the tree.  */
89
90template <typename KEY_TYPE, typename VALUE_TYPE>
91inline VALUE_TYPE
92typed_splay_tree<KEY_TYPE, VALUE_TYPE>::predecessor (key_type key)
93{
94  splay_tree_node node = splay_tree_predecessor (m_inner, (splay_tree_key)key);
95  return node_to_value (node);
96}
97
98/* Return the immediate successor of KEY, or NULL if there is no
99   successor.  KEY need not be present in the tree.  */
100
101template <typename KEY_TYPE, typename VALUE_TYPE>
102inline VALUE_TYPE
103typed_splay_tree<KEY_TYPE, VALUE_TYPE>::successor (key_type k)
104{
105  splay_tree_node node = splay_tree_successor (m_inner, (splay_tree_key)k);
106  return node_to_value (node);
107}
108
109/* Insert a new node (associating KEY with VALUE).  If a
110   previous node with the indicated KEY exists, its data is replaced
111   with the new value.  */
112
113template <typename KEY_TYPE, typename VALUE_TYPE>
114inline void
115typed_splay_tree<KEY_TYPE, VALUE_TYPE>::insert (key_type key,
116						value_type value)
117{
118  splay_tree_insert (m_inner,
119		     (splay_tree_key)key,
120		     (splay_tree_value)value);
121}
122
123/* Internal function for converting from splay_tree_node to
124   VALUE_TYPE.  */
125template <typename KEY_TYPE, typename VALUE_TYPE>
126inline VALUE_TYPE
127typed_splay_tree<KEY_TYPE, VALUE_TYPE>::node_to_value (splay_tree_node node)
128{
129  if (node)
130    return (value_type)node->value;
131  else
132    return 0;
133}
134
135#endif  /* GCC_TYPED_SPLAY_TREE_H  */
136