Warning: That file was not part of the compilation database. It may have many parsing errors.

1 | /* A typesafe wrapper around libiberty's splay-tree.h. |
---|---|

2 | Copyright (C) 2015-2017 Free Software Foundation, Inc. |

3 | |

4 | This file is part of GCC. |

5 | |

6 | GCC is free software; you can redistribute it and/or modify it under |

7 | the terms of the GNU General Public License as published by the Free |

8 | Software Foundation; either version 3, or (at your option) any later |

9 | version. |

10 | |

11 | GCC is distributed in the hope that it will be useful, but WITHOUT ANY |

12 | WARRANTY; without even the implied warranty of MERCHANTABILITY or |

13 | FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |

14 | for more details. |

15 | |

16 | You should have received a copy of the GNU General Public License |

17 | along 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. */ |

26 | template <typename KEY_TYPE, typename VALUE_TYPE> |

27 | class 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 | typedef int (*foreach_fn) (key_type, value_type, void *); |

37 | |

38 | typed_splay_tree (compare_fn, |

39 | delete_key_fn, |

40 | delete_value_fn); |

41 | ~typed_splay_tree (); |

42 | |

43 | value_type lookup (key_type k); |

44 | value_type predecessor (key_type k); |

45 | value_type successor (key_type k); |

46 | void insert (key_type k, value_type v); |

47 | value_type max (); |

48 | value_type min (); |

49 | int foreach (foreach_fn, void *); |

50 | |

51 | private: |

52 | /* Helper type for typed_splay_tree::foreach. */ |

53 | struct closure |

54 | { |

55 | closure (foreach_fn outer_cb, void *outer_user_data) |

56 | : m_outer_cb (outer_cb), m_outer_user_data (outer_user_data) {} |

57 | |

58 | foreach_fn m_outer_cb; |

59 | void *m_outer_user_data; |

60 | }; |

61 | |

62 | static int inner_foreach_fn (splay_tree_node node, void *user_data); |

63 | |

64 | static value_type node_to_value (splay_tree_node node); |

65 | |

66 | private: |

67 | ::splay_tree m_inner; |

68 | }; |

69 | |

70 | /* Constructor for typed_splay_tree <K, V>. */ |

71 | |

72 | template <typename KEY_TYPE, typename VALUE_TYPE> |

73 | inline typed_splay_tree<KEY_TYPE, VALUE_TYPE>:: |

74 | typed_splay_tree (compare_fn compare_fn, |

75 | delete_key_fn delete_key_fn, |

76 | delete_value_fn delete_value_fn) |

77 | { |

78 | m_inner = splay_tree_new ((splay_tree_compare_fn)compare_fn, |

79 | (splay_tree_delete_key_fn)delete_key_fn, |

80 | (splay_tree_delete_value_fn)delete_value_fn); |

81 | } |

82 | |

83 | /* Destructor for typed_splay_tree <K, V>. */ |

84 | |

85 | template <typename KEY_TYPE, typename VALUE_TYPE> |

86 | inline typed_splay_tree<KEY_TYPE, VALUE_TYPE>:: |

87 | ~typed_splay_tree () |

88 | { |

89 | splay_tree_delete (m_inner); |

90 | } |

91 | |

92 | /* Lookup KEY, returning a value if present, and NULL |

93 | otherwise. */ |

94 | |

95 | template <typename KEY_TYPE, typename VALUE_TYPE> |

96 | inline VALUE_TYPE |

97 | typed_splay_tree<KEY_TYPE, VALUE_TYPE>::lookup (key_type key) |

98 | { |

99 | splay_tree_node node = splay_tree_lookup (m_inner, (splay_tree_key)key); |

100 | return node_to_value (node); |

101 | } |

102 | |

103 | /* Return the immediate predecessor of KEY, or NULL if there is no |

104 | predecessor. KEY need not be present in the tree. */ |

105 | |

106 | template <typename KEY_TYPE, typename VALUE_TYPE> |

107 | inline VALUE_TYPE |

108 | typed_splay_tree<KEY_TYPE, VALUE_TYPE>::predecessor (key_type key) |

