mirror/mariadb
1
0
Fork 0
mirror of https://github.com/MariaDB/server.git synced 2025-01-15 19:42:28 +01:00
Code Issues Projects Releases Packages Wiki Activity Actions
mariadb/mysys/tree.c
Sergei Golubchik 7c58e97bf6 perfschema memory related instrumentation changes
2020-03-10 19:24:22 +01:00

804 lines
20 KiB
C
Raw Permalink Blame History

/* Copyright (c) 2000, 2016, Oracle and/or its affiliates.
Copyright (c) 2010, 2016, MariaDB
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., 51 Franklin St, Fifth Floor, Boston, MA 02110-1335 USA */
/*
Code for handling red-black (balanced) binary trees.
key in tree is allocated accrding 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.
Implemented by monty.
*/
/*
NOTE:
tree->compare function should be ALWAYS called as
(*tree->compare)(custom_arg, ELEMENT_KEY(tree,element), key)
and not other way around, as
(*tree->compare)(custom_arg, key, ELEMENT_KEY(tree,element))
ft_boolean_search.c (at least) relies on that.
*/
#include "mysys_priv.h"
#include <m_string.h>
#include <my_tree.h>
#include "my_base.h"
#define BLACK 1
#define RED 0
#define DEFAULT_ALLOC_SIZE 8192
#define DEFAULT_ALIGN_SIZE 8192
static int delete_tree_element(TREE *,TREE_ELEMENT *, my_bool abort);
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 TREE_ELEMENT null_element= { NULL, NULL, 0, BLACK };
/* The actual code for handling binary trees */
#ifndef DBUG_OFF
static int test_rb_tree(TREE_ELEMENT *element);
#endif
void init_tree(TREE *tree, size_t default_alloc_size, size_t memory_limit,
int size, qsort_cmp2 compare,
tree_element_free free_element, void *custom_arg,
myf my_flags)
{
DBUG_ENTER("init_tree");
DBUG_PRINT("enter",("tree: %p size: %d", tree, size));
if (default_alloc_size < DEFAULT_ALLOC_SIZE)
default_alloc_size= DEFAULT_ALLOC_SIZE;
default_alloc_size= MY_ALIGN(default_alloc_size, DEFAULT_ALIGN_SIZE);
tree->root= &null_element;
tree->compare=compare;
tree->size_of_element= size > 0 ? (uint) size : 0;
tree->memory_limit=memory_limit;
tree->free=free_element;
tree->allocated=0;
tree->elements_in_tree=0;
tree->custom_arg = custom_arg;
tree->my_flags= my_flags;
tree->flag= 0;
if (!free_element && size >= 0 &&
((uint) size <= sizeof(void*) || ((uint) size & (sizeof(void*)-1))))
{
/*
We know that the data doesn't have to be aligned (like if the key
contains a double), so we can store the data combined with the
TREE_ELEMENT.
*/
tree->offset_to_key=sizeof(TREE_ELEMENT); /* Put key after element */
/* Fix allocation size so that we don't lose any memory */
default_alloc_size/=(sizeof(TREE_ELEMENT)+size);
if (!default_alloc_size)
default_alloc_size=1;
default_alloc_size*=(sizeof(TREE_ELEMENT)+size);
}
else
{
tree->offset_to_key=0; /* use key through pointer */
tree->size_of_element+=sizeof(void*);
}
if (!(tree->with_delete= MY_TEST(my_flags & MY_TREE_WITH_DELETE)))
{
init_alloc_root(key_memory_TREE, &tree->mem_root, default_alloc_size, 0,
MYF(my_flags));
tree->mem_root.min_malloc= sizeof(TREE_ELEMENT)+tree->size_of_element;
}
DBUG_VOID_RETURN;
}
static int free_tree(TREE *tree, my_bool abort, myf free_flags)
{
int error, first_error= 0;
DBUG_ENTER("free_tree");
DBUG_PRINT("enter",("tree: %p", tree));
if (tree->root) /* If initialized */
{
if (tree->with_delete)
{
if ((error= delete_tree_element(tree, tree->root, abort)))
{
first_error= first_error ? first_error : error;
abort= 1;
}
}
else
{
if (tree->free)
{
if (tree->memory_limit)
(*tree->free)(NULL, free_init, tree->custom_arg);
if ((error= delete_tree_element(tree, tree->root, abort)))
first_error= first_error ? first_error : error;
if (tree->memory_limit)
(*tree->free)(NULL, free_end, tree->custom_arg);
}
free_root(&tree->mem_root, free_flags);
}
}
tree->root= &null_element;
tree->elements_in_tree=0;
tree->allocated=0;
DBUG_RETURN(first_error);
}
/**
Delete tree.
@param tree Tree
@param abort 0 if normal, 1 if tree->free should not be called.
@return 0 ok
<> 0 Returns first <> 0 from (tree->free)(*,free_free,*)
@Notes
If one (tree->free)(,free_free,) returns <> 0, no future
tree->free(*,free_free,*) will be called.
Other tree->free operations (free_init, free_end) will be called
*/
int delete_tree(TREE* tree, my_bool abort)
{
return free_tree(tree, abort, MYF(0)); /* my_free() mem_root if applicable */
}
int reset_tree(TREE* tree)
{
/* do not free mem_root, just mark blocks as free */
return free_tree(tree, 0, MYF(MY_MARK_BLOCKS_FREE));
}
static int delete_tree_element(TREE *tree, TREE_ELEMENT *element,
my_bool abort)
{
int error, first_error= 0;
if (element != &null_element)
{
if ((first_error= delete_tree_element(tree, element->left, abort)))
abort= 1;
if (!abort && tree->free)
{
if ((error= (*tree->free)(ELEMENT_KEY(tree,element), free_free,
tree->custom_arg)))
{
first_error= first_error ? first_error : error;
abort= 1;
}
}
if ((error= delete_tree_element(tree, element->right, abort)))
first_error= first_error ? first_error : error;
if (tree->with_delete)
my_free(element);
}
return first_error;
}
/*
insert, search and delete of elements
The following should be true:
parent[0] = & parent[-1][0]->left ||
parent[0] = & parent[-1][0]->right
*/
TREE_ELEMENT *tree_insert(TREE *tree, void *key, uint key_size,
void* custom_arg)
{
int cmp;
TREE_ELEMENT *element,***parent;
parent= tree->parents;
*parent = &tree->root; element= tree->root;
for (;;)
{
if (element == &null_element ||
(cmp = (*tree->compare)(custom_arg, ELEMENT_KEY(tree,element),
key)) == 0)
break;
if (cmp < 0)
{
*++parent= &element->right; element= element->right;
}
else
{
*++parent = &element->left; element= element->left;
}
}
if (element == &null_element)
{
uint alloc_size;
if (tree->flag & TREE_ONLY_DUPS)
return TREE_ELEMENT_UNIQUE;
alloc_size=sizeof(TREE_ELEMENT)+key_size+tree->size_of_element;
tree->allocated+=alloc_size;
if (tree->memory_limit && tree->elements_in_tree
&& tree->allocated > tree->memory_limit)
{
reset_tree(tree);
return tree_insert(tree, key, key_size, custom_arg);
}
key_size+=tree->size_of_element;
if (tree->with_delete)
element=(TREE_ELEMENT *) my_malloc(key_memory_TREE, alloc_size,
MYF(tree->my_flags | MY_WME));
else
element=(TREE_ELEMENT *) alloc_root(&tree->mem_root,alloc_size);
if (!element)
return(NULL);
**parent=element;
element->left=element->right= &null_element;
if (!tree->offset_to_key)
{
if (key_size == sizeof(void*)) /* no length, save pointer */
*((void**) (element+1))=key;
else
{
*((void**) (element+1))= (void*) ((void **) (element+1)+1);
memcpy((uchar*) *((void **) (element+1)),key,
(size_t) (key_size-sizeof(void*)));
}
}
else
memcpy((uchar*) element+tree->offset_to_key,key,(size_t) key_size);
element->count=1; /* May give warning in purify */
tree->elements_in_tree++;
rb_insert(tree,parent,element); /* rebalance tree */
}
else
{
if (tree->flag & TREE_NO_DUPS)
return(NULL);
element->count++;
/* Avoid a wrap over of the count. */
if (! element->count)
element->count--;
}
DBUG_EXECUTE("check_tree", test_rb_tree(tree->root););
return element;
}
int tree_delete(TREE *tree, void *key, uint key_size, void *custom_arg)
{
int cmp,remove_colour;
TREE_ELEMENT *element,***parent, ***org_parent, *nod;
if (!tree->with_delete)
return 1; /* not allowed */
parent= tree->parents;
*parent= &tree->root; element= tree->root;
for (;;)
{
if (element == &null_element)
return 1; /* Was not in tree */
if ((cmp = (*tree->compare)(custom_arg, ELEMENT_KEY(tree,element),
key)) == 0)
break;
if (cmp < 0)
{
*++parent= &element->right; element= element->right;
}
else
{
*++parent = &element->left; element= element->left;
}
}
if (element->left == &null_element)
{
(**parent)=element->right;
remove_colour= element->colour;
}
else if (element->right == &null_element)
{
(**parent)=element->left;
remove_colour= element->colour;
}
else
{
org_parent= parent;
*++parent= &element->right; nod= element->right;
while (nod->left != &null_element)
{
*++parent= &nod->left; nod= nod->left;
}
(**parent)=nod->right; /* unlink nod from tree */
remove_colour= nod->colour;
org_parent[0][0]=nod; /* put y in place of element */
org_parent[1]= &nod->right;
nod->left=element->left;
nod->right=element->right;
nod->colour=element->colour;
}
if (remove_colour == BLACK)
rb_delete_fixup(tree,parent);
if (tree->free)
(*tree->free)(ELEMENT_KEY(tree,element), free_free, tree->custom_arg);
tree->allocated-= sizeof(TREE_ELEMENT) + tree->size_of_element + key_size;
my_free(element);
tree->elements_in_tree--;
return 0;
}
void *tree_search(TREE *tree, void *key, void *custom_arg)
{
int cmp;
TREE_ELEMENT *element=tree->root;
for (;;)
{
if (element == &null_element)
return (void*) 0;
if ((cmp = (*tree->compare)(custom_arg, ELEMENT_KEY(tree,element),
key)) == 0)
return ELEMENT_KEY(tree,element);
if (cmp < 0)
element=element->right;
else
element=element->left;
}
}
void *tree_search_key(TREE *tree, const void *key,
TREE_ELEMENT **parents, TREE_ELEMENT ***last_pos,
enum ha_rkey_function flag, void *custom_arg)
{
int cmp;
TREE_ELEMENT *element= tree->root;
TREE_ELEMENT **last_left_step_parent= NULL, **last_right_step_parent= NULL;
TREE_ELEMENT **last_equal_element= NULL;
/*
TODO: support for HA_READ_KEY_OR_PREV, HA_READ_PREFIX flags if needed.
*/
*parents = &null_element;
while (element != &null_element)
{
*++parents= element;
if ((cmp= (*tree->compare)(custom_arg, ELEMENT_KEY(tree, element),
key)) == 0)
{
switch (flag) {
case HA_READ_KEY_EXACT:
case HA_READ_KEY_OR_NEXT:
case HA_READ_BEFORE_KEY:
case HA_READ_KEY_OR_PREV:
last_equal_element= parents;
cmp= 1;
break;
case HA_READ_AFTER_KEY:
cmp= -1;
break;
case HA_READ_PREFIX_LAST:
case HA_READ_PREFIX_LAST_OR_PREV:
last_equal_element= parents;
cmp= -1;
break;
default:
return NULL;
}
}
if (cmp < 0) /* element < key */
{
last_right_step_parent= parents;
element= element->right;
}
else
{
last_left_step_parent= parents;
element= element->left;
}
}
switch (flag) {
case HA_READ_KEY_EXACT:
case HA_READ_PREFIX_LAST:
*last_pos= last_equal_element;
break;
case HA_READ_KEY_OR_NEXT:
*last_pos= last_equal_element ? last_equal_element : last_left_step_parent;
break;
case HA_READ_AFTER_KEY:
*last_pos= last_left_step_parent;
break;
case HA_READ_PREFIX_LAST_OR_PREV:
*last_pos= last_equal_element ? last_equal_element : last_right_step_parent;
break;
case HA_READ_BEFORE_KEY:
*last_pos= last_right_step_parent;
break;
case HA_READ_KEY_OR_PREV:
*last_pos= last_equal_element ? last_equal_element : last_right_step_parent;
break;
default:
return NULL;
}
return *last_pos ? ELEMENT_KEY(tree, **last_pos) : NULL;
}
/*
Search first (the most left) or last (the most right) tree element
*/
void *tree_search_edge(TREE *tree, TREE_ELEMENT **parents,
TREE_ELEMENT ***last_pos, int child_offs)
{
TREE_ELEMENT *element= tree->root;
*parents= &null_element;
while (element != &null_element)
{
*++parents= element;
element= ELEMENT_CHILD(element, child_offs);
}
*last_pos= parents;
return **last_pos != &null_element ?
ELEMENT_KEY(tree, **last_pos) : NULL;
}
void *tree_search_next(TREE *tree, TREE_ELEMENT ***last_pos, int l_offs,
int r_offs)
{
TREE_ELEMENT *x= **last_pos;
if (ELEMENT_CHILD(x, r_offs) != &null_element)
{
x= ELEMENT_CHILD(x, r_offs);
*++*last_pos= x;
while (ELEMENT_CHILD(x, l_offs) != &null_element)
{
x= ELEMENT_CHILD(x, l_offs);
*++*last_pos= x;
}
return ELEMENT_KEY(tree, x);
}
else
{
TREE_ELEMENT *y= *--*last_pos;
while (y != &null_element && x == ELEMENT_CHILD(y, r_offs))
{
x= y;
y= *--*last_pos;
}
return y == &null_element ? NULL : ELEMENT_KEY(tree, y);
}
}
/*
Expected that tree is fully balanced
(each path from root to leaf has the same length)
*/
ha_rows tree_record_pos(TREE *tree, const void *key,
enum ha_rkey_function flag, void *custom_arg)
{
int cmp;
TREE_ELEMENT *element= tree->root;
double left= 1;
double right= tree->elements_in_tree;
while (element != &null_element)
{
if ((cmp= (*tree->compare)(custom_arg, ELEMENT_KEY(tree, element),
key)) == 0)
{
switch (flag) {
case HA_READ_KEY_EXACT:
case HA_READ_BEFORE_KEY:
cmp= 1;
break;
case HA_READ_AFTER_KEY:
cmp= -1;
break;
default:
return HA_POS_ERROR;
}
}
if (cmp < 0) /* element < key */
{
element= element->right;
left= (left + right) / 2;
}
else
{
element= element->left;
right= (left + right) / 2;
}
}
switch (flag) {
case HA_READ_KEY_EXACT:
case HA_READ_BEFORE_KEY:
return (ha_rows) right;
case HA_READ_AFTER_KEY:
return (ha_rows) left;
default:
return HA_POS_ERROR;
}
}
int tree_walk(TREE *tree, tree_walk_action action, void *argument, TREE_WALK visit)
{
switch (visit) {
case left_root_right:
return tree_walk_left_root_right(tree,tree->root,action,argument);
case right_root_left:
return tree_walk_right_root_left(tree,tree->root,action,argument);
}
return 0; /* Keep gcc happy */
}
static int tree_walk_left_root_right(TREE *tree, TREE_ELEMENT *element, tree_walk_action action, void *argument)
{
int error;
if (element->left) /* Not null_element */
{
if ((error=tree_walk_left_root_right(tree,element->left,action,
argument)) == 0 &&
(error=(*action)(ELEMENT_KEY(tree,element),
(element_count) element->count,
argument)) == 0)
error=tree_walk_left_root_right(tree,element->right,action,argument);
return error;
}
return 0;
}
static int tree_walk_right_root_left(TREE *tree, TREE_ELEMENT *element, tree_walk_action action, void *argument)
{
int error;
if (element->right) /* Not null_element */
{
if ((error=tree_walk_right_root_left(tree,element->right,action,
argument)) == 0 &&
(error=(*action)(ELEMENT_KEY(tree,element),
(element_count) element->count,
argument)) == 0)
error=tree_walk_right_root_left(tree,element->left,action,argument);
return error;
}
return 0;
}
/* Functions to fix up the tree after insert and delete */
static void left_rotate(TREE_ELEMENT **parent, TREE_ELEMENT *leaf)
{
TREE_ELEMENT *y;
y=leaf->right;
leaf->right=y->left;
parent[0]=y;
y->left=leaf;
}
static void right_rotate(TREE_ELEMENT **parent, TREE_ELEMENT *leaf)
{
TREE_ELEMENT *x;
x=leaf->left;
leaf->left=x->right;
parent[0]=x;
x->right=leaf;
}
static void rb_insert(TREE *tree, TREE_ELEMENT ***parent, TREE_ELEMENT *leaf)
{
TREE_ELEMENT *y,*par,*par2;
leaf->colour=RED;
while (leaf != tree->root && (par=parent[-1][0])->colour == RED)
{
if (par == (par2=parent[-2][0])->left)
{
y= par2->right;
if (y->colour == RED)
{
par->colour=BLACK;
y->colour=BLACK;
leaf=par2;
parent-=2;
leaf->colour=RED; /* And the loop continues */
}
else
{
if (leaf == par->right)
{
left_rotate(parent[-1],par);
par=leaf; /* leaf is now parent to old leaf */
}
par->colour=BLACK;
par2->colour=RED;
right_rotate(parent[-2],par2);
break;
}
}
else
{
y= par2->left;
if (y->colour == RED)
{
par->colour=BLACK;
y->colour=BLACK;
leaf=par2;
parent-=2;
leaf->colour=RED; /* And the loop continues */
}
else
{
if (leaf == par->left)
{
right_rotate(parent[-1],par);
par=leaf;
}
par->colour=BLACK;
par2->colour=RED;
left_rotate(parent[-2],par2);
break;
}
}
}
tree->root->colour=BLACK;
}
static void rb_delete_fixup(TREE *tree, TREE_ELEMENT ***parent)
{
TREE_ELEMENT *x,*w,*par;
x= **parent;
while (x != tree->root && x->colour == BLACK)
{
if (x == (par=parent[-1][0])->left)
{
w=par->right;
if (w->colour == RED)
{
w->colour=BLACK;
par->colour=RED;
left_rotate(parent[-1],par);
parent[0]= &w->left;
*++parent= &par->left;
w=par->right;
}
if (w->left->colour == BLACK && w->right->colour == BLACK)
{
w->colour=RED;
x=par;
parent--;
}
else
{
if (w->right->colour == BLACK)
{
w->left->colour=BLACK;
w->colour=RED;
right_rotate(&par->right,w);
w=par->right;
}
w->colour=par->colour;
par->colour=BLACK;
w->right->colour=BLACK;
left_rotate(parent[-1],par);
x=tree->root;
break;
}
}
else
{
w=par->left;
if (w->colour == RED)
{
w->colour=BLACK;
par->colour=RED;
right_rotate(parent[-1],par);
parent[0]= &w->right;
*++parent= &par->right;
w=par->left;
}
if (w->right->colour == BLACK && w->left->colour == BLACK)
{
w->colour=RED;
x=par;
parent--;
}
else
{
if (w->left->colour == BLACK)
{
w->right->colour=BLACK;
w->colour=RED;
left_rotate(&par->left,w);
w=par->left;
}
w->colour=par->colour;
par->colour=BLACK;
w->left->colour=BLACK;
right_rotate(parent[-1],par);
x=tree->root;
break;
}
}
}
x->colour=BLACK;
}
#ifndef DBUG_OFF
/* Test that the proporties for a red-black tree holds */
static int test_rb_tree(TREE_ELEMENT *element)
{
int count_l,count_r;
if (!element->left)
return 0; /* Found end of tree */
if (element->colour == RED &&
(element->left->colour == RED || element->right->colour == RED))
{
printf("Wrong tree: Found two red in a row\n");
return -1;
}
count_l=test_rb_tree(element->left);
count_r=test_rb_tree(element->right);
if (count_l >= 0 && count_r >= 0)
{
if (count_l == count_r)
return count_l+(element->colour == BLACK);
printf("Wrong tree: Incorrect black-count: %d - %d\n",count_l,count_r);
}
return -1;
}
#endif
Reference in a new issue View git blame Copy permalink