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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
|
// Standard C
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// RB-Implementierung
#include <sys/tree.h>
// clang-format off
struct address {
char name[41];
int age;
RB_ENTRY(address) links;
};
// clang-format on
// type: struct address_tree { ... };
RB_HEAD(address_tree, address);
int
address_compare(const struct address *lhs, const struct address *rhs)
{
int res;
if ( (res = strcmp(lhs->name, rhs->name)) != 0 )
return res;
return (lhs->age < rhs->age) ? -1 : (lhs->age > rhs->age);
}
void
address_init(struct address *address, const char *name, int age)
{
strlcpy(address->name, name, sizeof(address->name));
address->age = age;
}
struct address *
address_new(const char *name, int age)
{
struct address *address;
if ( (address = malloc(sizeof *address)) != NULL ) {
address_init(address, name, age);
}
return address;
}
// Prototypen
RB_PROTOTYPE_STATIC(address_tree, address, links, address_compare)
// Implemtierungen
RB_GENERATE_STATIC(address_tree, address, links, address_compare)
void
insert(struct address_tree *addresses, struct address *address)
{
RB_INSERT(address_tree, addresses, address);
}
void
iterate(struct address_tree *addresses)
{
struct address *ptr;
for ( ptr = RB_MIN(address_tree, addresses);
ptr != NULL;
ptr = RB_NEXT(address_tree, addresses, ptr) ) {
printf("%s\n", ptr->name);
}
}
void
iterate2(struct address_tree *addresses)
{
struct address *ptr;
RB_FOREACH(ptr, address_tree, addresses)
{
printf("%s\n", ptr->name);
}
}
struct address *
search(struct address_tree *addresses, const char *name, int age)
{
struct address key;
address_init(&key, name, age);
return RB_FIND(address_tree, addresses, &key);
}
void
delete_one(struct address_tree *addresses, struct address *address)
{
if ( address != NULL ) {
RB_REMOVE(address_tree, addresses, address);
free(address);
}
}
void
delete_all(struct address_tree *addresses)
{
struct address *ptr;
while ( (ptr = RB_MIN(address_tree, addresses)) != NULL ) {
RB_REMOVE(address_tree, addresses, ptr);
free(ptr);
}
}
int
main(void)
{
struct address_tree addresses = RB_INITIALIZER(&addresses);
// struct address_tree addresses;
// RB_INIT(&addresses);
insert(&addresses, address_new("Thomas", 44));
insert(&addresses, address_new("Markus", 44));
insert(&addresses, address_new("Miriam", 44));
insert(&addresses, address_new("Albert", 44));
iterate(&addresses);
struct address *ptr_miriam = search(&addresses, "Miriam", 44);
if ( ptr_miriam != NULL )
printf("Gefunden: %s (%d)\n", ptr_miriam->name, ptr_miriam->age);
else
printf("Nicht gefunden\n");
delete_one(&addresses, ptr_miriam);
iterate2(&addresses);
delete_all(&addresses);
return EXIT_SUCCESS;
}
|
