/* Copyright (C) 2000 MySQL AB 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; either version 2 of the License, or (at your option) any later version. 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 */ /* 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 allign) then key will be put on a 8 alligned adress. Else the key will be on adress (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 #include #include "my_base.h" #define BLACK 1 #define RED 0 #define DEFAULT_ALLOC_SIZE 8192 #define DEFAULT_ALIGN_SIZE 8192 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); /* The actuall code for handling binary trees */ #ifndef DBUG_OFF static int test_rb_tree(TREE_ELEMENT *element); #endif void init_tree(TREE *tree, uint default_alloc_size, uint memory_limit, int size, qsort_cmp2 compare, my_bool with_delete, tree_element_free free_element, void *custom_arg) { DBUG_ENTER("init_tree"); DBUG_PRINT("enter",("tree: 0x%lx 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); bzero((gptr) &tree->null_element,sizeof(tree->null_element)); tree->root= &tree->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->null_element.colour=BLACK; tree->null_element.left=tree->null_element.right=0; 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=with_delete)) { init_alloc_root(&tree->mem_root, default_alloc_size,0); tree->mem_root.min_malloc=(sizeof(TREE_ELEMENT)+tree->size_of_element); } DBUG_VOID_RETURN; } static void free_tree(TREE *tree, myf free_flags) { DBUG_ENTER("free_tree"); DBUG_PRINT("enter",("tree: 0x%lx",tree)); if (tree->root) /* If initialized */ { if (tree->with_delete) delete_tree_element(tree,tree->root); else { if (tree->free) { if (tree->memory_limit) (*tree->free)(NULL, free_init, tree->custom_arg); delete_tree_element(tree,tree->root); if (tree->memory_limit) (*tree->free)(NULL, free_end, tree->custom_arg); } free_root(&tree->mem_root, free_flags); } } tree->root= &tree->null_element; tree->elements_in_tree=0; tree->allocated=0; DBUG_VOID_RETURN; } void delete_tree(TREE* tree) { free_tree(tree, MYF(0)); /* my_free() mem_root if applicable */ } void reset_tree(TREE* tree) { /* do not free mem_root, just mark blocks as free */ free_tree(tree, MYF(MY_MARK_BLOCKS_FREE)); } static void delete_tree_element(TREE *tree, TREE_ELEMENT *element) { if (element != &tree->null_element) { delete_tree_element(tree,element->left); if (tree->free) (*tree->free)(ELEMENT_KEY(tree,element), free_free, tree->custom_arg); delete_tree_element(tree,element->right); if (tree->with_delete) my_free((char*) element,MYF(0)); } } /* 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 == &tree->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 == &tree->null_element) { uint 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(alloc_size, MYF(MY_WME)); else element=(TREE_ELEMENT *) alloc_root(&tree->mem_root,alloc_size); if (!element) return(NULL); **parent=element; element->left=element->right= &tree->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((byte*) *((void **) (element+1)),key, (size_t) (key_size-sizeof(void*))); } } else memcpy((byte*) 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++; } DBUG_EXECUTE("check_tree", test_rb_tree(tree->root);); return element; } int tree_delete(TREE *tree, void *key, 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 == &tree->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 == &tree->null_element) { (**parent)=element->right; remove_colour= element->colour; } else if (element->right == &tree->null_element) { (**parent)=element->left; remove_colour= element->colour; } else { org_parent= parent; *++parent= &element->right; nod= element->right; while (nod->left != &tree->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); /* This doesn't include key_size, but better than nothing */ tree->allocated-= sizeof(TREE_ELEMENT)+tree->size_of_element; my_free((gptr) element,MYF(0)); 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 == &tree->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 = &tree->null_element; while (element != &tree->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: 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; 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= &tree->null_element; while (element != &tree->null_element) { *++parents= element; element= ELEMENT_CHILD(element, child_offs); } *last_pos= parents; return **last_pos != &tree->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) != &tree->null_element) { x= ELEMENT_CHILD(x, r_offs); *++*last_pos= x; while (ELEMENT_CHILD(x, l_offs) != &tree->null_element) { x= ELEMENT_CHILD(x, l_offs); *++*last_pos= x; } return ELEMENT_KEY(tree, x); } else { TREE_ELEMENT *y= *--*last_pos; while (y != &tree->null_element && x == ELEMENT_CHILD(y, r_offs)) { x= y; y= *--*last_pos; } return y == &tree->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 != &tree->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