Go to the source code of this file.
Classes | |
struct | ib_rbt_node_struct |
struct | ib_rbt_struct |
struct | ib_rbt_bound_struct |
Typedefs | |
typedef struct ib_rbt_struct | ib_rbt_t |
typedef struct ib_rbt_node_struct | ib_rbt_node_t |
typedef struct ib_rbt_bound_struct | ib_rbt_bound_t |
typedef void(* | ib_rbt_print_node) (const ib_rbt_node_t *node) |
typedef int(* | ib_rbt_compare) (const void *p1, const void *p2) |
typedef enum ib_rbt_color_enum | ib_rbt_color_t |
Enumerations | |
enum | ib_rbt_color_enum { IB_RBT_RED, IB_RBT_BLACK } |
Functions | |
UNIV_INTERN void | rbt_free (ib_rbt_t *tree) |
UNIV_INTERN ib_rbt_t * | rbt_create (size_t sizeof_value, ib_rbt_compare compare) |
UNIV_INTERN ibool | rbt_delete (ib_rbt_t *tree, const void *key) |
UNIV_INTERN ib_rbt_node_t * | rbt_remove_node (ib_rbt_t *tree, const ib_rbt_node_t *node) |
UNIV_INTERN const ib_rbt_node_t * | rbt_lookup (const ib_rbt_t *tree, const void *key) |
UNIV_INTERN const ib_rbt_node_t * | rbt_insert (ib_rbt_t *tree, const void *key, const void *value) |
UNIV_INTERN const ib_rbt_node_t * | rbt_add_node (ib_rbt_t *tree, ib_rbt_bound_t *parent, const void *value) |
UNIV_INTERN const ib_rbt_node_t * | rbt_first (const ib_rbt_t *tree) |
UNIV_INTERN const ib_rbt_node_t * | rbt_last (const ib_rbt_t *tree) |
UNIV_INTERN const ib_rbt_node_t * | rbt_next (const ib_rbt_t *tree, const ib_rbt_node_t *current) |
UNIV_INTERN const ib_rbt_node_t * | rbt_prev (const ib_rbt_t *tree, const ib_rbt_node_t *current) |
UNIV_INTERN const ib_rbt_node_t * | rbt_lower_bound (const ib_rbt_t *tree, const void *key) |
UNIV_INTERN const ib_rbt_node_t * | rbt_upper_bound (const ib_rbt_t *tree, const void *key) |
UNIV_INTERN int | rbt_search (const ib_rbt_t *tree, ib_rbt_bound_t *parent, const void *key) |
UNIV_INTERN int | rbt_search_cmp (const ib_rbt_t *tree, ib_rbt_bound_t *parent, const void *key, ib_rbt_compare compare) |
UNIV_INTERN void | rbt_clear (ib_rbt_t *tree) |
UNIV_INTERN ulint | rbt_merge_uniq (ib_rbt_t *dst, const ib_rbt_t *src) |
UNIV_INTERN ulint | rbt_merge_uniq_destructive (ib_rbt_t *dst, ib_rbt_t *src) |
UNIV_INTERN ibool | rbt_validate (const ib_rbt_t *tree) |
UNIV_INTERN void | rbt_print (const ib_rbt_t *tree, ib_rbt_print_node print) |
Copyright (C) 2007, 2010, Innobase Oy. All Rights Reserved.
Portions of this file contain modifications contributed and copyrighted by Sun Microsystems, Inc. Those modifications are gratefully acknowledged and are described briefly in the InnoDB documentation. The contributions by Sun Microsystems are incorporated with their permission, and subject to the conditions contained in the file COPYING.Sun_Microsystems.
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 Foundation; version 2 of the License.
This program 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 this program; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
Various utilities
Created 2007-03-20 Sunny Bains
Definition in file ut0rbt.h.
enum ib_rbt_color_enum |
UNIV_INTERN const ib_rbt_node_t* rbt_add_node | ( | ib_rbt_t * | tree, |
ib_rbt_bound_t * | parent, | ||
const void * | value | ||
) |
Add a new node to the tree, useful for data that is pre-sorted.
Add a new node to the tree, useful for data that is pre-sorted.
tree | in: rb tree |
parent | in: bounds |
value | in: this value is copied to the node |
Definition at line 824 of file ut0rbt.cc.
References rbt_validate(), ut_a, and ut_malloc().
Referenced by rbt_merge_uniq().
UNIV_INTERN void rbt_clear | ( | ib_rbt_t * | tree | ) |
UNIV_INTERN ib_rbt_t* rbt_create | ( | size_t | sizeof_value, |
ib_rbt_compare | compare | ||
) |
Create an instance of a red black tree
Create an instance of a red black tree.
sizeof_value | in: sizeof data item |
compare | in: fn to compare items |
Definition at line 757 of file ut0rbt.cc.
References ut_malloc().
Referenced by btr_create(), and buf_flush_init_flush_rbt().
UNIV_INTERN ibool rbt_delete | ( | ib_rbt_t * | tree, |
const void * | key | ||
) |
Delete a node from the red black tree, identified by key
Delete a node indentified by key.
tree | in: rb tree |
key | in: key to delete |
Definition at line 890 of file ut0rbt.cc.
References rbt_lookup(), and ut_free().
UNIV_INTERN const ib_rbt_node_t* rbt_first | ( | const ib_rbt_t * | tree | ) |
Return the left most data node in the tree
Return the left most node in the tree.
Definition at line 1074 of file ut0rbt.cc.
Referenced by rbt_merge_uniq(), and rbt_merge_uniq_destructive().
UNIV_INTERN void rbt_free | ( | ib_rbt_t * | tree | ) |
Free an instance of a red black tree in: rb tree to free
Free all the nodes and free the tree.
tree | in: rb tree to free |
Definition at line 743 of file ut0rbt.cc.
References ut_free().
Referenced by buf_flush_free_flush_rbt(), and dict_mem_index_free().
UNIV_INTERN const ib_rbt_node_t* rbt_insert | ( | ib_rbt_t * | tree, |
const void * | key, | ||
const void * | value | ||
) |
Add data to the red black tree, identified by key (no dups yet!)
Generic insert of a value in the rb tree.
tree | in: rb tree |
key | in: key for ordering |
value | in: value of key, this value is copied to the node |
Definition at line 795 of file ut0rbt.cc.
References ut_malloc().
UNIV_INTERN const ib_rbt_node_t* rbt_last | ( | const ib_rbt_t * | tree | ) |
UNIV_INTERN const ib_rbt_node_t* rbt_lookup | ( | const ib_rbt_t * | tree, |
const void * | key | ||
) |
Return a node from the red black tree, identified by key, NULL if not found
Find a matching node in the rb tree.
tree | in: rb tree |
key | in: key to use for search |
Definition at line 862 of file ut0rbt.cc.
Referenced by rbt_delete().
UNIV_INTERN const ib_rbt_node_t* rbt_lower_bound | ( | const ib_rbt_t * | tree, |
const void * | key | ||
) |
Find the node that has the lowest key that is >= key.
Find the node that has the lowest key that is >= key.
tree | in: rb tree |
key | in: key to search |
Merge the node from dst into src. Return the number of nodes merged.
Merge the node from dst into src. Return the number of nodes merged.
dst | in: dst rb tree |
src | in: src rb tree |
Definition at line 1155 of file ut0rbt.cc.
References rbt_add_node(), rbt_first(), rbt_next(), and rbt_search().
Merge the node from dst into src. Return the number of nodes merged. 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).
Merge the node from dst into src. Return the number of nodes merged. Delete the nodes from src after copying node to dst. As a side effect the duplicates will be left untouched in the src.
dst | in: dst rb tree |
src | in: src rb tree |
Definition at line 1186 of file ut0rbt.cc.
References rbt_first(), rbt_next(), rbt_search(), rbt_validate(), and ut_a.
UNIV_INTERN const ib_rbt_node_t* rbt_next | ( | const ib_rbt_t * | tree, |
const ib_rbt_node_t * | current | ||
) |
Return the next node from current.
Return the next node.
tree | in: rb tree |
current | in: current node |
Definition at line 1115 of file ut0rbt.cc.
Referenced by rbt_merge_uniq(), and rbt_merge_uniq_destructive().
UNIV_INTERN const ib_rbt_node_t* rbt_prev | ( | const ib_rbt_t * | tree, |
const ib_rbt_node_t * | current | ||
) |
UNIV_INTERN void rbt_print | ( | const ib_rbt_t * | tree, |
ib_rbt_print_node | |||
) |
UNIV_INTERN ib_rbt_node_t* rbt_remove_node | ( | ib_rbt_t * | tree, |
const ib_rbt_node_t * | const_node | ||
) |
Remove a node from the red black tree, NOTE: This function will not delete the node instance, THAT IS THE CALLERS RESPONSIBILITY.
Remove a node from the rb tree, the node is not free'd, that is the callers responsibility.
tree | in: rb tree |
const_node | in: node to delete, this is a fudge and declared const because the caller can access only const nodes |
UNIV_INTERN int rbt_search | ( | const ib_rbt_t * | tree, |
ib_rbt_bound_t * | parent, | ||
const void * | key | ||
) |
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.
Find the node that has the greatest key that is <= key.
tree | in: rb tree |
parent | in: search bounds |
key | in: key to search |
Definition at line 1005 of file ut0rbt.cc.
Referenced by rbt_merge_uniq(), and rbt_merge_uniq_destructive().
UNIV_INTERN int rbt_search_cmp | ( | const ib_rbt_t * | tree, |
ib_rbt_bound_t * | parent, | ||
const void * | key, | ||
ib_rbt_compare | compare | ||
) |
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.
Find the node that has the greatest key that is <= key. But use the supplied comparison function.
tree | in: rb tree |
parent | in: search bounds |
key | in: key to search |
compare | in: fn to compare items |
UNIV_INTERN const ib_rbt_node_t* rbt_upper_bound | ( | const ib_rbt_t * | tree, |
const void * | key | ||
) |
Find the node that has the greatest key that is <= key.
Find the node that has the greatest key that is <= key.
tree | in: rb tree |
key | in: key to search |
UNIV_INTERN ibool rbt_validate | ( | const ib_rbt_t * | tree | ) |
Verify the integrity of the RB tree. For debugging. 0 failure else height of tree (in count of black nodes).
Check that every path from the root to the leaves has the same count and the tree nodes are in order.
tree | in: RB tree to validate |
Definition at line 1233 of file ut0rbt.cc.
Referenced by rbt_add_node(), and rbt_merge_uniq_destructive().