tests/search_test.cpp

   1 /*
   2  * Copyright (C) 2014 The Android Open Source Project
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *      http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 #include <gtest/gtest.h>
  18
  19 #include <search.h>
  20
  21 static int int_cmp(const void* lhs, const void* rhs) {
  22   return *reinterpret_cast<const int*>(rhs) - *reinterpret_cast<const int*>(lhs);
  23 }
  24
  25 TEST(search, lfind_lsearch) {
  26   int xs[10];
  27   memset(xs, 0, sizeof(xs));
  28   size_t x_size = 0;
  29
  30   int needle;
  31
  32   // lfind(3) can't find '2' in the empty table.
  33   needle = 2;
  34   ASSERT_EQ(nullptr, lfind(&needle, xs, &x_size, sizeof(xs[0]), int_cmp));
  35   ASSERT_EQ(0U, x_size);
  36
  37   // lsearch(3) will add it.
  38   ASSERT_EQ(&xs[0], lsearch(&needle, xs, &x_size, sizeof(xs[0]), int_cmp));
  39   ASSERT_EQ(2, xs[0]);
  40   ASSERT_EQ(1U, x_size);
  41
  42   // And then lfind(3) can find it.
  43   ASSERT_EQ(&xs[0], lfind(&needle, xs, &x_size, sizeof(xs[0]), int_cmp));
  44   ASSERT_EQ(1U, x_size);
  45
  46   // Inserting a duplicate does nothing (but returns the existing element).
  47   ASSERT_EQ(&xs[0], lsearch(&needle, xs, &x_size, sizeof(xs[0]), int_cmp));
  48   ASSERT_EQ(1U, x_size);
  49 }
  50
  51 struct node {
  52   node(const char* s) : s(strdup(s)) {}
  53
  54   char* s;
  55 };
  56
  57 static int node_cmp(const void* lhs, const void* rhs) {
  58   return strcmp(reinterpret_cast<const node*>(lhs)->s, reinterpret_cast<const node*>(rhs)->s);
  59 }
  60
  61 static std::vector<std::string> g_nodes;
  62
  63 static void node_walk(const void* p, VISIT order, int) {
  64   const node* n = *reinterpret_cast<const node* const*>(p);
  65   if (order == postorder || order == leaf)  {
  66     g_nodes.push_back(n->s);
  67   }
  68 }
  69
  70 static size_t g_free_calls;
  71
  72 static void node_free(void* p) {
  73   node* n = reinterpret_cast<node*>(p);
  74   free(n->s);
  75   ++g_free_calls;
  76 }
  77
  78 TEST(search, tfind_tsearch_twalk_tdestroy) {
  79   void* root = nullptr;
  80
  81   node n1("z");
  82   node n2("a");
  83   node n3("m");
  84
  85   // tfind(3) can't find anything in the empty tree.
  86   ASSERT_EQ(nullptr, tfind(&n1, &root, node_cmp));
  87   ASSERT_EQ(nullptr, tfind(&n2, &root, node_cmp));
  88   ASSERT_EQ(nullptr, tfind(&n3, &root, node_cmp));
  89
  90   // tsearch(3) inserts and returns a pointer to a new node.
  91   void* i1 = tsearch(&n1, &root, node_cmp);
  92   ASSERT_NE(nullptr, i1);
  93
  94   // ...which tfind(3) will then return.
  95   ASSERT_EQ(i1, tfind(&n1, &root, node_cmp));
  96   ASSERT_EQ(nullptr, tfind(&n2, &root, node_cmp));
  97   ASSERT_EQ(nullptr, tfind(&n3, &root, node_cmp));
  98
  99   // Add the other nodes.
 100   ASSERT_NE(nullptr, tsearch(&n2, &root, node_cmp));
 101   ASSERT_NE(nullptr, tsearch(&n3, &root, node_cmp));
 102
 103   // Use twalk(3) to iterate over the nodes.
 104   g_nodes.clear();
 105   twalk(root, node_walk);
 106   ASSERT_EQ(3U, g_nodes.size());
 107   ASSERT_EQ("a", g_nodes[0]);
 108   ASSERT_EQ("m", g_nodes[1]);
 109   ASSERT_EQ("z", g_nodes[2]);
 110
 111   // tdestroy(3) removes nodes under a node, calling our callback to destroy each one.
 112   g_free_calls = 0;
 113   tdestroy(root, node_free);
 114   ASSERT_EQ(3U, g_free_calls);
 115 }
 116
 117 struct pod_node {
 118   pod_node(int i) : i(i) {}
 119   int i;
 120 };
 121
 122 static int pod_node_cmp(const void* lhs, const void* rhs) {
 123   return reinterpret_cast<const pod_node*>(rhs)->i - reinterpret_cast<const pod_node*>(lhs)->i;
 124 }
 125
 126 TEST(search, tdelete) {
 127   void* root = nullptr;
 128
 129   pod_node n1(123);
 130   ASSERT_NE(nullptr, tsearch(&n1, &root, pod_node_cmp));
 131
 132   // tdelete(3) leaks n1.
 133   pod_node not_there(456);
 134   ASSERT_EQ(nullptr, tdelete(&not_there, &root, pod_node_cmp));
 135   ASSERT_NE(nullptr, tdelete(&n1, &root, pod_node_cmp));
 136 }
 137
 138 struct q_node {
 139   q_node(int i) : i(i) {}
 140
 141   q_node* next;
 142   q_node* prev;
 143
 144   int i;
 145 };
 146
 147 TEST(search, insque_remque) {
 148   q_node zero(0);
 149   q_node one(1);
 150   q_node two(2);
 151
 152   // Linear (not circular).
 153
 154   insque(&zero, NULL);
 155   insque(&one, &zero);
 156   insque(&two, &one);
 157
 158   int expected = 0;
 159   for (q_node* q = &zero; q != NULL; q = q->next) {
 160     ASSERT_EQ(expected, q->i);
 161     ++expected;
 162   }
 163   ASSERT_EQ(3, expected);
 164
 165   for (q_node* q = &two; q != NULL; q = q->prev) {
 166     --expected;
 167     ASSERT_EQ(expected, q->i);
 168   }
 169   ASSERT_EQ(0, expected);
 170
 171   q_node* head = &zero;
 172
 173   remque(&one);
 174   ASSERT_EQ(0, head->i);
 175   ASSERT_EQ(2, head->next->i);
 176   ASSERT_EQ(nullptr, head->next->next);
 177
 178   remque(&two);
 179   ASSERT_EQ(0, head->i);
 180   ASSERT_EQ(nullptr, head->next);
 181
 182   remque(&zero);
 183
 184   // Circular.
 185
 186   zero.next = &zero;
 187   zero.prev = &zero;
 188
 189   insque(&one, &zero);
 190   insque(&two, &one);
 191
 192   ASSERT_EQ(0, head->i);
 193   ASSERT_EQ(1, head->next->i);
 194   ASSERT_EQ(2, head->next->next->i);
 195   ASSERT_EQ(0, head->next->next->next->i);
 196   ASSERT_EQ(1, head->next->next->next->next->i);
 197   ASSERT_EQ(2, head->next->next->next->next->next->i);
 198
 199   remque(&one);
 200   ASSERT_EQ(0, head->i);
 201   ASSERT_EQ(2, head->next->i);
 202   ASSERT_EQ(0, head->next->next->i);
 203   ASSERT_EQ(2, head->next->next->next->i);
 204
 205   remque(&two);
 206   ASSERT_EQ(0, head->i);
 207   ASSERT_EQ(0, head->next->i);
 208
 209   remque(&zero);
 210 }