OLD | NEW |
1 // Copyright 2008 the V8 project authors. All rights reserved. | 1 // Copyright 2008 the V8 project authors. All rights reserved. |
2 // Redistribution and use in source and binary forms, with or without | 2 // Redistribution and use in source and binary forms, with or without |
3 // modification, are permitted provided that the following conditions are | 3 // modification, are permitted provided that the following conditions are |
4 // met: | 4 // met: |
5 // | 5 // |
6 // * Redistributions of source code must retain the above copyright | 6 // * Redistributions of source code must retain the above copyright |
7 // notice, this list of conditions and the following disclaimer. | 7 // notice, this list of conditions and the following disclaimer. |
8 // * Redistributions in binary form must reproduce the above | 8 // * Redistributions in binary form must reproduce the above |
9 // copyright notice, this list of conditions and the following | 9 // copyright notice, this list of conditions and the following |
10 // disclaimer in the documentation and/or other materials provided | 10 // disclaimer in the documentation and/or other materials provided |
11 // with the distribution. | 11 // with the distribution. |
12 // * Neither the name of Google Inc. nor the names of its | 12 // * Neither the name of Google Inc. nor the names of its |
13 // contributors may be used to endorse or promote products derived | 13 // contributors may be used to endorse or promote products derived |
14 // from this software without specific prior written permission. | 14 // from this software without specific prior written permission. |
15 // | 15 // |
16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS | 16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
17 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT | 17 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
18 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR | 18 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |
19 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT | 19 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT |
20 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, | 20 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
21 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT | 21 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT |
22 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, | 22 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
23 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY | 23 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT | 24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE | 25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE |
26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. | 26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
27 | 27 |
28 | 28 |
29 #include <stdlib.h> | 29 #include <stdlib.h> |
30 #include <set> | |
31 | 30 |
32 #include "v8.h" | 31 #include "v8.h" |
33 | 32 |
34 #include "string-stream.h" | 33 #include "string-stream.h" |
35 #include "cctest.h" | 34 #include "cctest.h" |
36 #include "zone-inl.h" | 35 #include "zone-inl.h" |
37 #include "parser.h" | 36 #include "parser.h" |
38 #include "ast.h" | 37 #include "ast.h" |
39 #include "jsregexp-inl.h" | 38 #include "jsregexp-inl.h" |
40 #include "regexp-macro-assembler.h" | 39 #include "regexp-macro-assembler.h" |
(...skipping 451 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
492 else | 491 else |
493 return 0; | 492 return 0; |
494 } | 493 } |
495 }; | 494 }; |
496 | 495 |
497 | 496 |
498 const int TestConfig::kNoKey = 0; | 497 const int TestConfig::kNoKey = 0; |
499 const int TestConfig::kNoValue = 0; | 498 const int TestConfig::kNoValue = 0; |
500 | 499 |
501 | 500 |
502 static int PseudoRandom(int i, int j) { | 501 static unsigned PseudoRandom(int i, int j) { |
503 return ~(~((i * 781) ^ (j * 329))); | 502 return ~(~((i * 781) ^ (j * 329))); |
504 } | 503 } |
505 | 504 |
506 | 505 |
507 TEST(SplayTreeSimple) { | 506 TEST(SplayTreeSimple) { |
508 static const int kLimit = 1000; | 507 static const unsigned kLimit = 1000; |
509 ZoneScope zone_scope(DELETE_ON_EXIT); | 508 ZoneScope zone_scope(DELETE_ON_EXIT); |
510 ZoneSplayTree<TestConfig> tree; | 509 ZoneSplayTree<TestConfig> tree; |
511 std::set<int> seen; | 510 bool seen[kLimit]; |
| 511 for (unsigned i = 0; i < kLimit; i++) seen[i] = false; |
512 #define CHECK_MAPS_EQUAL() do { \ | 512 #define CHECK_MAPS_EQUAL() do { \ |
513 for (int k = 0; k < kLimit; k++) \ | 513 for (unsigned k = 0; k < kLimit; k++) \ |
514 CHECK_EQ(seen.find(k) != seen.end(), tree.Find(k, &loc)); \ | 514 CHECK_EQ(seen[k], tree.Find(k, &loc)); \ |
515 } while (false) | 515 } while (false) |
516 for (int i = 0; i < 50; i++) { | 516 for (int i = 0; i < 50; i++) { |
517 for (int j = 0; j < 50; j++) { | 517 for (int j = 0; j < 50; j++) { |
518 int next = PseudoRandom(i, j) % kLimit; | 518 unsigned next = PseudoRandom(i, j) % kLimit; |
519 if (seen.find(next) != seen.end()) { | 519 if (seen[next]) { |
520 // We've already seen this one. Check the value and remove | 520 // We've already seen this one. Check the value and remove |
521 // it. | 521 // it. |
522 ZoneSplayTree<TestConfig>::Locator loc; | 522 ZoneSplayTree<TestConfig>::Locator loc; |
523 CHECK(tree.Find(next, &loc)); | 523 CHECK(tree.Find(next, &loc)); |
524 CHECK_EQ(next, loc.key()); | 524 CHECK_EQ(next, loc.key()); |
525 CHECK_EQ(3 * next, loc.value()); | 525 CHECK_EQ(3 * next, loc.value()); |
526 tree.Remove(next); | 526 tree.Remove(next); |
527 seen.erase(next); | 527 seen[next] = false; |
528 CHECK_MAPS_EQUAL(); | 528 CHECK_MAPS_EQUAL(); |
529 } else { | 529 } else { |
530 // Check that it wasn't there already and then add it. | 530 // Check that it wasn't there already and then add it. |
531 ZoneSplayTree<TestConfig>::Locator loc; | 531 ZoneSplayTree<TestConfig>::Locator loc; |
532 CHECK(!tree.Find(next, &loc)); | 532 CHECK(!tree.Find(next, &loc)); |
533 CHECK(tree.Insert(next, &loc)); | 533 CHECK(tree.Insert(next, &loc)); |
534 CHECK_EQ(next, loc.key()); | 534 CHECK_EQ(next, loc.key()); |
535 loc.set_value(3 * next); | 535 loc.set_value(3 * next); |
536 seen.insert(next); | 536 seen[next] = true; |
537 CHECK_MAPS_EQUAL(); | 537 CHECK_MAPS_EQUAL(); |
538 } | 538 } |
539 int val = PseudoRandom(j, i) % kLimit; | 539 int val = PseudoRandom(j, i) % kLimit; |
540 for (int k = val; k >= 0; k--) { | 540 if (seen[val]) { |
541 if (seen.find(val) != seen.end()) { | 541 ZoneSplayTree<TestConfig>::Locator loc; |
542 ZoneSplayTree<TestConfig>::Locator loc; | 542 CHECK(tree.FindGreatestLessThan(val, &loc)); |
543 CHECK(tree.FindGreatestLessThan(val, &loc)); | 543 CHECK_EQ(loc.key(), val); |
544 CHECK_EQ(loc.key(), val); | 544 break; |
545 break; | |
546 } | |
547 } | 545 } |
548 val = PseudoRandom(i + j, i - j) % kLimit; | 546 val = PseudoRandom(i + j, i - j) % kLimit; |
549 for (int k = val; k < kLimit; k++) { | 547 if (seen[val]) { |
550 if (seen.find(val) != seen.end()) { | 548 ZoneSplayTree<TestConfig>::Locator loc; |
551 ZoneSplayTree<TestConfig>::Locator loc; | 549 CHECK(tree.FindLeastGreaterThan(val, &loc)); |
552 CHECK(tree.FindLeastGreaterThan(val, &loc)); | 550 CHECK_EQ(loc.key(), val); |
553 CHECK_EQ(loc.key(), val); | 551 break; |
554 break; | |
555 } | |
556 } | 552 } |
557 } | 553 } |
558 } | 554 } |
559 } | 555 } |
560 | 556 |
561 | 557 |
562 TEST(DispatchTableConstruction) { | 558 TEST(DispatchTableConstruction) { |
563 // Initialize test data. | 559 // Initialize test data. |
564 static const int kLimit = 1000; | 560 static const int kLimit = 1000; |
565 static const int kRangeCount = 8; | 561 static const int kRangeCount = 8; |
(...skipping 961 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1527 CHECK(!InClass(i, excluded)); | 1523 CHECK(!InClass(i, excluded)); |
1528 } | 1524 } |
1529 } | 1525 } |
1530 } | 1526 } |
1531 | 1527 |
1532 | 1528 |
1533 TEST(Graph) { | 1529 TEST(Graph) { |
1534 V8::Initialize(NULL); | 1530 V8::Initialize(NULL); |
1535 Execute("(?:(?:x(.))?\1)+$", false, true, true); | 1531 Execute("(?:(?:x(.))?\1)+$", false, true, true); |
1536 } | 1532 } |
OLD | NEW |