-
Notifications
You must be signed in to change notification settings - Fork 2
/
avl.h
124 lines (103 loc) · 4.39 KB
/
avl.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
/*
* Copyright (c) 2010 Axel Neumann
* This program is free software; you can redistribute it and/or
* modify it under the terms of version 2 of the GNU General Public
* License as published by the Free Software Foundation.
*
* This program is distributed in the hope that it will be useful, but
* WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
* 02110-1301, USA
*/
/*
* avl code inspired by:
* http://eternallyconfuzzled.com/tuts/datastructures/jsw_tut_avl.aspx
* where Julienne Walker said (web page from 28. 2. 2010 12:55):
* ...Once again, all of the code in this tutorial is in the public domain.
* You can do whatever you want with it, but I assume no responsibility
* for any damages from improper use. ;-)
*/
#ifndef _AVL_H
#define _AVL_H
#include <stdint.h>
#define AVL_MAX_HEIGHT 128
struct avl_node {
void *item;
int balance;
struct avl_node * up;
struct avl_node * down[2];
#ifdef AVL_5XLINKED
struct avl_node * left; // it less-equal node
struct avl_node * right; // it greater node
#endif
};
// obtain key pointer based on avl_node pointer
#define AVL_NODE_KEY( a_tree, a_node ) ( (void*) ( ((char*)(a_node)->item)+((a_tree)->key_offset) ) )
// obtain key pointer based on item pointer
#define AVL_ITEM_KEY( a_tree, a_item ) ( (void*) ( ((char*)(a_item))+((a_tree)->key_offset) ) )
struct avl_tree {
struct avl_node *root;
#ifdef AVL_5XLINKED
struct avl_node *first;
struct avl_node *last;
#endif
uint16_t key_size;
uint16_t key_offset;
uint32_t items;
};
#ifdef AVL_5XLINKED
#define AVL_INIT_TREE(tree, element_type, key_field) do { \
tree.root = NULL; \
tree.first = NULL; \
tree.last = NULL; \
tree.key_size = sizeof( (((element_type *) 0)->key_field) ); \
tree.key_offset = ((unsigned long) (&((element_type *) 0)->key_field)); \
tree.items = 0; \
} while (0)
#define AVL_TREE(tree, element_type, key_field) struct avl_tree (tree) = { \
NULL, NULL, NULL, \
(sizeof( (((element_type *) 0)->key_field) )), \
((unsigned long)(&(((element_type *)0)->key_field))), \
0 }
#else
#define AVL_INIT_TREE(tree, element_type, key_field) do { \
tree.root = NULL; \
tree.key_size = sizeof( (((element_type *) 0)->key_field) ); \
tree.key_offset = ((unsigned long) (&((element_type *) 0)->key_field)); \
tree.items = 0; \
} while (0)
#define AVL_TREE(tree, element_type, key_field) struct avl_tree (tree) = { \
NULL, \
(sizeof( (((element_type *) 0)->key_field) )), \
((unsigned long)(&(((element_type *)0)->key_field))), \
0 }
#endif
#define avl_height(p) ((p) == NULL ? -1 : (p)->balance)
#define avl_max(a,b) ((a) > (b) ? (a) : (b))
struct avl_node *avl_find( struct avl_tree *tree, void *key );
void *avl_find_item( struct avl_tree *tree, void *key );
void *avl_next_item(struct avl_tree *tree, void *key);
void *avl_first_item(struct avl_tree *tree);
void *avl_iterate_item(struct avl_tree *tree, struct avl_node **it );
void *_avl_find_item_by_field(struct avl_tree *tree, void *value, unsigned long offset, uint32_t size);
#define avl_find_item_by_field(tree,val,s,field) _avl_find_item_by_field( tree, val, (unsigned long)((&(((struct s*)0)->field))), sizeof(((struct s*)0)->field) )
void avl_insert(struct avl_tree *tree, void *node, int32_t tag);
void *avl_remove(struct avl_tree *tree, void *key, int32_t tag);
void *avl_remove_first_item(struct avl_tree *tree, int32_t tag);
void init_avl(void);
#ifdef AVL_DEBUG
struct avl_iterator {
struct avl_node * up[AVL_MAX_HEIGHT];
int upd[AVL_MAX_HEIGHT];
int top;
};
struct avl_node *avl_iter(struct avl_tree *tree, struct avl_iterator *it );
void avl_debug( struct avl_tree *tree );
void avl_test(int m);
#endif
#endif