LibC: Implement tfind and tsearch

4 files changed, 125 insertions, 0 deletions

diff --git a/Userland/Libraries/LibC/CMakeLists.txt b/Userland/Libraries/LibC/CMakeLists.txt
index 42d9704355..7115afe75b 100644
--- a/Userland/Libraries/LibC/CMakeLists.txt
+++ b/Userland/Libraries/LibC/CMakeLists.txt
@@ -33,6 +33,7 @@ set(LIBC_SOURCES
     resolv.cpp
     scanf.cpp
     sched.cpp
+    search.cpp
     serenity.cpp
     shadow.cpp
     signal.cpp
diff --git a/Userland/Libraries/LibC/bits/search.h b/Userland/Libraries/LibC/bits/search.h
new file mode 100644
index 0000000000..9c68cd8a93
--- /dev/null
+++ b/Userland/Libraries/LibC/bits/search.h
@@ -0,0 +1,18 @@
+/*
+ * Copyright (c) 2021, the SerenityOS developers.
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#pragma once
+
+// This is technically an implementation detail, but we require this for testing.
+// The key always has to be the first struct member.
+struct search_tree_node {
+    const void* key;
+    struct search_tree_node* left;
+    struct search_tree_node* right;
+};
+
+struct search_tree_node* new_tree_node(const void* key);
+void delete_node_recursive(struct search_tree_node* node);
diff --git a/Userland/Libraries/LibC/search.cpp b/Userland/Libraries/LibC/search.cpp
new file mode 100644
index 0000000000..9909e42cb6
--- /dev/null
+++ b/Userland/Libraries/LibC/search.cpp
@@ -0,0 +1,92 @@
+/*
+ * 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" {
+
+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();
+}
+
+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;
+}
+}
diff --git a/Userland/Libraries/LibC/search.h b/Userland/Libraries/LibC/search.h
new file mode 100644
index 0000000000..a9f4fd96e2
--- /dev/null
+++ b/Userland/Libraries/LibC/search.h
@@ -0,0 +1,14 @@
+/*
+ * Copyright (c) 2021, the SerenityOS developers.
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#pragma once
+
+__BEGIN_DECLS
+
+void* tsearch(const void*, void**, int (*)(const void*, const void*));
+void* tfind(const void*, void* const*, int (*)(const void*, const void*));
+
+__END_DECLS