1 // Copyright (c) 2000, 2017, Oracle and/or its affiliates. All rights reserved. 2 // 3 // This program is free software; you can redistribute it and/or modify 4 // it under the terms of the GNU General Public License, version 2.0, as 5 // published by the Free Software Foundation. 6 // 7 // This program is also distributed with certain software (including 8 // but not limited to OpenSSL) that is licensed under separate terms, 9 // as designated in a particular file or component or in included license 10 // documentation. The authors of MySQL hereby grant you an 11 // additional permission to link the program and your derivative works 12 // with the separately licensed software that they have included with 13 // MySQL. 14 // 15 // Without limiting anything contained in the foregoing, this file, 16 // which is part of MySQL Server, is also subject to the 17 // Universal FOSS Exception, version 1.0, a copy of which can be found at 18 // http://oss.oracle.com/licenses/universal-foss-exception. 19 // 20 // This program is distributed in the hope that it will be useful, but 21 // WITHOUT ANY WARRANTY; without even the implied warranty of 22 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. 23 // See the GNU General Public License, version 2.0, for more details. 24 // 25 // You should have received a copy of the GNU General Public License 26 // along with this program; if not, write to the Free Software Foundation, Inc., 27 // 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA 28 29 #ifndef _tree_h 30 #define _tree_h 31 32 /** 33 @file include/my_tree.h 34 */ 35 36 #include <stddef.h> 37 #include <sys/types.h> 38 39 #include "my_alloc.h" /* MEM_ROOT */ 40 #include "my_base.h" /* get 'enum ha_rkey_function' */ 41 #include "my_inttypes.h" 42 #include "my_sys.h" /* qsort2_cmp */ 43 44 /* Worst case tree is half full. This gives use 2^(MAX_TREE_HEIGHT/2) leafs */ 45 #define MAX_TREE_HEIGHT 64 46 47 #define ELEMENT_KEY(tree, element) \ 48 (tree->offset_to_key ? (void *)((uchar *)element + tree->offset_to_key) \ 49 : *((void **)(element + 1))) 50 51 #define tree_set_pointer(element, ptr) \ 52 *((uchar **)(element + 1)) = ((uchar *)(ptr)) 53 54 #define TREE_NO_DUPS 1 55 56 typedef enum { left_root_right, right_root_left } TREE_WALK; 57 typedef uint32 element_count; 58 typedef int (*tree_walk_action)(void *, element_count, void *); 59 60 typedef enum { free_init, free_free, free_end } TREE_FREE; 61 typedef void (*tree_element_free)(void *, TREE_FREE, const void *); 62 63 struct TREE_ELEMENT { TREE_ELEMENTTREE_ELEMENT64 TREE_ELEMENT() : count(0), colour(0) {} 65 66 TREE_ELEMENT *left{nullptr}, *right{nullptr}; 67 uint32 count : 31, colour : 1; /* black is marked as 1 */ 68 }; 69 70 #define ELEMENT_CHILD(element, offs) \ 71 (*(TREE_ELEMENT **)((char *)element + offs)) 72 73 struct TREE { 74 TREE_ELEMENT *root{nullptr}, null_element; 75 TREE_ELEMENT **parents[MAX_TREE_HEIGHT]{nullptr}; 76 uint offset_to_key{0}, elements_in_tree{0}, size_of_element{0}; 77 ulong memory_limit{0}, allocated{0}; 78 qsort2_cmp compare{nullptr}; 79 const void *custom_arg{nullptr}; 80 MEM_ROOT mem_root; 81 bool with_delete{false}; 82 tree_element_free free{nullptr}; 83 uint flag{0}; 84 }; 85 86 /* Functions on whole tree */ 87 void init_tree(TREE *tree, size_t default_alloc_size, ulong memory_limit, 88 int size, qsort2_cmp compare, bool with_delete, 89 tree_element_free free_element, const void *custom_arg); 90 void delete_tree(TREE *); 91 void reset_tree(TREE *); 92 /* similar to delete tree, except we do not my_free() blocks in mem_root 93 */ 94 #define is_tree_inited(tree) ((tree)->root != 0) 95 96 /* Functions on leafs */ 97 TREE_ELEMENT *tree_insert(TREE *tree, void *key, uint key_size, 98 const void *custom_arg); 99 void *tree_search(TREE *tree, void *key, const void *custom_arg); 100 int tree_walk(TREE *tree, tree_walk_action action, void *argument, 101 TREE_WALK visit); 102 int tree_delete(TREE *tree, void *key, uint key_size, const void *custom_arg); 103 void *tree_search_key(TREE *tree, const void *key, TREE_ELEMENT **parents, 104 TREE_ELEMENT ***last_pos, enum ha_rkey_function flag, 105 const void *custom_arg); 106 void *tree_search_edge(TREE *tree, TREE_ELEMENT **parents, 107 TREE_ELEMENT ***last_pos, int child_offs); 108 void *tree_search_next(TREE *tree, TREE_ELEMENT ***last_pos, int l_offs, 109 int r_offs); 110 ha_rows tree_record_pos(TREE *tree, const void *key, 111 enum ha_rkey_function search_flag, 112 const void *custom_arg); 113 114 #define TREE_ELEMENT_EXTRA_SIZE (sizeof(TREE_ELEMENT) + sizeof(void *)) 115 116 #endif 117