Eneboo - Documentación para desarrolladores
src/libmysql_macosx/include/my_tree.h
Ir a la documentación de este archivo.
00001 /* Copyright (C) 2000 MySQL AB
00002 
00003    This program is free software; you can redistribute it and/or modify
00004    it under the terms of the GNU General Public License as published by
00005    the Free Software Foundation; either version 2 of the License, or
00006    (at your option) any later version.
00007 
00008    This program is distributed in the hope that it will be useful,
00009    but WITHOUT ANY WARRANTY; without even the implied warranty of
00010    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00011    GNU General Public License for more details.
00012 
00013    You should have received a copy of the GNU General Public License
00014    along with this program; if not, write to the Free Software
00015    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
00016 
00017 #ifndef _tree_h
00018 #define _tree_h
00019 #ifdef  __cplusplus
00020 extern "C" {
00021 #endif
00022 
00023 #include "my_base.h"            /* get 'enum ha_rkey_function' */
00024 
00025 /* Worst case tree is half full. This gives use 2^(MAX_TREE_HEIGHT/2) leafs */
00026 #define MAX_TREE_HEIGHT 64
00027 
00028 #define ELEMENT_KEY(tree,element)\
00029 (tree->offset_to_key ? (void*)((byte*) element+tree->offset_to_key) :\
00030                         *((void**) (element+1)))
00031 
00032 #define tree_set_pointer(element,ptr) *((byte **) (element+1))=((byte*) (ptr))
00033 
00034 #define TREE_NO_DUPS 1
00035 
00036 typedef enum { left_root_right, right_root_left } TREE_WALK;
00037 typedef uint32 element_count;
00038 typedef int (*tree_walk_action)(void *,element_count,void *);
00039 
00040 typedef enum { free_init, free_free, free_end } TREE_FREE;
00041 typedef void (*tree_element_free)(void*, TREE_FREE, void *);
00042 
00043 #ifdef MSDOS
00044 typedef struct st_tree_element {
00045   struct st_tree_element *left,*right;
00046   unsigned long count;
00047   uchar    colour;                      /* black is marked as 1 */
00048 } TREE_ELEMENT;
00049 #else
00050 typedef struct st_tree_element {
00051   struct st_tree_element *left,*right;
00052   uint32 count:31,
00053          colour:1;                      /* black is marked as 1 */
00054 } TREE_ELEMENT;
00055 #endif /* MSDOS */
00056 
00057 #define ELEMENT_CHILD(element, offs) (*(TREE_ELEMENT**)((char*)element + offs))
00058 
00059 typedef struct st_tree {
00060   TREE_ELEMENT *root,null_element;
00061   TREE_ELEMENT **parents[MAX_TREE_HEIGHT];
00062   uint offset_to_key,elements_in_tree,size_of_element,memory_limit,allocated;
00063   qsort_cmp2 compare;
00064   void *custom_arg;
00065   MEM_ROOT mem_root;
00066   my_bool with_delete;
00067   tree_element_free free;
00068   uint flag;
00069 } TREE;
00070 
00071         /* Functions on whole tree */
00072 void init_tree(TREE *tree, uint default_alloc_size, uint memory_limit,
00073                int size, qsort_cmp2 compare, my_bool with_delete,
00074                tree_element_free free_element, void *custom_arg);
00075 void delete_tree(TREE*);
00076 void reset_tree(TREE*);
00077   /* similar to delete tree, except we do not my_free() blocks in mem_root
00078    */
00079 #define is_tree_inited(tree) ((tree)->root != 0)
00080 
00081         /* Functions on leafs */
00082 TREE_ELEMENT *tree_insert(TREE *tree,void *key, uint key_size, 
00083                           void *custom_arg);
00084 void *tree_search(TREE *tree, void *key, void *custom_arg);
00085 int tree_walk(TREE *tree,tree_walk_action action,
00086               void *argument, TREE_WALK visit);
00087 int tree_delete(TREE *tree, void *key, void *custom_arg);
00088 void *tree_search_key(TREE *tree, const void *key, 
00089                       TREE_ELEMENT **parents, TREE_ELEMENT ***last_pos,
00090                       enum ha_rkey_function flag, void *custom_arg);
00091 void *tree_search_edge(TREE *tree, TREE_ELEMENT **parents, 
00092                         TREE_ELEMENT ***last_pos, int child_offs);
00093 void *tree_search_next(TREE *tree, TREE_ELEMENT ***last_pos, int l_offs, 
00094                        int r_offs);
00095 ha_rows tree_record_pos(TREE *tree, const void *key, 
00096                      enum ha_rkey_function search_flag, void *custom_arg);
00097 
00098 #define TREE_ELEMENT_EXTRA_SIZE (sizeof(TREE_ELEMENT) + sizeof(void*))
00099 
00100 #ifdef  __cplusplus
00101 }
00102 #endif
00103 #endif
 Todo Clases Namespaces Archivos Funciones Variables 'typedefs' Enumeraciones Valores de enumeraciones Propiedades Amigas 'defines'