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
|
/*
* Copyright (c) 2021, the SerenityOS developers.
* Copyright (c) 2021, Tim Schumacher <timschumi@gmx.de>
*
* SPDX-License-Identifier: BSD-2-Clause
*/
#include <AK/Format.h>
#include <bits/search.h>
#include <search.h>
struct search_tree_node* new_tree_node(const void* key)
{
auto* node = static_cast<struct search_tree_node*>(malloc(sizeof(struct search_tree_node)));
if (!node)
return nullptr;
node->key = key;
node->left = nullptr;
node->right = nullptr;
return node;
}
void delete_node_recursive(struct search_tree_node* node)
{
if (!node)
return;
delete_node_recursive(node->left);
delete_node_recursive(node->right);
free(node);
}
extern "C" {
// https://pubs.opengroup.org/onlinepubs/9699919799/functions/tsearch.html
void* tsearch(const void* key, void** rootp, int (*comparator)(const void*, const void*))
{
if (!rootp)
return nullptr;
if (!*rootp) {
*rootp = new_tree_node(key);
return *rootp;
}
auto node = static_cast<struct search_tree_node*>(*rootp);
while (node != nullptr) {
auto comp = comparator(key, node->key);
if (comp < 0 && node->left) {
node = node->left;
} else if (comp < 0 && !node->left) {
node->left = new_tree_node(key);
return node->left;
} else if (comp > 0 && node->right) {
node = node->right;
} else if (comp > 0 && !node->right) {
node->right = new_tree_node(key);
return node->right;
} else {
return node;
}
}
VERIFY_NOT_REACHED();
}
// https://pubs.opengroup.org/onlinepubs/9699919799/functions/tfind.html
void* tfind(const void* key, void* const* rootp, int (*comparator)(const void*, const void*))
{
if (!rootp)
return nullptr;
auto node = static_cast<struct search_tree_node*>(*rootp);
while (node != nullptr) {
auto comp = comparator(key, node->key);
if (comp < 0)
node = node->left;
else if (comp > 0)
node = node->right;
else
return node;
}
return nullptr;
}
// https://pubs.opengroup.org/onlinepubs/9699919799/functions/tdelete.html
void* tdelete(const void*, void**, int (*)(const void*, const void*))
{
dbgln("FIXME: Implement tdelete()");
TODO();
}
static void twalk_internal(const struct search_tree_node* node, void (*action)(const void*, VISIT, int), int depth)
{
if (!node)
return;
if (!node->right && !node->left) {
action(node, leaf, depth);
return;
}
action(node, preorder, depth);
twalk_internal(node->left, action, depth + 1);
action(node, postorder, depth);
twalk_internal(node->right, action, depth + 1);
action(node, endorder, depth);
}
// https://pubs.opengroup.org/onlinepubs/9699919799/functions/twalk.html
void twalk(const void* rootp, void (*action)(const void*, VISIT, int))
{
auto node = static_cast<const struct search_tree_node*>(rootp);
twalk_internal(node, action, 0);
}
}
|
