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 AVL_H
00027 #define AVL_H 1
00028
00029 #include <stddef.h>
00030
00031
00032 typedef int avl_comparison_func (const void *avl_a, const void *avl_b,
00033 void *avl_param);
00034 typedef void avl_item_func (void *avl_item, void *avl_param);
00035 typedef void *avl_copy_func (void *avl_item, void *avl_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 avl_allocator_default;
00049 void *avl_malloc (struct libavl_allocator *, size_t);
00050 void avl_free (struct libavl_allocator *, void *);
00051
00052
00053 #ifndef AVL_MAX_HEIGHT
00054 #define AVL_MAX_HEIGHT 32
00055 #endif
00056
00057
00058 struct avl_table
00059 {
00060 struct avl_node *avl_root;
00061 avl_comparison_func *avl_compare;
00062 void *avl_param;
00063 struct libavl_allocator *avl_alloc;
00064 size_t avl_count;
00065 unsigned long avl_generation;
00066 };
00067
00068
00069 struct avl_node
00070 {
00071 struct avl_node *avl_link[2];
00072 void *avl_data;
00073 signed char avl_balance;
00074 };
00075
00076
00077 struct avl_traverser
00078 {
00079 struct avl_table *avl_table;
00080 struct avl_node *avl_node;
00081 struct avl_node *avl_stack[AVL_MAX_HEIGHT];
00082
00083 size_t avl_height;
00084 unsigned long avl_generation;
00085 };
00086
00087
00088 struct avl_table *avl_create (avl_comparison_func *, void *,
00089 struct libavl_allocator *);
00090 struct avl_table *avl_copy (const struct avl_table *, avl_copy_func *,
00091 avl_item_func *, struct libavl_allocator *);
00092 void avl_destroy (struct avl_table *, avl_item_func *);
00093 void **avl_probe (struct avl_table *, void *);
00094 void *avl_insert (struct avl_table *, void *);
00095 void *avl_replace (struct avl_table *, void *);
00096 void *avl_delete (struct avl_table *, const void *);
00097 void *avl_find (const struct avl_table *, const void *);
00098 void avl_assert_insert (struct avl_table *, void *);
00099 void *avl_assert_delete (struct avl_table *, void *);
00100
00101 #define avl_count(table) ((size_t) (table)->avl_count)
00102
00103
00104 void avl_t_init (struct avl_traverser *, struct avl_table *);
00105 void *avl_t_first (struct avl_traverser *, struct avl_table *);
00106 void *avl_t_last (struct avl_traverser *, struct avl_table *);
00107 void *avl_t_find (struct avl_traverser *, struct avl_table *, void *);
00108 void *avl_t_insert (struct avl_traverser *, struct avl_table *, void *);
00109 void *avl_t_copy (struct avl_traverser *, const struct avl_traverser *);
00110 void *avl_t_next (struct avl_traverser *);
00111 void *avl_t_prev (struct avl_traverser *);
00112 void *avl_t_cur (struct avl_traverser *);
00113 void *avl_t_replace (struct avl_traverser *, void *);
00114
00115 #endif