1 /* A typesafe wrapper around libiberty's splay-tree.h. 2 Copyright (C) 2015-2018 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) 79 (void (*) (void)) compare_fn, 80 (splay_tree_delete_key_fn) 81 (void (*) (void)) delete_key_fn, 82 (splay_tree_delete_value_fn) 83 (void (*) (void)) delete_value_fn); 84 } 85 86 /* Destructor for typed_splay_tree <K, V>. */ 87 88 template <typename KEY_TYPE, typename VALUE_TYPE> 89 inline typed_splay_tree<KEY_TYPE, VALUE_TYPE>:: 90 ~typed_splay_tree () 91 { 92 splay_tree_delete (m_inner); 93 } 94 95 /* Lookup KEY, returning a value if present, and NULL 96 otherwise. */ 97 98 template <typename KEY_TYPE, typename VALUE_TYPE> 99 inline VALUE_TYPE 100 typed_splay_tree<KEY_TYPE, VALUE_TYPE>::lookup (key_type key) 101 { 102 splay_tree_node node = splay_tree_lookup (m_inner, (splay_tree_key)key); 103 return node_to_value (node); 104 } 105 106 /* Return the immediate predecessor of KEY, or NULL if there is no 107 predecessor. KEY need not be present in the tree. */ 108 109 template <typename KEY_TYPE, typename VALUE_TYPE> 110 inline VALUE_TYPE 111 typed_splay_tree<KEY_TYPE, VALUE_TYPE>::predecessor (key_type key) 112 { 113 splay_tree_node node = splay_tree_predecessor (m_inner, (splay_tree_key)key); 114 return node_to_value (node); 115 } 116 117 /* Return the immediate successor of KEY, or NULL if there is no 118 successor. KEY need not be present in the tree. */ 119 120 template <typename KEY_TYPE, typename VALUE_TYPE> 121 inline VALUE_TYPE 122 typed_splay_tree<KEY_TYPE, VALUE_TYPE>::successor (key_type k) 123 { 124 splay_tree_node node = splay_tree_successor (m_inner, (splay_tree_key)k); 125 return node_to_value (node); 126 } 127 128 /* Insert a new node (associating KEY with VALUE). If a 129 previous node with the indicated KEY exists, its data is replaced 130 with the new value. */ 131 132 template <typename KEY_TYPE, typename VALUE_TYPE> 133 inline void 134 typed_splay_tree<KEY_TYPE, VALUE_TYPE>::insert (key_type key, 135 value_type value) 136 { 137 splay_tree_insert (m_inner, 138 (splay_tree_key)key, 139 (splay_tree_value)value); 140 } 141 142 /* Get the value with maximal key. */ 143 144 template <typename KEY_TYPE, typename VALUE_TYPE> 145 inline VALUE_TYPE 146 typed_splay_tree<KEY_TYPE, VALUE_TYPE>::max () 147 { 148 return node_to_value (splay_tree_max (m_inner)); 149 } 150 151 /* Get the value with minimal key. */ 152 153 template <typename KEY_TYPE, typename VALUE_TYPE> 154 inline VALUE_TYPE 155 typed_splay_tree<KEY_TYPE, VALUE_TYPE>::min () 156 { 157 return node_to_value (splay_tree_min (m_inner)); 158 } 159 160 /* Call OUTER_CB, passing it the OUTER_USER_DATA, for every node, 161 following an in-order traversal. If OUTER_CB ever returns a non-zero 162 value, the iteration ceases immediately, and the value is returned. 163 Otherwise, this function returns 0. */ 164 165 template <typename KEY_TYPE, typename VALUE_TYPE> 166 inline int 167 typed_splay_tree<KEY_TYPE, VALUE_TYPE>::foreach (foreach_fn outer_cb, 168 void *outer_user_data) 169 { 170 closure c (outer_cb, outer_user_data); 171 172 return splay_tree_foreach (m_inner, inner_foreach_fn, &c); 173 } 174 175 /* Helper function for typed_splay_tree::foreach. */ 176 177 template <typename KEY_TYPE, typename VALUE_TYPE> 178 int 179 typed_splay_tree<KEY_TYPE, VALUE_TYPE>::inner_foreach_fn (splay_tree_node node, 180 void *user_data) 181 { 182 closure *c = (closure *)user_data; 183 184 return c->m_outer_cb ((KEY_TYPE)node->key, (VALUE_TYPE)node->value, 185 c->m_outer_user_data); 186 } 187 188 /* Internal function for converting from splay_tree_node to 189 VALUE_TYPE. */ 190 template <typename KEY_TYPE, typename VALUE_TYPE> 191 inline VALUE_TYPE 192 typed_splay_tree<KEY_TYPE, VALUE_TYPE>::node_to_value (splay_tree_node node) 193 { 194 if (node) 195 return (value_type)node->value; 196 else 197 return 0; 198 } 199 200 #endif /* GCC_TYPED_SPLAY_TREE_H */ 201