third_party/re2/util/sparse_array_test.cc

   1 // Copyright 2006 The RE2 Authors.  All Rights Reserved.
   2 // Use of this source code is governed by a BSD-style
   3 // license that can be found in the LICENSE file.
   4
   5 // Simple tests that SparseArray behaves.
   6
   7 #include "util/util.h"
   8 #include "utest/utest.h"
   9
  10 namespace re2 {
  11
  12 static const string kNotFound = "NOT FOUND";
  13
  14 TEST(SparseArray, BasicOperations) {
  15   static const int n = 50;
  16   SparseArray<int> set(n);
  17
  18   int order[n];
  19   int value[n];
  20   for (int i = 0; i < n; i++)
  21     order[i] = i;
  22   for (int i = 0; i < n; i++)
  23     value[i] = rand()%1000 + 1;
  24   for (int i = 1; i < n; i++) {
  25     int j = rand()%i;
  26     int t = order[i];
  27     order[i] = order[j];
  28     order[j] = t;
  29   }
  30
  31   for (int i = 0;; i++) {
  32     for (int j = 0; j < i; j++) {
  33       ASSERT_TRUE(set.has_index(order[j]));
  34       ASSERT_EQ(value[order[j]], set.get(order[j], -1));
  35     }
  36     if (i >= n)
  37       break;
  38     for (int j = i; j < n; j++)
  39       ASSERT_FALSE(set.has_index(order[j]));
  40     set.set(order[i], value[order[i]]);
  41   }
  42
  43   int nn = 0;
  44   for (SparseArray<int>::iterator i = set.begin(); i != set.end(); ++i) {
  45     ASSERT_EQ(order[nn++], i->index());
  46     ASSERT_EQ(value[i->index()], i->value());
  47   }
  48   ASSERT_EQ(nn, n);
  49
  50   set.clear();
  51   for (int i = 0; i < n; i++)
  52     ASSERT_FALSE(set.has_index(i));
  53
  54   ASSERT_EQ(0, set.size());
  55   ASSERT_EQ(0, distance(set.begin(), set.end()));
  56 }
  57
  58 class SparseArrayStringTest : public testing::Test {
  59  protected:
  60   SparseArrayStringTest()
  61       : str_map_(10) {
  62     InsertOrUpdate(&str_map_, 1, "a");
  63     InsertOrUpdate(&str_map_, 5, "b");
  64     InsertOrUpdate(&str_map_, 2, "c");
  65     InsertOrUpdate(&str_map_, 7, "d");
  66   }
  67
  68   SparseArray<string> str_map_;
  69   typedef SparseArray<string>::iterator iterator;
  70 };
  71
  72 TEST_F(SparseArrayStringTest, FindGetsPresentElement) {
  73   iterator it = str_map_.find(2);
  74   ASSERT_TRUE(str_map_.end() != it);
  75   EXPECT_EQ("c", it->second);
  76 }
  77
  78 TEST_F(SparseArrayStringTest, FindDoesNotFindAbsentElement) {
  79   iterator it = str_map_.find(3);
  80   ASSERT_TRUE(str_map_.end() == it);
  81 }
  82
  83 TEST_F(SparseArrayStringTest, ContainsKey) {
  84   EXPECT_TRUE(ContainsKey(str_map_, 1));
  85   EXPECT_TRUE(ContainsKey(str_map_, 2));
  86   EXPECT_FALSE(ContainsKey(str_map_, 3));
  87 }
  88
  89 TEST_F(SparseArrayStringTest, InsertIfNotPresent) {
  90   EXPECT_FALSE(ContainsKey(str_map_, 3));
  91   EXPECT_TRUE(InsertIfNotPresent(&str_map_, 3, "r"));
  92   EXPECT_EQ("r", FindWithDefault(str_map_, 3, kNotFound));
  93   EXPECT_FALSE(InsertIfNotPresent(&str_map_, 3, "other value"));
  94   EXPECT_EQ("r", FindWithDefault(str_map_, 3, kNotFound));
  95 }
  96
  97 TEST(SparseArrayTest, Erase) {
  98   SparseArray<string> str_map(5);
  99   str_map.set(1, "a");
 100   str_map.set(2, "b");
 101   EXPECT_EQ("a", FindWithDefault(str_map, 1, kNotFound));
 102   EXPECT_EQ("b", FindWithDefault(str_map, 2, kNotFound));
 103   str_map.erase(1);
 104   EXPECT_EQ("NOT FOUND", FindWithDefault(str_map, 1, kNotFound));
 105   EXPECT_EQ("b", FindWithDefault(str_map, 2, kNotFound));
 106 }
 107
 108 typedef SparseArrayStringTest SparseArrayStringSurvivesInvalidIndexTest;
 109 // TODO(jyasskin): Cover invalid arguments to every method.
 110
 111 TEST_F(SparseArrayStringSurvivesInvalidIndexTest, SetNegative) {
 112   EXPECT_DEBUG_DEATH(str_map_.set(-123456789, "hi"),
 113                      "\\(jyasskin\\) Illegal index -123456789 passed to"
 114                      " SparseArray\\(10\\).set\\(\\).");
 115   EXPECT_EQ(4, str_map_.size());
 116 }
 117
 118 TEST_F(SparseArrayStringSurvivesInvalidIndexTest, SetTooBig) {
 119   EXPECT_DEBUG_DEATH(str_map_.set(12345678, "hi"),
 120                      "\\(jyasskin\\) Illegal index 12345678 passed to"
 121                      " SparseArray\\(10\\).set\\(\\).");
 122   EXPECT_EQ(4, str_map_.size());
 123 }
 124
 125 TEST_F(SparseArrayStringSurvivesInvalidIndexTest, SetNew_Negative) {
 126   EXPECT_DEBUG_DEATH(str_map_.set_new(-123456789, "hi"),
 127                      "\\(jyasskin\\) Illegal index -123456789 passed to"
 128                      " SparseArray\\(10\\).set_new\\(\\).");
 129   EXPECT_EQ(4, str_map_.size());
 130 }
 131
 132 TEST_F(SparseArrayStringSurvivesInvalidIndexTest, SetNew_Existing) {
 133   EXPECT_DEBUG_DEATH({
 134     str_map_.set_new(2, "hi");
 135     EXPECT_EQ("hi", FindWithDefault(str_map_, 2, kNotFound));
 136
 137     // The old value for 2 is still present, but can never be removed.
 138     // This risks crashing later, if the map fills up.
 139     EXPECT_EQ(5, str_map_.size());
 140   }, "Check failed: !has_index\\(i\\)");
 141 }
 142
 143 TEST_F(SparseArrayStringSurvivesInvalidIndexTest, SetNew_TooBig) {
 144   EXPECT_DEBUG_DEATH(str_map_.set_new(12345678, "hi"),
 145                      "\\(jyasskin\\) Illegal index 12345678 passed to"
 146                      " SparseArray\\(10\\).set_new\\(\\).");
 147   EXPECT_EQ(4, str_map_.size());
 148 }
 149
 150 }  // namespace re2