GCC Middle and Back End API Reference
Data Structures | Public Types | Public Member Functions | Private Types | Private Member Functions | Static Private Member Functions | Private Attributes
typed_splay_tree< KEY_TYPE, VALUE_TYPE > Class Template Reference

#include <typed-splay-tree.h>

Inheritance diagram for typed_splay_tree< KEY_TYPE, VALUE_TYPE >:
Inheritance graph
[legend]
Collaboration diagram for typed_splay_tree< KEY_TYPE, VALUE_TYPE >:
Collaboration graph
[legend]

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
 

Detailed Description

template<typename KEY_TYPE, typename VALUE_TYPE>
class typed_splay_tree< KEY_TYPE, VALUE_TYPE >
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.

Member Typedef Documentation

◆ compare_fn

template<typename KEY_TYPE , typename VALUE_TYPE >
int(*) typed_splay_tree< KEY_TYPE, VALUE_TYPE >::compare_fn(key_type, key_type)

◆ delete_key_fn

template<typename KEY_TYPE , typename VALUE_TYPE >
void(*) typed_splay_tree< KEY_TYPE, VALUE_TYPE >::delete_key_fn(key_type)

◆ delete_value_fn

template<typename KEY_TYPE , typename VALUE_TYPE >
void(*) typed_splay_tree< KEY_TYPE, VALUE_TYPE >::delete_value_fn(value_type)

◆ foreach_fn

template<typename KEY_TYPE , typename VALUE_TYPE >
int(*) typed_splay_tree< KEY_TYPE, VALUE_TYPE >::foreach_fn(key_type, value_type, void *)

◆ key_type

template<typename KEY_TYPE , typename VALUE_TYPE >
KEY_TYPE typed_splay_tree< KEY_TYPE, VALUE_TYPE >::key_type

◆ splay_tree_key

template<typename KEY_TYPE , typename VALUE_TYPE >
key_type typed_splay_tree< KEY_TYPE, VALUE_TYPE >::splay_tree_key
private

◆ splay_tree_node

template<typename KEY_TYPE , typename VALUE_TYPE >
splay_tree_node_s* typed_splay_tree< KEY_TYPE, VALUE_TYPE >::splay_tree_node
private

◆ splay_tree_value

template<typename KEY_TYPE , typename VALUE_TYPE >
value_type typed_splay_tree< KEY_TYPE, VALUE_TYPE >::splay_tree_value
private

◆ value_type

template<typename KEY_TYPE , typename VALUE_TYPE >
VALUE_TYPE typed_splay_tree< KEY_TYPE, VALUE_TYPE >::value_type

Constructor & Destructor Documentation

◆ typed_splay_tree() [1/2]

template<typename KEY_TYPE , typename VALUE_TYPE >
typed_splay_tree< KEY_TYPE, VALUE_TYPE >::typed_splay_tree ( compare_fn compare_fn,
delete_key_fn delete_key_fn,
delete_value_fn delete_value_fn )
inline 
Constructor for typed_splay_tree <K, V>.

References comp, and NULL.

◆ ~typed_splay_tree()

template<typename KEY_TYPE , typename VALUE_TYPE >
typed_splay_tree< KEY_TYPE, VALUE_TYPE >::~typed_splay_tree ( )
inline 
Destructor for typed_splay_tree <K, V>.

◆ typed_splay_tree() [2/2]

template<typename KEY_TYPE , typename VALUE_TYPE >
typed_splay_tree< KEY_TYPE, VALUE_TYPE >::typed_splay_tree ( const typed_splay_tree< KEY_TYPE, VALUE_TYPE > & )
private

Member Function Documentation

◆ foreach()

template<typename KEY_TYPE , typename VALUE_TYPE >
int typed_splay_tree< KEY_TYPE, VALUE_TYPE >::foreach ( foreach_fn foreach_fn,
void * user_data )
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().

◆ insert()

template<typename KEY_TYPE , typename VALUE_TYPE >
void typed_splay_tree< KEY_TYPE, VALUE_TYPE >::insert ( key_type key,
value_type value )
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().

◆ KDEL()

template<typename KEY_TYPE , typename VALUE_TYPE >
void typed_splay_tree< KEY_TYPE, VALUE_TYPE >::KDEL ( splay_tree_key x)
inlineprivate

◆ lookup()

template<typename KEY_TYPE , typename VALUE_TYPE >
VALUE_TYPE typed_splay_tree< KEY_TYPE, VALUE_TYPE >::lookup ( key_type key)
inline 
Lookup KEY, returning a value if present, and NULL
otherwise.

Referenced by edit_context::get_file(), and edited_file::get_line().

◆ max()

template<typename KEY_TYPE , typename VALUE_TYPE >
VALUE_TYPE typed_splay_tree< KEY_TYPE, VALUE_TYPE >::max ( )
inline 
Get the value with maximal key.

◆ min()

template<typename KEY_TYPE , typename VALUE_TYPE >
VALUE_TYPE typed_splay_tree< KEY_TYPE, VALUE_TYPE >::min ( )
inline 
Get the value with minimal key.

Referenced by edited_file::print_diff().

◆ node_to_value()

template<typename KEY_TYPE , typename VALUE_TYPE >
VALUE_TYPE typed_splay_tree< KEY_TYPE, VALUE_TYPE >::node_to_value ( splay_tree_node node)
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.

◆ operator=()

template<typename KEY_TYPE , typename VALUE_TYPE >
typed_splay_tree & typed_splay_tree< KEY_TYPE, VALUE_TYPE >::operator= ( const typed_splay_tree< KEY_TYPE, VALUE_TYPE > & )
private

