File indexing completed on 2024-11-24 04:54:36
0001 /* 0002 SPDX-License-Identifier: MPL-2.0 0003 */ 0004 0005 /* Copyright (c) 2015 Brian R. Bondy. Distributed under the MPL2 license. 0006 * This Source Code Form is subject to the terms of the Mozilla Public 0007 * License, v. 2.0. If a copy of the MPL was not distributed with this 0008 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ 0009 0010 #include "./CppUnitLite/TestHarness.h" 0011 #include "./CppUnitLite/Test.h" 0012 #include "./hash_set.h" 0013 #include "./example_data.h" 0014 #include "./hashFn.h" 0015 0016 TEST(hash_set, not_multi_set) { 0017 { 0018 HashSet<ExampleData> hash_set(2, false); 0019 hash_set.Add(ExampleData("test")); 0020 uint32_t len; 0021 char *buffer = hash_set.Serialize(&len); 0022 HashSet<ExampleData> hash_set2(0, false); 0023 hash_set2.Deserialize(buffer, len); 0024 hash_set2.Exists(ExampleData("test")); 0025 } 0026 0027 HashSet<ExampleData> hash_sets[] = {HashSet<ExampleData>(1, false), 0028 HashSet<ExampleData>(2, false), HashSet<ExampleData>(500, false)}; 0029 for (unsigned int i = 0; i < sizeof(hash_sets) / sizeof(hash_sets[0]); i++) { 0030 HashSet<ExampleData> &hash_set = hash_sets[i]; 0031 CHECK(!hash_set.IsMultiSet()); 0032 LONGS_EQUAL(0, hash_set.GetSize()); 0033 hash_set.Add(ExampleData("test")); 0034 LONGS_EQUAL(1, hash_set.GetSize()); 0035 CHECK(hash_set.Exists(ExampleData("test"))); 0036 hash_set.Add(ExampleData("test")); 0037 CHECK(hash_set.Exists(ExampleData("test"))); 0038 LONGS_EQUAL(1, hash_set.GetSize()); 0039 hash_set.Add(ExampleData("test2")); 0040 CHECK(hash_set.Exists(ExampleData("test2"))); 0041 LONGS_EQUAL(2, hash_set.GetSize()); 0042 hash_set.Add(ExampleData("test3")); 0043 CHECK(hash_set.Exists(ExampleData("test3"))); 0044 hash_set.Add(ExampleData("test4")); 0045 CHECK(hash_set.Exists(ExampleData("test4"))); 0046 0047 // Check that a smaller substring of something that exists, doesn't exist 0048 CHECK(!hash_set.Exists(ExampleData("tes"))); 0049 // Check that a longer string of something that exists, doesn't exist 0050 CHECK(!hash_set.Exists(ExampleData("test22"))); 0051 CHECK(!hash_set.Exists(ExampleData("test5"))); 0052 0053 LONGS_EQUAL(4, hash_set.GetSize()); 0054 hash_set.Add(ExampleData("a\0b\0\0c", 6)); 0055 LONGS_EQUAL(5, hash_set.GetSize()); 0056 CHECK(!hash_set.Exists(ExampleData("a"))); 0057 CHECK(!hash_set.Exists(ExampleData("a", 1))); 0058 CHECK(hash_set.Exists(ExampleData("a\0b\0\0c", 6))); 0059 CHECK(!hash_set.Exists(ExampleData("a\0b\0\0c", 7))); 0060 0061 // Test that remove works 0062 LONGS_EQUAL(5, hash_set.GetSize()); 0063 CHECK(hash_set.Exists(ExampleData("test2"))); 0064 CHECK(hash_set.Remove(ExampleData("test2"))); 0065 LONGS_EQUAL(4, hash_set.GetSize()); 0066 CHECK(!hash_set.Exists(ExampleData("test2"))); 0067 CHECK(!hash_set.Remove(ExampleData("test2"))); 0068 LONGS_EQUAL(4, hash_set.GetSize()); 0069 CHECK(hash_set.Add(ExampleData("test2"))); 0070 LONGS_EQUAL(5, hash_set.GetSize()); 0071 0072 // Try to find something that doesn't exist 0073 CHECK(hash_set.Find(ExampleData("fdsafasd")) == nullptr); 0074 0075 // Show how extra data works 0076 ExampleData item("ok"); 0077 item.extra_data_ = 1; 0078 hash_set.Add(item); 0079 0080 ExampleData *p = hash_set.Find(ExampleData("ok")); 0081 LONGS_EQUAL(1, p->extra_data_); 0082 0083 item.extra_data_ = 2; 0084 hash_set.Add(item); 0085 LONGS_EQUAL(6, hash_set.GetSize()); 0086 // ExampleData is configuredd to merge extra_data_ on updates 0087 LONGS_EQUAL(3, p->extra_data_); 0088 } 0089 0090 uint32_t len = 0; 0091 for (unsigned int i = 0; i < sizeof(hash_sets) / sizeof(hash_sets[0]); i++) { 0092 HashSet<ExampleData> &hs1 = hash_sets[i]; 0093 char *buffer = hs1.Serialize(&len); 0094 HashSet<ExampleData> dhs(0, false); 0095 // Deserializing some invalid data should fail 0096 CHECK(!dhs.Deserialize(const_cast<char*>("31131"), 2)); 0097 CHECK(dhs.Deserialize(buffer, len)); 0098 CHECK(dhs.Exists(ExampleData("test"))); 0099 CHECK(dhs.Exists(ExampleData("test2"))); 0100 CHECK(dhs.Exists(ExampleData("test3"))); 0101 CHECK(dhs.Exists(ExampleData("test4"))); 0102 CHECK(!dhs.Exists(ExampleData("tes"))); 0103 CHECK(!dhs.Exists(ExampleData("test22"))); 0104 CHECK(!dhs.Exists(ExampleData("test5"))); 0105 CHECK(!dhs.Exists(ExampleData("a"))); 0106 CHECK(!dhs.Exists(ExampleData("a", 1))); 0107 CHECK(dhs.Exists(ExampleData("a\0b\0\0c", 6))); 0108 CHECK(!dhs.Exists(ExampleData("a\0b\0\0c", 7))); 0109 LONGS_EQUAL(6, dhs.GetSize()); 0110 0111 // Make sure HashSet clears correctly 0112 CHECK(dhs.Exists(ExampleData("test"))); 0113 dhs.Clear(); 0114 CHECK(!dhs.Exists(ExampleData("test"))); 0115 0116 delete[] buffer; 0117 } 0118 0119 // Make sure HashFn produces the correct hash 0120 HashFn h(19, false); 0121 HashFn h2(19, true); 0122 const char *sz = "facebook.com"; 0123 const char *sz2 = "abcde"; 0124 LONGS_EQUAL(h(sz, strlen(sz)), 12510474367240317); 0125 LONGS_EQUAL(h2(sz, strlen(sz)), 12510474367240317); 0126 LONGS_EQUAL(h(sz2, strlen(sz2)), 13351059); 0127 LONGS_EQUAL(h2(sz2, strlen(sz2)), 13351059); 0128 } 0129 0130 TEST(hash_set, multi_set) { 0131 { 0132 HashSet<ExampleData> hash_set(2, true); 0133 hash_set.Add(ExampleData("test")); 0134 uint32_t len; 0135 char *buffer = hash_set.Serialize(&len); 0136 HashSet<ExampleData> hash_set2(0, true); 0137 hash_set2.Deserialize(buffer, len); 0138 hash_set2.Exists(ExampleData("test")); 0139 } 0140 0141 HashSet<ExampleData> hash_sets[] = {HashSet<ExampleData>(1, true), 0142 HashSet<ExampleData>(2, true), HashSet<ExampleData>(500, true)}; 0143 for (unsigned int i = 0; i < sizeof(hash_sets) / sizeof(hash_sets[0]); i++) { 0144 HashSet<ExampleData> &hash_set = hash_sets[i]; 0145 CHECK(hash_set.IsMultiSet()); 0146 LONGS_EQUAL(0, hash_set.GetSize()); 0147 hash_set.Add(ExampleData("test"), false); 0148 LONGS_EQUAL(1, hash_set.GetSize()); 0149 CHECK(hash_set.Exists(ExampleData("test"))); 0150 hash_set.Add(ExampleData("test"), false); 0151 CHECK(hash_set.Exists(ExampleData("test"))); 0152 LONGS_EQUAL(2, hash_set.GetSize()); 0153 hash_set.Add(ExampleData("test2"), false); 0154 CHECK(hash_set.Exists(ExampleData("test2"))); 0155 LONGS_EQUAL(3, hash_set.GetSize()); 0156 hash_set.Add(ExampleData("test3"), false); 0157 CHECK(hash_set.Exists(ExampleData("test3"))); 0158 hash_set.Add(ExampleData("test4"), false); 0159 CHECK(hash_set.Exists(ExampleData("test4"))); 0160 0161 // Make sure multi set has 2 items for test's hash 0162 LONGS_EQUAL(2, hash_set.GetMatchingCount(ExampleData("test"))) 0163 0164 // Check that a smaller substring of something that exists, doesn't exist 0165 CHECK(!hash_set.Exists(ExampleData("tes"))); 0166 // Check that a longer string of something that exists, doesn't exist 0167 CHECK(!hash_set.Exists(ExampleData("test22"))); 0168 CHECK(!hash_set.Exists(ExampleData("test5"))); 0169 0170 LONGS_EQUAL(5, hash_set.GetSize()); 0171 hash_set.Add(ExampleData("a\0b\0\0c", 6), false); 0172 LONGS_EQUAL(6, hash_set.GetSize()); 0173 CHECK(!hash_set.Exists(ExampleData("a"))); 0174 CHECK(!hash_set.Exists(ExampleData("a", 1))); 0175 CHECK(hash_set.Exists(ExampleData("a\0b\0\0c", 6))); 0176 CHECK(!hash_set.Exists(ExampleData("a\0b\0\0c", 7))); 0177 0178 // Test that remove works 0179 LONGS_EQUAL(6, hash_set.GetSize()); 0180 CHECK(hash_set.Exists(ExampleData("test2"))); 0181 CHECK(hash_set.Remove(ExampleData("test2"))); 0182 LONGS_EQUAL(5, hash_set.GetSize()); 0183 CHECK(!hash_set.Exists(ExampleData("test2"))); 0184 CHECK(!hash_set.Remove(ExampleData("test2"))); 0185 LONGS_EQUAL(5, hash_set.GetSize()); 0186 CHECK(hash_set.Add(ExampleData("test2"), false)); 0187 LONGS_EQUAL(6, hash_set.GetSize()); 0188 0189 // Try to find something that doesn't exist 0190 CHECK(hash_set.Find(ExampleData("fdsafasd")) == nullptr); 0191 0192 // Show how extra data works 0193 ExampleData item("ok"); 0194 item.extra_data_ = 1; 0195 hash_set.Add(item, false); 0196 0197 ExampleData item2("ok"); 0198 item2.extra_data_ = 2; 0199 hash_set.Add(item2, true); 0200 0201 ExampleData item3("ok"); 0202 item3.extra_data_ = 4; 0203 hash_set.Add(item3, false); 0204 0205 ExampleData *p = hash_set.Find(ExampleData("ok")); 0206 // ExampleData is configuredd to merge extra_data_ on updates 0207 LONGS_EQUAL(3, p->extra_data_); 0208 0209 std::vector<ExampleData *> items; 0210 hash_set.FindAll(ExampleData("ok"), &items); 0211 LONGS_EQUAL(2, items.size()); 0212 LONGS_EQUAL(3, items[0]->extra_data_); 0213 LONGS_EQUAL(4, items[1]->extra_data_); 0214 LONGS_EQUAL(8, hash_set.GetSize()); 0215 } 0216 0217 uint32_t len = 0; 0218 for (unsigned int i = 0; i < sizeof(hash_sets) / sizeof(hash_sets[0]); i++) { 0219 HashSet<ExampleData> &hs1 = hash_sets[i]; 0220 char *buffer = hs1.Serialize(&len); 0221 HashSet<ExampleData> dhs(0, true); 0222 // Deserializing some invalid data should fail 0223 CHECK(!dhs.Deserialize(const_cast<char*>("31131"), 2)); 0224 CHECK(dhs.Deserialize(buffer, len)); 0225 CHECK(dhs.Exists(ExampleData("test"))); 0226 CHECK(dhs.Exists(ExampleData("test2"))); 0227 CHECK(dhs.Exists(ExampleData("test3"))); 0228 CHECK(dhs.Exists(ExampleData("test4"))); 0229 CHECK(!dhs.Exists(ExampleData("tes"))); 0230 CHECK(!dhs.Exists(ExampleData("test22"))); 0231 CHECK(!dhs.Exists(ExampleData("test5"))); 0232 CHECK(!dhs.Exists(ExampleData("a"))); 0233 CHECK(!dhs.Exists(ExampleData("a", 1))); 0234 CHECK(dhs.Exists(ExampleData("a\0b\0\0c", 6))); 0235 CHECK(!dhs.Exists(ExampleData("a\0b\0\0c", 7))); 0236 LONGS_EQUAL(8, dhs.GetSize()); 0237 0238 // Make sure HashSet clears correctly 0239 CHECK(dhs.Exists(ExampleData("test"))); 0240 dhs.Clear(); 0241 CHECK(!dhs.Exists(ExampleData("test"))); 0242 0243 delete[] buffer; 0244 } 0245 0246 // Make sure HashFn produces the correct hash 0247 HashFn h(19, true); 0248 HashFn h2(19, true); 0249 const char *sz = "facebook.com"; 0250 const char *sz2 = "abcde"; 0251 LONGS_EQUAL(h(sz, strlen(sz)), 12510474367240317); 0252 LONGS_EQUAL(h2(sz, strlen(sz)), 12510474367240317); 0253 LONGS_EQUAL(h(sz2, strlen(sz2)), 13351059); 0254 LONGS_EQUAL(h2(sz2, strlen(sz2)), 13351059); 0255 }