1 /* Copyright (c) 2000-2002, 2004, 2006, 2007 MySQL AB
3 This program is free software; you can redistribute it and/or modify
4 it under the terms of the GNU General Public License as published by
5 the Free Software Foundation; version 2 of the License.
7 This program is distributed in the hope that it will be useful,
8 but WITHOUT ANY WARRANTY; without even the implied warranty of
9 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10 GNU General Public License for more details.
12 You should have received a copy of the GNU General Public License
13 along with this program; if not, write to the Free Software
14 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA */
22 #include "my_base.h" /* get 'enum ha_rkey_function' */
24 /* Worst case tree is half full. This gives use 2^(MAX_TREE_HEIGHT/2) leafs */
25 #define MAX_TREE_HEIGHT 64
27 #define ELEMENT_KEY(tree,element)\
28 (tree->offset_to_key ? (void*)((uchar*) element+tree->offset_to_key) :\
29 *((void**) (element+1)))
31 #define tree_set_pointer(element,ptr) *((uchar **) (element+1))=((uchar*) (ptr))
33 #define TREE_NO_DUPS 1
35 typedef enum { left_root_right
, right_root_left
} TREE_WALK
;
36 typedef uint32 element_count
;
37 typedef int (*tree_walk_action
)(void *,element_count
,void *);
39 typedef enum { free_init
, free_free
, free_end
} TREE_FREE
;
40 typedef void (*tree_element_free
)(void*, TREE_FREE
, void *);
42 typedef struct st_tree_element
{
43 struct st_tree_element
*left
,*right
;
45 colour
:1; /* black is marked as 1 */
48 #define ELEMENT_CHILD(element, offs) (*(TREE_ELEMENT**)((char*)element + offs))
50 typedef struct st_tree
{
51 TREE_ELEMENT
*root
,null_element
;
52 TREE_ELEMENT
**parents
[MAX_TREE_HEIGHT
];
53 uint offset_to_key
,elements_in_tree
,size_of_element
;
54 ulong memory_limit
, allocated
;
59 tree_element_free free
;
63 /* Functions on whole tree */
64 void init_tree(TREE
*tree
, ulong default_alloc_size
, ulong memory_limit
,
65 int size
, qsort_cmp2 compare
, my_bool with_delete
,
66 tree_element_free free_element
, void *custom_arg
);
67 void delete_tree(TREE
*);
68 void reset_tree(TREE
*);
69 /* similar to delete tree, except we do not my_free() blocks in mem_root
71 #define is_tree_inited(tree) ((tree)->root != 0)
73 /* Functions on leafs */
74 TREE_ELEMENT
*tree_insert(TREE
*tree
,void *key
, uint key_size
,
76 void *tree_search(TREE
*tree
, void *key
, void *custom_arg
);
77 int tree_walk(TREE
*tree
,tree_walk_action action
,
78 void *argument
, TREE_WALK visit
);
79 int tree_delete(TREE
*tree
, void *key
, uint key_size
, void *custom_arg
);
80 void *tree_search_key(TREE
*tree
, const void *key
,
81 TREE_ELEMENT
**parents
, TREE_ELEMENT
***last_pos
,
82 enum ha_rkey_function flag
, void *custom_arg
);
83 void *tree_search_edge(TREE
*tree
, TREE_ELEMENT
**parents
,
84 TREE_ELEMENT
***last_pos
, int child_offs
);
85 void *tree_search_next(TREE
*tree
, TREE_ELEMENT
***last_pos
, int l_offs
,
87 ha_rows
tree_record_pos(TREE
*tree
, const void *key
,
88 enum ha_rkey_function search_flag
, void *custom_arg
);
90 #define TREE_ELEMENT_EXTRA_SIZE (sizeof(TREE_ELEMENT) + sizeof(void*))