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_ELEMENT *	tree_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