Implement twalk(3), add unit tests.
I've also added insque(3) and remque(3) (from NetBSD because the OpenBSD
ones are currently broken for non-circular lists).
I've not added the three hash table functions that should be in this header
because they operate on a single global hash table and thus aren't likely
to be useful.
Bug: https://code.google.com/p/android/issues/detail?id=73719
Change-Id: I97397a7b921e2e860fd9c8032cafd9097380498a
diff --git a/tests/search_test.cpp b/tests/search_test.cpp
new file mode 100644
index 0000000..3900c89
--- /dev/null
+++ b/tests/search_test.cpp
@@ -0,0 +1,210 @@
+/*
+ * Copyright (C) 2014 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#include <gtest/gtest.h>
+
+#include <search.h>
+
+static int int_cmp(const void* lhs, const void* rhs) {
+ return *reinterpret_cast<const int*>(rhs) - *reinterpret_cast<const int*>(lhs);
+}
+
+TEST(search, lfind_lsearch) {
+ int xs[10];
+ memset(xs, 0, sizeof(xs));
+ size_t x_size = 0;
+
+ int needle;
+
+ // lfind(3) can't find '2' in the empty table.
+ needle = 2;
+ ASSERT_EQ(nullptr, lfind(&needle, xs, &x_size, sizeof(xs[0]), int_cmp));
+ ASSERT_EQ(0U, x_size);
+
+ // lsearch(3) will add it.
+ ASSERT_EQ(&xs[0], lsearch(&needle, xs, &x_size, sizeof(xs[0]), int_cmp));
+ ASSERT_EQ(2, xs[0]);
+ ASSERT_EQ(1U, x_size);
+
+ // And then lfind(3) can find it.
+ ASSERT_EQ(&xs[0], lfind(&needle, xs, &x_size, sizeof(xs[0]), int_cmp));
+ ASSERT_EQ(1U, x_size);
+
+ // Inserting a duplicate does nothing (but returns the existing element).
+ ASSERT_EQ(&xs[0], lsearch(&needle, xs, &x_size, sizeof(xs[0]), int_cmp));
+ ASSERT_EQ(1U, x_size);
+}
+
+struct node {
+ node(const char* s) : s(strdup(s)) {}
+
+ char* s;
+};
+
+static int node_cmp(const void* lhs, const void* rhs) {
+ return strcmp(reinterpret_cast<const node*>(lhs)->s, reinterpret_cast<const node*>(rhs)->s);
+}
+
+static std::vector<std::string> g_nodes;
+
+static void node_walk(const void* p, VISIT order, int) {
+ const node* n = *reinterpret_cast<const node* const*>(p);
+ if (order == postorder || order == leaf) {
+ g_nodes.push_back(n->s);
+ }
+}
+
+static size_t g_free_calls;
+
+static void node_free(void* p) {
+ node* n = reinterpret_cast<node*>(p);
+ free(n->s);
+ ++g_free_calls;
+}
+
+TEST(search, tfind_tsearch_twalk_tdestroy) {
+ void* root = nullptr;
+
+ node n1("z");
+ node n2("a");
+ node n3("m");
+
+ // tfind(3) can't find anything in the empty tree.
+ ASSERT_EQ(nullptr, tfind(&n1, &root, node_cmp));
+ ASSERT_EQ(nullptr, tfind(&n2, &root, node_cmp));
+ ASSERT_EQ(nullptr, tfind(&n3, &root, node_cmp));
+
+ // tsearch(3) inserts and returns a pointer to a new node.
+ void* i1 = tsearch(&n1, &root, node_cmp);
+ ASSERT_NE(nullptr, i1);
+
+ // ...which tfind(3) will then return.
+ ASSERT_EQ(i1, tfind(&n1, &root, node_cmp));
+ ASSERT_EQ(nullptr, tfind(&n2, &root, node_cmp));
+ ASSERT_EQ(nullptr, tfind(&n3, &root, node_cmp));
+
+ // Add the other nodes.
+ ASSERT_NE(nullptr, tsearch(&n2, &root, node_cmp));
+ ASSERT_NE(nullptr, tsearch(&n3, &root, node_cmp));
+
+ // Use twalk(3) to iterate over the nodes.
+ g_nodes.clear();
+ twalk(root, node_walk);
+ ASSERT_EQ(3U, g_nodes.size());
+ ASSERT_EQ("a", g_nodes[0]);
+ ASSERT_EQ("m", g_nodes[1]);
+ ASSERT_EQ("z", g_nodes[2]);
+
+ // tdestroy(3) removes nodes under a node, calling our callback to destroy each one.
+ g_free_calls = 0;
+ tdestroy(root, node_free);
+ ASSERT_EQ(3U, g_free_calls);
+}
+
+struct pod_node {
+ pod_node(int i) : i(i) {}
+ int i;
+};
+
+static int pod_node_cmp(const void* lhs, const void* rhs) {
+ return reinterpret_cast<const pod_node*>(rhs)->i - reinterpret_cast<const pod_node*>(lhs)->i;
+}
+
+TEST(search, tdelete) {
+ void* root = nullptr;
+
+ pod_node n1(123);
+ ASSERT_NE(nullptr, tsearch(&n1, &root, pod_node_cmp));
+
+ // tdelete(3) leaks n1.
+ pod_node not_there(456);
+ ASSERT_EQ(nullptr, tdelete(¬_there, &root, pod_node_cmp));
+ ASSERT_NE(nullptr, tdelete(&n1, &root, pod_node_cmp));
+}
+
+struct q_node {
+ q_node(int i) : i(i) {}
+
+ q_node* next;
+ q_node* prev;
+
+ int i;
+};
+
+TEST(search, insque_remque) {
+ q_node zero(0);
+ q_node one(1);
+ q_node two(2);
+
+ // Linear (not circular).
+
+ insque(&zero, NULL);
+ insque(&one, &zero);
+ insque(&two, &one);
+
+ int expected = 0;
+ for (q_node* q = &zero; q != NULL; q = q->next) {
+ ASSERT_EQ(expected, q->i);
+ ++expected;
+ }
+ ASSERT_EQ(3, expected);
+
+ for (q_node* q = &two; q != NULL; q = q->prev) {
+ --expected;
+ ASSERT_EQ(expected, q->i);
+ }
+ ASSERT_EQ(0, expected);
+
+ q_node* head = &zero;
+
+ remque(&one);
+ ASSERT_EQ(0, head->i);
+ ASSERT_EQ(2, head->next->i);
+ ASSERT_EQ(nullptr, head->next->next);
+
+ remque(&two);
+ ASSERT_EQ(0, head->i);
+ ASSERT_EQ(nullptr, head->next);
+
+ remque(&zero);
+
+ // Circular.
+
+ zero.next = &zero;
+ zero.prev = &zero;
+
+ insque(&one, &zero);
+ insque(&two, &one);
+
+ ASSERT_EQ(0, head->i);
+ ASSERT_EQ(1, head->next->i);
+ ASSERT_EQ(2, head->next->next->i);
+ ASSERT_EQ(0, head->next->next->next->i);
+ ASSERT_EQ(1, head->next->next->next->next->i);
+ ASSERT_EQ(2, head->next->next->next->next->next->i);
+
+ remque(&one);
+ ASSERT_EQ(0, head->i);
+ ASSERT_EQ(2, head->next->i);
+ ASSERT_EQ(0, head->next->next->i);
+ ASSERT_EQ(2, head->next->next->next->i);
+
+ remque(&two);
+ ASSERT_EQ(0, head->i);
+ ASSERT_EQ(0, head->next->i);
+
+ remque(&zero);
+}