00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016 #pragma once
00017
00018 #include <unistd.h>
00019
00020 #include <drizzled/base.h>
00021 #include <drizzled/qsort_cmp.h>
00022 #include <drizzled/memory/root.h>
00023
00024 namespace drizzled
00025 {
00026
00027
00028 static const int MAX_TREE_HEIGHT= 64;
00029
00030 static const int TREE_NO_DUPS= 1;
00031
00032 typedef enum { left_root_right, right_root_left } TREE_WALK;
00033 typedef int (*tree_walk_action)(void *,uint32_t,void *);
00034
00035 typedef enum { free_init, free_free, free_end } TREE_FREE;
00036 typedef void (*tree_element_free)(void*, TREE_FREE, void *);
00037
00038 typedef struct st_tree_element {
00039 struct st_tree_element *left,*right;
00040 uint32_t count:31,
00041 colour:1;
00042 } TREE_ELEMENT;
00043
00044 static const int TREE_ELEMENT_EXTRA_SIZE= (sizeof(TREE_ELEMENT) + sizeof(void*));
00045
00046
00047 typedef struct st_tree {
00048 TREE_ELEMENT *root,null_element;
00049 TREE_ELEMENT **parents[MAX_TREE_HEIGHT];
00050 uint32_t offset_to_key, elements_in_tree, size_of_element;
00051 size_t memory_limit;
00052 size_t allocated;
00053 qsort_cmp2 compare;
00054 void *custom_arg;
00055 memory::Root mem_root;
00056 bool with_delete;
00057 tree_element_free free;
00058 uint32_t flag;
00059 } TREE;
00060
00061
00062 void init_tree(TREE *tree, size_t default_alloc_size, uint32_t memory_limit,
00063 uint32_t size, qsort_cmp2 compare, bool with_delete,
00064 tree_element_free free_element, void *custom_arg);
00065 void delete_tree(TREE*);
00066 void reset_tree(TREE*);
00067
00068
00069
00070
00071 #define is_tree_inited(tree) ((tree)->root != 0)
00072
00073
00074 TREE_ELEMENT *tree_insert(TREE *tree,void *key, uint32_t key_size,
00075 void *custom_arg);
00076 int tree_walk(TREE *tree,tree_walk_action action,
00077 void *argument, TREE_WALK visit);
00078 int tree_delete(TREE *tree, void *key, uint32_t key_size, void *custom_arg);
00079 void *tree_search_key(TREE *tree, const void *key,
00080 TREE_ELEMENT **parents, TREE_ELEMENT ***last_pos,
00081 enum ha_rkey_function flag, void *custom_arg);
00082 void *tree_search_edge(TREE *tree, TREE_ELEMENT **parents,
00083 TREE_ELEMENT ***last_pos, int child_offs);
00084 void *tree_search_next(TREE *tree, TREE_ELEMENT ***last_pos, int l_offs,
00085 int r_offs);
00086 ha_rows tree_record_pos(TREE *tree, const void *key,
00087 enum ha_rkey_function search_flag, void *custom_arg);
00088
00089 }
00090