MySQL 8.0.30
Source Code Documentation
tree.cc File Reference

Code for handling red-black (balanced) binary trees. More...

#include <stdio.h>
#include <string.h>
#include <sys/types.h>
#include "my_alloc.h"
#include "my_base.h"
#include "my_dbug.h"
#include "my_inttypes.h"
#include "my_pointer_arithmetic.h"
#include "my_sys.h"
#include "my_tree.h"
#include "mysql/service_mysql_alloc.h"
#include "mysys/mysys_priv.h"

Macros

#define BLACK   1
 
#define RED   0
 
#define DEFAULT_ALLOC_SIZE   8192
 

Functions

static void delete_tree_element (TREE *, TREE_ELEMENT *)
 
static int tree_walk_left_root_right (TREE *, TREE_ELEMENT *, tree_walk_action, void *)
 
static int tree_walk_right_root_left (TREE *, TREE_ELEMENT *, tree_walk_action, void *)
 
static void left_rotate (TREE_ELEMENT **parent, TREE_ELEMENT *leaf)
 
static void right_rotate (TREE_ELEMENT **parent, TREE_ELEMENT *leaf)
 
static void rb_insert (TREE *tree, TREE_ELEMENT ***parent, TREE_ELEMENT *leaf)
 
static void rb_delete_fixup (TREE *tree, TREE_ELEMENT ***parent)
 
static int test_rb_tree (TREE_ELEMENT *element)
 
void init_tree (TREE *tree, ulong memory_limit, int element_size, qsort2_cmp compare, bool with_delete, tree_element_free free_element, const void *custom_arg)
 
static void free_tree (TREE *tree, bool reuse)
 
void delete_tree (TREE *tree)
 
void reset_tree (TREE *tree)
 
TREE_ELEMENTtree_insert (TREE *tree, void *key, uint key_size, const void *custom_arg)
 
int tree_delete (TREE *tree, void *key, uint key_size, const void *custom_arg)
 
void * tree_search (TREE *tree, void *key, const void *custom_arg)
 
void * tree_search_key (TREE *tree, const void *key, TREE_ELEMENT **parents, TREE_ELEMENT ***last_pos, enum ha_rkey_function flag, const void *custom_arg)
 
void * tree_search_edge (TREE *tree, TREE_ELEMENT **parents, TREE_ELEMENT ***last_pos, int child_offs)
 
void * tree_search_next (TREE *tree, TREE_ELEMENT ***last_pos, int l_offs, int r_offs)
 
ha_rows tree_record_pos (TREE *tree, const void *key, enum ha_rkey_function flag, const void *custom_arg)
 
int tree_walk (TREE *tree, tree_walk_action action, void *argument, TREE_WALK visit)
 

Detailed Description

Code for handling red-black (balanced) binary trees.

key in tree is allocated according to following:

1) If size < 0 then tree will not allocate keys and only a pointer to each key is saved in tree. compare and search functions uses and returns key-pointer

2) If size == 0 then there are two options:

  • key_size != 0 to tree_insert: The key will be stored in the tree.
  • key_size == 0 to tree_insert: A pointer to the key is stored. compare and search functions uses and returns key-pointer.

3) if key_size is given to init_tree then each node will continue the key and calls to insert_key may increase length of key. if key_size > sizeof(pointer) and key_size is a multiple of 8 (double align) then key will be put on a 8 aligned address. Else the key will be on address (element+1). This is transparent for user compare and search functions uses a pointer to given key-argument.

  • If you use a free function for tree-elements and you are freeing the element itself, you should use key_size = 0 to init_tree and tree_search

The actual key in TREE_ELEMENT is saved as a pointer or after the TREE_ELEMENT struct. If one uses only pointers in tree one can use tree_set_pointer() to change address of data.

Macro Definition Documentation

◆ BLACK

#define BLACK   1

◆ DEFAULT_ALLOC_SIZE

#define DEFAULT_ALLOC_SIZE   8192

◆ RED

#define RED   0

Function Documentation

◆ delete_tree()

void delete_tree ( TREE tree)

◆ delete_tree_element()

static void delete_tree_element ( TREE tree,
TREE_ELEMENT element 
)
static

◆ free_tree()

static void free_tree ( TREE tree,
bool  reuse 
)
static

◆ init_tree()

void init_tree ( TREE tree,
ulong  memory_limit,
int  element_size,
qsort2_cmp  compare,
bool  with_delete,
tree_element_free  free_element,
const void *  custom_arg 
)

◆ left_rotate()

static void left_rotate ( TREE_ELEMENT **  parent,
TREE_ELEMENT leaf 
)
static

◆ rb_delete_fixup()

static void rb_delete_fixup ( TREE tree,
TREE_ELEMENT ***  parent 
)
static

◆ rb_insert()

static void rb_insert ( TREE tree,
TREE_ELEMENT ***  parent,
TREE_ELEMENT leaf 
)
static

◆ reset_tree()

void reset_tree ( TREE tree)

◆ right_rotate()

static void right_rotate ( TREE_ELEMENT **  parent,
TREE_ELEMENT leaf 
)
static

◆ test_rb_tree()

static int test_rb_tree ( TREE_ELEMENT element)
static

◆ tree_delete()

int tree_delete ( TREE tree,
void *  key,
uint  key_size,
const void *  custom_arg 
)

◆ tree_insert()

TREE_ELEMENT * tree_insert ( TREE tree,
void *  key,
uint  key_size,
const void *  custom_arg 
)

◆ tree_record_pos()

ha_rows tree_record_pos ( TREE tree,
const void *  key,
enum ha_rkey_function  flag,
const void *  custom_arg 
)

◆ tree_search()

void * tree_search ( TREE tree,
void *  key,
const void *  custom_arg 
)

◆ tree_search_edge()

void * tree_search_edge ( TREE tree,
TREE_ELEMENT **  parents,
TREE_ELEMENT ***  last_pos,
int  child_offs 
)

◆ tree_search_key()

void * tree_search_key ( TREE tree,
const void *  key,
TREE_ELEMENT **  parents,
TREE_ELEMENT ***  last_pos,
enum ha_rkey_function  flag,
const void *  custom_arg 
)

◆ tree_search_next()

void * tree_search_next ( TREE tree,
TREE_ELEMENT ***  last_pos,
int  l_offs,
int  r_offs 
)

◆ tree_walk()

int tree_walk ( TREE tree,
tree_walk_action  action,
void *  argument,
TREE_WALK  visit 
)

◆ tree_walk_left_root_right()

static int tree_walk_left_root_right ( TREE tree,
TREE_ELEMENT element,
tree_walk_action  action,
void *  argument 
)
static

◆ tree_walk_right_root_left()

static int tree_walk_right_root_left ( TREE tree,
TREE_ELEMENT element,
tree_walk_action  action,
void *  argument 
)
static