109 | { |

110 | splay_tree_node node = splay_tree_predecessor (m_inner, (splay_tree_key)key); |

111 | return node_to_value (node); |

112 | } |

113 | |

114 | /* Return the immediate successor of KEY, or NULL if there is no |

115 | successor. KEY need not be present in the tree. */ |

116 | |

117 | template <typename KEY_TYPE, typename VALUE_TYPE> |

118 | inline VALUE_TYPE |

119 | typed_splay_tree<KEY_TYPE, VALUE_TYPE>::successor (key_type k) |

120 | { |

121 | splay_tree_node node = splay_tree_successor (m_inner, (splay_tree_key)k); |

122 | return node_to_value (node); |

123 | } |

124 | |

125 | /* Insert a new node (associating KEY with VALUE). If a |

126 | previous node with the indicated KEY exists, its data is replaced |

127 | with the new value. */ |

128 | |

129 | template <typename KEY_TYPE, typename VALUE_TYPE> |

130 | inline void |

131 | typed_splay_tree<KEY_TYPE, VALUE_TYPE>::insert (key_type key, |

132 | value_type value) |

133 | { |

134 | splay_tree_insert (m_inner, |

135 | (splay_tree_key)key, |

136 | (splay_tree_value)value); |

137 | } |

138 | |

139 | /* Get the value with maximal key. */ |

140 | |

141 | template <typename KEY_TYPE, typename VALUE_TYPE> |

142 | inline VALUE_TYPE |

143 | typed_splay_tree<KEY_TYPE, VALUE_TYPE>::max () |

144 | { |

145 | return node_to_value (splay_tree_max (m_inner)); |

146 | } |

147 | |

148 | /* Get the value with minimal key. */ |

149 | |

150 | template <typename KEY_TYPE, typename VALUE_TYPE> |

151 | inline VALUE_TYPE |

152 | typed_splay_tree<KEY_TYPE, VALUE_TYPE>::min () |

153 | { |

154 | return node_to_value (splay_tree_min (m_inner)); |

155 | } |

156 | |

157 | /* Call OUTER_CB, passing it the OUTER_USER_DATA, for every node, |

158 | following an in-order traversal. If OUTER_CB ever returns a non-zero |

159 | value, the iteration ceases immediately, and the value is returned. |

160 | Otherwise, this function returns 0. */ |

161 | |

162 | template <typename KEY_TYPE, typename VALUE_TYPE> |

163 | inline int |

164 | typed_splay_tree<KEY_TYPE, VALUE_TYPE>::foreach (foreach_fn outer_cb, |

165 | void *outer_user_data) |

166 | { |

167 | closure c (outer_cb, outer_user_data); |

168 | |

169 | return splay_tree_foreach (m_inner, inner_foreach_fn, &c); |

170 | } |

171 | |

172 | /* Helper function for typed_splay_tree::foreach. */ |

173 | |

174 | template <typename KEY_TYPE, typename VALUE_TYPE> |

175 | int |

176 | typed_splay_tree<KEY_TYPE, VALUE_TYPE>::inner_foreach_fn (splay_tree_node node, |

177 | void *user_data) |

178 | { |

179 | closure *c = (closure *)user_data; |

180 | |

181 | return c->m_outer_cb ((KEY_TYPE)node->key, (VALUE_TYPE)node->value, |

182 | c->m_outer_user_data); |

183 | } |

184 | |

185 | /* Internal function for converting from splay_tree_node to |

186 | VALUE_TYPE. */ |

187 | template <typename KEY_TYPE, typename VALUE_TYPE> |

188 | inline VALUE_TYPE |

189 | typed_splay_tree<KEY_TYPE, VALUE_TYPE>::node_to_value (splay_tree_node node) |

190 | { |

191 | if (node) |

192 | return (value_type)node->value; |

193 | else |

194 | return 0; |

195 | } |

196 | |

197 | #endif /* GCC_TYPED_SPLAY_TREE_H */ |

198 |

Warning: That file was not part of the compilation database. It may have many parsing errors.