my_tree.h
上传用户:romrleung
上传日期:2022-05-23
资源大小:18897k
文件大小:4k
源码类别:

MySQL数据库

开发平台:

Visual C++

  1. /* Copyright (C) 2000 MySQL AB
  2.    This program is free software; you can redistribute it and/or modify
  3.    it under the terms of the GNU General Public License as published by
  4.    the Free Software Foundation; either version 2 of the License, or
  5.    (at your option) any later version.
  6.    This program is distributed in the hope that it will be useful,
  7.    but WITHOUT ANY WARRANTY; without even the implied warranty of
  8.    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  9.    GNU General Public License for more details.
  10.    You should have received a copy of the GNU General Public License
  11.    along with this program; if not, write to the Free Software
  12.    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
  13. #ifndef _tree_h
  14. #define _tree_h
  15. #ifdef __cplusplus
  16. extern "C" {
  17. #endif
  18. #include "my_base.h" /* get 'enum ha_rkey_function' */
  19. /* Worst case tree is half full. This gives use 2^(MAX_TREE_HEIGHT/2) leafs */
  20. #define MAX_TREE_HEIGHT 64
  21. #define ELEMENT_KEY(tree,element)
  22. (tree->offset_to_key ? (void*)((byte*) element+tree->offset_to_key) :
  23. *((void**) (element+1)))
  24. #define tree_set_pointer(element,ptr) *((byte **) (element+1))=((byte*) (ptr))
  25. #define TREE_NO_DUPS 1
  26. typedef enum { left_root_right, right_root_left } TREE_WALK;
  27. typedef uint32 element_count;
  28. typedef int (*tree_walk_action)(void *,element_count,void *);
  29. typedef enum { free_init, free_free, free_end } TREE_FREE;
  30. typedef void (*tree_element_free)(void*, TREE_FREE, void *);
  31. #ifdef MSDOS
  32. typedef struct st_tree_element {
  33.   struct st_tree_element *left,*right;
  34.   unsigned long count;
  35.   uchar    colour; /* black is marked as 1 */
  36. } TREE_ELEMENT;
  37. #else
  38. typedef struct st_tree_element {
  39.   struct st_tree_element *left,*right;
  40.   uint32 count:31,
  41.  colour:1; /* black is marked as 1 */
  42. } TREE_ELEMENT;
  43. #endif /* MSDOS */
  44. #define ELEMENT_CHILD(element, offs) (*(TREE_ELEMENT**)((char*)element + offs))
  45. typedef struct st_tree {
  46.   TREE_ELEMENT *root,null_element;
  47.   TREE_ELEMENT **parents[MAX_TREE_HEIGHT];
  48.   uint offset_to_key,elements_in_tree,size_of_element,memory_limit,allocated;
  49.   qsort_cmp2 compare;
  50.   void *custom_arg;
  51.   MEM_ROOT mem_root;
  52.   my_bool with_delete;
  53.   tree_element_free free;
  54.   uint flag;
  55. } TREE;
  56. /* Functions on whole tree */
  57. void init_tree(TREE *tree, uint default_alloc_size, uint memory_limit,
  58.                int size, qsort_cmp2 compare, my_bool with_delete,
  59.        tree_element_free free_element, void *custom_arg);
  60. void delete_tree(TREE*);
  61. void reset_tree(TREE*);
  62.   /* similar to delete tree, except we do not my_free() blocks in mem_root
  63.    */
  64. #define is_tree_inited(tree) ((tree)->root != 0)
  65. /* Functions on leafs */
  66. TREE_ELEMENT *tree_insert(TREE *tree,void *key, uint key_size, 
  67.                           void *custom_arg);
  68. void *tree_search(TREE *tree, void *key, void *custom_arg);
  69. int tree_walk(TREE *tree,tree_walk_action action,
  70.       void *argument, TREE_WALK visit);
  71. int tree_delete(TREE *tree, void *key, void *custom_arg);
  72. void *tree_search_key(TREE *tree, const void *key, 
  73.                       TREE_ELEMENT **parents, TREE_ELEMENT ***last_pos,
  74.                       enum ha_rkey_function flag, void *custom_arg);
  75. void *tree_search_edge(TREE *tree, TREE_ELEMENT **parents, 
  76.                         TREE_ELEMENT ***last_pos, int child_offs);
  77. void *tree_search_next(TREE *tree, TREE_ELEMENT ***last_pos, int l_offs, 
  78.                        int r_offs);
  79. ha_rows tree_record_pos(TREE *tree, const void *key, 
  80.                      enum ha_rkey_function search_flag, void *custom_arg);
  81. #define TREE_ELEMENT_EXTRA_SIZE (sizeof(TREE_ELEMENT) + sizeof(void*))
  82. #ifdef __cplusplus
  83. }
  84. #endif
  85. #endif