| 1 | #include "mycpp/gc_dict.h"
|
| 2 |
|
| 3 | #include <unordered_map>
|
| 4 |
|
| 5 | #include "mycpp/gc_mylib.h"
|
| 6 | #include "vendor/greatest.h"
|
| 7 |
|
| 8 | // Convenience function
|
| 9 | template <typename K, typename V>
|
| 10 | Dict<K, V>* NewDict() {
|
| 11 | return Alloc<Dict<K, V>>();
|
| 12 | }
|
| 13 |
|
| 14 | GLOBAL_STR(kStrFoo, "foo");
|
| 15 | GLOBAL_STR(kStrBar, "bar");
|
| 16 |
|
| 17 | TEST test_dict_init() {
|
| 18 | BigStr* s = StrFromC("foo");
|
| 19 | BigStr* s2 = StrFromC("bar");
|
| 20 |
|
| 21 | Dict<int, BigStr*>* d = Alloc<Dict<int, BigStr*>>(
|
| 22 | std::initializer_list<int>{42}, std::initializer_list<BigStr*>{s});
|
| 23 | ASSERT_EQ(s, d->at(42));
|
| 24 |
|
| 25 | Dict<BigStr*, int>* d2 =
|
| 26 | Alloc<Dict<BigStr*, int>>(std::initializer_list<BigStr*>{s, s2},
|
| 27 | std::initializer_list<int>{43, 99});
|
| 28 | ASSERT_EQ(43, d2->at(s));
|
| 29 | ASSERT_EQ(99, d2->at(s2));
|
| 30 |
|
| 31 | PASS();
|
| 32 | }
|
| 33 |
|
| 34 | TEST test_dict() {
|
| 35 | Dict<int, BigStr*>* d = NewDict<int, BigStr*>();
|
| 36 |
|
| 37 | // Regression: clear empty dict
|
| 38 | d->clear();
|
| 39 |
|
| 40 | d->set(1, StrFromC("foo"));
|
| 41 | log("d[1] = %s", d->at(1)->data_);
|
| 42 |
|
| 43 | auto d2 = NewDict<BigStr*, int>();
|
| 44 | BigStr* key = StrFromC("key");
|
| 45 | d2->set(key, 42);
|
| 46 |
|
| 47 | log("d2['key'] = %d", d2->at(key));
|
| 48 | d2->set(StrFromC("key2"), 2);
|
| 49 | d2->set(StrFromC("key3"), 3);
|
| 50 |
|
| 51 | ASSERT_EQ_FMT(3, len(d2), "%d");
|
| 52 | ASSERT_EQ_FMT(3, len(d2->keys()), "%d");
|
| 53 | ASSERT_EQ_FMT(3, len(d2->values()), "%d");
|
| 54 |
|
| 55 | d2->clear();
|
| 56 | ASSERT_EQ(0, len(d2));
|
| 57 |
|
| 58 | log(" iterating over Dict");
|
| 59 | for (DictIter<BigStr*, int> it(d2); !it.Done(); it.Next()) {
|
| 60 | log("k = %s, v = %d", it.Key()->data_, it.Value());
|
| 61 | }
|
| 62 |
|
| 63 | ASSERT(dict_contains(d, 1));
|
| 64 | ASSERT(!dict_contains(d, 423));
|
| 65 |
|
| 66 | BigStr* v1 = d->get(1);
|
| 67 | log("v1 = %s", v1->data_);
|
| 68 | ASSERT(str_equals0("foo", v1));
|
| 69 |
|
| 70 | BigStr* v2 = d->get(423); // nonexistent
|
| 71 | ASSERT_EQ(nullptr, v2);
|
| 72 | log("v2 = %p", v2);
|
| 73 |
|
| 74 | auto d3 = NewDict<BigStr*, int>();
|
| 75 | ASSERT_EQ(0, len(d3));
|
| 76 |
|
| 77 | auto a = StrFromC("a");
|
| 78 |
|
| 79 | d3->set(StrFromC("b"), 11);
|
| 80 | ASSERT_EQ(1, len(d3));
|
| 81 |
|
| 82 | d3->set(StrFromC("c"), 12);
|
| 83 | ASSERT_EQ(2, len(d3));
|
| 84 |
|
| 85 | d3->set(StrFromC("a"), 10);
|
| 86 | ASSERT_EQ(3, len(d3));
|
| 87 |
|
| 88 | ASSERT_EQ(10, d3->at(StrFromC("a")));
|
| 89 | ASSERT_EQ(11, d3->at(StrFromC("b")));
|
| 90 | ASSERT_EQ(12, d3->at(StrFromC("c")));
|
| 91 | ASSERT_EQ(3, len(d3));
|
| 92 |
|
| 93 | auto keys = sorted(d3);
|
| 94 | ASSERT(str_equals0("a", keys->at(0)));
|
| 95 | ASSERT(str_equals0("b", keys->at(1)));
|
| 96 | ASSERT(str_equals0("c", keys->at(2)));
|
| 97 | ASSERT_EQ(3, len(keys));
|
| 98 |
|
| 99 | auto keys3 = d3->keys();
|
| 100 | ASSERT(list_contains(keys3, a));
|
| 101 | ASSERT(!list_contains(keys3, StrFromC("zzz")));
|
| 102 |
|
| 103 | ASSERT(dict_contains(d3, a));
|
| 104 | mylib::dict_erase(d3, a);
|
| 105 | ASSERT(!dict_contains(d3, a));
|
| 106 | ASSERT_EQ(2, len(d3));
|
| 107 |
|
| 108 | // Test removed item
|
| 109 | for (DictIter<BigStr*, int> it(d3); !it.Done(); it.Next()) {
|
| 110 | auto key = it.Key();
|
| 111 | printf("d3 key = ");
|
| 112 | print(key);
|
| 113 | }
|
| 114 |
|
| 115 | // Test a different type of dict, to make sure partial template
|
| 116 | // specialization works
|
| 117 | auto ss = NewDict<BigStr*, BigStr*>();
|
| 118 | ss->set(a, a);
|
| 119 | ASSERT_EQ(1, len(ss));
|
| 120 |
|
| 121 | ASSERT_EQ(1, len(ss->keys()));
|
| 122 | ASSERT_EQ(1, len(ss->values()));
|
| 123 |
|
| 124 | mylib::dict_erase(ss, a);
|
| 125 | ASSERT_EQ(0, len(ss));
|
| 126 |
|
| 127 | // Test removed item
|
| 128 | for (DictIter<BigStr*, BigStr*> it(ss); !it.Done(); it.Next()) {
|
| 129 | auto key = it.Key();
|
| 130 | printf("ss key = ");
|
| 131 | print(key);
|
| 132 | }
|
| 133 |
|
| 134 | // Testing NewDict() stub for ordered dicts ... hm.
|
| 135 | //
|
| 136 | // Dict<int, int>* frame = nullptr;
|
| 137 | // frame = NewDict<int, int>();
|
| 138 |
|
| 139 | PASS();
|
| 140 | }
|
| 141 |
|
| 142 | // TODO:
|
| 143 | // - Test set() can resize the dict
|
| 144 | // - I guess you have to do rehashing?
|
| 145 |
|
| 146 | TEST test_dict_internals() {
|
| 147 | auto dict1 = NewDict<int, int>();
|
| 148 | StackRoots _roots1({&dict1});
|
| 149 | auto dict2 = NewDict<BigStr*, BigStr*>();
|
| 150 | StackRoots _roots2({&dict2});
|
| 151 |
|
| 152 | ASSERT_EQ(0, len(dict1));
|
| 153 | ASSERT_EQ(0, len(dict2));
|
| 154 |
|
| 155 | ASSERT_EQ_FMT(HeapTag::FixedSize, ObjHeader::FromObject(dict1)->heap_tag,
|
| 156 | "%d");
|
| 157 | ASSERT_EQ_FMT(HeapTag::FixedSize, ObjHeader::FromObject(dict1)->heap_tag,
|
| 158 | "%d");
|
| 159 |
|
| 160 | ASSERT_EQ_FMT(0, dict1->capacity_, "%d");
|
| 161 | ASSERT_EQ_FMT(0, dict2->capacity_, "%d");
|
| 162 |
|
| 163 | ASSERT_EQ(nullptr, dict1->index_);
|
| 164 | ASSERT_EQ(nullptr, dict1->keys_);
|
| 165 | ASSERT_EQ(nullptr, dict1->values_);
|
| 166 |
|
| 167 | // Make sure they're on the heap
|
| 168 | #ifndef MARK_SWEEP
|
| 169 | int diff1 = reinterpret_cast<char*>(dict1) - gHeap.from_space_.begin_;
|
| 170 | int diff2 = reinterpret_cast<char*>(dict2) - gHeap.from_space_.begin_;
|
| 171 | ASSERT(diff1 < 1024);
|
| 172 | ASSERT(diff2 < 1024);
|
| 173 | #endif
|
| 174 |
|
| 175 | dict1->set(42, 5);
|
| 176 | ASSERT_EQ(5, dict1->at(42));
|
| 177 | ASSERT_EQ(1, len(dict1));
|
| 178 | #if 0
|
| 179 | ASSERT_EQ_FMT(6, dict1->capacity_, "%d");
|
| 180 | #endif
|
| 181 |
|
| 182 | #if 0
|
| 183 | ASSERT_EQ_FMT(32, ObjHeader::FromObject(dict1->index_)->obj_len, "%d");
|
| 184 | ASSERT_EQ_FMT(32, ObjHeader::FromObject(dict1->keys_)->obj_len, "%d");
|
| 185 | ASSERT_EQ_FMT(32, ObjHeader::FromObject(dict1->values_)->obj_len, "%d");
|
| 186 | #endif
|
| 187 |
|
| 188 | dict1->set(42, 99);
|
| 189 | ASSERT_EQ(99, dict1->at(42));
|
| 190 | ASSERT_EQ(1, len(dict1));
|
| 191 | #if 0
|
| 192 | ASSERT_EQ_FMT(6, dict1->capacity_, "%d");
|
| 193 | #endif
|
| 194 |
|
| 195 | dict1->set(43, 10);
|
| 196 | ASSERT_EQ(10, dict1->at(43));
|
| 197 | ASSERT_EQ(2, len(dict1));
|
| 198 | #if 0
|
| 199 | ASSERT_EQ_FMT(6, dict1->capacity_, "%d");
|
| 200 | #endif
|
| 201 |
|
| 202 | // Dict<int, int>
|
| 203 | // capacity: 6 -> 14 -> 30 -> ...
|
| 204 | // index len: 9 -> 21 -> 45 -> ...
|
| 205 |
|
| 206 | // 6 * 4 bytes = 24, plus 8 byte header = 32, which fits in the second pool
|
| 207 | // 9 * 4 bytes = 36, plus 8 byte header = 44, which fits in the second pool
|
| 208 | for (int i = 0; i < 14; ++i) {
|
| 209 | dict1->set(i, i + 999);
|
| 210 | log("len_ = %d, capacity = %d, index len %d", dict1->len_, dict1->capacity_,
|
| 211 | dict1->index_len_);
|
| 212 |
|
| 213 | // make sure we didn't lose old entry after resize
|
| 214 | ASSERT_EQ(10, dict1->at(43));
|
| 215 | }
|
| 216 |
|
| 217 | BigStr* foo = nullptr;
|
| 218 | BigStr* bar = nullptr;
|
| 219 | StackRoots _roots3({&foo, &bar});
|
| 220 | foo = StrFromC("foo");
|
| 221 | bar = StrFromC("bar");
|
| 222 |
|
| 223 | dict2->set(foo, bar);
|
| 224 |
|
| 225 | ASSERT_EQ(1, len(dict2));
|
| 226 | ASSERT(str_equals(bar, dict2->at(foo)));
|
| 227 |
|
| 228 | #if 0
|
| 229 | ASSERT_EQ_FMT(32, ObjHeader::FromObject(dict2->index_)->obj_len, "%d");
|
| 230 | ASSERT_EQ_FMT(64, ObjHeader::FromObject(dict2->keys_)->obj_len, "%d");
|
| 231 | ASSERT_EQ_FMT(64, ObjHeader::FromObject(dict2->values_)->obj_len, "%d");
|
| 232 | #endif
|
| 233 |
|
| 234 | auto dict_si = NewDict<BigStr*, int>();
|
| 235 | StackRoots _roots4({&dict_si});
|
| 236 | dict_si->set(foo, 42);
|
| 237 | ASSERT_EQ(1, len(dict_si));
|
| 238 |
|
| 239 | #if 0
|
| 240 | ASSERT_EQ_FMT(32, ObjHeader::FromObject(dict_si->index_)->obj_len, "%d");
|
| 241 | ASSERT_EQ_FMT(64, ObjHeader::FromObject(dict_si->keys_)->obj_len, "%d");
|
| 242 | ASSERT_EQ_FMT(32, ObjHeader::FromObject(dict_si->values_)->obj_len, "%d");
|
| 243 | #endif
|
| 244 |
|
| 245 | auto dict_is = NewDict<int, BigStr*>();
|
| 246 | StackRoots _roots5({&dict_is});
|
| 247 | dict_is->set(42, foo);
|
| 248 | PASS();
|
| 249 |
|
| 250 | ASSERT_EQ(1, len(dict_is));
|
| 251 |
|
| 252 | #if 0
|
| 253 | ASSERT_EQ_FMT(32, ObjHeader::FromObject(dict_is->index_)->obj_len, "%d");
|
| 254 | ASSERT_EQ_FMT(32, ObjHeader::FromObject(dict_is->keys_)->obj_len, "%d");
|
| 255 | ASSERT_EQ_FMT(64, ObjHeader::FromObject(dict_is->values_)->obj_len, "%d");
|
| 256 | #endif
|
| 257 |
|
| 258 | auto two = StrFromC("two");
|
| 259 | StackRoots _roots6({&two});
|
| 260 |
|
| 261 | auto dict3 = Alloc<Dict<int, BigStr*>>(
|
| 262 | std::initializer_list<int>{1, 2},
|
| 263 | std::initializer_list<BigStr*>{kEmptyString, two});
|
| 264 | StackRoots _roots7({&dict3});
|
| 265 |
|
| 266 | ASSERT_EQ_FMT(2, len(dict3), "%d");
|
| 267 | ASSERT(str_equals(kEmptyString, dict3->get(1)));
|
| 268 | ASSERT(str_equals(two, dict3->get(2)));
|
| 269 |
|
| 270 | PASS();
|
| 271 | }
|
| 272 |
|
| 273 | TEST test_empty_dict() {
|
| 274 | auto d = Alloc<Dict<BigStr*, BigStr*>>();
|
| 275 |
|
| 276 | // Look up in empty dict
|
| 277 | BigStr* val = d->get(StrFromC("nonexistent"));
|
| 278 | log("val %p", val);
|
| 279 | ASSERT_EQ(nullptr, val);
|
| 280 |
|
| 281 | BigStr* val2 = d->get(StrFromC("nonexistent"), kEmptyString);
|
| 282 | ASSERT_EQ(kEmptyString, val2);
|
| 283 |
|
| 284 | PASS();
|
| 285 | }
|
| 286 |
|
| 287 | TEST dict_methods_test() {
|
| 288 | Dict<int, BigStr*>* d = nullptr;
|
| 289 | Dict<BigStr*, int>* d2 = nullptr;
|
| 290 | BigStr* key = nullptr;
|
| 291 | StackRoots _roots({&d, &d2, &key});
|
| 292 |
|
| 293 | d = Alloc<Dict<int, BigStr*>>();
|
| 294 | d->set(1, kStrFoo);
|
| 295 | ASSERT(str_equals0("foo", d->at(1)));
|
| 296 |
|
| 297 | d2 = Alloc<Dict<BigStr*, int>>();
|
| 298 | key = StrFromC("key");
|
| 299 | d2->set(key, 42);
|
| 300 | ASSERT_EQ(42, d2->at(key));
|
| 301 |
|
| 302 | PASS();
|
| 303 |
|
| 304 | d2->set(StrFromC("key2"), 2);
|
| 305 | d2->set(StrFromC("key3"), 3);
|
| 306 |
|
| 307 | ASSERT_EQ_FMT(3, len(d2), "%d");
|
| 308 |
|
| 309 | auto keys = d2->keys();
|
| 310 | ASSERT_EQ_FMT(3, len(keys), "%d");
|
| 311 |
|
| 312 | // Retain insertion order
|
| 313 | ASSERT(str_equals0("key", keys->at(0)));
|
| 314 | ASSERT(str_equals0("key2", keys->at(1)));
|
| 315 | ASSERT(str_equals0("key3", keys->at(2)));
|
| 316 |
|
| 317 | mylib::dict_erase(d2, StrFromC("key"));
|
| 318 | ASSERT_EQ_FMT(2, len(d2), "%d");
|
| 319 |
|
| 320 | auto keys2 = d2->keys();
|
| 321 | ASSERT_EQ_FMT(2, len(keys2), "%d");
|
| 322 | ASSERT(str_equals0("key2", keys2->at(0)));
|
| 323 | ASSERT(str_equals0("key3", keys2->at(1)));
|
| 324 |
|
| 325 | auto values = d2->values();
|
| 326 | ASSERT_EQ_FMT(2, len(values), "%d");
|
| 327 | ASSERT_EQ(2, values->at(0));
|
| 328 | ASSERT_EQ(3, values->at(1));
|
| 329 |
|
| 330 | int j = 0;
|
| 331 | for (DictIter<BigStr*, int> it(d2); !it.Done(); it.Next()) {
|
| 332 | auto key = it.Key();
|
| 333 | auto value = it.Value();
|
| 334 | log("d2 key = %s, value = %d", key->data_, value);
|
| 335 | ++j;
|
| 336 | }
|
| 337 | ASSERT_EQ_FMT(len(d2), j, "%d");
|
| 338 |
|
| 339 | d2->clear();
|
| 340 | ASSERT_EQ(0, len(d2));
|
| 341 | // Ensure it was zero'd
|
| 342 | ASSERT_EQ(nullptr, d2->keys_->items_[0]);
|
| 343 | ASSERT_EQ(0, d2->values_->items_[0]);
|
| 344 |
|
| 345 | // get()
|
| 346 | ASSERT(str_equals0("foo", d->get(1)));
|
| 347 |
|
| 348 | // dict_contains()
|
| 349 | ASSERT(dict_contains(d, 1));
|
| 350 | ASSERT(!dict_contains(d, 2));
|
| 351 |
|
| 352 | ASSERT_EQ(nullptr, d->get(423)); // nonexistent
|
| 353 |
|
| 354 | // get(k, default)
|
| 355 | ASSERT_EQ(kEmptyString, d->get(423, kEmptyString));
|
| 356 | ASSERT_EQ(-99, d2->get(kEmptyString, -99));
|
| 357 |
|
| 358 | // sorted()
|
| 359 | auto d3 = Alloc<Dict<BigStr*, int>>();
|
| 360 | auto a = StrFromC("a");
|
| 361 |
|
| 362 | d3->set(StrFromC("b"), 11);
|
| 363 | d3->set(StrFromC("c"), 12);
|
| 364 | d3->set(StrFromC("a"), 10);
|
| 365 | ASSERT_EQ(10, d3->at(StrFromC("a")));
|
| 366 | ASSERT_EQ(11, d3->at(StrFromC("b")));
|
| 367 | ASSERT_EQ(12, d3->at(StrFromC("c")));
|
| 368 | ASSERT_EQ(3, len(d3));
|
| 369 |
|
| 370 | auto keys3 = sorted(d3);
|
| 371 | ASSERT_EQ(3, len(keys3));
|
| 372 | ASSERT(str_equals0("a", keys3->at(0)));
|
| 373 | ASSERT(str_equals0("b", keys3->at(1)));
|
| 374 | ASSERT(str_equals0("c", keys3->at(2)));
|
| 375 |
|
| 376 | auto keys4 = d3->keys();
|
| 377 | ASSERT(list_contains(keys4, a));
|
| 378 | ASSERT(!list_contains(keys4, StrFromC("zzz")));
|
| 379 |
|
| 380 | ASSERT(dict_contains(d3, a));
|
| 381 | mylib::dict_erase(d3, a);
|
| 382 | ASSERT(!dict_contains(d3, a));
|
| 383 | ASSERT_EQ(2, len(d3));
|
| 384 |
|
| 385 | // Test a different type of dict, to make sure partial template
|
| 386 | // specialization works
|
| 387 | auto ss = Alloc<Dict<BigStr*, BigStr*>>();
|
| 388 | ss->set(a, a);
|
| 389 | ASSERT_EQ(1, len(ss));
|
| 390 | ASSERT_EQ(1, len(ss->keys()));
|
| 391 | ASSERT_EQ(1, len(ss->values()));
|
| 392 |
|
| 393 | int k = 0;
|
| 394 | for (DictIter<BigStr*, BigStr*> it(ss); !it.Done(); it.Next()) {
|
| 395 | auto key = it.Key();
|
| 396 | log("ss key = %s", key->data_);
|
| 397 | ++k;
|
| 398 | }
|
| 399 | ASSERT_EQ_FMT(len(ss), k, "%d");
|
| 400 |
|
| 401 | mylib::dict_erase(ss, a);
|
| 402 | ASSERT_EQ(0, len(ss));
|
| 403 |
|
| 404 | int m = 0;
|
| 405 | for (DictIter<BigStr*, BigStr*> it(ss); !it.Done(); it.Next()) {
|
| 406 | auto key = it.Key();
|
| 407 | log("ss key = %s", key->data_);
|
| 408 | ++m;
|
| 409 | }
|
| 410 | ASSERT_EQ_FMT(0, m, "%d");
|
| 411 | ASSERT_EQ_FMT(len(ss), m, "%d");
|
| 412 |
|
| 413 | PASS();
|
| 414 | }
|
| 415 |
|
| 416 | TEST dict_iters_test() {
|
| 417 | Dict<BigStr*, int>* d2 = nullptr;
|
| 418 | List<BigStr*>* keys = nullptr;
|
| 419 | StackRoots _roots({&d2, &keys});
|
| 420 |
|
| 421 | d2 = Alloc<Dict<BigStr*, int>>();
|
| 422 | d2->set(kStrFoo, 2);
|
| 423 | d2->set(kStrBar, 3);
|
| 424 |
|
| 425 | keys = d2->keys();
|
| 426 | for (int i = 0; i < len(keys); ++i) {
|
| 427 | printf("k %s\n", keys->at(i)->data_);
|
| 428 | }
|
| 429 |
|
| 430 | log(" iterating over Dict");
|
| 431 | for (DictIter<BigStr*, int> it(d2); !it.Done(); it.Next()) {
|
| 432 | log("k = %s, v = %d", it.Key()->data_, it.Value());
|
| 433 | }
|
| 434 |
|
| 435 | PASS();
|
| 436 | }
|
| 437 |
|
| 438 | TEST test_tuple_construct() {
|
| 439 | auto kvs = Alloc<List<Tuple2<int, int>*>>();
|
| 440 | auto t1 = Alloc<Tuple2<int, int>>(0xdead, 0xbeef);
|
| 441 | auto t2 = Alloc<Tuple2<int, int>>(0xbeee, 0xeeef);
|
| 442 | kvs->append(t1);
|
| 443 | kvs->append(t2);
|
| 444 |
|
| 445 | auto d = dict(kvs);
|
| 446 | ASSERT_EQ(d->at(0xdead), 0xbeef);
|
| 447 | ASSERT_EQ(d->at(0xbeee), 0xeeef);
|
| 448 |
|
| 449 | PASS();
|
| 450 | }
|
| 451 |
|
| 452 | TEST test_update_dict() {
|
| 453 | auto d = Alloc<Dict<int, int>>();
|
| 454 | d->set(1, 0xdead);
|
| 455 | d->set(2, 0xbeef);
|
| 456 | ASSERT_EQ(d->at(1), 0xdead);
|
| 457 | ASSERT_EQ(d->at(2), 0xbeef);
|
| 458 |
|
| 459 | auto kvs = Alloc<List<Tuple2<int, int>*>>();
|
| 460 | auto t1 = Alloc<Tuple2<int, int>>(2, 0xfeeb);
|
| 461 | auto t2 = Alloc<Tuple2<int, int>>(3, 0x3333);
|
| 462 | kvs->append(t1);
|
| 463 | kvs->append(t2);
|
| 464 | d->update(kvs);
|
| 465 | ASSERT_EQ(d->at(1), 0xdead);
|
| 466 | ASSERT_EQ(d->at(2), 0xfeeb);
|
| 467 | ASSERT_EQ(d->at(3), 0x3333);
|
| 468 |
|
| 469 | PASS();
|
| 470 | }
|
| 471 |
|
| 472 | TEST test_tuple_key() {
|
| 473 | auto d1 = Alloc<Dict<Tuple2<int, int>*, int>>();
|
| 474 | auto t1 = Alloc<Tuple2<int, int>>(0xdead, 0xbeef);
|
| 475 | auto t2 = Alloc<Tuple2<int, int>>(0xbeee, 0xeeef);
|
| 476 | d1->set(t1, -42);
|
| 477 | d1->set(t2, 17);
|
| 478 | ASSERT_EQ(d1->at(t1), -42);
|
| 479 | ASSERT_EQ(d1->at(t2), 17);
|
| 480 |
|
| 481 | auto d2 = Alloc<Dict<Tuple2<BigStr*, int>*, int>>();
|
| 482 | auto t3 = Alloc<Tuple2<BigStr*, int>>(StrFromC("foo"), 0xbeef);
|
| 483 | auto t4 = Alloc<Tuple2<BigStr*, int>>(StrFromC("bar"), 0xeeef);
|
| 484 | d2->set(t3, 12345);
|
| 485 | d2->set(t4, 67890);
|
| 486 | ASSERT_EQ(d2->at(t3), 12345);
|
| 487 | ASSERT_EQ(d2->at(t4), 67890);
|
| 488 |
|
| 489 | PASS();
|
| 490 | }
|
| 491 |
|
| 492 | TEST test_dict_erase() {
|
| 493 | auto d = Alloc<Dict<int, int>>();
|
| 494 | d->set(25315, 0xdead);
|
| 495 | d->set(25316, 0xbeef);
|
| 496 | d->set(25317, 0xc0ffee);
|
| 497 |
|
| 498 | ASSERT_EQ(0xdead, d->at(25315));
|
| 499 | ASSERT_EQ(0xbeef, d->at(25316));
|
| 500 | ASSERT_EQ(0xc0ffee, d->at(25317));
|
| 501 |
|
| 502 | mylib::dict_erase(d, 25315);
|
| 503 | ASSERT_FALSE(dict_contains(d, 25315));
|
| 504 | ASSERT_EQ(0xbeef, d->at(25316));
|
| 505 | ASSERT_EQ(0xc0ffee, d->at(25317));
|
| 506 |
|
| 507 | mylib::dict_erase(d, 25316);
|
| 508 | ASSERT_FALSE(dict_contains(d, 25316));
|
| 509 | ASSERT_EQ(0xc0ffee, d->at(25317));
|
| 510 |
|
| 511 | // This is a trace of processes coming and going in a real shell. It tickles a
|
| 512 | // (now fixed) bug in dict_erase() that would prematurely open a slot in the
|
| 513 | // index before compacting the last inserted entry. With the right sequence of
|
| 514 | // collisions (hence this trace) this behavior can lead to an index slot that
|
| 515 | // points to an invalid entry, causing future calls to `find_key_in_index()`
|
| 516 | // to crash (e.g. by dereferencing a bad pointer).
|
| 517 | d = Alloc<Dict<int, int>>();
|
| 518 | d->set(326224, 0);
|
| 519 | d->set(326225, 1);
|
| 520 | d->set(326226, 2);
|
| 521 | d->set(326227, 3);
|
| 522 | d->set(326228, 4);
|
| 523 | mylib::dict_erase(d, 326227);
|
| 524 | d->set(326229, 4);
|
| 525 | d->set(326230, 5);
|
| 526 | mylib::dict_erase(d, 326229);
|
| 527 | d->set(326231, 5);
|
| 528 | d->set(326232, 6);
|
| 529 | mylib::dict_erase(d, 326231);
|
| 530 | d->set(326233, 6);
|
| 531 | d->set(326234, 7);
|
| 532 | mylib::dict_erase(d, 326233);
|
| 533 | d->set(326235, 7);
|
| 534 | d->set(326236, 8);
|
| 535 | mylib::dict_erase(d, 326235);
|
| 536 | d->set(326237, 8);
|
| 537 | d->set(326238, 9);
|
| 538 | mylib::dict_erase(d, 326237);
|
| 539 | d->set(326239, 9);
|
| 540 | d->set(326240, 10);
|
| 541 | mylib::dict_erase(d, 326239);
|
| 542 | d->set(326241, 10);
|
| 543 |
|
| 544 | PASS();
|
| 545 | }
|
| 546 |
|
| 547 | TEST test_dict_erase2() {
|
| 548 | auto d = NewDict<int, BigStr*>();
|
| 549 |
|
| 550 | for (int i = 0; i < 6; ++i) {
|
| 551 | d->set(i, kEmptyString);
|
| 552 | }
|
| 553 | log("len(d) = %d", len(d));
|
| 554 | ASSERT_EQ(6, len(d));
|
| 555 |
|
| 556 | mylib::dict_erase(d, 99);
|
| 557 | ASSERT_EQ(6, len(d));
|
| 558 |
|
| 559 | PASS();
|
| 560 | }
|
| 561 |
|
| 562 | // Ints hash to themselves, so we can control when collisions happen. This test
|
| 563 | // sets up a few contrived workloads and checks that Dict still operates as
|
| 564 | // expected.
|
| 565 | TEST test_dict_probe() {
|
| 566 | auto d = Alloc<Dict<int, int>>();
|
| 567 |
|
| 568 | // This trace is a regression test for a weird bug where the index is full but
|
| 569 | // the table has two free slots, causing a write to needlessly fail.
|
| 570 | d->set(584818, -1);
|
| 571 | d->set(584828, -1);
|
| 572 | mylib::dict_erase(d, 584828);
|
| 573 | d->set(584833, -1);
|
| 574 | mylib::dict_erase(d, 584833);
|
| 575 | d->set(584888, -1);
|
| 576 |
|
| 577 | d->reserve(32);
|
| 578 | d->clear();
|
| 579 |
|
| 580 | // First, fill the table to the brim and check that we can recall
|
| 581 | // everything.
|
| 582 | int n = d->capacity_;
|
| 583 | for (int i = 0; i < n; i++) {
|
| 584 | d->set(i, i);
|
| 585 | }
|
| 586 | ASSERT_EQ(n, d->capacity_);
|
| 587 | for (int i = 0; i < n; i++) {
|
| 588 | ASSERT_EQ(i, d->at(i));
|
| 589 | }
|
| 590 | // Triger a rehash, and check that everything is OK.
|
| 591 | d->set(n, n);
|
| 592 | ASSERT(d->capacity_ > n);
|
| 593 | for (int i = 0; i <= n; i++) {
|
| 594 | ASSERT_EQ(i, d->at(i));
|
| 595 | }
|
| 596 | for (int i = 0; i <= n; i++) {
|
| 597 | d->set(i, n * i);
|
| 598 | }
|
| 599 | for (int i = 0; i <= n; i++) {
|
| 600 | ASSERT_EQ(n * i, d->at(i));
|
| 601 | }
|
| 602 |
|
| 603 | // Reset and fill the table with keys that all has onto the same index slot
|
| 604 | n = d->capacity_;
|
| 605 | int target = n / 2; // pick a slot in the middle to test wrap around
|
| 606 | d->clear();
|
| 607 | for (int i = 0; i < n; i++) {
|
| 608 | d->set(target * i, i);
|
| 609 | }
|
| 610 | // Remove each entry one-by-one, stopping after each removal to check that
|
| 611 | // the other keys can be set and retrieved without issue. This implicitly
|
| 612 | // checks that special index entries like tombstones are working correctly.
|
| 613 | for (int i = 0; i < n; i++) {
|
| 614 | mylib::dict_erase(d, target * i);
|
| 615 | for (int j = i + 1; j < n; j++) {
|
| 616 | d->set(target * j, j + 1);
|
| 617 | ASSERT_EQ(j + 1, d->at(target * j));
|
| 618 | }
|
| 619 | }
|
| 620 |
|
| 621 | PASS();
|
| 622 | }
|
| 623 |
|
| 624 | GLOBAL_DICT(gDict, int, int, 2, {42 COMMA 43}, {1 COMMA 2});
|
| 625 |
|
| 626 | GLOBAL_DICT(gStrDict, BigStr*, BigStr*, 2, {kStrFoo COMMA kStrBar},
|
| 627 | {kStrBar COMMA kStrFoo});
|
| 628 |
|
| 629 | TEST test_global_dict() {
|
| 630 | log("gDict len = %d", len(gDict));
|
| 631 | ASSERT_EQ(2, len(gDict));
|
| 632 | ASSERT_EQ(1, gDict->at(42));
|
| 633 | ASSERT_EQ(2, gDict->at(43));
|
| 634 |
|
| 635 | log("gStrDict len = %d", len(gStrDict));
|
| 636 | ASSERT_EQ(kStrFoo, gStrDict->at(kStrBar));
|
| 637 | ASSERT_EQ(kStrBar, gStrDict->at(kStrFoo));
|
| 638 |
|
| 639 | ASSERT(dict_contains(gStrDict, kStrFoo));
|
| 640 | ASSERT(dict_contains(gStrDict, kStrBar));
|
| 641 | ASSERT(!dict_contains(gStrDict, kEmptyString));
|
| 642 |
|
| 643 | PASS();
|
| 644 | }
|
| 645 |
|
| 646 | TEST test_dict_ordering() {
|
| 647 | auto d = Alloc<Dict<int, int>>();
|
| 648 |
|
| 649 | auto in = NewList<int>(std::initializer_list<int>{95, 9, 67, 70, 93, 30, 25,
|
| 650 | 98, 80, 39, 56, 48, 99});
|
| 651 | for (ListIter<int> it(in); !it.Done(); it.Next()) {
|
| 652 | d->set(it.Value(), -1);
|
| 653 | }
|
| 654 |
|
| 655 | auto keys = d->keys();
|
| 656 | ASSERT_EQ(len(in), len(keys));
|
| 657 | for (int i = 0; i < len(in); i++) {
|
| 658 | ASSERT_EQ(in->at(i), keys->at(i));
|
| 659 | }
|
| 660 |
|
| 661 | // check that order survives rehashing
|
| 662 | d->reserve(2 * len(d));
|
| 663 | keys = d->keys();
|
| 664 | ASSERT_EQ(len(in), len(keys));
|
| 665 | for (int i = 0; i < len(in); i++) {
|
| 666 | ASSERT_EQ(in->at(i), keys->at(i));
|
| 667 | }
|
| 668 |
|
| 669 | PASS();
|
| 670 | }
|
| 671 |
|
| 672 | TEST test_hash() {
|
| 673 | int i = 0;
|
| 674 | int j = 0;
|
| 675 | log("&i = %p", &i);
|
| 676 | log("&j = %p", &j);
|
| 677 |
|
| 678 | unsigned h1 = hash_key(&i);
|
| 679 | log("h1 = %d", h1);
|
| 680 | unsigned h2 = hash_key(&i);
|
| 681 | log("h2 = %d", h2);
|
| 682 | unsigned h3 = hash_key(&j);
|
| 683 | log("h3 = %d", h3);
|
| 684 |
|
| 685 | ASSERT_EQ_FMT(h1, h2, "%d");
|
| 686 | ASSERT(h1 != h3);
|
| 687 |
|
| 688 | PASS();
|
| 689 | }
|
| 690 |
|
| 691 | TEST hash_pileup_bug() {
|
| 692 | auto* d = Alloc<Dict<mops::BigInt, BigStr*>>();
|
| 693 |
|
| 694 | std::unordered_map<unsigned, bool> hist;
|
| 695 |
|
| 696 | for (int i = 0; i < 24; ++i) {
|
| 697 | mops::BigInt index{1 << i};
|
| 698 | // log("index %ld", index);
|
| 699 |
|
| 700 | for (mops::BigInt j = index; j < index + 2000; ++j) {
|
| 701 | d->set(j, kEmptyString);
|
| 702 | unsigned h = hash_key(j);
|
| 703 | hist[h] = true;
|
| 704 | // log("%ld %d", j, h);
|
| 705 | }
|
| 706 | // log("len %d", len(d));
|
| 707 | }
|
| 708 |
|
| 709 | log("len %d", len(d));
|
| 710 | log("unique hashes %d", hist.size());
|
| 711 |
|
| 712 | PASS();
|
| 713 | }
|
| 714 |
|
| 715 | GREATEST_MAIN_DEFS();
|
| 716 |
|
| 717 | int main(int argc, char** argv) {
|
| 718 | gHeap.Init();
|
| 719 |
|
| 720 | GREATEST_MAIN_BEGIN();
|
| 721 |
|
| 722 | RUN_TEST(test_dict_init);
|
| 723 | RUN_TEST(test_dict);
|
| 724 | RUN_TEST(test_dict_internals);
|
| 725 | RUN_TEST(test_empty_dict);
|
| 726 | RUN_TEST(test_tuple_construct);
|
| 727 | RUN_TEST(test_update_dict);
|
| 728 | RUN_TEST(test_tuple_key);
|
| 729 | RUN_TEST(test_dict_erase);
|
| 730 | RUN_TEST(test_dict_erase2);
|
| 731 | RUN_TEST(test_global_dict);
|
| 732 | RUN_TEST(test_dict_ordering);
|
| 733 | RUN_TEST(test_dict_probe);
|
| 734 |
|
| 735 | RUN_TEST(dict_methods_test);
|
| 736 | RUN_TEST(dict_iters_test);
|
| 737 |
|
| 738 | RUN_TEST(test_hash);
|
| 739 | RUN_TEST(hash_pileup_bug);
|
| 740 |
|
| 741 | gHeap.CleanProcessExit();
|
| 742 |
|
| 743 | GREATEST_MAIN_END();
|
| 744 | return 0;
|
| 745 | }
|