Drizzled Public API Documentation

ut0rbt.h File Reference
#include "univ.i"
#include "ut0mem.h"

Go to the source code of this file.

Classes

struct  ib_rbt_node_struct
 
struct  ib_rbt_struct
 
struct  ib_rbt_bound_struct
 

Macros

#define INNOBASE_UT0RBT_H
 
#define rbt_size(t)   (t->n_nodes)
 
#define rbt_empty(t)   (rbt_size(t) == 0)
 
#define rbt_value(t, n)   ((t*) &n->value[0])
 
#define rbt_compare(t, k, n)   (t->compare(k, n->value))
 

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_trbt_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_trbt_remove_node (ib_rbt_t *tree, const ib_rbt_node_t *node)
 
UNIV_INTERN const ib_rbt_node_trbt_lookup (const ib_rbt_t *tree, const void *key)
 
UNIV_INTERN const ib_rbt_node_trbt_insert (ib_rbt_t *tree, const void *key, const void *value)
 
UNIV_INTERN const ib_rbt_node_trbt_add_node (ib_rbt_t *tree, ib_rbt_bound_t *parent, const void *value)
 
UNIV_INTERN const ib_rbt_node_trbt_first (const ib_rbt_t *tree)
 
UNIV_INTERN const ib_rbt_node_trbt_last (const ib_rbt_t *tree)
 
UNIV_INTERN const ib_rbt_node_trbt_next (const ib_rbt_t *tree, const ib_rbt_node_t *current)
 
UNIV_INTERN const ib_rbt_node_trbt_prev (const ib_rbt_t *tree, const ib_rbt_node_t *current)
 
UNIV_INTERN const ib_rbt_node_trbt_lower_bound (const ib_rbt_t *tree, const void *key)
 
UNIV_INTERN const ib_rbt_node_trbt_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)
 

Detailed Description

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.

Enumeration Type Documentation

Red black tree color types

Definition at line 63 of file ut0rbt.h.

Function Documentation

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.

Returns
appended node in: this value is copied to the node

Add a new node to the tree, useful for data that is pre-sorted.

Returns
appended node
Parameters
treein: rb tree
parentin: bounds
valuein: 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)

Clear the tree, deletes (and free's) all the nodes. in: rb tree

Reset the tree. Delete all the nodes.

Parameters
treein: rb tree

Definition at line 1140 of file ut0rbt.cc.

UNIV_INTERN ib_rbt_t* rbt_create ( size_t  sizeof_value,
ib_rbt_compare  compare 
)

Create an instance of a red black tree

Returns
rb tree instance in: comparator

Create an instance of a red black tree.

Returns
an empty rb tree
Parameters
sizeof_valuein: sizeof data item
comparein: 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.

Returns
TRUE if success FALSE if not found
Parameters
treein: rb tree
keyin: 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

Returns
left most node in: rb 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.

Parameters
treein: 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!)

Returns
inserted node in: data that will be copied to the node.

Generic insert of a value in the rb tree.

Returns
inserted node
Parameters
treein: rb tree
keyin: key for ordering
valuein: 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)

Return the right most data node in the tree

Returns
right most node in: rb tree

Return the right most node in the tree.

Returns
the rightmost node or NULL
Parameters
treein: rb tree

Definition at line 1095 of file ut0rbt.cc.

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

Returns
node if found else return NULL in: key to lookup

Find a matching node in the rb tree.

Returns
NULL if not found else the node where key was found
Parameters
treein: rb tree
keyin: 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.

Returns
node that satisfies the lower bound constraint or NULL in: key to search

Find the node that has the lowest key that is >= key.

Returns
node satisfying the lower bound constraint or NULL
Parameters
treein: rb tree
keyin: key to search

Definition at line 937 of file ut0rbt.cc.

UNIV_INTERN ulint rbt_merge_uniq ( ib_rbt_t dst,
const ib_rbt_t src 
)

Merge the node from dst into src. Return the number of nodes merged.

Returns
no. of recs merged in: src rb tree

Merge the node from dst into src. Return the number of nodes merged.

Returns
no. of recs merged
Parameters
dstin: dst rb tree
srcin: src rb tree

Definition at line 1155 of file ut0rbt.cc.

References rbt_add_node(), rbt_first(), rbt_next(), and rbt_search().

UNIV_INTERN ulint rbt_merge_uniq_destructive ( ib_rbt_t dst,
ib_rbt_t src 
)

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

Returns
no. of recs merged in: src rb tree

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.

Returns
no. of recs merged
Parameters
dstin: dst rb tree
srcin: 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.

Returns
successor node to current that is passed in.

Return the next node.

Returns
node next from current
Parameters
treein: rb tree
currentin: 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 
)

Return the prev node from current.

Returns
precedessor node to current that is passed in

Return the previous node.

Returns
node prev from current
Parameters
treein: rb tree
currentin: current node

Definition at line 1128 of file ut0rbt.cc.

UNIV_INTERN void rbt_print ( const ib_rbt_t tree,
ib_rbt_print_node  print 
)

Iterate over the tree in depth first order. in: print function

Iterate over the tree in depth first order.

Parameters
treein: tree to traverse
printin: print function

Definition at line 1248 of file ut0rbt.cc.

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.

Returns
the deleted node with the const. in: node to delete, this is a fudge and declared const because the caller has access only to const nodes.

Remove a node from the rb tree, the node is not free'd, that is the callers responsibility.

Returns
deleted node but without the const
Parameters
treein: rb tree
const_nodein: node to delete, this is a fudge and declared const because the caller can access only const nodes

Definition at line 914 of file ut0rbt.cc.

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.

Returns
result of last comparison in: key to search

Find the node that has the greatest key that is <= key.

Returns
value of result
Parameters
treein: rb tree
parentin: search bounds
keyin: 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.

Returns
result of last comparison in: comparator

Find the node that has the greatest key that is <= key. But use the supplied comparison function.

Returns
value of result
Parameters
treein: rb tree
parentin: search bounds
keyin: key to search
comparein: fn to compare items

Definition at line 1040 of file ut0rbt.cc.

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.

Returns
node that satisifies the upper bound constraint or NULL in: key to search

Find the node that has the greatest key that is <= key.

Returns
node satisfying the upper bound constraint or NULL
Parameters
treein: rb tree
keyin: key to search

Definition at line 971 of file ut0rbt.cc.

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

Returns
TRUE if OK FALSE if tree invalid. in: tree to validate

Check that every path from the root to the leaves has the same count and the tree nodes are in order.

Returns
TRUE if OK FALSE otherwise
Parameters
treein: RB tree to validate

Definition at line 1233 of file ut0rbt.cc.

Referenced by rbt_add_node(), and rbt_merge_uniq_destructive().