#include <typed-splay-tree.h>

Inheritance diagram for typed_splay_tree< KEY_TYPE, VALUE_TYPE >:

Collaboration diagram for typed_splay_tree< KEY_TYPE, VALUE_TYPE >:

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

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 >

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

◆ delete_key_fn

template<typename KEY_TYPE , typename VALUE_TYPE >

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

◆ delete_value_fn

template<typename KEY_TYPE , typename VALUE_TYPE >

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

◆ foreach_fn

template<typename KEY_TYPE , typename VALUE_TYPE >

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

◆ key_type

template<typename KEY_TYPE , typename VALUE_TYPE >

typedef KEY_TYPE typed_splay_tree< KEY_TYPE, VALUE_TYPE >::key_type

◆ splay_tree_key

template<typename KEY_TYPE , typename VALUE_TYPE >

typedef key_type typed_splay_tree< KEY_TYPE, VALUE_TYPE >::splay_tree_key

private

◆ splay_tree_node

template<typename KEY_TYPE , typename VALUE_TYPE >

typedef 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 >

typedef value_type typed_splay_tree< KEY_TYPE, VALUE_TYPE >::splay_tree_value

private

◆ value_type

template<typename KEY_TYPE , typename VALUE_TYPE >

typedef 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 ggc_alloc(), 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 ggc_alloc(), 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(), ggc_alloc(), 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:

typed-splay-tree.h

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 ()

Data Structures

Public Types

Public Member Functions

Private Types

Private Member Functions

Static Private Member Functions

Private Attributes

Detailed Description

Member Typedef Documentation

◆ compare_fn

◆ delete_key_fn

◆ delete_value_fn

◆ foreach_fn

◆ key_type

◆ splay_tree_key

◆ splay_tree_node

◆ splay_tree_value

◆ value_type

Constructor & Destructor Documentation

◆ typed_splay_tree() [1/2]

◆ ~typed_splay_tree()

◆ typed_splay_tree() [2/2]

Member Function Documentation

◆ foreach()

◆ insert()

◆ KDEL()

◆ lookup()

◆ max()

◆ min()

◆ node_to_value()

◆ operator=()

◆ predecessor()

◆ remove()

◆ rotate_left()

◆ rotate_right()

◆ splay_tree_delete_helper()

◆ splay_tree_foreach_helper()

◆ splay_tree_insert()

◆ splay_tree_lookup()

◆ splay_tree_max()

◆ splay_tree_min()

◆ splay_tree_predecessor()

◆ splay_tree_remove()

◆ splay_tree_splay()

◆ splay_tree_successor()

◆ successor()

◆ VDEL()

Field Documentation

◆ comp

◆ delete_key

◆ delete_value

◆ root