00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026 #ifndef TAVL_H
00027 #define TAVL_H 1
00028
00029 #include <stddef.h>
00030
00031
00032 typedef int tavl_comparison_func (const void *tavl_a, const void *tavl_b,
00033 void *tavl_param);
00034 typedef void tavl_item_func (void *tavl_item, void *tavl_param);
00035 typedef void *tavl_copy_func (void *tavl_item, void *tavl_param);
00036
00037 #ifndef LIBAVL_ALLOCATOR
00038 #define LIBAVL_ALLOCATOR
00039
00040 struct libavl_allocator
00041 {
00042 void *(*libavl_malloc) (struct libavl_allocator *, size_t libavl_size);
00043 void (*libavl_free) (struct libavl_allocator *, void *libavl_block);
00044 };
00045 #endif
00046
00047
00048 extern struct libavl_allocator tavl_allocator_default;
00049 void *tavl_malloc (struct libavl_allocator *, size_t);
00050 void tavl_free (struct libavl_allocator *, void *);
00051
00052
00053 #ifndef TAVL_MAX_HEIGHT
00054 #define TAVL_MAX_HEIGHT 32
00055 #endif
00056
00057
00058 struct tavl_table
00059 {
00060 struct tavl_node *tavl_root;
00061 tavl_comparison_func *tavl_compare;
00062 void *tavl_param;
00063 struct libavl_allocator *tavl_alloc;
00064 size_t tavl_count;
00065 };
00066
00067
00068 enum tavl_tag
00069 {
00070 TAVL_CHILD,
00071 TAVL_THREAD
00072 };
00073
00074
00075 struct tavl_node
00076 {
00077 struct tavl_node *tavl_link[2];
00078 void *tavl_data;
00079 unsigned char tavl_tag[2];
00080 signed char tavl_balance;
00081 };
00082
00083
00084 struct tavl_traverser
00085 {
00086 struct tavl_table *tavl_table;
00087 struct tavl_node *tavl_node;
00088 };
00089
00090
00091 struct tavl_table *tavl_create (tavl_comparison_func *, void *,
00092 struct libavl_allocator *);
00093 struct tavl_table *tavl_copy (const struct tavl_table *, tavl_copy_func *,
00094 tavl_item_func *, struct libavl_allocator *);
00095 void tavl_destroy (struct tavl_table *, tavl_item_func *);
00096 void **tavl_probe (struct tavl_table *, void *);
00097 void *tavl_insert (struct tavl_table *, void *);
00098 void *tavl_replace (struct tavl_table *, void *);
00099 void *tavl_delete (struct tavl_table *, const void *);
00100 void *tavl_find (const struct tavl_table *, const void *);
00101 void tavl_assert_insert (struct tavl_table *, void *);
00102 void *tavl_assert_delete (struct tavl_table *, void *);
00103
00104 #define tavl_count(table) ((size_t) (table)->tavl_count)
00105
00106
00107 void tavl_t_init (struct tavl_traverser *, struct tavl_table *);
00108 void *tavl_t_first (struct tavl_traverser *, struct tavl_table *);
00109 void *tavl_t_last (struct tavl_traverser *, struct tavl_table *);
00110 void *tavl_t_find (struct tavl_traverser *, struct tavl_table *, void *);
00111 void *tavl_t_insert (struct tavl_traverser *, struct tavl_table *, void *);
00112 void *tavl_t_copy (struct tavl_traverser *, const struct tavl_traverser *);
00113 void *tavl_t_next (struct tavl_traverser *);
00114 void *tavl_t_prev (struct tavl_traverser *);
00115 void *tavl_t_cur (struct tavl_traverser *);
00116 void *tavl_t_replace (struct tavl_traverser *, void *);
00117
00118 #endif