GCC Middle and Back End API Reference
|
#include <typed-splay-tree.h>
Data Structures | |
struct | splay_tree_node_s |
Public Types | |
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) |
typedef int(*) | foreach_fn(key_type, value_type, void *) |
Public Member Functions | |
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) |
void | insert (key_type k, value_type v) |
void | remove (key_type k) |
value_type | max () |
value_type | min () |
int | foreach (foreach_fn, void *) |
Private Types | |
typedef key_type | splay_tree_key |
typedef value_type | splay_tree_value |
typedef splay_tree_node_s * | splay_tree_node |
Private Member Functions | |
typed_splay_tree (const typed_splay_tree &) | |
typed_splay_tree & | operator= (const typed_splay_tree &) |
void | KDEL (splay_tree_key) |
void | VDEL (splay_tree_value) |
void | splay_tree_delete_helper (splay_tree_node) |
void | splay_tree_splay (splay_tree_key) |
splay_tree_node | splay_tree_insert (splay_tree_key, splay_tree_value) |
void | splay_tree_remove (splay_tree_key key) |
splay_tree_node | splay_tree_lookup (splay_tree_key key) |
splay_tree_node | splay_tree_predecessor (splay_tree_key) |
splay_tree_node | splay_tree_successor (splay_tree_key) |
splay_tree_node | splay_tree_max () |
splay_tree_node | splay_tree_min () |
Static Private Member Functions | |
static void | rotate_left (splay_tree_node *, splay_tree_node, splay_tree_node) |
static void | rotate_right (splay_tree_node *, splay_tree_node, splay_tree_node) |
static int | splay_tree_foreach_helper (splay_tree_node, foreach_fn, void *) |
static value_type | node_to_value (splay_tree_node node) |
Private Attributes | |
splay_tree_node | root |
compare_fn | comp |
delete_key_fn | delete_key |
delete_value_fn | delete_value |
A typesafe wrapper around libiberty's splay-tree.h. Copyright (C) 2015-2024 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/>.
Typesafe wrapper around libiberty's splay-tree.h.
int(*) typed_splay_tree< KEY_TYPE, VALUE_TYPE >::compare_fn(key_type, key_type) |
void(*) typed_splay_tree< KEY_TYPE, VALUE_TYPE >::delete_key_fn(key_type) |
void(*) typed_splay_tree< KEY_TYPE, VALUE_TYPE >::delete_value_fn(value_type) |
int(*) typed_splay_tree< KEY_TYPE, VALUE_TYPE >::foreach_fn(key_type, value_type, void *) |
KEY_TYPE typed_splay_tree< KEY_TYPE, VALUE_TYPE >::key_type |
|
private |
|
private |
|
private |
VALUE_TYPE typed_splay_tree< KEY_TYPE, VALUE_TYPE >::value_type |
|
inline |
|
inline |
Destructor for typed_splay_tree <K, V>.
|
private |
|
inline |
Call OUTER_CB, passing it the OUTER_USER_DATA, for every node, following an in-order traversal. If OUTER_CB ever returns a non-zero value, the iteration ceases immediately, and the value is returned. Otherwise, this function returns 0.
Referenced by edit_context::print_diff().
|
inline |
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.
Referenced by edit_context::get_or_insert_file(), and edited_file::get_or_insert_line().
|
inlineprivate |
|
inline |
Lookup KEY, returning a value if present, and NULL otherwise.
Referenced by edit_context::get_file(), and edited_file::get_line().
|
inline |
Get the value with maximal key.
|
inline |
Get the value with minimal key.
Referenced by edited_file::print_diff().
|
inlinestaticprivate |
Internal function for converting from splay_tree_node to VALUE_TYPE.
References typed_splay_tree< KEY_TYPE, VALUE_TYPE >::splay_tree_node_s::value.
|
private |
|
inline |
Return the immediate predecessor of KEY, or NULL if there is no predecessor. KEY need not be present in the tree.
|
inline |
Remove a node (associating KEY with VALUE).
|
inlinestaticprivate |
Rotate the edge joining the left child N with its parent P. PP is the grandparents' pointer to P.
References typed_splay_tree< KEY_TYPE, VALUE_TYPE >::splay_tree_node_s::left, and typed_splay_tree< KEY_TYPE, VALUE_TYPE >::splay_tree_node_s::right.
|
inlinestaticprivate |
Rotate the edge joining the right child N with its parent P. PP is the grandparents' pointer to P.
References typed_splay_tree< KEY_TYPE, VALUE_TYPE >::splay_tree_node_s::left, and typed_splay_tree< KEY_TYPE, VALUE_TYPE >::splay_tree_node_s::right.
|
private |
Deallocate NODE (a member of SP), and all its sub-trees.
References typed_splay_tree< KEY_TYPE, VALUE_TYPE >::splay_tree_node_s::back, typed_splay_tree< KEY_TYPE, VALUE_TYPE >::splay_tree_node_s::key, typed_splay_tree< KEY_TYPE, VALUE_TYPE >::splay_tree_node_s::left, NULL, typed_splay_tree< KEY_TYPE, VALUE_TYPE >::splay_tree_node_s::right, and typed_splay_tree< KEY_TYPE, VALUE_TYPE >::splay_tree_node_s::value.
|
staticprivate |
Call FN, passing it the DATA, for every node below NODE, all of which are from SP, following an in-order traversal. If FN every returns a non-zero value, the iteration ceases immediately, and the value is returned. Otherwise, this function returns 0.
References typed_splay_tree< KEY_TYPE, VALUE_TYPE >::splay_tree_node_s::back, typed_splay_tree< KEY_TYPE, VALUE_TYPE >::splay_tree_node_s::key, typed_splay_tree< KEY_TYPE, VALUE_TYPE >::splay_tree_node_s::left, NULL, typed_splay_tree< KEY_TYPE, VALUE_TYPE >::splay_tree_node_s::right, and typed_splay_tree< KEY_TYPE, VALUE_TYPE >::splay_tree_node_s::value.
|
private |
Insert a new node (associating KEY with DATA) into SP. If a previous node with the indicated KEY exists, its data is replaced with the new value. Returns the new node.
References typed_splay_tree< KEY_TYPE, VALUE_TYPE >::splay_tree_node_s::key, typed_splay_tree< KEY_TYPE, VALUE_TYPE >::splay_tree_node_s::left, typed_splay_tree< KEY_TYPE, VALUE_TYPE >::splay_tree_node_s::right, and typed_splay_tree< KEY_TYPE, VALUE_TYPE >::splay_tree_node_s::value.
|
private |
Lookup KEY in SP, returning VALUE if present, and NULL otherwise.
References comp.
|
private |
Return the node in SP with the greatest key.
References NULL, and typed_splay_tree< KEY_TYPE, VALUE_TYPE >::splay_tree_node_s::right.
|
private |
Return the node in SP with the smallest key.
References typed_splay_tree< KEY_TYPE, VALUE_TYPE >::splay_tree_node_s::left, and NULL.
|
private |
Return the immediate predecessor KEY, or NULL if there is no predecessor. KEY need not be present in the tree.
References typed_splay_tree< KEY_TYPE, VALUE_TYPE >::splay_tree_node_s::left, NULL, and typed_splay_tree< KEY_TYPE, VALUE_TYPE >::splay_tree_node_s::right.
|
private |
Remove KEY from SP. It is not an error if it did not exist.
References comp, typed_splay_tree< KEY_TYPE, VALUE_TYPE >::splay_tree_node_s::left, and typed_splay_tree< KEY_TYPE, VALUE_TYPE >::splay_tree_node_s::right.
|
private |
|
private |
Return the immediate successor KEY, or NULL if there is no successor. KEY need not be present in the tree.
References typed_splay_tree< KEY_TYPE, VALUE_TYPE >::splay_tree_node_s::left, NULL, and typed_splay_tree< KEY_TYPE, VALUE_TYPE >::splay_tree_node_s::right.
|
inline |
Return the immediate successor of KEY, or NULL if there is no successor. KEY need not be present in the tree.
Referenced by edited_file::print_diff().
|
inlineprivate |
|
private |
|
private |
|
private |
|
private |