diff options
Diffstat (limited to 'storage/innobase/include/ut0rbt.h')
| -rw-r--r-- | storage/innobase/include/ut0rbt.h | 59 |
1 files changed, 19 insertions, 40 deletions
diff --git a/storage/innobase/include/ut0rbt.h b/storage/innobase/include/ut0rbt.h index 59e3fc94598..9555fe6137c 100644 --- a/storage/innobase/include/ut0rbt.h +++ b/storage/innobase/include/ut0rbt.h @@ -1,6 +1,6 @@ -/***************************************************************************//** +/***************************************************************************** -Copyright (c) 2007, 2010, Oracle and/or its affiliates. All Rights Reserved. +Copyright (c) 2007, 2014, Oracle and/or its affiliates. All Rights Reserved. This program 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 @@ -111,15 +111,13 @@ struct ib_rbt_bound_t { /**********************************************************************//** Free an instance of a red black tree */ -UNIV_INTERN void rbt_free( /*=====*/ ib_rbt_t* tree); /*!< in: rb tree to free */ /**********************************************************************//** Create an instance of a red black tree -@return rb tree instance */ -UNIV_INTERN +@return rb tree instance */ ib_rbt_t* rbt_create( /*=======*/ @@ -128,8 +126,7 @@ rbt_create( /**********************************************************************//** Create an instance of a red black tree, whose comparison function takes an argument -@return rb tree instance */ -UNIV_INTERN +@return rb tree instance */ ib_rbt_t* rbt_create_arg_cmp( /*===============*/ @@ -139,7 +136,6 @@ rbt_create_arg_cmp( void* cmp_arg); /*!< in: compare fn arg */ /**********************************************************************//** Delete a node from the red black tree, identified by key */ -UNIV_INTERN ibool rbt_delete( /*=======*/ @@ -149,8 +145,7 @@ rbt_delete( /**********************************************************************//** Remove a node from the red black tree, NOTE: This function will not delete the node instance, THAT IS THE CALLERS RESPONSIBILITY. -@return the deleted node with the const. */ -UNIV_INTERN +@return the deleted node with the const. */ ib_rbt_node_t* rbt_remove_node( /*============*/ @@ -163,8 +158,7 @@ rbt_remove_node( /**********************************************************************//** Return a node from the red black tree, identified by key, NULL if not found -@return node if found else return NULL */ -UNIV_INTERN +@return node if found else return NULL */ const ib_rbt_node_t* rbt_lookup( /*=======*/ @@ -172,8 +166,7 @@ rbt_lookup( const void* key); /*!< in: key to lookup */ /**********************************************************************//** Add data to the red black tree, identified by key (no dups yet!) -@return inserted node */ -UNIV_INTERN +@return inserted node */ const ib_rbt_node_t* rbt_insert( /*=======*/ @@ -183,8 +176,7 @@ rbt_insert( copied to the node.*/ /**********************************************************************//** Add a new node to the tree, useful for data that is pre-sorted. -@return appended node */ -UNIV_INTERN +@return appended node */ const ib_rbt_node_t* rbt_add_node( /*=========*/ @@ -194,24 +186,21 @@ rbt_add_node( to the node */ /**********************************************************************//** Return the left most data node in the tree -@return left most node */ -UNIV_INTERN +@return left most node */ const ib_rbt_node_t* rbt_first( /*======*/ const ib_rbt_t* tree); /*!< in: rb tree */ /**********************************************************************//** Return the right most data node in the tree -@return right most node */ -UNIV_INTERN +@return right most node */ const ib_rbt_node_t* rbt_last( /*=====*/ const ib_rbt_t* tree); /*!< in: rb tree */ /**********************************************************************//** Return the next node from current. -@return successor node to current that is passed in. */ -UNIV_INTERN +@return successor node to current that is passed in. */ const ib_rbt_node_t* rbt_next( /*=====*/ @@ -220,8 +209,7 @@ rbt_next( current); /**********************************************************************//** Return the prev node from current. -@return precedessor node to current that is passed in */ -UNIV_INTERN +@return precedessor node to current that is passed in */ const ib_rbt_node_t* rbt_prev( /*=====*/ @@ -230,8 +218,7 @@ rbt_prev( current); /**********************************************************************//** Find the node that has the lowest key that is >= key. -@return node that satisfies the lower bound constraint or NULL */ -UNIV_INTERN +@return node that satisfies the lower bound constraint or NULL */ const ib_rbt_node_t* rbt_lower_bound( /*============*/ @@ -239,8 +226,7 @@ rbt_lower_bound( const void* key); /*!< in: key to search */ /**********************************************************************//** Find the node that has the greatest key that is <= key. -@return node that satisifies the upper bound constraint or NULL */ -UNIV_INTERN +@return node that satisifies the upper bound constraint or NULL */ const ib_rbt_node_t* rbt_upper_bound( /*============*/ @@ -250,8 +236,7 @@ rbt_upper_bound( Search for the key, a node will be retuned in parent.last, whether it was found or not. If not found then parent.last will contain the parent node for the possibly new key otherwise the matching node. -@return result of last comparison */ -UNIV_INTERN +@return result of last comparison */ int rbt_search( /*=======*/ @@ -262,8 +247,7 @@ rbt_search( Search for the key, a node will be retuned in parent.last, whether it was found or not. If not found then parent.last will contain the parent node for the possibly new key otherwise the matching node. -@return result of last comparison */ -UNIV_INTERN +@return result of last comparison */ int rbt_search_cmp( /*===========*/ @@ -276,15 +260,13 @@ rbt_search_cmp( with argument */ /**********************************************************************//** Clear the tree, deletes (and free's) all the nodes. */ -UNIV_INTERN void rbt_clear( /*======*/ ib_rbt_t* tree); /*!< in: rb tree */ /**********************************************************************//** Merge the node from dst into src. Return the number of nodes merged. -@return no. of recs merged */ -UNIV_INTERN +@return no. of recs merged */ ulint rbt_merge_uniq( /*===========*/ @@ -296,8 +278,7 @@ Delete the nodes from src after copying node to dst. As a side effect the duplicates will be left untouched in the src, since we don't support duplicates (yet). NOTE: src and dst must be similar, the function doesn't check for this condition (yet). -@return no. of recs merged */ -UNIV_INTERN +@return no. of recs merged */ ulint rbt_merge_uniq_destructive( /*=======================*/ @@ -306,15 +287,13 @@ rbt_merge_uniq_destructive( /**********************************************************************//** Verify the integrity of the RB tree. For debugging. 0 failure else height of tree (in count of black nodes). -@return TRUE if OK FALSE if tree invalid. */ -UNIV_INTERN +@return TRUE if OK FALSE if tree invalid. */ ibool rbt_validate( /*=========*/ const ib_rbt_t* tree); /*!< in: tree to validate */ /**********************************************************************//** Iterate over the tree in depth first order. */ -UNIV_INTERN void rbt_print( /*======*/ |