◆ predecessor()

template<typename KEY_TYPE , typename VALUE_TYPE >
VALUE_TYPE typed_splay_tree< KEY_TYPE, VALUE_TYPE >::predecessor ( key_type key)
inline 
Return the immediate predecessor of KEY, or NULL if there is no
predecessor.  KEY need not be present in the tree.

◆ remove()

template<typename KEY_TYPE , typename VALUE_TYPE >
void typed_splay_tree< KEY_TYPE, VALUE_TYPE >::remove ( key_type key)
inline 
Remove a node (associating KEY with VALUE).

◆ rotate_left()

template<typename KEY_TYPE , typename VALUE_TYPE >
void typed_splay_tree< KEY_TYPE, VALUE_TYPE >::rotate_left ( splay_tree_node * pp,
splay_tree_node p,
splay_tree_node n )
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.

◆ rotate_right()

template<typename KEY_TYPE , typename VALUE_TYPE >
void typed_splay_tree< KEY_TYPE, VALUE_TYPE >::rotate_right ( splay_tree_node * pp,
splay_tree_node p,
splay_tree_node n )
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.

◆ splay_tree_delete_helper()

template<typename KEY_TYPE , typename VALUE_TYPE >
void typed_splay_tree< KEY_TYPE, VALUE_TYPE >::splay_tree_delete_helper ( splay_tree_node node)
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.

◆ splay_tree_foreach_helper()

template<typename KEY_TYPE , typename VALUE_TYPE >
int typed_splay_tree< KEY_TYPE, VALUE_TYPE >::splay_tree_foreach_helper ( splay_tree_node node,
foreach_fn fn,
void * data )
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.

◆ splay_tree_insert()

template<typename KEY_TYPE , typename VALUE_TYPE >
typed_splay_tree< KEY_TYPE, VALUE_TYPE >::splay_tree_node typed_splay_tree< KEY_TYPE, VALUE_TYPE >::splay_tree_insert ( splay_tree_key key,
splay_tree_value 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.

◆ splay_tree_lookup()

template<typename KEY_TYPE , typename VALUE_TYPE >
typed_splay_tree< KEY_TYPE, VALUE_TYPE >::splay_tree_node typed_splay_tree< KEY_TYPE, VALUE_TYPE >::splay_tree_lookup ( splay_tree_key key)
private 
Lookup KEY in SP, returning VALUE if present, and NULL
otherwise.

References comp.

◆ splay_tree_max()

template<typename KEY_TYPE , typename VALUE_TYPE >
typed_splay_tree< KEY_TYPE, VALUE_TYPE >::splay_tree_node typed_splay_tree< KEY_TYPE, VALUE_TYPE >::splay_tree_max ( )
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.

◆ splay_tree_min()

template<typename KEY_TYPE , typename VALUE_TYPE >
typed_splay_tree< KEY_TYPE, VALUE_TYPE >::splay_tree_node typed_splay_tree< KEY_TYPE, VALUE_TYPE >::splay_tree_min ( )
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.

◆ splay_tree_predecessor()

template<typename KEY_TYPE , typename VALUE_TYPE >
typed_splay_tree< KEY_TYPE, VALUE_TYPE >::splay_tree_node typed_splay_tree< KEY_TYPE, VALUE_TYPE >::splay_tree_predecessor ( splay_tree_key key)
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.

◆ splay_tree_remove()

template<typename KEY_TYPE , typename VALUE_TYPE >
void typed_splay_tree< KEY_TYPE, VALUE_TYPE >::splay_tree_remove ( splay_tree_key key)
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.

◆ splay_tree_splay()

template<typename KEY_TYPE , typename VALUE_TYPE >
void typed_splay_tree< KEY_TYPE, VALUE_TYPE >::splay_tree_splay ( splay_tree_key key)
private 
Bottom up splay of key.

References cmp1(), 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, and typed_splay_tree< KEY_TYPE, VALUE_TYPE >::splay_tree_node_s::right.

◆ splay_tree_successor()

template<typename KEY_TYPE , typename VALUE_TYPE >
typed_splay_tree< KEY_TYPE, VALUE_TYPE >::splay_tree_node typed_splay_tree< KEY_TYPE, VALUE_TYPE >::splay_tree_successor ( splay_tree_key key)
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.

◆ successor()

template<typename KEY_TYPE , typename VALUE_TYPE >
VALUE_TYPE typed_splay_tree< KEY_TYPE, VALUE_TYPE >::successor ( key_type key)
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().

◆ VDEL()

template<typename KEY_TYPE , typename VALUE_TYPE >
void typed_splay_tree< KEY_TYPE, VALUE_TYPE >::VDEL ( splay_tree_value x)
inlineprivate

Field Documentation

◆ comp

template<typename KEY_TYPE , typename VALUE_TYPE >
compare_fn typed_splay_tree< KEY_TYPE, VALUE_TYPE >::comp
private

◆ delete_key

template<typename KEY_TYPE , typename VALUE_TYPE >
delete_key_fn typed_splay_tree< KEY_TYPE, VALUE_TYPE >::delete_key
private

◆ delete_value

template<typename KEY_TYPE , typename VALUE_TYPE >
delete_value_fn typed_splay_tree< KEY_TYPE, VALUE_TYPE >::delete_value
private

◆ root

template<typename KEY_TYPE , typename VALUE_TYPE >
splay_tree_node typed_splay_tree< KEY_TYPE, VALUE_TYPE >::root
private
The documentation for this class was generated from the following file: