blob: 479e2a608620b27ec0788bc6b8cda6a95b74191b (
plain)
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
|
/*
* tree.c
* (c) 2019 Jonas Gunz
* License: MIT
* */
#include "tree.h"
static int string_compare ( char* _1, char* _2 );
int tree_insert ( struct tree_node** _root, char* _key, void* _data )
{
struct tree_node** node = _root;
while( *node ) {
int ret = string_compare ( (*node)->key, _key );
if ( ret > 0 ) {
node = & (*node)->above;
} else if ( ret < 0 ) {
node = & (*node)->below;
} else { //Already exists
return 1;
}
}
*node = malloc (sizeof(typeof(**node)));
if( ! *node )
return 2;
memset ( *node, 0, sizeof(typeof(**node)) );
(*node)->key = _key;
(*node)->data = _data;
return 0;
}
int tree_balance ( struct tree_node** _root )
{
return 1;
}
int tree_destroy ( struct tree_node** _root, uint8_t _options )
{
while(*_root)
{
struct tree_node** node = _root;
while( (*node)->above || (*node)->below )
node= (*node)->above ? & (*node)->above : & (*node)->below ;
printf( "%s\n", (*node)->data );
if (_options & _TREE_FREE_KEY)
free( (*node)->data );
if (_options & _TREE_FREE_KEY)
free( (*node)->key );
free ( *node );
*node = NULL;
}
return 0;
}
static int string_compare ( char* _1, char* _2 )
{
if ( !_1 || !_2 )
return 99;
int i;
for (i = 0; _1[i] && _2[i]; i++) {
char c1 = _1[i];
char c2 = _2[i];
//Convert to uppercase
if ( c1 >= 97 && c1 <= 122 )
c1 -= 32;
if ( c2 >= 97 && c2 <= 122 )
c2 -= 32;
if (c1 > c2)
return 1;
if (c1 < c2)
return -1;
}
if ( _1[i] == _2[i] )
return 0;
if ( _1[i] )
return 1;
if ( _2[i] )
return -1;
//TODO WARN may reach end of non-void function
return 99;
}
void* tree_get ( struct tree_node** _root, char* _query )
{
struct tree_node** node = _root;
while(*node) {
int ret = string_compare ( (*node)->key, _query );
if ( ret > 0 ) {
node = & (*node)->above;
} else if ( ret < 0 ) {
node = & (*node)->below;
} else {
break;
}
}
return *node ? (*node)->data : NULL;
return 0;
}
|