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