jcs.org
Serenity Operating System
1/*
2 * Copyright (c) 2021, the SerenityOS developers.
3 * Copyright (c) 2021, Tim Schumacher <timschumi@gmx.de>
4 *
5 * SPDX-License-Identifier: BSD-2-Clause
6 */
7
8#include <AK/Format.h>
9#include <bits/search.h>
10#include <search.h>
11
12struct search_tree_node* new_tree_node(void const* key)
13{
14 auto* node = static_cast<struct search_tree_node*>(malloc(sizeof(struct search_tree_node)));
15
16 if (!node)
17 return nullptr;
18
19 node->key = key;
20 node->left = nullptr;
21 node->right = nullptr;
22
23 return node;
24}
25
26void delete_node_recursive(struct search_tree_node* node)
27{
28 if (!node)
29 return;
30
31 delete_node_recursive(node->left);
32 delete_node_recursive(node->right);
33
34 free(node);
35}
36
37extern "C" {
38
39// https://pubs.opengroup.org/onlinepubs/9699919799/functions/tsearch.html
40void* tsearch(void const* key, void** rootp, int (*comparator)(void const*, void const*))
41{
42 if (!rootp)
43 return nullptr;
44
45 if (!*rootp) {
46 *rootp = new_tree_node(key);
47 return *rootp;
48 }
49
50 auto node = static_cast<struct search_tree_node*>(*rootp);
51
52 while (node != nullptr) {
53 auto comp = comparator(key, node->key);
54
55 if (comp < 0 && node->left) {
56 node = node->left;
57 } else if (comp < 0 && !node->left) {
58 node->left = new_tree_node(key);
59 return node->left;
60 } else if (comp > 0 && node->right) {
61 node = node->right;
62 } else if (comp > 0 && !node->right) {
63 node->right = new_tree_node(key);
64 return node->right;
65 } else {
66 return node;
67 }
68 }
69
70 VERIFY_NOT_REACHED();
71}
72
73// https://pubs.opengroup.org/onlinepubs/9699919799/functions/tfind.html
74void* tfind(void const* key, void* const* rootp, int (*comparator)(void const*, void const*))
75{
76 if (!rootp)
77 return nullptr;
78
79 auto node = static_cast<struct search_tree_node*>(*rootp);
80
81 while (node != nullptr) {
82 auto comp = comparator(key, node->key);
83
84 if (comp < 0)
85 node = node->left;
86 else if (comp > 0)
87 node = node->right;
88 else
89 return node;
90 }
91
92 return nullptr;
93}
94
95// https://pubs.opengroup.org/onlinepubs/9699919799/functions/tdelete.html
96void* tdelete(void const*, void**, int (*)(void const*, void const*))
97{
98 dbgln("FIXME: Implement tdelete()");
99 return nullptr;
100}
101
102static void twalk_internal(const struct search_tree_node* node, void (*action)(void const*, VISIT, int), int depth)
103{
104 if (!node)
105 return;
106
107 if (!node->right && !node->left) {
108 action(node, leaf, depth);
109 return;
110 }
111
112 action(node, preorder, depth);
113 twalk_internal(node->left, action, depth + 1);
114 action(node, postorder, depth);
115 twalk_internal(node->right, action, depth + 1);
116 action(node, endorder, depth);
117}
118
119// https://pubs.opengroup.org/onlinepubs/9699919799/functions/twalk.html
120void twalk(void const* rootp, void (*action)(void const*, VISIT, int))
121{
122 auto node = static_cast<const struct search_tree_node*>(rootp);
123
124 twalk_internal(node, action, 0);
125}
126}