LibC: Implement tfind and tsearch

6 files changed, 265 insertions, 0 deletions

diff --git a/Tests/LibC/CMakeLists.txt b/Tests/LibC/CMakeLists.txt
index c309b233a3..9976d2ebab 100644
--- a/Tests/LibC/CMakeLists.txt
+++ b/Tests/LibC/CMakeLists.txt
@@ -11,6 +11,7 @@ set(TEST_SOURCES
     TestQsort.cpp
     TestRealpath.cpp
     TestScanf.cpp
+    TestSearch.cpp
     TestSnprintf.cpp
     TestStackSmash.cpp
     TestStrlcpy.cpp
diff --git a/Tests/LibC/TestSearch.cpp b/Tests/LibC/TestSearch.cpp
new file mode 100644
index 0000000000..170f1345f0
--- /dev/null
+++ b/Tests/LibC/TestSearch.cpp
@@ -0,0 +1,139 @@
+/*
+ * Copyright (c) 2021, Tim Schumacher <timschumi@gmx.de>
+ *
+ * SPDX-License-Identifier: BSD-2-Clause
+ */
+
+#include <LibTest/TestCase.h>
+
+#include <bits/search.h>
+#include <search.h>
+#include <string.h>
+
+#define NODE(node) static_cast<struct search_tree_node*>(node)
+#define ROOTP(root) reinterpret_cast<void**>(root)
+#define COMP(func) reinterpret_cast<int (*)(const void*, const void*)>(func)
+
+TEST_CASE(tsearch)
+{
+    struct search_tree_node* root = nullptr;
+    void* ret;
+    const char* key;
+    char* search;
+
+    // Try a nullptr rootp.
+    ret = tsearch("buggie", nullptr, COMP(strcmp));
+    EXPECT_EQ(ret, nullptr);
+
+    // Try creating a new tree.
+    key = "5";
+    ret = tsearch(key, ROOTP(&root), COMP(strcmp));
+    EXPECT_EQ(ret, root);
+    EXPECT_EQ(NODE(ret)->key, key);
+
+    // Insert an element on the left side.
+    key = "3";
+    ret = tsearch(key, ROOTP(&root), COMP(strcmp));
+    EXPECT_EQ(ret, root->left);
+    EXPECT_EQ(NODE(ret)->key, key);
+
+    // Insert an element on the right side.
+    key = "7";
+    ret = tsearch(key, ROOTP(&root), COMP(strcmp));
+    EXPECT_EQ(ret, root->right);
+    EXPECT_EQ(NODE(ret)->key, key);
+
+    // Add another layer for testing.
+    ret = tsearch("2", ROOTP(&root), COMP(strcmp));
+    EXPECT_EQ(ret, root->left->left);
+    ret = tsearch("4", ROOTP(&root), COMP(strcmp));
+    EXPECT_EQ(ret, root->left->right);
+    ret = tsearch("6", ROOTP(&root), COMP(strcmp));
+    EXPECT_EQ(ret, root->right->left);
+    ret = tsearch("8", ROOTP(&root), COMP(strcmp));
+    EXPECT_EQ(ret, root->right->right);
+
+    // Find the root element.
+    // strdup ensures that we are using the comparator.
+    search = strdup("5");
+    ret = tsearch(search, ROOTP(&root), COMP(strcmp));
+    EXPECT_EQ(ret, root);
+    free(search);
+
+    // Find the lowest-level elements.
+    search = strdup("2");
+    ret = tsearch(search, ROOTP(&root), COMP(strcmp));
+    EXPECT_EQ(ret, root->left->left);
+    free(search);
+
+    search = strdup("4");
+    ret = tsearch(search, ROOTP(&root), COMP(strcmp));
+    EXPECT_EQ(ret, root->left->right);
+    free(search);
+
+    search = strdup("6");
+    ret = tsearch(search, ROOTP(&root), COMP(strcmp));
+    EXPECT_EQ(ret, root->right->left);
+    free(search);
+
+    search = strdup("8");
+    ret = tsearch(search, ROOTP(&root), COMP(strcmp));
+    EXPECT_EQ(ret, root->right->right);
+    free(search);
+
+    delete_node_recursive(root);
+}
+
+TEST_CASE(tfind)
+{
+    struct search_tree_node* root = nullptr;
+    void* ret;
+    char* search;
+
+    // Try a nullptr rootp.
+    ret = tfind("buggie", nullptr, COMP(strcmp));
+    EXPECT_EQ(ret, nullptr);
+
+    // Search for something that doesn't exist.
+    ret = tfind("buggie", ROOTP(&root), COMP(strcmp));
+    EXPECT_EQ(ret, nullptr);
+
+    // Construct a tree for testing.
+    root = new_tree_node("5");
+    root->left = new_tree_node("3");
+    root->right = new_tree_node("7");
+    root->left->left = new_tree_node("2");
+    root->left->right = new_tree_node("4");
+    root->right->left = new_tree_node("6");
+    root->right->right = new_tree_node("8");
+
+    // Find the root element.
+    // strdup ensures that we are using the comparator.
+    search = strdup("5");
+    ret = tfind(search, ROOTP(&root), COMP(strcmp));
+    EXPECT_EQ(ret, root);
+    free(search);
+
+    // Find the lowest-level elements.
+    search = strdup("2");
+    ret = tfind(search, ROOTP(&root), COMP(strcmp));
+    EXPECT_EQ(ret, root->left->left);
+    free(search);
+
+    search = strdup("4");
+    ret = tfind(search, ROOTP(&root), COMP(strcmp));
+    EXPECT_EQ(ret, root->left->right);
+    free(search);
+
+    search = strdup("6");
+    ret = tfind(search, ROOTP(&root), COMP(strcmp));
+    EXPECT_EQ(ret, root->right->left);
+    free(search);
+
+    search = strdup("8");
+    ret = tfind(search, ROOTP(&root), COMP(strcmp));
+    EXPECT_EQ(ret, root->right->right);
+    free(search);
+
+    delete_node_recursive(root);
+}
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